1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/test/dijkstra_heap_test.cc Fri Apr 23 18:48:56 2004 +0000
1.3 @@ -0,0 +1,137 @@
1.4 +//Tests dijsktra.h with two heap implementations:
1.5 +//the default binary heap of bin_heap.h, and the
1.6 +//Fibonacci heap of fib_heap.h.
1.7 +
1.8 +//The input is a graph in standard dimacs format from the standard input (like
1.9 +//in /hugo_loc/testfiles/dimacs). It runs dijkstra.h on this graph with
1.10 +//both heaps, checking two postconditions:
1.11 +
1.12 +//- if the edges e=uv of the shortest path tree reported by dijkstra.h have
1.13 +//dist(v)-dist(u)=length(e)
1.14 +
1.15 +// - if all edges e=uv with u reachable from the root have
1.16 +//dist(v)-dist(u)>=length(e)
1.17 +#include <iostream>
1.18 +#include <math.h>
1.19 +
1.20 +#include <smart_graph.h>
1.21 +#include <dimacs.h>
1.22 +#include <dijkstra.h>
1.23 +#include <time_measure.h>
1.24 +#include <bin_heap.h>
1.25 +#include <for_each_macros.h>
1.26 +
1.27 +using namespace hugo;
1.28 +
1.29 +int main(int, char **) {
1.30 +
1.31 + typedef SmartGraph Graph;
1.32 +
1.33 + typedef Graph::Edge Edge;
1.34 + typedef Graph::Node Node;
1.35 + typedef Graph::EdgeIt EdgeIt;
1.36 + typedef Graph::NodeIt NodeIt;
1.37 + typedef Graph::EdgeMap<int> LengthMap;
1.38 +
1.39 + Graph G;
1.40 + Node s, t;
1.41 + LengthMap cap(G);
1.42 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.43 + Timer ts;
1.44 +
1.45 + std::cout <<
1.46 + "\n Testing dijkstra.h with binary heap implementation bin_heap.h,"
1.47 + <<std::endl;
1.48 + std::cout<<" on a graph with " <<
1.49 + G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.50 + << std::endl<<std::endl;
1.51 +
1.52 + Dijkstra<Graph, LengthMap>
1.53 + dijkstra_test(G, cap);
1.54 + ts.reset();
1.55 + dijkstra_test.run(s);
1.56 + std::cout << "elapsed time: " << ts << std::endl;
1.57 +
1.58 + int error1=0;
1.59 + int error2=0;
1.60 +
1.61 + FOR_EACH_LOC ( EdgeIt, e, G) {
1.62 + Node u=G.tail(e);
1.63 + Node v=G.head(e);
1.64 + if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
1.65 + if ( dijkstra_test.reached(u) ) {
1.66 + std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
1.67 + <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.68 + - cap[e]<<std::endl;
1.69 + ++error1;
1.70 + }
1.71 + }
1.72 +
1.73 + FOR_EACH_LOC ( NodeIt, v, G) {
1.74 + if ( dijkstra_test.reached(v) ) {
1.75 + Edge e=dijkstra_test.pred(v);
1.76 + Node u=G.tail(e);
1.77 + if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
1.78 + std::cout<<"Error in a shortest path tree edge! Difference: "
1.79 + <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
1.80 + - cap[e])<<std::endl;
1.81 + ++error2;
1.82 + }
1.83 + }
1.84 + }
1.85 +
1.86 +
1.87 +
1.88 + std::cout << error1 << " non-tree and " << error2
1.89 + << " shortest path tree edge is erroneous."<<std::endl;
1.90 +
1.91 +
1.92 +
1.93 + std::cout <<
1.94 + "\n Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
1.95 + <<std::endl;
1.96 + std::cout<<" on a graph with " <<
1.97 + G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
1.98 + << std::endl<<std::endl;
1.99 +
1.100 + Dijkstra<Graph, LengthMap, FibHeap>
1.101 + dijkstra_test2(G, cap);
1.102 + ts.reset();
1.103 + dijkstra_test2.run(s);
1.104 + std::cout << "elapsed time: " << ts << std::endl;
1.105 +
1.106 + error1=0;
1.107 + error2=0;
1.108 +
1.109 + FOR_EACH_LOC ( EdgeIt, e, G) {
1.110 + Node u=G.tail(e);
1.111 + Node v=G.head(e);
1.112 + if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
1.113 + if ( dijkstra_test2.reached(u) ) {
1.114 + std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
1.115 + <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
1.116 + - cap[e]<<std::endl;
1.117 + ++error1;
1.118 + }
1.119 + }
1.120 +
1.121 + FOR_EACH_LOC ( NodeIt, v, G) {
1.122 + if ( dijkstra_test2.reached(v) ) {
1.123 + Edge e=dijkstra_test2.pred(v);
1.124 + Node u=G.tail(e);
1.125 + if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
1.126 + std::cout<<"Error in a shortest path tree edge! Difference: "
1.127 + <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
1.128 + - cap[e])<<std::endl;
1.129 + ++error2;
1.130 + }
1.131 + }
1.132 + }
1.133 +
1.134 +
1.135 + std::cout << error1 << " non-tree and " << error2
1.136 + << " shortest path tree edge is erroneous."<<std::endl;
1.137 +
1.138 +
1.139 + return 0;
1.140 +}