Several changes. \n If new map is added to mapstorage it emits signal with the name of the new map. This was important, because from now on not only tha mapwin should be updated. \n Furthermore algobox gets a pointer to mapstorage instead of only the mapnames from it. This is important because without it it would be complicated to pass all of the required maps to algobox.
2 * demo/min_route.cc - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 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>
32 /// \brief Minimal route on a plan graph with eucledian distances.
34 /// Minimal route on a plan graph with eucledian distances.
36 /// \include min_route.cc
39 using namespace lemon;
41 template <typename CoordMap>
45 typedef typename CoordMap::Key Key;
47 PotentialMap(const CoordMap& _coord, const xy<double>& _target)
48 : coord(_coord), target(_target) {}
50 double operator[](const Key& node) const {
51 return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
52 (coord[node].y - target.y) * (coord[node].y - target.y));
55 const CoordMap& coord;
59 template <typename Graph, typename LengthMap, typename PotentialMap>
60 class ReducedLengthMap {
63 typedef typename LengthMap::Key Key;
65 ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
66 const PotentialMap& _pot)
67 : graph(_graph), length(_length), pot(_pot) {}
69 Value operator[](const Key& edge) const {
70 return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
75 const LengthMap& length;
76 const PotentialMap& pot;
80 typedef SmartGraph Graph;
82 typedef Graph::Edge Edge;
83 typedef Graph::Node Node;
84 typedef Graph::EdgeIt EdgeIt;
85 typedef Graph::NodeIt NodeIt;
86 typedef Graph::EdgeMap<double> LengthMap;
87 typedef Graph::NodeMap<xy<double> > CoordMap;
91 std::ifstream is("route.lgf");
92 GraphReader<Graph> reader(is, graph);
94 CoordMap coord(graph);
95 XMap<CoordMap> xcoord = xMap(coord);
96 reader.readNodeMap("coordinates_x", xcoord);
97 YMap<CoordMap> ycoord = yMap(coord);
98 reader.readNodeMap("coordinates_y", ycoord);
100 LengthMap length(graph);
101 reader.readEdgeMap("length", length);
104 reader.readNode("source", source);
105 reader.readNode("target", target);
111 Dijkstra<Graph, LengthMap> dijkstra(graph, length);
113 dijkstra.addSource(source);
114 dijkstra.start(target);
116 std::cout << dijkstra.dist(target) << std::endl;
117 std::cout << timer << std::endl;
121 typedef PotentialMap<CoordMap> Potential;
122 Potential potential(coord, coord[target]);
124 typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
125 ReducedLength reduced(graph, length, potential);
127 Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
130 dijkstra.addSource(source);
131 dijkstra.start(target);
133 std::cout << dijkstra.dist(target) + potential[source] << std::endl;
134 std::cout << timer << std::endl;