COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_heap_test.cc @ 1138:f68cb8752d81

Last change on this file since 1138:f68cb8752d81 was 986:e997802b855c, checked in by Alpar Juttner, 16 years ago

Naming changes:

  • head -> target
  • tail -> source
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  EdgeIt e;
75  for(G.first(e); e!=INVALID; ++e) {
76    Node u=G.source(e);
77    Node v=G.target(e);
78    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap[e] )
79      if ( dijkstra_test.reached(u) ) {
80        std::cout<<"Error! dist(target)-dist(source)- edge_length= "
81                 <<dijkstra_test.dist(v) - dijkstra_test.dist(u)
82          - cap[e]<<std::endl;
83        ++error1;
84      }
85  }
86
87  NodeIt v;
88  for(G.first(v); v!=INVALID; ++v) {
89    if ( dijkstra_test.reached(v) ) {
90      Edge e=dijkstra_test.pred(v);
91      Node u=G.source(e);
92      if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) != cap[e] ) {
93        std::cout<<"Error in a shortest path tree edge! Difference: "
94                 <<std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
95                            - cap[e])<<std::endl;
96        ++error2;
97      }
98    }
99  }
100
101
102 
103  std::cout << error1 << " non-tree and " << error2
104            << " shortest path tree edge is erroneous."<<std::endl;
105
106
107
108  std::cout <<
109    "\n\n  Testing dijkstra.h with Fibonacci heap implementation fib_heap.h,"
110            <<std::endl;
111  std::cout<<"  on a graph with " <<
112    G.nodeNum() << " nodes and " << G.edgeNum() << " edges..."
113           << std::endl<<std::endl;
114 
115  Dijkstra<Graph, LengthMap, FibHeap>
116    dijkstra_test2(G, cap);
117  ts.reset();
118  dijkstra_test2.run(s);
119  std::cout << "elapsed time: " << ts << std::endl;
120 
121  error1=0;
122  error2=0;
123
124  for(G.first(e); e!=INVALID; ++e) {
125    Node u=G.source(e);
126    Node v=G.target(e);
127    if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) > cap[e] )
128      if ( dijkstra_test2.reached(u) ) {
129        std::cout<<"Error! dist(target)-dist(source)- edge_length= "
130                 <<dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
131          - cap[e]<<std::endl;
132        ++error1;
133      }
134  }
135
136  for(G.first(v); v!=INVALID; ++v) {
137    if ( dijkstra_test2.reached(v) ) {
138      Edge e=dijkstra_test2.pred(v);
139      Node u=G.source(e);
140      if ( dijkstra_test2.dist(v) - dijkstra_test2.dist(u) != cap[e] ) {
141        std::cout<<"Error in a shortest path tree edge! Difference: "
142                 <<std::abs(dijkstra_test2.dist(v) - dijkstra_test2.dist(u)
143                            - cap[e])<<std::endl;
144        ++error2;
145      }
146    }
147  }
148
149
150  std::cout << error1 << " non-tree and " << error2
151            << " shortest path tree edge is erroneous."<<std::endl;
152
153
154  return 0;
155}
Note: See TracBrowser for help on using the repository browser.