COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_heap_test.cc @ 394:3a34c5626e52

Last change on this file since 394:3a34c5626e52 was 386:0bdc7c279e79, checked in by jacint, 21 years ago

aprosag

File size: 3.6 KB
Line 
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.
4
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
7//both heaps, checking two postconditions:
8
9//- if the edges e=uv of the shortest path tree reported by dijkstra.h have
10//dist(v)-dist(u)=length(e)
11
12// - if all edges e=uv with u reachable from the root have
13//dist(v)-dist(u)>=length(e)
14#include <iostream>
15#include <math.h>
16
17#include <smart_graph.h>
18#include <dimacs.h>
19#include <dijkstra.h>
20#include <time_measure.h>
21#include <bin_heap.h>
22#include <fib_heap.h>
23#include <for_each_macros.h>
24
25using namespace hugo;
26
27int main(int, char **) {
28 
29  typedef SmartGraph Graph;
30
31  typedef Graph::Edge Edge;
32  typedef Graph::Node Node;
33  typedef Graph::EdgeIt EdgeIt;
34  typedef Graph::NodeIt NodeIt;
35  typedef Graph::EdgeMap<int> LengthMap;
36
37  Graph G;
38  Node s, t;
39  LengthMap cap(G);
40  readDimacsMaxFlow(std::cin, G, s, t, cap);
41  Timer ts;
42   
43  std::cout <<
44    "\n  Testing dijkstra.h with binary heap implementation bin_heap.h,"
45            <<std::endl;
46  std::cout<<"  on a graph with " <<
47    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
48           << std::endl<<std::endl;
49 
50  Dijkstra<Graph, LengthMap>
51    dijkstra_test(G, cap);
52  ts.reset();
53  dijkstra_test.run(s);
54  std::cout << "elapsed time: " << ts << std::endl;
55 
56  int error1=0;
57  int error2=0;
58
59  FOR_EACH_LOC ( EdgeIt, e, G) {
60    Node u=G.tail(e);
61    Node v=G.head(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)
66          - cap[e]<<std::endl;
67        ++error1;
68      }
69  }
70
71  FOR_EACH_LOC ( NodeIt, v, G) {
72    if ( dijkstra_test.reached(v) ) {
73      Edge e=dijkstra_test.pred(v);
74      Node u=G.tail(e);
75      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
76        std::cout<<"Error in a shortest path tree edge! Difference: "
77                 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
78                            - cap[e])<<std::endl;
79        ++error2;
80      }
81    }
82  }
83
84
85 
86  std::cout << error1 << " non-tree and " << error2
87            << " shortest path tree edge is erroneous."<<std::endl;
88
89
90
91  std::cout <<
92    "\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
93            <<std::endl;
94  std::cout<<"  on a graph with " <<
95    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
96           << std::endl<<std::endl;
97 
98  Dijkstra<Graph, LengthMap, FibHeap>
99    dijkstra_test2(G, cap);
100  ts.reset();
101  dijkstra_test2.run(s);
102  std::cout << "elapsed time: " << ts << std::endl;
103 
104  error1=0;
105  error2=0;
106
107  FOR_EACH_LOC ( EdgeIt, e, G) {
108    Node u=G.tail(e);
109    Node v=G.head(e);
110    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
111      if ( dijkstra_test2.reached(u) ) {
112        std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
113                 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
114          - cap[e]<<std::endl;
115        ++error1;
116      }
117  }
118
119  FOR_EACH_LOC ( NodeIt, v, G) {
120    if ( dijkstra_test2.reached(v) ) {
121      Edge e=dijkstra_test2.pred(v);
122      Node u=G.tail(e);
123      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
124        std::cout<<"Error in a shortest path tree edge! Difference: "
125                 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
126                            - cap[e])<<std::endl;
127        ++error2;
128      }
129    }
130  }
131
132
133  std::cout << error1 << " non-tree and " << error2
134            << " shortest path tree edge is erroneous."<<std::endl;
135
136
137  return 0;
138}
Note: See TracBrowser for help on using the repository browser.