6 |
6 |
7 #include <lemon/smart_graph.h> |
7 #include <lemon/smart_graph.h> |
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 |
|
12 #include <lemon/fib_heap.h> |
11 |
13 |
12 #include <lemon/time_measure.h> |
14 #include <lemon/time_measure.h> |
13 #include "test_tools.h" |
15 #include "test_tools.h" |
14 |
16 |
15 using namespace lemon; |
17 using namespace lemon; |
54 Timer timer; |
56 Timer timer; |
55 johnson.run(); |
57 johnson.run(); |
56 cout << "Johnson: " << timer << endl; |
58 cout << "Johnson: " << timer << endl; |
57 } |
59 } |
58 |
60 |
|
61 typedef FibHeap<Node, double, Graph::NodeMap<int> > DoubleFibHeap; |
|
62 Johnson<Graph, LengthMap>::DefStandardHeap<DoubleFibHeap> |
|
63 ::Create fibJohnson(graph, length); |
|
64 { |
|
65 Timer timer; |
|
66 fibJohnson.run(); |
|
67 cout << "Johnson with fibonacci heap: " << timer << endl; |
|
68 } |
|
69 |
59 FloydWarshall<Graph, LengthMap> floyd(graph, length); |
70 FloydWarshall<Graph, LengthMap> floyd(graph, length); |
60 { |
71 { |
61 Timer timer; |
72 Timer timer; |
62 floyd.run(); |
73 floyd.run(); |
63 cout << "FloydWarshall: " << timer << endl; |
74 cout << "FloydWarshall: " << timer << endl; |
65 |
76 |
66 for (NodeIt it(graph); it != INVALID; ++it) { |
77 for (NodeIt it(graph); it != INVALID; ++it) { |
67 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
78 for (NodeIt jt(graph); jt != INVALID; ++jt) { |
68 check(johnson.connected(it, jt) == floyd.connected(it, jt), |
79 check(johnson.connected(it, jt) == floyd.connected(it, jt), |
69 "Wrong connection in all pairs shortest path"); |
80 "Wrong connection in all pairs shortest path"); |
|
81 check(johnson.connected(it, jt) == fibJohnson.connected(it, jt), |
|
82 "Wrong connection in all pairs shortest path"); |
70 if (johnson.connected(it, jt)) { |
83 if (johnson.connected(it, jt)) { |
71 check(johnson.dist(it, jt) == floyd.dist(it, jt), |
84 check(johnson.dist(it, jt) == floyd.dist(it, jt), |
|
85 "Wrong distance in all pairs shortest path"); |
|
86 check(johnson.dist(it, jt) == fibJohnson.dist(it, jt), |
72 "Wrong distance in all pairs shortest path"); |
87 "Wrong distance in all pairs shortest path"); |
73 if (it != jt) { |
88 if (it != jt) { |
74 check(johnson.dist(it, jt) == |
89 check(johnson.dist(it, jt) == |
75 johnson.dist(it, johnson.predNode(it, jt)) + |
90 johnson.dist(it, johnson.predNode(it, jt)) + |
76 length[johnson.pred(it, jt)], |
91 length[johnson.pred(it, jt)], |
|
92 "Wrong edge in all pairs shortest path"); |
|
93 check(fibJohnson.dist(it, jt) == |
|
94 fibJohnson.dist(it, fibJohnson.predNode(it, jt)) + |
|
95 length[fibJohnson.pred(it, jt)], |
77 "Wrong edge in all pairs shortest path"); |
96 "Wrong edge in all pairs shortest path"); |
78 check(floyd.dist(it, jt) == |
97 check(floyd.dist(it, jt) == |
79 floyd.dist(it, floyd.predNode(it, jt)) + |
98 floyd.dist(it, floyd.predNode(it, jt)) + |
80 length[floyd.pred(it, jt)], |
99 length[floyd.pred(it, jt)], |
81 "Wrong edge in all pairs shortest path"); |
100 "Wrong edge in all pairs shortest path"); |