COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/test/dijkstra_test.cc @ 783:81bf2d766164

Last change on this file since 783:81bf2d766164 was 780:e06d0d16595f, checked in by Alpar Juttner, 17 years ago
  • DFS class (bfs.h and bfs_test.cc) added
  • Bugfixes in Dijkstra and Bfs
File size: 2.2 KB
RevLine 
[578]1#include "test_tools.h"
[568]2#include <hugo/smart_graph.h>
3#include <hugo/dijkstra.h>
4
5using namespace hugo;
6
7const int PET_SIZE =5;
8
[570]9
10void check_Dijkstra_SmartGraph_BinHeap_Compile()
11{
12  typedef int VType;
13  typedef SmartGraph Graph;
14
15  typedef Graph::Edge Edge;
16  typedef Graph::Node Node;
17  typedef Graph::EdgeIt EdgeIt;
18  typedef Graph::NodeIt NodeIt;
19  typedef Graph::EdgeMap<VType> LengthMap;
20 
21  typedef Dijkstra<Graph, LengthMap> DType;
22 
23  Graph G;
24  Node n;
25  Edge e;
26  VType l;
27  bool b;
28  DType::DistMap d(G);
29  DType::PredMap p(G);
30  DType::PredNodeMap pn(G);
31  LengthMap cap(G);
32
33  DType dijkstra_test(G,cap);
34
35  dijkstra_test.run(n);
36
37  l  = dijkstra_test.dist(n);
38  e  = dijkstra_test.pred(n);
39  n  = dijkstra_test.predNode(n);
40  d  = dijkstra_test.distMap();
41  p  = dijkstra_test.predMap();
42  pn = dijkstra_test.predNodeMap();
43  b  = dijkstra_test.reached(n);
44
45}
46
[568]47int main()
48{
49   
50  typedef SmartGraph Graph;
51
52  typedef Graph::Edge Edge;
53  typedef Graph::Node Node;
54  typedef Graph::EdgeIt EdgeIt;
55  typedef Graph::NodeIt NodeIt;
56  typedef Graph::EdgeMap<int> LengthMap;
57
58  Graph G;
59  Node s, t;
60  LengthMap cap(G);
61  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
[578]62   
[568]63  for(int i=0;i<PET_SIZE;i++) {
64    cap[ps.outcir[i]]=4;
65    cap[ps.incir[i]]=1;
66    cap[ps.chords[i]]=10;
67  }
68  s=ps.outer[0];
69  t=ps.inner[1];
70 
71  Dijkstra<Graph, LengthMap>
72        dijkstra_test(G, cap);
73  dijkstra_test.run(s);
74 
75  check(dijkstra_test.dist(t)==13,"Dijkstra found a wrong path.");
[585]76
77
[776]78  for(EdgeIt e(G); e!=INVALID; ++e) {
[585]79    Node u=G.tail(e);
80    Node v=G.head(e);
81    check( !dijkstra_test.reached(u) ||
82           (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap[e]),
83           "dist(head)-dist(tail)- edge_length= "
84           << dijkstra_test.dist(v) - dijkstra_test.dist(u)
85           - cap[e]);
86  }
87
88  ///\bug This works only for integer lengths
[780]89  for(NodeIt v(G); v!=INVALID; ++v){
90    check(dijkstra_test.reached(v),"Each node should be reached.");
91    if ( dijkstra_test.pred(v)!=INVALID ) {
[585]92      Edge e=dijkstra_test.pred(v);
93      Node u=G.tail(e);
[780]94      check(u==dijkstra_test.predNode(v),"Wrong tree.");
[585]95      check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
[780]96            "Wrong distance! Difference: "
[585]97            << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u)
98                            - cap[e]));
99    }
[780]100  }
[568]101}
[780]102
Note: See TracBrowser for help on using the repository browser.