COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_heap_test.cc @ 1139:f59038affc7e

Last change on this file since 1139:f59038affc7e was 1139:f59038affc7e, checked in by Balazs Dezso, 15 years ago

Changing first to iterators.

File size: 4.2 KB
Line 
1/* -*- C++ -*-
2 * src/test/dijkstra_heap_test.cc - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17//Tests dijsktra.h with two heap implementations:
18//the default binary heap of bin_heap.h, and the
19//Fibonacci heap of fib_heap.h.
20
21//The input is a graph in standard dimacs format from the standard input (like
22//in /lemon_loc/testfiles/dimacs). It runs dijkstra.h on this graph with both
23//heaps, checking two postconditions:
24
25//- if the edges e=uv of the shortest path tree reported by dijkstra.h have
26//dist(v)-dist(u)=length(e)
27
28// - if all edges e=uv with u reachable from the root have
29//dist(v)-dist(u)>=length(e)
30#include <iostream>
31#include <math.h>
32
33#include <lemon/smart_graph.h>
34#include <lemon/dimacs.h>
35#include <lemon/dijkstra.h>
36#include <lemon/time_measure.h>
37#include <lemon/bin_heap.h>
38#include <lemon/fib_heap.h>
39
40using namespace lemon;
41
42int main(int, char **) {
43 
44  typedef SmartGraph Graph;
45
46  typedef Graph::Edge Edge;
47  typedef Graph::Node Node;
48  typedef Graph::EdgeIt EdgeIt;
49  typedef Graph::NodeIt NodeIt;
50  typedef Graph::template EdgeMap<int> LengthMap;
51
52  Graph G;
53  Node s, t;
54  LengthMap cap(G);
55  readDimacsMaxFlow(std::cin, G, s, t, cap);
56  Timer ts;
57   
58  std::cout <<
59    "\n  Testing dijkstra.h with binary heap implementation bin_heap.h,"
60            <<std::endl;
61  std::cout<<"  on a graph with " <<
62    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
63           << std::endl<<std::endl;
64 
65  Dijkstra<Graph, LengthMap>
66    dijkstra_test(G, cap);
67  ts.reset();
68  dijkstra_test.run(s);
69  std::cout << "elapsed time: " << ts << std::endl;
70 
71  int error1=0;
72  int error2=0;
73
74  for(EdgeIt e(G); e!=INVALID; ++e) {
75    Node u=G.source(e);
76    Node v=G.target(e);
77    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
78      if ( dijkstra_test.reached(u) ) {
79        std::cout<<"Error! dist(target)-dist(source)- edge_length= "
80                 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
81          - cap[e]<<std::endl;
82        ++error1;
83      }
84  }
85
86  NodeIt v;
87  for(NodeIt v(G); v!=INVALID; ++v) {
88    if ( dijkstra_test.reached(v) ) {
89      Edge e=dijkstra_test.pred(v);
90      Node u=G.source(e);
91      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
92        std::cout<<"Error in a shortest path tree edge! Difference: "
93                 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
94                            - cap[e])<<std::endl;
95        ++error2;
96      }
97    }
98  }
99
100
101 
102  std::cout << error1 << " non-tree and " << error2
103            << " shortest path tree edge is erroneous."<<std::endl;
104
105
106
107  std::cout <<
108    "\n\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
109            <<std::endl;
110  std::cout<<"  on a graph with " <<
111    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
112           << std::endl<<std::endl;
113 
114  Dijkstra<Graph, LengthMap, FibHeap>
115    dijkstra_test2(G, cap);
116  ts.reset();
117  dijkstra_test2.run(s);
118  std::cout << "elapsed time: " << ts << std::endl;
119 
120  error1=0;
121  error2=0;
122
123  for(EdgeIt e(G); e!=INVALID; ++e) {
124    Node u=G.source(e);
125    Node v=G.target(e);
126    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
127      if ( dijkstra_test2.reached(u) ) {
128        std::cout<<"Error! dist(target)-dist(source)- edge_length= "
129                 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
130          - cap[e]<<std::endl;
131        ++error1;
132      }
133  }
134
135  for(NodeIt n(G); v!=INVALID; ++v) {
136    if ( dijkstra_test2.reached(v) ) {
137      Edge e=dijkstra_test2.pred(v);
138      Node u=G.source(e);
139      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
140        std::cout<<"Error in a shortest path tree edge! Difference: "
141                 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
142                            - cap[e])<<std::endl;
143        ++error2;
144      }
145    }
146  }
147
148
149  std::cout << error1 << " non-tree and " << error2
150            << " shortest path tree edge is erroneous."<<std::endl;
151
152
153  return 0;
154}
Note: See TracBrowser for help on using the repository browser.