COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/dijkstra_test.cc @ 2296:02088c3c0d14

Last change on this file since 2296:02088c3c0d14 was 2296:02088c3c0d14, checked in by Alpar Juttner, 14 years ago

Test the automatic compilation checker 1/3

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