Include functional because of std::less.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
22 #include <lemon/smart_graph.h>
23 #include <lemon/dijkstra.h>
24 #include <lemon/maps.h>
25 #include <lemon/dim2.h>
26 #include <lemon/graph_reader.h>
28 #include <lemon/time_measure.h>
34 /// \brief Minimal route on a planar graph with eucledian distances.
36 /// Minimal route on a planar graph with eucledian distances.
38 /// \include min_route.cc
41 using namespace lemon;
43 template <typename CoordMap>
47 typedef typename CoordMap::Key Key;
49 PotentialMap(const CoordMap& _coord, const dim2::Point<double>& _target)
50 : coord(_coord), target(_target) {}
52 double operator[](const Key& node) const {
53 return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) +
54 (coord[node].y - target.y) * (coord[node].y - target.y));
57 const CoordMap& coord;
58 dim2::Point<double> target;
61 template <typename Graph, typename LengthMap, typename PotentialMap>
62 class ReducedLengthMap {
65 typedef typename LengthMap::Key Key;
67 ReducedLengthMap(const Graph& _graph, const LengthMap& _length,
68 const PotentialMap& _pot)
69 : graph(_graph), length(_length), pot(_pot) {}
71 Value operator[](const Key& edge) const {
72 return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
77 const LengthMap& length;
78 const PotentialMap& pot;
82 typedef SmartGraph Graph;
84 typedef Graph::Edge Edge;
85 typedef Graph::Node Node;
86 typedef Graph::EdgeIt EdgeIt;
87 typedef Graph::NodeIt NodeIt;
88 typedef Graph::EdgeMap<double> LengthMap;
89 typedef Graph::NodeMap<dim2::Point<double> > CoordMap;
93 std::ifstream is("route.lgf");
94 GraphReader<Graph> reader(is, graph);
96 CoordMap coord(graph);
97 dim2::XMap<CoordMap> xcoord = xMap(coord);
98 reader.readNodeMap("coordinates_x", xcoord);
99 dim2::YMap<CoordMap> ycoord = yMap(coord);
100 reader.readNodeMap("coordinates_y", ycoord);
102 LengthMap length(graph);
103 reader.readEdgeMap("length", length);
106 reader.readNode("source", source);
107 reader.readNode("target", target);
113 Dijkstra<Graph, LengthMap> dijkstra(graph, length);
115 dijkstra.addSource(source);
116 dijkstra.start(target);
118 std::cout << dijkstra.dist(target) << std::endl;
119 std::cout << timer << std::endl;
123 typedef PotentialMap<CoordMap> Potential;
124 Potential potential(coord, coord[target]);
126 typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
127 ReducedLength reduced(graph, length, potential);
129 Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
132 dijkstra.addSource(source);
133 dijkstra.start(target);
135 std::cout << dijkstra.dist(target) + potential[source] << std::endl;
136 std::cout << timer << std::endl;