Specialization for string literals.
4 #include <lemon/smart_graph.h>
5 #include <lemon/dijkstra.h>
6 #include <lemon/maps.h>
8 #include <lemon/graph_reader.h>
10 #include <lemon/time_measure.h>
15 using namespace lemon;
17 template <typename CoordMap>
21 typedef typename CoordMap::Key Key;
23 PotentialMap(const CoordMap& _coord, const xy<double>& _target)
24 : coord(_coord), target(_target) {}
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));
31 const CoordMap& coord;
35 template <typename Graph, typename LengthMap, typename PotentialMap>
36 class ReducedLengthMap {
39 typedef typename LengthMap::Key Key;
41 ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
42 const PotentialMap& _pot)
43 : graph(_graph), length(_length), pot(_pot) {}
45 Value operator[](const Key& edge) const {
46 return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
51 const LengthMap& length;
52 const PotentialMap& pot;
56 typedef SmartGraph Graph;
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;
67 std::ifstream is("route.lgf");
68 GraphReader<Graph> reader(is, graph);
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);
76 LengthMap length(graph);
77 reader.readEdgeMap("length", length);
80 reader.readNode("source", source);
81 reader.readNode("target", target);
87 Dijkstra<Graph, LengthMap> dijkstra(graph, length);
89 dijkstra.addSource(source);
90 dijkstra.start(target);
92 std::cout << dijkstra.dist(target) << std::endl;
93 std::cout << timer << std::endl;
97 typedef PotentialMap<CoordMap> Potential;
98 Potential potential(coord, coord[target]);
100 typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
101 ReducedLength reduced(graph, length, potential);
103 Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
106 dijkstra.addSource(source);
107 dijkstra.start(target);
109 std::cout << dijkstra.dist(target) + potential[source] << std::endl;
110 std::cout << timer << std::endl;