Permissions and svn:ignore cleanup.
2 * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
20 #include <lemon/smart_graph.h>
21 #include <lemon/dijkstra.h>
22 #include <lemon/maps.h>
24 #include <lemon/graph_reader.h>
26 #include <lemon/time_measure.h>
31 using namespace lemon;
33 template <typename CoordMap>
37 typedef typename CoordMap::Key Key;
39 PotentialMap(const CoordMap& _coord, const xy<double>& _target)
40 : coord(_coord), target(_target) {}
42 double operator[](const Key& node) const {
43 return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
44 (coord[node].y - target.y) * (coord[node].y - target.y));
47 const CoordMap& coord;
51 template <typename Graph, typename LengthMap, typename PotentialMap>
52 class ReducedLengthMap {
55 typedef typename LengthMap::Key Key;
57 ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
58 const PotentialMap& _pot)
59 : graph(_graph), length(_length), pot(_pot) {}
61 Value operator[](const Key& edge) const {
62 return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
67 const LengthMap& length;
68 const PotentialMap& pot;
72 typedef SmartGraph Graph;
74 typedef Graph::Edge Edge;
75 typedef Graph::Node Node;
76 typedef Graph::EdgeIt EdgeIt;
77 typedef Graph::NodeIt NodeIt;
78 typedef Graph::EdgeMap<double> LengthMap;
79 typedef Graph::NodeMap<xy<double> > CoordMap;
83 std::ifstream is("route.lgf");
84 GraphReader<Graph> reader(is, graph);
86 CoordMap coord(graph);
87 XMap<CoordMap> xcoord = xMap(coord);
88 reader.readNodeMap("coordinates_x", xcoord);
89 YMap<CoordMap> ycoord = yMap(coord);
90 reader.readNodeMap("coordinates_y", ycoord);
92 LengthMap length(graph);
93 reader.readEdgeMap("length", length);
96 reader.readNode("source", source);
97 reader.readNode("target", target);
103 Dijkstra<Graph, LengthMap> dijkstra(graph, length);
105 dijkstra.addSource(source);
106 dijkstra.start(target);
108 std::cout << dijkstra.dist(target) << std::endl;
109 std::cout << timer << std::endl;
113 typedef PotentialMap<CoordMap> Potential;
114 Potential potential(coord, coord[target]);
116 typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
117 ReducedLength reduced(graph, length, potential);
119 Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
122 dijkstra.addSource(source);
123 dijkstra.start(target);
125 std::cout << dijkstra.dist(target) + potential[source] << std::endl;
126 std::cout << timer << std::endl;