COIN-OR::LEMON - Graph Library

source: lemon-0.x/test/dijkstra_test.cc

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

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