COIN-OR::LEMON - Graph Library

source: lemon-1.1/test/dijkstra_test.cc @ 481:861a9d5ff283

Last change on this file since 481:861a9d5ff283 was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 16 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 5.1 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;
64  Arc e;
65  VType l;
66  bool b;
67  DType::DistMap d(G);
68  DType::PredMap p(G);
69  LengthMap length;
70  Path<Digraph> pp;
71
72  {
73    DType dijkstra_test(G,length);
74
75    dijkstra_test.run(s);
76    dijkstra_test.run(s,t);
77
78    l  = dijkstra_test.dist(t);
79    e  = dijkstra_test.predArc(t);
80    s  = dijkstra_test.predNode(t);
81    b  = dijkstra_test.reached(t);
82    d  = dijkstra_test.distMap();
83    p  = dijkstra_test.predMap();
84    pp = dijkstra_test.path(t);
85  }
86  {
87    DType
88      ::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
89      ::SetDistMap<concepts::ReadWriteMap<Node,VType> >
90      ::SetProcessedMap<concepts::WriteMap<Node,bool> >
91      ::SetStandardProcessedMap
92      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
93      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
94      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
95      ::Create dijkstra_test(G,length);
96
97    dijkstra_test.run(s);
98    dijkstra_test.run(s,t);
99
100    l  = dijkstra_test.dist(t);
101    e  = dijkstra_test.predArc(t);
102    s  = dijkstra_test.predNode(t);
103    b  = dijkstra_test.reached(t);
104    pp = dijkstra_test.path(t);
105  }
106
107}
108
109void checkDijkstraFunctionCompile()
110{
111  typedef int VType;
112  typedef concepts::Digraph Digraph;
113  typedef Digraph::Arc Arc;
114  typedef Digraph::Node Node;
115  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
116
117  Digraph g;
118  bool b;
119  dijkstra(g,LengthMap()).run(Node());
120  b=dijkstra(g,LengthMap()).run(Node(),Node());
121  dijkstra(g,LengthMap())
122    .predMap(concepts::ReadWriteMap<Node,Arc>())
123    .distMap(concepts::ReadWriteMap<Node,VType>())
124    .processedMap(concepts::WriteMap<Node,bool>())
125    .run(Node());
126  b=dijkstra(g,LengthMap())
127    .predMap(concepts::ReadWriteMap<Node,Arc>())
128    .distMap(concepts::ReadWriteMap<Node,VType>())
129    .processedMap(concepts::WriteMap<Node,bool>())
130    .path(concepts::Path<Digraph>())
131    .dist(VType())
132    .run(Node(),Node());
133}
134
135template <class Digraph>
136void checkDijkstra() {
137  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
138  typedef typename Digraph::template ArcMap<int> LengthMap;
139
140  Digraph G;
141  Node s, t;
142  LengthMap length(G);
143
144  std::istringstream input(test_lgf);
145  digraphReader(G, input).
146    arcMap("length", length).
147    node("source", s).
148    node("target", t).
149    run();
150
151  Dijkstra<Digraph, LengthMap>
152        dijkstra_test(G, length);
153  dijkstra_test.run(s);
154
155  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
156
157  Path<Digraph> p = dijkstra_test.path(t);
158  check(p.length()==3,"path() found a wrong path.");
159  check(checkPath(G, p),"path() found a wrong path.");
160  check(pathSource(G, p) == s,"path() found a wrong path.");
161  check(pathTarget(G, p) == t,"path() found a wrong path.");
162
163  for(ArcIt e(G); e!=INVALID; ++e) {
164    Node u=G.source(e);
165    Node v=G.target(e);
166    check( !dijkstra_test.reached(u) ||
167           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
168           "Wrong output. dist(target)-dist(source)-arc_length=" <<
169           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
170  }
171
172  for(NodeIt v(G); v!=INVALID; ++v) {
173    if (dijkstra_test.reached(v)) {
174      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
175      if (dijkstra_test.predArc(v)!=INVALID ) {
176        Arc e=dijkstra_test.predArc(v);
177        Node u=G.source(e);
178        check(u==dijkstra_test.predNode(v),"Wrong tree.");
179        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
180              "Wrong distance! Difference: " <<
181              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
182      }
183    }
184  }
185
186  {
187    NullMap<Node,Arc> myPredMap;
188    dijkstra(G,length).predMap(myPredMap).run(s);
189  }
190}
191
192int main() {
193  checkDijkstra<ListDigraph>();
194  checkDijkstra<SmartDigraph>();
195  return 0;
196}
Note: See TracBrowser for help on using the repository browser.