COIN-OR::LEMON - Graph Library

source: lemon-main/test/dijkstra_test.cc @ 724:d8073df341f6

Last change on this file since 724:d8073df341f6 was 585:65fbcf2f978a, checked in by Peter Kovacs <kpeter@…>, 16 years ago

Improve test files for some algorithms (#263)

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 *
[440]5 * Copyright (C) 2003-2009
[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;
68  DType::DistMap d(G);
69  DType::PredMap p(G);
70  LengthMap length;
[286]71  Path<Digraph> pp;
[585]72  concepts::ReadMap<Node,bool> nm;
[170]73
[286]74  {
75    DType dijkstra_test(G,length);
[585]76    const DType& const_dijkstra_test = dijkstra_test;
[170]77
[286]78    dijkstra_test.run(s);
79    dijkstra_test.run(s,t);
[170]80
[585]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
[286]144    l  = dijkstra_test.dist(t);
145    e  = dijkstra_test.predArc(t);
146    s  = dijkstra_test.predNode(t);
147    b  = dijkstra_test.reached(t);
[585]148    b  = dijkstra_test.processed(t);
[286]149    pp = dijkstra_test.path(t);
[585]150    l  = dijkstra_test.currentDist(t);
[286]151  }
152
[170]153}
154
[209]155void checkDijkstraFunctionCompile()
[170]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;
[209]162
[170]163  Digraph g;
[278]164  bool b;
165  dijkstra(g,LengthMap()).run(Node());
166  b=dijkstra(g,LengthMap()).run(Node(),Node());
[170]167  dijkstra(g,LengthMap())
[278]168    .predMap(concepts::ReadWriteMap<Node,Arc>())
169    .distMap(concepts::ReadWriteMap<Node,VType>())
170    .processedMap(concepts::WriteMap<Node,bool>())
[170]171    .run(Node());
[278]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());
[170]179}
180
181template <class Digraph>
[209]182void checkDijkstra() {
[170]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);
[209]189
[228]190  std::istringstream input(test_lgf);
[293]191  digraphReader(G, input).
[228]192    arcMap("length", length).
193    node("source", s).
194    node("target", t).
195    run();
[209]196
197  Dijkstra<Digraph, LengthMap>
198        dijkstra_test(G, length);
[170]199  dijkstra_test.run(s);
[209]200
[228]201  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
[170]202
203  Path<Digraph> p = dijkstra_test.path(t);
[278]204  check(p.length()==3,"path() found a wrong path.");
[170]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.");
[209]208
[170]209  for(ArcIt e(G); e!=INVALID; ++e) {
210    Node u=G.source(e);
211    Node v=G.target(e);
[210]212    check( !dijkstra_test.reached(u) ||
213           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
[278]214           "Wrong output. dist(target)-dist(source)-arc_length=" <<
[210]215           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
[170]216  }
217
[228]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      }
[170]229    }
230  }
[209]231
[170]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.