COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_heap_test.cc @ 440:f92099d27236

Last change on this file since 440:f92099d27236 was 422:ede61a3d229b, checked in by jacint, 20 years ago

macro erase

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 <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
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  for(EdgeIt e=G.first(e); G.valid(e); G.next(e)) {
59    Node u=G.tail(e);
60    Node v=G.head(e);
61    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
62      if ( dijkstra_test.reached(u) ) {
63        std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
64                 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
65          - cap[e]<<std::endl;
66        ++error1;
67      }
68  }
69
70  for(NodeIt v=G.first(v); G.valid(v); G.next(v)) {
71    if ( dijkstra_test.reached(v) ) {
72      Edge e=dijkstra_test.pred(v);
73      Node u=G.tail(e);
74      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
75        std::cout<<"Error in a shortest path tree edge! Difference: "
76                 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
77                            - cap[e])<<std::endl;
78        ++error2;
79      }
80    }
81  }
82
83
84 
85  std::cout << error1 << " non-tree and " << error2
86            << " shortest path tree edge is erroneous."<<std::endl;
87
88
89
90  std::cout <<
91    "\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
92            <<std::endl;
93  std::cout<<"  on a graph with " <<
94    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
95           << std::endl<<std::endl;
96 
97  Dijkstra<Graph, LengthMap, FibHeap>
98    dijkstra_test2(G, cap);
99  ts.reset();
100  dijkstra_test2.run(s);
101  std::cout << "elapsed time: " << ts << std::endl;
102 
103  error1=0;
104  error2=0;
105
106  for(EdgeIt e=G.first(e); G.valid(e); G.next(e)) {
107    Node u=G.tail(e);
108    Node v=G.head(e);
109    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
110      if ( dijkstra_test2.reached(u) ) {
111        std::cout<<"Error! dist(head)-dist(tail)- edge_length= "
112                 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
113          - cap[e]<<std::endl;
114        ++error1;
115      }
116  }
117
118  for(NodeIt v=G.first(v); G.valid(v); G.next(v)) {
119    if ( dijkstra_test2.reached(v) ) {
120      Edge e=dijkstra_test2.pred(v);
121      Node u=G.tail(e);
122      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
123        std::cout<<"Error in a shortest path tree edge! Difference: "
124                 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
125                            - cap[e])<<std::endl;
126        ++error2;
127      }
128    }
129  }
130
131
132  std::cout << error1 << " non-tree and " << error2
133            << " shortest path tree edge is erroneous."<<std::endl;
134
135
136  return 0;
137}
Note: See TracBrowser for help on using the repository browser.