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 +}

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/test/makefile	Fri Apr 23 18:48:56 2004 +0000
     2.3 @@ -0,0 +1,22 @@
     2.4 +CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
     2.5 +CXX2 = g++-2.95
     2.6 +CXX=$(CXX3)
     2.7 +CC=$(CXX)
     2.8 +INCLUDEDIRS ?= -I../include -I.. -I../work/{marci,jacint,alpar,klao,akos,athos} 
     2.9 +CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS) 
    2.10 +LEDAROOT ?= /ledasrc/LEDA-4.1
    2.11 +
    2.12 +BINARIES = dijkstra_heap_test 
    2.13 +
    2.14 +all: $(BINARIES)
    2.15 +
    2.16 +.depend dep depend:
    2.17 +	-$(CXX) $(INCLUDEDIRS) -M $(BINARIES:=.cc) > .depend #2>/dev/null
    2.18 +
    2.19 +makefile: .depend
    2.20 +sinclude .depend
    2.21 +
    2.22 +clean:
    2.23 +	$(RM) *.o $(BINARIES) .depend
    2.24 +
    2.25 +.PHONY: all clean dep depend