COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/demo/min_route.cc @ 1416:1b481ced25e7

Last change on this file since 1416:1b481ced25e7 was 1410:dcfad73b3965, checked in by Balazs Dezso, 20 years ago

Bug fixes.

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