.
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.
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 both
7 //heaps, checking two postconditions:
9 //- if the edges e=uv of the shortest path tree reported by dijkstra.h have
10 //dist(v)-dist(u)=length(e)
12 // - if all edges e=uv with u reachable from the root have
13 //dist(v)-dist(u)>=length(e)
17 #include <hugo/smart_graph.h>
18 #include <hugo/dimacs.h>
19 #include <hugo/dijkstra.h>
20 #include <hugo/time_measure.h>
21 #include <hugo/bin_heap.h>
22 #include <hugo/fib_heap.h>
26 int main(int, char **) {
28 typedef SmartGraph Graph;
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;
39 readDimacsMaxFlow(std::cin, G, s, t, cap);
43 "\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
45 std::cout<<" on a graph with " <<
46 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
47 << std::endl<<std::endl;
49 Dijkstra<Graph, LengthMap>
50 dijkstra_test(G, cap);
53 std::cout << "elapsed time: " << ts << std::endl;
59 for(G.first(e); e!=INVALID; ++e) {
62 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
63 if ( dijkstra_test.reached(u) ) {
64 std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
65 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
72 for(G.first(v); v!=INVALID; ++v) {
73 if ( dijkstra_test.reached(v) ) {
74 Edge e=dijkstra_test.pred(v);
76 if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
77 std::cout<<"Error in a shortest path tree edge! Difference: "
78 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
87 std::cout << error1 << " non-tree and " << error2
88 << " shortest path tree edge is erroneous."<<std::endl;
93 "\n\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
95 std::cout<<" on a graph with " <<
96 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
97 << std::endl<<std::endl;
99 Dijkstra<Graph, LengthMap, FibHeap>
100 dijkstra_test2(G, cap);
102 dijkstra_test2.run(s);
103 std::cout << "elapsed time: " << ts << std::endl;
108 for(G.first(e); e!=INVALID; ++e) {
111 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
112 if ( dijkstra_test2.reached(u) ) {
113 std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
114 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
120 for(G.first(v); v!=INVALID; ++v) {
121 if ( dijkstra_test2.reached(v) ) {
122 Edge e=dijkstra_test2.pred(v);
124 if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
125 std::cout<<"Error in a shortest path tree edge! Difference: "
126 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
127 - cap[e])<<std::endl;
134 std::cout << error1 << " non-tree and " << error2
135 << " shortest path tree edge is erroneous."<<std::endl;