COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_test.cc @ 844:9bf990cb066d

Last change on this file since 844:9bf990cb066d was 793:9cd0aeea47b0, checked in by Alpar Juttner, 20 years ago
  • BFD/DFS/Dijkstra compile test is done with skeleton::GraphSkeleton? graph and skeleton::ReadMap?.
  • 'skeleton::' is explicitely written instead of 'using namespace ...' in graph_test.cc
  • Output messages of type "makeRep(3)..." in unionfind_test.cc have been changed in order not to confuse compiler output parsers.
File size: 2.3 KB
Line 
1#include "test_tools.h"
2#include <hugo/smart_graph.h>
3#include <hugo/dijkstra.h>
4#include<hugo/skeletons/graph.h>
5#include<hugo/skeletons/maps.h>
6using namespace hugo;
7
8const int PET_SIZE =5;
9
10
11void check_Dijkstra_BinHeap_Compile()
12{
13  typedef int VType;
14  typedef skeleton::StaticGraphSkeleton Graph;
15
16  typedef Graph::Edge Edge;
17  typedef Graph::Node Node;
18  typedef Graph::EdgeIt EdgeIt;
19  typedef Graph::NodeIt NodeIt;
20  typedef skeleton::ReadMap<Edge,VType> LengthMap;
21 
22  typedef Dijkstra<Graph, LengthMap> DType;
23 
24  Graph G;
25  Node n;
26  Edge e;
27  VType l;
28  bool b;
29  DType::DistMap d(G);
30  DType::PredMap p(G);
31  DType::PredNodeMap pn(G);
32  LengthMap cap;
33
34  DType dijkstra_test(G,cap);
35
36  dijkstra_test.run(n);
37
38  l  = dijkstra_test.dist(n);
39  e  = dijkstra_test.pred(n);
40  n  = dijkstra_test.predNode(n);
41  d  = dijkstra_test.distMap();
42  p  = dijkstra_test.predMap();
43  pn = dijkstra_test.predNodeMap();
44  b  = dijkstra_test.reached(n);
45
46}
47
48int main()
49{
50   
51  typedef SmartGraph Graph;
52
53  typedef Graph::Edge Edge;
54  typedef Graph::Node Node;
55  typedef Graph::EdgeIt EdgeIt;
56  typedef Graph::NodeIt NodeIt;
57  typedef Graph::EdgeMap<int> LengthMap;
58
59  Graph G;
60  Node s, t;
61  LengthMap cap(G);
62  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
63   
64  for(int i=0;i<PET_SIZE;i++) {
65    cap[ps.outcir[i]]=4;
66    cap[ps.incir[i]]=1;
67    cap[ps.chords[i]]=10;
68  }
69  s=ps.outer[0];
70  t=ps.inner[1];
71 
72  Dijkstra<Graph, LengthMap>
73        dijkstra_test(G, cap);
74  dijkstra_test.run(s);
75 
76  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
77
78
79  for(EdgeIt e(G); e!=INVALID; ++e) {
80    Node u=G.tail(e);
81    Node v=G.head(e);
82    check( !dijkstra_test.reached(u) ||
83           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
84           "dist(head)-dist(tail)- edge_length= "
85           << dijkstra_test.dist(v) - dijkstra_test.dist(u)
86           - cap[e]);
87  }
88
89  ///\bug This works only for integer lengths
90  for(NodeIt v(G); v!=INVALID; ++v){
91    check(dijkstra_test.reached(v),"Each node should be reached.");
92    if ( dijkstra_test.pred(v)!=INVALID ) {
93      Edge e=dijkstra_test.pred(v);
94      Node u=G.tail(e);
95      check(u==dijkstra_test.predNode(v),"Wrong tree.");
96      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
97            "Wrong distance! Difference: "
98            << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
99                            - cap[e]));
100    }
101  }
102}
103
Note: See TracBrowser for help on using the repository browser.