equal
deleted
inserted
replaced
1 //Tests dijsktra.h with two heap implementations: |
1 //Tests dijsktra.h with two heap implementations: |
2 //the default binary heap of bin_heap.h, and the |
2 //the default binary heap of bin_heap.h, and the |
3 //Fibonacci heap of fib_heap.h. |
3 //Fibonacci heap of fib_heap.h. |
4 |
4 |
5 //The input is a graph in standard dimacs format from the standard input (like |
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 |
6 //in /hugo_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both |
7 //both heaps, checking two postconditions: |
7 //heaps, checking two postconditions: |
8 |
8 |
9 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have |
9 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have |
10 //dist(v)-dist(u)=length(e) |
10 //dist(v)-dist(u)=length(e) |
11 |
11 |
12 // - if all edges e=uv with u reachable from the root have |
12 // - if all edges e=uv with u reachable from the root have |
18 #include <dimacs.h> |
18 #include <dimacs.h> |
19 #include <dijkstra.h> |
19 #include <dijkstra.h> |
20 #include <time_measure.h> |
20 #include <time_measure.h> |
21 #include <bin_heap.h> |
21 #include <bin_heap.h> |
22 #include <fib_heap.h> |
22 #include <fib_heap.h> |
23 #include <for_each_macros.h> |
|
24 |
23 |
25 using namespace hugo; |
24 using namespace hugo; |
26 |
25 |
27 int main(int, char **) { |
26 int main(int, char **) { |
28 |
27 |
54 std::cout << "elapsed time: " << ts << std::endl; |
53 std::cout << "elapsed time: " << ts << std::endl; |
55 |
54 |
56 int error1=0; |
55 int error1=0; |
57 int error2=0; |
56 int error2=0; |
58 |
57 |
59 FOR_EACH_LOC ( EdgeIt, e, G) { |
58 for(EdgeIt e=G.first(e); G.valid(e); G.next(e)) { |
60 Node u=G.tail(e); |
59 Node u=G.tail(e); |
61 Node v=G.head(e); |
60 Node v=G.head(e); |
62 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) |
61 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] ) |
63 if ( dijkstra_test.reached(u) ) { |
62 if ( dijkstra_test.reached(u) ) { |
64 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
63 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
66 - cap[e]<<std::endl; |
65 - cap[e]<<std::endl; |
67 ++error1; |
66 ++error1; |
68 } |
67 } |
69 } |
68 } |
70 |
69 |
71 FOR_EACH_LOC ( NodeIt, v, G) { |
70 for(NodeIt v=G.first(v); G.valid(v); G.next(v)) { |
72 if ( dijkstra_test.reached(v) ) { |
71 if ( dijkstra_test.reached(v) ) { |
73 Edge e=dijkstra_test.pred(v); |
72 Edge e=dijkstra_test.pred(v); |
74 Node u=G.tail(e); |
73 Node u=G.tail(e); |
75 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { |
74 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) { |
76 std::cout<<"Error in a shortest path tree edge! Difference: " |
75 std::cout<<"Error in a shortest path tree edge! Difference: " |
102 std::cout << "elapsed time: " << ts << std::endl; |
101 std::cout << "elapsed time: " << ts << std::endl; |
103 |
102 |
104 error1=0; |
103 error1=0; |
105 error2=0; |
104 error2=0; |
106 |
105 |
107 FOR_EACH_LOC ( EdgeIt, e, G) { |
106 for(EdgeIt e=G.first(e); G.valid(e); G.next(e)) { |
108 Node u=G.tail(e); |
107 Node u=G.tail(e); |
109 Node v=G.head(e); |
108 Node v=G.head(e); |
110 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) |
109 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] ) |
111 if ( dijkstra_test2.reached(u) ) { |
110 if ( dijkstra_test2.reached(u) ) { |
112 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
111 std::cout<<"Error! dist(head)-dist(tail)- edge_length= " |
114 - cap[e]<<std::endl; |
113 - cap[e]<<std::endl; |
115 ++error1; |
114 ++error1; |
116 } |
115 } |
117 } |
116 } |
118 |
117 |
119 FOR_EACH_LOC ( NodeIt, v, G) { |
118 for(NodeIt v=G.first(v); G.valid(v); G.next(v)) { |
120 if ( dijkstra_test2.reached(v) ) { |
119 if ( dijkstra_test2.reached(v) ) { |
121 Edge e=dijkstra_test2.pred(v); |
120 Edge e=dijkstra_test2.pred(v); |
122 Node u=G.tail(e); |
121 Node u=G.tail(e); |
123 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { |
122 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) { |
124 std::cout<<"Error in a shortest path tree edge! Difference: " |
123 std::cout<<"Error in a shortest path tree edge! Difference: " |