Bonjour,
Merci par avance à tous ceux qui essaieront de m'aider, je vous poste le code et je vous dis ce qui se passe !
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95 #ifndef JOHNSON_P #define JOHNSON_P #include "preprocesscl.hpp" #include "bellmanfordcl.hpp" #include "dijkstracl.hpp" #include <vector> #include <iostream> /* This module provides an implementation of the Johnson's algorithm for computing all shortest-paths in a graph that does not contain any negative-weight cycle */ template<typename Tvertex, typename Tweight> std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph); /* Aim : compute new weights for the graph in order to later apply Dijkstra's algorithm Args : the graph Return value : none Complexity : O(nm) (reduces to one invocation of Bellman-Ford algorithm) */ template<typename Tvertex, typename Tweight> std::vector<std::vector<Tweight>> johnson(graph<Tvertex, Tweight>& my_graph); /* Aim : compute all shortest-paths between all pairs of vertices of the graph Args : a graph Return value : a 2D vector that contains all shortest-paths Complexity : O(nmlog(n)) */ // OpenCL version, kind of have to specify the parameters for the template //void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances); template<typename Tvertex, typename Tweight> std::vector<Tweight> reweight(std::vector<std::vector<Tweight>>& my_graph){ std::vector<std::vector<Tweight>> copy_graph = my_graph; // so that we do not consider all fictitious edges after this function // we add a fictitious vertex std::vector<Tweight> fictitious_edges(std::vector<Tweight>(my_graph.size())); copy_graph.push_back(fictitious_edges); for(size_t i = 0; i < my_graph.size(); i++) copy_graph[i][my_graph.size()] = std::numeric_limits<double>::max() /2 ; std::vector<Tweight> new_weights = bellman_ford(copy_graph, copy_graph.size()-1); // apply bellman-ford on the graph using the fictitious vertex // as the source for(size_t i = 0; i < my_graph.size(); i++){ for(size_t j = 0; j < my_graph.size(); j++){ my_graph[i][j] += new_weights[i] - new_weights[j]; // update the edges } } return new_weights; } template<typename Tvertex, typename Tweight> std::vector<std::vector<Tweight>> johnson(std::vector<std::vector<Tweight>>& my_graph){ std::vector<std::vector<Tweight>> distances(my_graph.size(), std::vector<Tweight>(my_graph.size(), std::numeric_limits<Tweight>::max())); std::vector<Tweight> weights = reweight<Tvertex, Tweight>(my_graph); for(size_t i = 0; i < my_graph.size(); i++){ std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i); for(size_t j = 0; j < my_graph.size(); ++j){ std::cout << "i : " << i << " j " << j << std::endl; //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max()) // distances[i][j] = shortest_paths_from_i[j]; //else // distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i]; } } return distances; } /* void johnson(cl::CommandQueue &cmdQueue, cl::Program &prog, const int n_nodes, cl::Buffer &my_graph, cl::Buffer &distances){ cl::Kernel kernel(prog, "johnson"); kernel.setArg(0, (cl_uint) n_nodes); kernel.setArg(1, my_graph); kernel.setArg(2, distances); size_t group_size = 16; cl::NDRange local(group_size, group_size); cl::NDRange global((n_nodes + group_size - 1) / group_size * group_size, (n_nodes + group_size - 1) / group_size * group_size); cmdQueue.enqueueNDRangeKernel(kernel, cl::NullRange, global, local); } */ #endif
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 #include "preprocesscl.hpp" #include "bellmanfordcl.hpp" #include "johnsoncl.hpp" #include "dijkstracl.hpp" #include <chrono> //#include <omp.h> //#include "boost/graph/johnson_all_pairs_shortest.hpp" #include <iostream> int main(int argc, char* argv[]){ /* std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]); std::vector<double> distances = bellman_ford<long unsigned int, double>(my_graph, 0); std::vector<double> new_w = reweight<long unsigned int, double>(my_graph); for(size_t k = 0 ; k < new_w.size(); k++) std::cout << new_w[k] << " " ; std::cout << std::endl << std::endl; std::vector<double> distances_d = dijkstra(my_graph, 0); for(size_t i = 0; i < distances_d.size(); i++){ std::cout << distances_d[i] << " " ; } std::cout << std::endl; */ std::vector<std::vector<double>> my_graph = parse_graph<long unsigned int, double>(argv[1]); std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); std::vector<std::vector<double>> distances = johnson<long unsigned int, double>(my_graph); std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1); std::cout << time_span.count(); std::cout << std::endl; return 0; }
Le premier fichier contient deux fonctions une fonction qui permet de calculer des valeurs pour la deuxième qui perform l'algorithme de johnson.Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122 #ifndef DIJKSTRA_P #define DIJKSTRA_P #include <iostream> #include <vector> #include "heap_generic.hpp" #include "preprocesscl.hpp" #include <limits> #include <omp.h> /* std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1); std::cout << time_span.count(); std::cout << std::endl; */ template<typename Tnode, typename Tweight> struct dijkstra_pair { Tnode pivot; Tweight key; bool operator<(dijkstra_pair &other_pair){ return key < other_pair.key; } bool operator>(dijkstra_pair &other_pair){ return key > other_pair.key; } }; template<typename Tnode, typename Tweight> std::ostream& operator<<(std::ostream& out, const dijkstra_pair<Tnode, Tweight>& pair){ out << "Vertex : " << pair.pivot << ", key : " << pair.key << std::endl; return out; } template<typename Tnode, typename Tweight> std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode node); /* Aim : compute the shortest distances from source to every other vertex Args : the graph, represented as defined in preprocess.hpp and a source vertex Return value : a 1D array that contains the shortest distances Complexity : O(mlog(n)) */ template<typename Tnode, typename Tweight> std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source); /* Aim : initialize the shortest paths, a shortest path is equal to the value of the edge between source and vertex if it exists, 0 between source and source, infinity represented as numeric_limits<Tweight>::max() otherwise Args : a graph and a source node Return value : a 1D array containing all initialized distances Complexity : O(n) */ template<typename Tnode, typename Tweight> std::vector<Tweight> dijkstra(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){ //to store our computed distances std::vector<Tweight> distances = initialize_distances(my_graph, source); std::vector<bool> in_heap(my_graph.size(), false); // to keep track of nodes in the heap std::vector<bool> processed(my_graph.size(), false); // to keep track of processed nodes std::vector<dijkstra_pair<Tnode, Tweight>> heap = create_heap<dijkstra_pair<Tnode, Tweight>>(); // our amazing heap for BLAZINGLY FAST // implementation insert(heap, {source, 0}); // insert the source and mark it as "in the heap" in_heap[source] = true; while(size_heap(heap) != 1){ dijkstra_pair<Tnode, Tweight> new_pair = pop(heap); in_heap[new_pair.pivot] = false; // old min is not in the heap anymore processed[new_pair.pivot] = true; // old min is now processed distances[new_pair.pivot] = new_pair.key; // the old key is the permanent distance between source and associated node for(size_t i = 0; i < my_graph.size(); i++){ // we check all outgoing edges of the new added vertex edge<Tnode, Tweight> current_edge{new_pair.pivot, i, my_graph[new_pair.pivot][i]}; Tnode current_node = current_edge.head_; // the head of an outgoing edge whose tail is the new added vertex // if already in the heap we update its key if(in_heap[current_node]){ Tweight old_key = delete_element(heap, current_node).key; Tweight new_key = std::min(old_key, distances[new_pair.pivot] + current_edge.weight_); insert(heap, {current_node, new_key}); } else if(!processed[current_node]){ // otherwise we compute its key and insert it //Tweight new_key = compute_key(my_graph, current_node, in_heap, distances); Tweight new_key = distances[new_pair.pivot] + current_edge.weight_; insert(heap, {current_node, new_key}); in_heap[current_node] = true; } } } return distances; } template<typename Tnode, typename Tweight> std::vector<Tweight> initialize_distances(const std::vector<std::vector<Tweight>>& my_graph, const Tnode source){ std::vector<Tweight> distances(my_graph.size(), std::numeric_limits<Tweight>::max()/2); // std::numeric_limits<int> causes dist[smth] // + stuff to be -X which is always less than current key distances[source] = 0; for(size_t i = 0; i < my_graph.size(); i++) distances[my_graph[source][i]] = my_graph[source][i]; return distances; } #endif
Le main qui ne fait qu'appeler johnson et qui record le temps que ça prend :).
Le troisième qui contient la fonction qui perform l'algorithme de dijkstra.
Voici l'erreur qui me rend fou : free(): invalid next size (fast): 0x0000000001d3e840 ***
Le plus dingue : l'erreur intervient dans la boucle :
Lorsque i = 3. Cependant (oui vous allez voir c'est marrant), si à la place de i je mets 0 tout va bien (j'applique my_graph.size() l'algo de dijkstra avec le node 0 comme node source, vu que c'est pas celui là qui plantait ça me emble logique). Si à la place je mets 1 ça fonctionne, si à la place je mets 2 ça fonctionne une fois puis au second appel de dijkstra ça plante (alors que à la base c'est pas l'itération pour i = 2 qui plante), si je mets 3 ça fonctionne (c'est l'itération qui plantait...). Si je mets 4 5 6 ou 7 ça marche (mon petit exemple ne contient que 8 nodes).Code:
1
2
3
4
5
6
7
8
9
10 for(size_t i = 0; i < my_graph.size(); i++){ std::vector<Tweight> shortest_paths_from_i = dijkstra<Tvertex, Tweight>(my_graph, i); for(size_t j = 0; j < my_graph.size(); ++j){ std::cout << "i : " << i << " j " << j << std::endl; //if(shortest_paths_from_i[j] == std::numeric_limits<Tweight>::max()) // distances[i][j] = shortest_paths_from_i[j]; //else // distances[i][j] = shortest_paths_from_i[j] + weights[j] - weights[i]; } }
Quelq'un a t-il une idée de ce qu'il se passe ? J'ai lu sur le forum et ailleurs que cette erreur survient lors de dépassements de mémoire, de double free, de tentative d'accès à de la mémoire non allouée...
Cependant ici l'itération qui plante de base c'est lorsque j'appelle dijkstra<Tvertex, Tweight>(my_graph, 3), qui ne plante pas dans si j'écris dans ma boucle dijkstra<Tvertex, Tweight>(my_graph, 1 ou 2 ou 3 jusqu'à 7)
Donc je me dis, peut-être que mes itérations 0 ou 1 ou 2 provoquent des choses qui font que pour i = 3 ça plante (raison pour laquelle si je commence par la 3 ça ne plante pas par exemple). Cependant ma fonction dijkstra ne touchent pas à ses arguments déclarés "const" elle ne fait que retourner un std::vector<Tweight> (vous pouvez penser Tweight = double si vous voulez), du coup j'ai pas la moindre idée de ce qu'il se passe...
Merci encore à tous