COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/dijkstra_test.cc @ 797:30cb42e3e43a

Last change on this file since 797:30cb42e3e43a was 585:65fbcf2f978a, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improve test files for some algorithms (#263)

File size: 6.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2009
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <lemon/concepts/digraph.h>
20#include <lemon/smart_graph.h>
21#include <lemon/list_graph.h>
22#include <lemon/lgf_reader.h>
23#include <lemon/dijkstra.h>
24#include <lemon/path.h>
25#include <lemon/bin_heap.h>
26
27#include "graph_test.h"
28#include "test_tools.h"
29
30using namespace lemon;
31
32char test_lgf[] =
33  "@nodes\n"
34  "label\n"
35  "0\n"
36  "1\n"
37  "2\n"
38  "3\n"
39  "4\n"
40  "@arcs\n"
41  "     label length\n"
42  "0 1  0     1\n"
43  "1 2  1     1\n"
44  "2 3  2     1\n"
45  "0 3  4     5\n"
46  "0 3  5     10\n"
47  "0 3  6     7\n"
48  "4 2  7     1\n"
49  "@attributes\n"
50  "source 0\n"
51  "target 3\n";
52
53void checkDijkstraCompile()
54{
55  typedef int VType;
56  typedef concepts::Digraph Digraph;
57  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
58  typedef Dijkstra<Digraph, LengthMap> DType;
59  typedef Digraph::Node Node;
60  typedef Digraph::Arc Arc;
61
62  Digraph G;
63  Node s, t, n;
64  Arc e;
65  VType l;
66  int i;
67  bool b;
68  DType::DistMap d(G);
69  DType::PredMap p(G);
70  LengthMap length;
71  Path<Digraph> pp;
72  concepts::ReadMap<Node,bool> nm;
73
74  {
75    DType dijkstra_test(G,length);
76    const DType& const_dijkstra_test = dijkstra_test;
77
78    dijkstra_test.run(s);
79    dijkstra_test.run(s,t);
80
81    dijkstra_test.init();
82    dijkstra_test.addSource(s);
83    dijkstra_test.addSource(s, 1);
84    n = dijkstra_test.processNextNode();
85    n = const_dijkstra_test.nextNode();
86    b = const_dijkstra_test.emptyQueue();
87    i = const_dijkstra_test.queueSize();
88   
89    dijkstra_test.start();
90    dijkstra_test.start(t);
91    dijkstra_test.start(nm);
92
93    l  = const_dijkstra_test.dist(t);
94    e  = const_dijkstra_test.predArc(t);
95    s  = const_dijkstra_test.predNode(t);
96    b  = const_dijkstra_test.reached(t);
97    b  = const_dijkstra_test.processed(t);
98    d  = const_dijkstra_test.distMap();
99    p  = const_dijkstra_test.predMap();
100    pp = const_dijkstra_test.path(t);
101    l  = const_dijkstra_test.currentDist(t);
102  }
103  {
104    DType
105      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
106      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
107      ::SetStandardProcessedMap
108      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
109      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
110      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
111      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
113                concepts::ReadWriteMap<Node,int> >
114      ::Create dijkstra_test(G,length);
115
116    LengthMap length_map;
117    concepts::ReadWriteMap<Node,Arc> pred_map;
118    concepts::ReadWriteMap<Node,VType> dist_map;
119    concepts::WriteMap<Node,bool> processed_map;
120    concepts::ReadWriteMap<Node,int> heap_cross_ref;
121    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
122   
123    dijkstra_test
124      .lengthMap(length_map)
125      .predMap(pred_map)
126      .distMap(dist_map)
127      .processedMap(processed_map)
128      .heap(heap, heap_cross_ref);
129
130    dijkstra_test.run(s);
131    dijkstra_test.run(s,t);
132
133    dijkstra_test.addSource(s);
134    dijkstra_test.addSource(s, 1);
135    n = dijkstra_test.processNextNode();
136    n = dijkstra_test.nextNode();
137    b = dijkstra_test.emptyQueue();
138    i = dijkstra_test.queueSize();
139   
140    dijkstra_test.start();
141    dijkstra_test.start(t);
142    dijkstra_test.start(nm);
143
144    l  = dijkstra_test.dist(t);
145    e  = dijkstra_test.predArc(t);
146    s  = dijkstra_test.predNode(t);
147    b  = dijkstra_test.reached(t);
148    b  = dijkstra_test.processed(t);
149    pp = dijkstra_test.path(t);
150    l  = dijkstra_test.currentDist(t);
151  }
152
153}
154
155void checkDijkstraFunctionCompile()
156{
157  typedef int VType;
158  typedef concepts::Digraph Digraph;
159  typedef Digraph::Arc Arc;
160  typedef Digraph::Node Node;
161  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
162
163  Digraph g;
164  bool b;
165  dijkstra(g,LengthMap()).run(Node());
166  b=dijkstra(g,LengthMap()).run(Node(),Node());
167  dijkstra(g,LengthMap())
168    .predMap(concepts::ReadWriteMap<Node,Arc>())
169    .distMap(concepts::ReadWriteMap<Node,VType>())
170    .processedMap(concepts::WriteMap<Node,bool>())
171    .run(Node());
172  b=dijkstra(g,LengthMap())
173    .predMap(concepts::ReadWriteMap<Node,Arc>())
174    .distMap(concepts::ReadWriteMap<Node,VType>())
175    .processedMap(concepts::WriteMap<Node,bool>())
176    .path(concepts::Path<Digraph>())
177    .dist(VType())
178    .run(Node(),Node());
179}
180
181template <class Digraph>
182void checkDijkstra() {
183  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
184  typedef typename Digraph::template ArcMap<int> LengthMap;
185
186  Digraph G;
187  Node s, t;
188  LengthMap length(G);
189
190  std::istringstream input(test_lgf);
191  digraphReader(G, input).
192    arcMap("length", length).
193    node("source", s).
194    node("target", t).
195    run();
196
197  Dijkstra<Digraph, LengthMap>
198        dijkstra_test(G, length);
199  dijkstra_test.run(s);
200
201  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
202
203  Path<Digraph> p = dijkstra_test.path(t);
204  check(p.length()==3,"path() found a wrong path.");
205  check(checkPath(G, p),"path() found a wrong path.");
206  check(pathSource(G, p) == s,"path() found a wrong path.");
207  check(pathTarget(G, p) == t,"path() found a wrong path.");
208
209  for(ArcIt e(G); e!=INVALID; ++e) {
210    Node u=G.source(e);
211    Node v=G.target(e);
212    check( !dijkstra_test.reached(u) ||
213           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
214           "Wrong output. dist(target)-dist(source)-arc_length=" <<
215           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
216  }
217
218  for(NodeIt v(G); v!=INVALID; ++v) {
219    if (dijkstra_test.reached(v)) {
220      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
221      if (dijkstra_test.predArc(v)!=INVALID ) {
222        Arc e=dijkstra_test.predArc(v);
223        Node u=G.source(e);
224        check(u==dijkstra_test.predNode(v),"Wrong tree.");
225        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
226              "Wrong distance! Difference: " <<
227              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
228      }
229    }
230  }
231
232  {
233    NullMap<Node,Arc> myPredMap;
234    dijkstra(G,length).predMap(myPredMap).run(s);
235  }
236}
237
238int main() {
239  checkDijkstra<ListDigraph>();
240  checkDijkstra<SmartDigraph>();
241  return 0;
242}
Note: See TracBrowser for help on using the repository browser.