COIN-OR::LEMON - Graph Library

source: lemon-1.2/test/dijkstra_test.cc

Last change on this file was 983:8b2d4e5d96e4, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge #294 to branches >=1.2

File size: 6.7 KB
RevLine 
[209]1/* -*- mode: C++; indent-tabs-mode: nil; -*-
[170]2 *
[209]3 * This file is a part of LEMON, a generic C++ optimization library.
[170]4 *
[877]5 * Copyright (C) 2003-2010
[170]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>
[228]22#include <lemon/lgf_reader.h>
[170]23#include <lemon/dijkstra.h>
24#include <lemon/path.h>
[286]25#include <lemon/bin_heap.h>
[170]26
[171]27#include "graph_test.h"
[170]28#include "test_tools.h"
29
30using namespace lemon;
31
[228]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
[209]53void checkDijkstraCompile()
[170]54{
55  typedef int VType;
56  typedef concepts::Digraph Digraph;
57  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
58  typedef Dijkstra<Digraph, LengthMap> DType;
[286]59  typedef Digraph::Node Node;
60  typedef Digraph::Arc Arc;
[209]61
[170]62  Digraph G;
[585]63  Node s, t, n;
[286]64  Arc e;
[170]65  VType l;
[585]66  int i;
[170]67  bool b;
[982]68  ::lemon::ignore_unused_variable_warning(l,i,b);
[969]69
[170]70  DType::DistMap d(G);
71  DType::PredMap p(G);
72  LengthMap length;
[286]73  Path<Digraph> pp;
[585]74  concepts::ReadMap<Node,bool> nm;
[170]75
[286]76  {
77    DType dijkstra_test(G,length);
[585]78    const DType& const_dijkstra_test = dijkstra_test;
[170]79
[286]80    dijkstra_test.run(s);
81    dijkstra_test.run(s,t);
[170]82
[585]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();
[877]90
[585]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> > >
[877]114      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> >,
[585]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);
[877]124
[585]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();
[877]141
[585]142    dijkstra_test.start();
143    dijkstra_test.start(t);
144    dijkstra_test.start(nm);
145
[286]146    l  = dijkstra_test.dist(t);
147    e  = dijkstra_test.predArc(t);
148    s  = dijkstra_test.predNode(t);
149    b  = dijkstra_test.reached(t);
[585]150    b  = dijkstra_test.processed(t);
[286]151    pp = dijkstra_test.path(t);
[585]152    l  = dijkstra_test.currentDist(t);
[286]153  }
154
[170]155}
156
[209]157void checkDijkstraFunctionCompile()
[170]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;
[209]164
[170]165  Digraph g;
[278]166  bool b;
[982]167  ::lemon::ignore_unused_variable_warning(b);
[969]168
[278]169  dijkstra(g,LengthMap()).run(Node());
170  b=dijkstra(g,LengthMap()).run(Node(),Node());
[170]171  dijkstra(g,LengthMap())
[278]172    .predMap(concepts::ReadWriteMap<Node,Arc>())
173    .distMap(concepts::ReadWriteMap<Node,VType>())
174    .processedMap(concepts::WriteMap<Node,bool>())
[170]175    .run(Node());
[278]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());
[170]183}
184
185template <class Digraph>
[209]186void checkDijkstra() {
[170]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);
[209]193
[228]194  std::istringstream input(test_lgf);
[293]195  digraphReader(G, input).
[228]196    arcMap("length", length).
197    node("source", s).
198    node("target", t).
199    run();
[209]200
201  Dijkstra<Digraph, LengthMap>
202        dijkstra_test(G, length);
[170]203  dijkstra_test.run(s);
[209]204
[228]205  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
[170]206
207  Path<Digraph> p = dijkstra_test.path(t);
[278]208  check(p.length()==3,"path() found a wrong path.");
[170]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.");
[209]212
[170]213  for(ArcIt e(G); e!=INVALID; ++e) {
214    Node u=G.source(e);
215    Node v=G.target(e);
[210]216    check( !dijkstra_test.reached(u) ||
217           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
[278]218           "Wrong output. dist(target)-dist(source)-arc_length=" <<
[210]219           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
[170]220  }
221
[228]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      }
[170]233    }
234  }
[209]235
[170]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.