26 #include <lemon/dijkstra.h> |
26 #include <lemon/dijkstra.h> |
27 #include <lemon/floyd_warshall.h> |
27 #include <lemon/floyd_warshall.h> |
28 #include <lemon/johnson.h> |
28 #include <lemon/johnson.h> |
29 |
29 |
30 #include <lemon/fib_heap.h> |
30 #include <lemon/fib_heap.h> |
|
31 |
|
32 #include <lemon/path.h> |
31 |
33 |
32 #include <lemon/time_measure.h> |
34 #include <lemon/time_measure.h> |
33 #include "test_tools.h" |
35 #include "test_tools.h" |
34 |
36 |
35 using namespace lemon; |
37 using namespace lemon; |
88 Timer timer; |
90 Timer timer; |
89 floyd.run(); |
91 floyd.run(); |
90 cout << "FloydWarshall: " << timer << endl; |
92 cout << "FloydWarshall: " << timer << endl; |
91 } |
93 } |
92 |
94 |
|
95 bool checked_path = false; |
|
96 |
93 for (NodeIt it(graph); it != INVALID; ++it) { |
97 for (NodeIt it(graph); it != INVALID; ++it) { |
94 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
98 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
95 check(johnson.connected(it, jt) == floyd.connected(it, jt), |
99 check(johnson.connected(it, jt) == floyd.connected(it, jt), |
96 "Wrong connection in all pairs shortest path"); |
100 "Wrong connection in all pairs shortest path"); |
97 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt), |
101 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt), |
98 "Wrong connection in all pairs shortest path"); |
102 "Wrong connection in all pairs shortest path"); |
99 if (johnson.connected(it, jt)) { |
103 if (johnson.connected(it, jt)) { |
|
104 if (it != jt && !checked_path) { |
|
105 { |
|
106 Path<Graph> path = johnson.path(it, jt); |
|
107 check(checkPath(graph, path), "Wrong path."); |
|
108 check(pathSource(graph, path) == it, "Wrong path."); |
|
109 check(pathTarget(graph, path) == jt, "Wrong path."); |
|
110 } |
|
111 { |
|
112 Path<Graph> path = floyd.path(it, jt); |
|
113 check(checkPath(graph, path), "Wrong path."); |
|
114 check(pathSource(graph, path) == it, "Wrong path."); |
|
115 check(pathTarget(graph, path) == jt, "Wrong path."); |
|
116 } |
|
117 checked_path = true; |
|
118 std::cout << "Path checked" << std::endl; |
|
119 } |
100 check(johnson.dist(it, jt) == floyd.dist(it, jt), |
120 check(johnson.dist(it, jt) == floyd.dist(it, jt), |
101 "Wrong distance in all pairs shortest path"); |
121 "Wrong distance in all pairs shortest path"); |
102 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt), |
122 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt), |
103 "Wrong distance in all pairs shortest path"); |
123 "Wrong distance in all pairs shortest path"); |
104 if (it != jt) { |
124 if (it != jt) { |