ladanyi@1636: /* -*- C++ -*-
ladanyi@1636:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
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 <iostream>
deba@1358: #include <fstream>
deba@1358: 
deba@1342: #include <lemon/smart_graph.h>
deba@1342: #include <lemon/dijkstra.h>
deba@1342: #include <lemon/maps.h>
alpar@2207: #include <lemon/dim2.h>
deba@1342: #include <lemon/graph_reader.h>
deba@1342: 
deba@1342: #include <lemon/time_measure.h>
deba@1342: 
deba@1342: #include <cmath>
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 <typename CoordMap>
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<double>& _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<double> target;
deba@1342: };
deba@1342: 
deba@1342: template <typename Graph, typename LengthMap, typename PotentialMap>
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<double> LengthMap;
alpar@2207:   typedef Graph::NodeMap<dim2::Point<double> > CoordMap;
deba@1342: 
deba@1342:   SmartGraph graph;
deba@1342: 
deba@1358:   std::ifstream is("route.lgf");
deba@1358:   GraphReader<Graph> reader(is, graph);
deba@1342:   
deba@1342:   CoordMap coord(graph);
alpar@2207:   dim2::XMap<CoordMap> xcoord = xMap(coord);
deba@1394:   reader.readNodeMap("coordinates_x", xcoord);
alpar@2207:   dim2::YMap<CoordMap> 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<Graph, LengthMap> 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<CoordMap> Potential;
deba@1342:     Potential potential(coord, coord[target]);
deba@1342: 
deba@1342:     typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
deba@1342:     ReducedLength reduced(graph, length, potential);
deba@1342: 
deba@1342:     Dijkstra<Graph, ReducedLength> 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: }