8 #include <lemon/dijkstra.h> |
8 #include <lemon/dijkstra.h> |
9 #include <lemon/floyd_warshall.h> |
9 #include <lemon/floyd_warshall.h> |
10 #include <lemon/johnson.h> |
10 #include <lemon/johnson.h> |
11 |
11 |
12 #include <lemon/time_measure.h> |
12 #include <lemon/time_measure.h> |
|
13 #include "test_tools.h" |
13 |
14 |
14 using namespace lemon; |
15 using namespace lemon; |
15 using namespace std; |
16 using namespace std; |
16 |
17 |
17 int main(int argc, const char *argv[]) { |
18 int main(int argc, const char *argv[]) { |
24 |
25 |
25 typedef Graph::EdgeMap<double> LengthMap; |
26 typedef Graph::EdgeMap<double> LengthMap; |
26 typedef Graph::NodeMap<double> DistMap; |
27 typedef Graph::NodeMap<double> DistMap; |
27 |
28 |
28 const int n = argc > 1 ? atoi(argv[1]) : 20; |
29 const int n = argc > 1 ? atoi(argv[1]) : 20; |
29 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log(n)); |
30 const int e = argc > 2 ? atoi(argv[2]) : (int)(n * log((double)n)); |
30 const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0; |
31 const double m = argc > 3 ? (double)atoi(argv[3]) : 100.0; |
31 |
32 |
32 Graph graph; |
33 Graph graph; |
33 LengthMap length(graph); |
34 LengthMap length(graph); |
34 vector<Node> nodes; |
35 vector<Node> nodes; |
62 cout << "FloydWarshall: " << timer << endl; |
63 cout << "FloydWarshall: " << timer << endl; |
63 } |
64 } |
64 |
65 |
65 for (NodeIt it(graph); it != INVALID; ++it) { |
66 for (NodeIt it(graph); it != INVALID; ++it) { |
66 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
67 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
67 assert(johnson.connected(it, jt) == floyd.connected(it, jt)); |
68 check(johnson.connected(it, jt) == floyd.connected(it, jt), |
|
69 "Wrong connection in all pairs shortest path"); |
68 if (johnson.connected(it, jt)) { |
70 if (johnson.connected(it, jt)) { |
69 assert(johnson.dist(it, jt) == floyd.dist(it, jt)); |
71 check(johnson.dist(it, jt) == floyd.dist(it, jt), |
|
72 "Wrong distance in all pairs shortest path"); |
70 if (it != jt) { |
73 if (it != jt) { |
71 assert(johnson.dist(it, jt) == |
74 check(johnson.dist(it, jt) == |
72 johnson.dist(it, johnson.predNode(it, jt)) + |
75 johnson.dist(it, johnson.predNode(it, jt)) + |
73 length[johnson.pred(it, jt)]); |
76 length[johnson.pred(it, jt)], |
74 assert(floyd.dist(it, jt) == |
77 "Wrong edge in all pairs shortest path"); |
75 floyd.dist(it, floyd.predNode(it, jt)) + |
78 check(floyd.dist(it, jt) == |
76 length[floyd.pred(it, jt)]); |
79 floyd.dist(it, floyd.predNode(it, jt)) + |
|
80 length[floyd.pred(it, jt)], |
|
81 "Wrong edge in all pairs shortest path"); |
77 } |
82 } |
78 } |
83 } |
79 } |
84 } |
80 } |
85 } |
81 |
86 |