|
1 //Tests dijsktra.h with two heap implementations: |
|
2 //the default binary heap of bin_heap.h, and the |
|
3 //Fibonacci heap of fib_heap.h. |
|
4 |
|
5 //The input is a graph in standard dimacs format from the standard input (like |
|
6 //in /hugo_loc/testfiles/dimacs). It runs dijkstra.h on this graph with |
|
7 //both heaps, checking two postconditions: |
|
8 |
|
9 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have |
|
10 //dist(v)-dist(u)=length(e) |
|
11 |
|
12 // - if all edges e=uv with u reachable from the root have |
|
13 //dist(v)-dist(u)>=length(e) |
|
14 #include <iostream> |
|
15 #include <math.h> |
|
16 |
|
17 #include <smart_graph.h> |
|
18 #include <dimacs.h> |
|
19 #include <dijkstra.h> |
|
20 #include <time_measure.h> |
|
21 #include <bin_heap.h> |
|
22 #include <for_each_macros.h> |
|
23 |
|
24 using namespace hugo; |
|
25 |
|
26 int main(int, char **) { |
|
27 |
|
28 typedef SmartGraph Graph; |
|
29 |
|
30 typedef Graph::Edge Edge; |
|
31 typedef Graph::Node Node; |
|
32 typedef Graph::EdgeIt EdgeIt; |
|
33 typedef Graph::NodeIt NodeIt; |
|
34 typedef Graph::EdgeMap<int> LengthMap; |
|
35 |
|
36 Graph G; |
|
37 Node s, t; |
|
38 LengthMap cap(G); |
|
39 readDimacsMaxFlow(std::cin, G, s, t, cap); |
|
40 Timer ts; |
|
41 |
|
42 std::cout << |
|
43 "\n Testing dijkstra.h with binary heap implementation bin_heap.h," |
|
44 <<std::endl; |
|
45 std::cout<<" on a graph with " << |
|
46 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
|
47 << std::endl<<std::endl; |
|
48 |
|
49 Dijkstra<Graph, LengthMap> |
|
50 dijkstra_test(G, cap); |
|
51 ts.reset(); |
|
52 dijkstra_test.run(s); |
|
53 std::cout << "elapsed time: " << ts << std::endl; |
|
54 |
|
55 int error1=0; |
|
56 int error2=0; |
|
57 |
|
58 FOR_EACH_LOC ( EdgeIt, e, G) { |
|
59 Node u=G.tail(e); |
|
60 Node v=G.head(e); |
|
61 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) |
|
62 if ( dijkstra_test.reached(u) ) { |
|
63 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
|
64 <<dijkstra_test.dist(v) - dijkstra_test.dist(u) |
|
65 - cap[e]<<std::endl; |
|
66 ++error1; |
|
67 } |
|
68 } |
|
69 |
|
70 FOR_EACH_LOC ( NodeIt, v, G) { |
|
71 if ( dijkstra_test.reached(v) ) { |
|
72 Edge e=dijkstra_test.pred(v); |
|
73 Node u=G.tail(e); |
|
74 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { |
|
75 std::cout<<"Error in a shortest path tree edge! Difference: " |
|
76 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) |
|
77 - cap[e])<<std::endl; |
|
78 ++error2; |
|
79 } |
|
80 } |
|
81 } |
|
82 |
|
83 |
|
84 |
|
85 std::cout << error1 << " non-tree and " << error2 |
|
86 << " shortest path tree edge is erroneous."<<std::endl; |
|
87 |
|
88 |
|
89 |
|
90 std::cout << |
|
91 "\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h," |
|
92 <<std::endl; |
|
93 std::cout<<" on a graph with " << |
|
94 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
|
95 << std::endl<<std::endl; |
|
96 |
|
97 Dijkstra<Graph, LengthMap, FibHeap> |
|
98 dijkstra_test2(G, cap); |
|
99 ts.reset(); |
|
100 dijkstra_test2.run(s); |
|
101 std::cout << "elapsed time: " << ts << std::endl; |
|
102 |
|
103 error1=0; |
|
104 error2=0; |
|
105 |
|
106 FOR_EACH_LOC ( EdgeIt, e, G) { |
|
107 Node u=G.tail(e); |
|
108 Node v=G.head(e); |
|
109 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) |
|
110 if ( dijkstra_test2.reached(u) ) { |
|
111 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
|
112 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
|
113 - cap[e]<<std::endl; |
|
114 ++error1; |
|
115 } |
|
116 } |
|
117 |
|
118 FOR_EACH_LOC ( NodeIt, v, G) { |
|
119 if ( dijkstra_test2.reached(v) ) { |
|
120 Edge e=dijkstra_test2.pred(v); |
|
121 Node u=G.tail(e); |
|
122 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { |
|
123 std::cout<<"Error in a shortest path tree edge! Difference: " |
|
124 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u) |
|
125 - cap[e])<<std::endl; |
|
126 ++error2; |
|
127 } |
|
128 } |
|
129 } |
|
130 |
|
131 |
|
132 std::cout << error1 << " non-tree and " << error2 |
|
133 << " shortest path tree edge is erroneous."<<std::endl; |
|
134 |
|
135 |
|
136 return 0; |
|
137 } |