COIN-OR::LEMON - Graph Library

source: lemon/test/dijkstra_test.cc @ 463:88ed40ad0d4f

Last change on this file since 463:88ed40ad0d4f was 463:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 11 years ago

Happy New Year again

  • update the copyright headers + run the source unifier
File size: 5.1 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 *
[463]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;
[286]63  Node s, t;
64  Arc e;
[170]65  VType l;
66  bool b;
67  DType::DistMap d(G);
68  DType::PredMap p(G);
69  LengthMap length;
[286]70  Path<Digraph> pp;
[170]71
[286]72  {
73    DType dijkstra_test(G,length);
[170]74
[286]75    dijkstra_test.run(s);
76    dijkstra_test.run(s,t);
[170]77
[286]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
[412]92      ::SetOperationTraits<DijkstraDefaultOperationTraits<VType> >
[286]93      ::SetHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
94      ::SetStandardHeap<BinHeap<VType, concepts::ReadWriteMap<Node,int> > >
95      ::Create dijkstra_test(G,length);
[170]96
[286]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
[170]107}
108
[209]109void checkDijkstraFunctionCompile()
[170]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;
[209]116
[170]117  Digraph g;
[278]118  bool b;
119  dijkstra(g,LengthMap()).run(Node());
120  b=dijkstra(g,LengthMap()).run(Node(),Node());
[170]121  dijkstra(g,LengthMap())
[278]122    .predMap(concepts::ReadWriteMap<Node,Arc>())
123    .distMap(concepts::ReadWriteMap<Node,VType>())
124    .processedMap(concepts::WriteMap<Node,bool>())
[170]125    .run(Node());
[278]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());
[170]133}
134
135template <class Digraph>
[209]136void checkDijkstra() {
[170]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);
[209]143
[228]144  std::istringstream input(test_lgf);
[293]145  digraphReader(G, input).
[228]146    arcMap("length", length).
147    node("source", s).
148    node("target", t).
149    run();
[209]150
151  Dijkstra<Digraph, LengthMap>
152        dijkstra_test(G, length);
[170]153  dijkstra_test.run(s);
[209]154
[228]155  check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
[170]156
157  Path<Digraph> p = dijkstra_test.path(t);
[278]158  check(p.length()==3,"path() found a wrong path.");
[170]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.");
[209]162
[170]163  for(ArcIt e(G); e!=INVALID; ++e) {
164    Node u=G.source(e);
165    Node v=G.target(e);
[210]166    check( !dijkstra_test.reached(u) ||
167           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
[278]168           "Wrong output. dist(target)-dist(source)-arc_length=" <<
[210]169           dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
[170]170  }
171
[228]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      }
[170]183    }
184  }
[209]185
[170]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.