COIN-OR::LEMON - Graph Library

source: lemon-1.0/test/dijkstra_test.cc @ 278:931190050520

Last change on this file since 278:931190050520 was 278:931190050520, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Improve the function-type interface of bfs, dfs, and dijkstra (ticket #96)

File size: 4.3 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-2008
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
26#include "graph_test.h"
27#include "test_tools.h"
28
29using namespace lemon;
30
31char test_lgf[] =
32  "@nodes\n"
33  "label\n"
34  "0\n"
35  "1\n"
36  "2\n"
37  "3\n"
38  "4\n"
39  "@arcs\n"
40  "     label length\n"
41  "0 1  0     1\n"
42  "1 2  1     1\n"
43  "2 3  2     1\n"
44  "0 3  4     5\n"
45  "0 3  5     10\n"
46  "0 3  6     7\n"
47  "4 2  7     1\n"
48  "@attributes\n"
49  "source 0\n"
50  "target 3\n";
51
52void checkDijkstraCompile()
53{
54  typedef int VType;
55  typedef concepts::Digraph Digraph;
56  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
57  typedef Dijkstra<Digraph, LengthMap> DType;
58
59  Digraph G;
60  Digraph::Node n;
61  Digraph::Arc e;
62  VType l;
63  bool b;
64  DType::DistMap d(G);
65  DType::PredMap p(G);
66  LengthMap length;
67
68  DType dijkstra_test(G,length);
69
70  dijkstra_test.run(n);
71
72  l  = dijkstra_test.dist(n);
73  e  = dijkstra_test.predArc(n);
74  n  = dijkstra_test.predNode(n);
75  d  = dijkstra_test.distMap();
76  p  = dijkstra_test.predMap();
77  b  = dijkstra_test.reached(n);
78
79  Path<Digraph> pp = dijkstra_test.path(n);
80}
81
82void checkDijkstraFunctionCompile()
83{
84  typedef int VType;
85  typedef concepts::Digraph Digraph;
86  typedef Digraph::Arc Arc;
87  typedef Digraph::Node Node;
88  typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
89
90  Digraph g;
91  bool b;
92  dijkstra(g,LengthMap()).run(Node());
93  b=dijkstra(g,LengthMap()).run(Node(),Node());
94  dijkstra(g,LengthMap())
95    .predMap(concepts::ReadWriteMap<Node,Arc>())
96    .distMap(concepts::ReadWriteMap<Node,VType>())
97    .processedMap(concepts::WriteMap<Node,bool>())
98    .run(Node());
99  b=dijkstra(g,LengthMap())
100    .predMap(concepts::ReadWriteMap<Node,Arc>())
101    .distMap(concepts::ReadWriteMap<Node,VType>())
102    .processedMap(concepts::WriteMap<Node,bool>())
103    .path(concepts::Path<Digraph>())
104    .dist(VType())
105    .run(Node(),Node());
106}
107
108template <class Digraph>
109void checkDijkstra() {
110  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
111  typedef typename Digraph::template ArcMap<int> LengthMap;
112
113  Digraph G;
114  Node s, t;
115  LengthMap length(G);
116
117  std::istringstream input(test_lgf);
118  digraphReader(input, G).
119    arcMap("length", length).
120    node("source", s).
121    node("target", t).
122    run();
123
124  Dijkstra<Digraph, LengthMap>
125        dijkstra_test(G, length);
126  dijkstra_test.run(s);
127
128  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
129
130  Path<Digraph> p = dijkstra_test.path(t);
131  check(p.length()==3,"path() found a wrong path.");
132  check(checkPath(G, p),"path() found a wrong path.");
133  check(pathSource(G, p) == s,"path() found a wrong path.");
134  check(pathTarget(G, p) == t,"path() found a wrong path.");
135
136  for(ArcIt e(G); e!=INVALID; ++e) {
137    Node u=G.source(e);
138    Node v=G.target(e);
139    check( !dijkstra_test.reached(u) ||
140           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
141           "Wrong output. dist(target)-dist(source)-arc_length=" <<
142           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
143  }
144
145  for(NodeIt v(G); v!=INVALID; ++v) {
146    if (dijkstra_test.reached(v)) {
147      check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree.");
148      if (dijkstra_test.predArc(v)!=INVALID ) {
149        Arc e=dijkstra_test.predArc(v);
150        Node u=G.source(e);
151        check(u==dijkstra_test.predNode(v),"Wrong tree.");
152        check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e],
153              "Wrong distance! Difference: " <<
154              std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e]));
155      }
156    }
157  }
158
159  {
160    NullMap<Node,Arc> myPredMap;
161    dijkstra(G,length).predMap(myPredMap).run(s);
162  }
163}
164
165int main() {
166  checkDijkstra<ListDigraph>();
167  checkDijkstra<SmartDigraph>();
168  return 0;
169}
Note: See TracBrowser for help on using the repository browser.