ladanyi@1636: /* -*- C++ -*- ladanyi@1636: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport ladanyi@1636: * (Egervary Research Group on Combinatorial Optimization, EGRES). ladanyi@1636: * ladanyi@1636: * Permission to use, modify and distribute this software is granted ladanyi@1636: * provided that this copyright notice appears in all copies. For ladanyi@1636: * precise terms see the accompanying LICENSE file. ladanyi@1636: * ladanyi@1636: * This software is provided "AS IS" with no warranty of any kind, ladanyi@1636: * express or implied, and with no claim as to its suitability for any ladanyi@1636: * purpose. ladanyi@1636: * ladanyi@1636: */ ladanyi@1636: deba@1358: #include deba@1358: #include deba@1358: deba@1342: #include deba@1342: #include deba@1342: #include alpar@2207: #include deba@1342: #include deba@1342: deba@1342: #include deba@1342: alpar@2569: #include deba@1342: deba@1775: /// \ingroup demos deba@1775: /// \file alpar@1959: /// \brief Minimal route on a planar graph with eucledian distances. deba@1775: /// alpar@1959: /// Minimal route on a planar graph with eucledian distances. deba@1775: /// deba@1775: /// \include min_route.cc deba@1775: deba@1358: deba@1342: using namespace lemon; deba@1342: deba@1342: template deba@1342: class PotentialMap { deba@1342: public: deba@1342: typedef double Value; deba@1342: typedef typename CoordMap::Key Key; deba@1342: alpar@2207: PotentialMap(const CoordMap& _coord, const dim2::Point& _target) deba@1342: : coord(_coord), target(_target) {} deba@1342: deba@1342: double operator[](const Key& node) const { deba@1342: return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + deba@1342: (coord[node].y - target.y) * (coord[node].y - target.y)); deba@1342: } deba@1342: private: deba@1358: const CoordMap& coord; alpar@2207: dim2::Point target; deba@1342: }; deba@1342: deba@1342: template deba@1342: class ReducedLengthMap { deba@1342: public: deba@1342: typedef double Value; deba@1342: typedef typename LengthMap::Key Key; deba@1342: deba@1342: ReducedLengthMap(const Graph& _graph, const LengthMap& _length, deba@1342: const PotentialMap& _pot) deba@1342: : graph(_graph), length(_length), pot(_pot) {} deba@1342: deba@1342: Value operator[](const Key& edge) const { deba@1342: return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]); deba@1342: } deba@1342: deba@1342: private: deba@1342: const Graph& graph; deba@1342: const LengthMap& length; deba@1342: const PotentialMap& pot; deba@1342: }; deba@1342: deba@1342: int main() { deba@1342: typedef SmartGraph Graph; deba@1342: deba@1342: typedef Graph::Edge Edge; deba@1342: typedef Graph::Node Node; deba@1342: typedef Graph::EdgeIt EdgeIt; deba@1342: typedef Graph::NodeIt NodeIt; deba@1342: typedef Graph::EdgeMap LengthMap; alpar@2207: typedef Graph::NodeMap > CoordMap; deba@1342: deba@1342: SmartGraph graph; deba@1342: deba@1358: std::ifstream is("route.lgf"); deba@1358: GraphReader reader(is, graph); deba@1342: deba@1342: CoordMap coord(graph); alpar@2207: dim2::XMap xcoord = xMap(coord); deba@1394: reader.readNodeMap("coordinates_x", xcoord); alpar@2207: dim2::YMap ycoord = yMap(coord); deba@1394: reader.readNodeMap("coordinates_y", ycoord); deba@1342: deba@1342: LengthMap length(graph); deba@1394: reader.readEdgeMap("length", length); deba@1342: deba@1342: Node source, target; deba@1394: reader.readNode("source", source); deba@1394: reader.readNode("target", target); deba@1342: deba@1342: reader.run(); deba@1342: deba@1342: { deba@1342: Timer timer; deba@1342: Dijkstra dijkstra(graph, length); deba@1342: dijkstra.init(); deba@1342: dijkstra.addSource(source); deba@1342: dijkstra.start(target); deba@1342: deba@1342: std::cout << dijkstra.dist(target) << std::endl; deba@1342: std::cout << timer << std::endl; deba@1342: } deba@1342: { deba@1342: Timer timer; deba@1342: typedef PotentialMap Potential; deba@1342: Potential potential(coord, coord[target]); deba@1342: deba@1342: typedef ReducedLengthMap ReducedLength; deba@1342: ReducedLength reduced(graph, length, potential); deba@1342: deba@1342: Dijkstra dijkstra(graph, reduced); deba@1342: deba@1342: dijkstra.init(); deba@1342: dijkstra.addSource(source); deba@1342: dijkstra.start(target); deba@1342: deba@1342: std::cout << dijkstra.dist(target) + potential[source] << std::endl; deba@1342: std::cout << timer << std::endl; deba@1342: } deba@1342: deba@1342: return 0; deba@1342: }