COIN-OR::LEMON - Graph Library

source: lemon-main/test/dijkstra_test.cc @ 1060:45befc97b1bc

Last change on this file since 1060:45befc97b1bc was 1008:d216e1c8b3fa, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #453 to branches >=1.2

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-2010
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  ignore_unused_variable_warning(l,i,b);
69
70  DType::DistMap d(G);
71  DType::PredMap p(G);
72  LengthMap length;
73  Path<Digraph> pp;
74  concepts::ReadMap<Node,bool> nm;
75
76  {
77    DType dijkstra_test(G,length);
78    const DType& const_dijkstra_test = dijkstra_test;
79
80    dijkstra_test.run(s);
81    dijkstra_test.run(s,t);
82
83    dijkstra_test.init();
84    dijkstra_test.addSource(s);
85    dijkstra_test.addSource(s, 1);
86    n = dijkstra_test.processNextNode();
87    n = const_dijkstra_test.nextNode();
88    b = const_dijkstra_test.emptyQueue();
89    i = const_dijkstra_test.queueSize();
90
91    dijkstra_test.start();
92    dijkstra_test.start(t);
93    dijkstra_test.start(nm);
94
95    l  = const_dijkstra_test.dist(t);
96    e  = const_dijkstra_test.predArc(t);
97    s  = const_dijkstra_test.predNode(t);
98    b  = const_dijkstra_test.reached(t);
99    b  = const_dijkstra_test.processed(t);
100    d  = const_dijkstra_test.distMap();
101    p  = const_dijkstra_test.predMap();
102    pp = const_dijkstra_test.path(t);
103    l  = const_dijkstra_test.currentDist(t);
104  }
105  {
106    DType
107      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
108      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
109      ::SetStandardProcessedMap
110      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
111      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
112      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
113      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
114      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
115                concepts::ReadWriteMap<Node,int> >
116      ::Create dijkstra_test(G,length);
117
118    LengthMap length_map;
119    concepts::ReadWriteMap<Node,Arc> pred_map;
120    concepts::ReadWriteMap<Node,VType> dist_map;
121    concepts::WriteMap<Node,bool> processed_map;
122    concepts::ReadWriteMap<Node,int> heap_cross_ref;
123    BinHeap<VType, concepts::ReadWriteMap<Node,int> > heap(heap_cross_ref);
124
125    dijkstra_test
126      .lengthMap(length_map)
127      .predMap(pred_map)
128      .distMap(dist_map)
129      .processedMap(processed_map)
130      .heap(heap, heap_cross_ref);
131
132    dijkstra_test.run(s);
133    dijkstra_test.run(s,t);
134
135    dijkstra_test.addSource(s);
136    dijkstra_test.addSource(s, 1);
137    n = dijkstra_test.processNextNode();
138    n = dijkstra_test.nextNode();
139    b = dijkstra_test.emptyQueue();
140    i = dijkstra_test.queueSize();
141
142    dijkstra_test.start();
143    dijkstra_test.start(t);
144    dijkstra_test.start(nm);
145
146    l  = dijkstra_test.dist(t);
147    e  = dijkstra_test.predArc(t);
148    s  = dijkstra_test.predNode(t);
149    b  = dijkstra_test.reached(t);
150    b  = dijkstra_test.processed(t);
151    pp = dijkstra_test.path(t);
152    l  = dijkstra_test.currentDist(t);
153  }
154
155}
156
157void checkDijkstraFunctionCompile()
158{
159  typedef int VType;
160  typedef concepts::Digraph Digraph;
161  typedef Digraph::Arc Arc;
162  typedef Digraph::Node Node;
163  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
164
165  Digraph g;
166  bool b;
167  ignore_unused_variable_warning(b);
168
169  dijkstra(g,LengthMap()).run(Node());
170  b=dijkstra(g,LengthMap()).run(Node(),Node());
171  dijkstra(g,LengthMap())
172    .predMap(concepts::ReadWriteMap<Node,Arc>())
173    .distMap(concepts::ReadWriteMap<Node,VType>())
174    .processedMap(concepts::WriteMap<Node,bool>())
175    .run(Node());
176  b=dijkstra(g,LengthMap())
177    .predMap(concepts::ReadWriteMap<Node,Arc>())
178    .distMap(concepts::ReadWriteMap<Node,VType>())
179    .processedMap(concepts::WriteMap<Node,bool>())
180    .path(concepts::Path<Digraph>())
181    .dist(VType())
182    .run(Node(),Node());
183}
184
185template <class Digraph>
186void checkDijkstra() {
187  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
188  typedef typename Digraph::template ArcMap<int> LengthMap;
189
190  Digraph G;
191  Node s, t;
192  LengthMap length(G);
193
194  std::istringstream input(test_lgf);
195  digraphReader(G, input).
196    arcMap("length", length).
197    node("source", s).
198    node("target", t).
199    run();
200
201  Dijkstra<Digraph, LengthMap>
202        dijkstra_test(G, length);
203  dijkstra_test.run(s);
204
205  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
206
207  Path<Digraph> p = dijkstra_test.path(t);
208  check(p.length()==3,"path() found a wrong path.");
209  check(checkPath(G, p),"path() found a wrong path.");
210  check(pathSource(G, p) == s,"path() found a wrong path.");
211  check(pathTarget(G, p) == t,"path() found a wrong path.");
212
213  for(ArcIt e(G); e!=INVALID; ++e) {
214    Node u=G.source(e);
215    Node v=G.target(e);
216    check( !dijkstra_test.reached(u) ||
217           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
218           "Wrong output. dist(target)-dist(source)-arc_length=" <<
219           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
220  }
221
222  for(NodeIt v(G); v!=INVALID; ++v) {
223    if (dijkstra_test.reached(v)) {
224      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
225      if (dijkstra_test.predArc(v)!=INVALID ) {
226        Arc e=dijkstra_test.predArc(v);
227        Node u=G.source(e);
228        check(u==dijkstra_test.predNode(v),"Wrong tree.");
229        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
230              "Wrong distance! Difference: " <<
231              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
232      }
233    }
234  }
235
236  {
237    NullMap<Node,Arc> myPredMap;
238    dijkstra(G,length).predMap(myPredMap).run(s);
239  }
240}
241
242int main() {
243  checkDijkstra<ListDigraph>();
244  checkDijkstra<SmartDigraph>();
245  return 0;
246}
Note: See TracBrowser for help on using the repository browser.