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 |
|
15 using namespace lemon; |
|
16 |
|
17 template <typename CoordMap> |
|
18 class PotentialMap { |
|
19 public: |
|
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 } |
|
30 private: |
|
31 const CoordMap& coord; |
|
32 xy<double> target; |
|
33 }; |
|
34 |
|
35 template <typename Graph, typename LengthMap, typename PotentialMap> |
|
36 class ReducedLengthMap { |
|
37 public: |
|
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 |
|
49 private: |
|
50 const Graph& graph; |
|
51 const LengthMap& length; |
|
52 const PotentialMap& pot; |
|
53 }; |
|
54 |
|
55 int 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 } |
|