COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/demo/min_route.cc @ 1342:e335eebdae5b

Last change on this file since 1342:e335eebdae5b was 1342:e335eebdae5b, checked in by Balazs Dezso, 15 years ago

Demo program
Dijkstra with reduced lengths

File size: 2.6 KB
Line 
1#include <lemon/smart_graph.h>
2#include <lemon/dijkstra.h>
3#include <lemon/maps.h>
4#include <lemon/xy.h>
5#include <lemon/graph_reader.h>
6
7#include <lemon/time_measure.h>
8
9#include <cmath>
10
11using namespace lemon;
12
13template <typename CoordMap>
14class PotentialMap {
15public:
16  typedef double Value;
17  typedef typename CoordMap::Key Key;
18
19  PotentialMap(const CoordMap& _coord, const xy<double>& _target)
20    : coord(_coord), target(_target) {}
21
22  double operator[](const Key& node) const {
23    return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
24                     (coord[node].y - target.y) * (coord[node].y - target.y));
25  }
26private:
27  xy<double> target;
28  const CoordMap& coord;
29};
30
31template <typename Graph, typename LengthMap, typename PotentialMap>
32class ReducedLengthMap {
33public:
34  typedef double Value;
35  typedef typename LengthMap::Key Key;
36
37  ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
38                   const PotentialMap& _pot)
39    : graph(_graph), length(_length), pot(_pot) {}
40
41  Value operator[](const Key& edge) const {
42    return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
43  }
44
45private:
46  const Graph& graph;
47  const LengthMap& length;
48  const PotentialMap& pot;
49};
50
51int main() {
52  typedef SmartGraph Graph;
53
54  typedef Graph::Edge Edge;
55  typedef Graph::Node Node;
56  typedef Graph::EdgeIt EdgeIt;
57  typedef Graph::NodeIt NodeIt;
58  typedef Graph::EdgeMap<double> LengthMap;
59  typedef Graph::NodeMap<xy<double> > CoordMap;
60
61  SmartGraph graph;
62
63  GraphReader<Graph> reader(std::cin, graph);
64 
65  CoordMap coord(graph);
66  XMap<CoordMap> xcoord = xMap(coord);
67  reader.addNodeMap("coordinates_x", xcoord);
68  YMap<CoordMap> ycoord = yMap(coord);
69  reader.addNodeMap("coordinates_y", ycoord);
70
71  LengthMap length(graph);
72  reader.addEdgeMap("length", length);
73
74  Node source, target;
75  reader.addNode("source", source);
76  reader.addNode("target", target);
77
78  reader.run();
79
80  {
81    Timer timer;
82    Dijkstra<Graph, LengthMap> dijkstra(graph, length);
83    dijkstra.init();
84    dijkstra.addSource(source);
85    dijkstra.start(target);
86
87    std::cout << dijkstra.dist(target) << std::endl;
88    std::cout << timer << std::endl;
89  }
90
91  {
92    Timer timer;
93    typedef PotentialMap<CoordMap> Potential;
94    Potential potential(coord, coord[target]);
95
96    typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
97    ReducedLength reduced(graph, length, potential);
98
99    Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
100
101    dijkstra.init();
102    dijkstra.addSource(source);
103    dijkstra.start(target);
104 
105    std::cout << dijkstra.dist(target) + potential[source] << std::endl;
106    std::cout << timer << std::endl;
107  }
108
109  return 0;
110}
Note: See TracBrowser for help on using the repository browser.