1.1 --- a/src/test/dijkstra_heap_test.cc	Fri Mar 04 17:18:25 2005 +0000
     1.2 +++ b/src/test/dijkstra_heap_test.cc	Fri Mar 04 17:20:11 2005 +0000
     1.3 @@ -31,49 +31,81 @@
     1.4  #include <math.h>
     1.5  
     1.6  #include <lemon/smart_graph.h>
     1.7 +
     1.8 +#include <lemon/graph_writer.h>
     1.9 +#include <lemon/map_utils.h>
    1.10 +
    1.11 +
    1.12  #include <lemon/dimacs.h>
    1.13  #include <lemon/dijkstra.h>
    1.14  #include <lemon/time_measure.h>
    1.15 +#include <lemon/graph_utils.h>
    1.16 +
    1.17  #include <lemon/bin_heap.h>
    1.18  #include <lemon/fib_heap.h>
    1.19 +#include <lemon/radix_heap.h>
    1.20  
    1.21  using namespace lemon;
    1.22  
    1.23 -int main(int, char **) {
    1.24 +typedef ListGraph Graph;
    1.25 +
    1.26 +typedef Graph::Edge Edge;
    1.27 +typedef Graph::Node Node;
    1.28 +typedef Graph::EdgeIt EdgeIt;
    1.29 +typedef Graph::NodeIt NodeIt;
    1.30 +typedef Graph::EdgeMap<int> LengthMap;
    1.31 +
    1.32 +
    1.33 +struct FibTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
    1.34 +  typedef FibHeap<Graph::Node, LengthMap::Value, Graph::NodeMap<int> > Heap;
    1.35 +};
    1.36 +
    1.37 +struct RadixTraits : public DijkstraDefaultTraits<Graph, LengthMap> {
    1.38 +  typedef RadixHeap<Graph::Node, Graph::NodeMap<int> > Heap;
    1.39 +};
    1.40 +
    1.41 +
    1.42 +int main(int argc, const char* argv[]) {
    1.43    
    1.44 -  typedef SmartGraph Graph;
    1.45  
    1.46 -  typedef Graph::Edge Edge;
    1.47 -  typedef Graph::Node Node;
    1.48 -  typedef Graph::EdgeIt EdgeIt;
    1.49 -  typedef Graph::NodeIt NodeIt;
    1.50 -  typedef Graph::template EdgeMap<int> LengthMap;
    1.51 +  Graph graph;
    1.52 +  Node s, t;
    1.53 +  LengthMap cap(graph);
    1.54 +  readDimacs(std::cin, graph, cap, s, t);
    1.55 +  Timer ts;
    1.56  
    1.57 -  Graph G;
    1.58 -  Node s, t;
    1.59 -  LengthMap cap(G);
    1.60 -  readDimacsMaxFlow(std::cin, G, s, t, cap);
    1.61 -  Timer ts;
    1.62 +  GraphWriter<Graph> writer(std::cout, graph);
    1.63 +
    1.64 +  IdMap<Graph, Node> nodeIdMap(graph);
    1.65 +  writer.addNodeMap("id", nodeIdMap);
    1.66 +
    1.67 +  IdMap<Graph, Edge> edgeIdMap(graph);
    1.68 +  writer.addEdgeMap("id", edgeIdMap);
    1.69 +
    1.70 +  writer.addEdgeMap("cap", cap);
    1.71 +
    1.72 +  writer.run();
    1.73      
    1.74    std::cout <<
    1.75      "\n  Testing dijkstra.h with binary heap implementation bin_heap.h,"
    1.76  	    <<std::endl;
    1.77    std::cout<<"  on a graph with " << 
    1.78 -    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
    1.79 +    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
    1.80  	   << std::endl<<std::endl;
    1.81 -  
    1.82 +
    1.83 +
    1.84    Dijkstra<Graph, LengthMap> 
    1.85 -    dijkstra_test(G, cap);
    1.86 +    dijkstra_test(graph, cap);
    1.87    ts.reset();
    1.88 -  dijkstra_test.run(s);
    1.89 +   dijkstra_test.run(s);
    1.90    std::cout << "elapsed time: " << ts << std::endl;
    1.91 -  
    1.92 +
    1.93    int error1=0;
    1.94    int error2=0;
    1.95  
    1.96 -  for(EdgeIt e(G); e!=INVALID; ++e) {
    1.97 -    Node u=G.source(e);
    1.98 -    Node v=G.target(e);
    1.99 +  for(EdgeIt e(graph); e!=INVALID; ++e) {
   1.100 +    Node u=graph.source(e); 
   1.101 +    Node v=graph.target(e);
   1.102      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
   1.103        if ( dijkstra_test.reached(u) ) {
   1.104  	std::cout<<"Error! dist(target)-dist(source)- edge_length= " 
   1.105 @@ -84,10 +116,10 @@
   1.106    }
   1.107  
   1.108    NodeIt v;
   1.109 -  for(NodeIt v(G); v!=INVALID; ++v) {
   1.110 +  for(NodeIt v(graph); v!=INVALID; ++v) {
   1.111      if ( dijkstra_test.reached(v) ) {
   1.112        Edge e=dijkstra_test.pred(v);
   1.113 -      Node u=G.source(e);
   1.114 +      Node u=graph.source(e);
   1.115        if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
   1.116  	std::cout<<"Error in a shortest path tree edge! Difference: " 
   1.117  		 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
   1.118 @@ -108,11 +140,12 @@
   1.119      "\n\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
   1.120  	    <<std::endl;
   1.121    std::cout<<"  on a graph with " << 
   1.122 -    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
   1.123 +    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
   1.124  	   << std::endl<<std::endl;
   1.125    
   1.126 -  Dijkstra<Graph, LengthMap, FibHeap> 
   1.127 -    dijkstra_test2(G, cap);
   1.128 +
   1.129 +  Dijkstra<Graph, LengthMap, FibTraits> 
   1.130 +    dijkstra_test2(graph, cap);
   1.131    ts.reset();
   1.132    dijkstra_test2.run(s);
   1.133    std::cout << "elapsed time: " << ts << std::endl;
   1.134 @@ -120,9 +153,9 @@
   1.135    error1=0;
   1.136    error2=0;
   1.137  
   1.138 -  for(EdgeIt e(G); e!=INVALID; ++e) {
   1.139 -    Node u=G.source(e);
   1.140 -    Node v=G.target(e);
   1.141 +  for(EdgeIt e(graph); e!=INVALID; ++e) {
   1.142 +    Node u=graph.source(e);
   1.143 +    Node v=graph.target(e);
   1.144      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
   1.145        if ( dijkstra_test2.reached(u) ) {
   1.146  	std::cout<<"Error! dist(target)-dist(source)- edge_length= " 
   1.147 @@ -132,10 +165,10 @@
   1.148        }
   1.149    }
   1.150  
   1.151 -  for(NodeIt n(G); v!=INVALID; ++v) {
   1.152 +  for(NodeIt n(graph); v!=INVALID; ++v) {
   1.153      if ( dijkstra_test2.reached(v) ) {
   1.154        Edge e=dijkstra_test2.pred(v);
   1.155 -      Node u=G.source(e);
   1.156 +      Node u=graph.source(e);
   1.157        if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
   1.158  	std::cout<<"Error in a shortest path tree edge! Difference: " 
   1.159  		 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u) 
   1.160 @@ -149,6 +182,52 @@
   1.161    std::cout << error1 << " non-tree and " << error2 
   1.162  	    << " shortest path tree edge is erroneous."<<std::endl;
   1.163  
   1.164 +  std::cout <<
   1.165 +    "\n\n  Testing dijkstra.h with Radix heap implementation radix_heap.h,"
   1.166 +	    <<std::endl;
   1.167 +  std::cout<<"  on a graph with " << 
   1.168 +    countNodes(graph) << " nodes and " << countEdges(graph) << " edges..."
   1.169 +	   << std::endl<<std::endl;
   1.170 +
   1.171 +
   1.172 +  Dijkstra<Graph, LengthMap, RadixTraits> 
   1.173 +    dijkstra_test3(graph, cap);
   1.174 +  ts.reset();
   1.175 +  dijkstra_test3.run(s);
   1.176 +  std::cout << "elapsed time: " << ts << std::endl;
   1.177 +  
   1.178 +
   1.179 +  error1=0;
   1.180 +  error2=0;
   1.181 +
   1.182 +  for(EdgeIt e(graph); e!=INVALID; ++e) {
   1.183 +    Node u=graph.source(e);
   1.184 +    Node v=graph.target(e);
   1.185 +    if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) > cap[e] )
   1.186 +      if ( dijkstra_test3.reached(u) ) {
   1.187 +	std::cout<<"Error! dist(target)-dist(source)- edge_length= " 
   1.188 +		 <<dijkstra_test3.dist(v) - dijkstra_test3.dist(u) 
   1.189 +	  - cap[e]<<std::endl;
   1.190 +	++error1;
   1.191 +      }
   1.192 +  }
   1.193 +
   1.194 +  for(NodeIt n(graph); v!=INVALID; ++v) {
   1.195 +    if ( dijkstra_test3.reached(v) ) {
   1.196 +      Edge e=dijkstra_test3.pred(v);
   1.197 +      Node u=graph.source(e);
   1.198 +      if ( dijkstra_test3.dist(v) - dijkstra_test3.dist(u) != cap[e] ) {
   1.199 +	std::cout<<"Error in a shortest path tree edge! Difference: " 
   1.200 +		 <<std::abs(dijkstra_test3.dist(v) - dijkstra_test3.dist(u) 
   1.201 +			    - cap[e])<<std::endl;
   1.202 +	++error2;
   1.203 +      }
   1.204 +    }
   1.205 +  }
   1.206 +
   1.207 +
   1.208 +  std::cout << error1 << " non-tree and " << error2 
   1.209 +	    << " shortest path tree edge is erroneous."<<std::endl;
   1.210  
   1.211    return 0;
   1.212  }