COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_heap_test.cc @ 542:69bde1d90c04

Last change on this file since 542:69bde1d90c04 was 542:69bde1d90c04, checked in by Akos Ladanyi, 17 years ago

Set up automake environment.

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 both
7//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 <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>
23
24using namespace hugo;
25
26int main(int, char **) {
27 
28  typedef SmartGraph Graph;
29
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;
35
36  Graph G;
37  Node s, t;
38  LengthMap cap(G);
39  readDimacsMaxFlow(std::cin, G, s, t, cap);
40  Timer ts;
41   
42  std::cout <<
43    "\n  Testing dijkstra.h with binary heap implementation bin_heap.h,"
44            <<std::endl;
45  std::cout<<"  on a graph with " <<
46    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
47           << std::endl<<std::endl;
48 
49  Dijkstra<Graph, LengthMap>
50    dijkstra_test(G, cap);
51  ts.reset();
52  dijkstra_test.run(s);
53  std::cout << "elapsed time: " << ts << std::endl;
54 
55  int error1=0;
56  int error2=0;
57
58  EdgeIt e;
59  for(G.first(e); G.valid(e); G.next(e)) {
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  NodeIt v;
72  for(G.first(v); G.valid(v); G.next(v)) {
73    if ( dijkstra_test.reached(v) ) {
74      Edge e=dijkstra_test.pred(v);
75      Node u=G.tail(e);
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)
79                            - cap[e])<<std::endl;
80        ++error2;
81      }
82    }
83  }
84
85
86 
87  std::cout << error1 << " non-tree and " << error2
88            << " shortest path tree edge is erroneous."<<std::endl;
89
90
91
92  std::cout <<
93    "\n\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
94            <<std::endl;
95  std::cout<<"  on a graph with " <<
96    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
97           << std::endl<<std::endl;
98 
99  Dijkstra<Graph, LengthMap, FibHeap>
100    dijkstra_test2(G, cap);
101  ts.reset();
102  dijkstra_test2.run(s);
103  std::cout << "elapsed time: " << ts << std::endl;
104 
105  error1=0;
106  error2=0;
107
108  for(G.first(e); G.valid(e); G.next(e)) {
109    Node u=G.tail(e);
110    Node v=G.head(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)
115          - cap[e]<<std::endl;
116        ++error1;
117      }
118  }
119
120  for(G.first(v); G.valid(v); G.next(v)) {
121    if ( dijkstra_test2.reached(v) ) {
122      Edge e=dijkstra_test2.pred(v);
123      Node u=G.tail(e);
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;
128        ++error2;
129      }
130    }
131  }
132
133
134  std::cout << error1 << " non-tree and " << error2
135            << " shortest path tree edge is erroneous."<<std::endl;
136
137
138  return 0;
139}
Note: See TracBrowser for help on using the repository browser.