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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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 : Sélectionner tout - Visualiser dans une fenêtre à part
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
Partager