COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/dijkstra_test.cc @ 2297:49c8d69c0640

Last change on this file since 2297:49c8d69c0640 was 2297:49c8d69c0640, checked in by Alpar Juttner, 14 years ago

Test the automatic compilation checker 2/3: wrong commit

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