COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/dijkstra_test.cc @ 2247:269a0dcee70b

Last change on this file since 2247:269a0dcee70b was 2247:269a0dcee70b, checked in by Balazs Dezso, 13 years ago

Update the Path concept
Concept check for paths

DirPath? renamed to Path
The interface updated to the new lemon interface
Make difference between the empty path and the path from one node
Builder interface have not been changed

I wanted but there was not accordance about it

UPath is removed
It was a buggy implementation, it could not iterate on the
nodes in the right order
Right way to use undirected paths => path of edges in undirected graphs

The tests have been modified to the current implementation

File size: 3.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 "test_tools.h"
20#include <lemon/smart_graph.h>
21#include <lemon/dijkstra.h>
22#include <lemon/path.h>
23#include <lemon/maps.h>
24#include <lemon/concept/graph.h>
25#include <lemon/concept/maps.h>
26using namespace lemon;
27
28const int PET_SIZE =5;
29
30
31void check_Dijkstra_BinHeap_Compile()
32{
33  typedef int VType;
34  typedef concept::Graph Graph;
35
36  typedef Graph::Edge Edge;
37  typedef Graph::Node Node;
38  typedef Graph::EdgeIt EdgeIt;
39  typedef Graph::NodeIt NodeIt;
40  typedef concept::ReadMap<Edge,VType> LengthMap;
41 
42  typedef Dijkstra<Graph, LengthMap> DType;
43 
44  Graph G;
45  Node n;
46  Edge e;
47  VType l;
48  bool b;
49  DType::DistMap d(G);
50  DType::PredMap p(G);
51  //  DType::PredNodeMap pn(G);
52  LengthMap cap;
53
54  DType dijkstra_test(G,cap);
55
56  dijkstra_test.run(n);
57
58  l  = dijkstra_test.dist(n);
59  e  = dijkstra_test.predEdge(n);
60  n  = dijkstra_test.predNode(n);
61  d  = dijkstra_test.distMap();
62  p  = dijkstra_test.predMap();
63  //  pn = dijkstra_test.predNodeMap();
64  b  = dijkstra_test.reached(n);
65
66  Path<Graph> pp(G);
67  dijkstra_test.getPath(pp,n);
68}
69
70void check_Dijkstra_Function_Compile()
71{
72  typedef int VType;
73  typedef concept::Graph Graph;
74
75  typedef Graph::Edge Edge;
76  typedef Graph::Node Node;
77  typedef Graph::EdgeIt EdgeIt;
78  typedef Graph::NodeIt NodeIt;
79  typedef concept::ReadMap<Edge,VType> LengthMap;
80   
81  Graph g;
82  dijkstra(g,LengthMap(),Node()).run();
83  dijkstra(g,LengthMap()).source(Node()).run();
84  dijkstra(g,LengthMap())
85    .predMap(concept::WriteMap<Node,Edge>())
86    .distMap(concept::WriteMap<Node,VType>())
87    .run(Node());
88 
89}
90
91
92int main()
93{
94   
95  typedef SmartGraph Graph;
96
97  typedef Graph::Edge Edge;
98  typedef Graph::Node Node;
99  typedef Graph::EdgeIt EdgeIt;
100  typedef Graph::NodeIt NodeIt;
101  typedef Graph::EdgeMap<int> LengthMap;
102
103  Graph G;
104  Node s, t;
105  LengthMap cap(G);
106  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
107   
108  for(int i=0;i<PET_SIZE;i++) {
109    cap[ps.outcir[i]]=4;
110    cap[ps.incir[i]]=1;
111    cap[ps.chords[i]]=10;
112  }
113  s=ps.outer[0];
114  t=ps.inner[1];
115 
116  Dijkstra<Graph, LengthMap>
117        dijkstra_test(G, cap);
118  dijkstra_test.run(s);
119 
120  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
121
122
123  Path<Graph> p(G);
124  check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
125  check(p.length()==4,"getPath() found a wrong path.");
126 
127
128  for(EdgeIt e(G); e!=INVALID; ++e) {
129    Node u=G.source(e);
130    Node v=G.target(e);
131    check( !dijkstra_test.reached(u) ||
132           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
133           "dist(target)-dist(source)- edge_length= "
134           << dijkstra_test.dist(v) - dijkstra_test.dist(u)
135           - cap[e]);
136  }
137
138  ///\bug This works only for integer lengths
139  for(NodeIt v(G); v!=INVALID; ++v){
140    check(dijkstra_test.reached(v),"Each node should be reached.");
141    if ( dijkstra_test.predEdge(v)!=INVALID ) {
142      Edge e=dijkstra_test.predEdge(v);
143      Node u=G.source(e);
144      check(u==dijkstra_test.predNode(v),"Wrong tree.");
145      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
146            "Wrong distance! Difference: "
147            << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
148                            - cap[e]));
149    }
150  }
151
152 
153  {
154    NullMap<Node,Edge> myPredMap;
155    dijkstra(G,cap).predMap(myPredMap).run(s);
156  }
157  return 0;
158}
Note: See TracBrowser for help on using the repository browser.