demo/min_route.cc
author alpar
Wed, 09 Aug 2006 12:47:31 +0000
changeset 2169 9f71586a3f74
parent 1956 a055123339d5
child 2207 75a29ac69c19
permissions -rw-r--r--
This script lists all the header files included directly or indirectly by a certain header file.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     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.
    12  *
    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
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <iostream>
    20 #include <fstream>
    21 
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/dijkstra.h>
    24 #include <lemon/maps.h>
    25 #include <lemon/xy.h>
    26 #include <lemon/graph_reader.h>
    27 
    28 #include <lemon/time_measure.h>
    29 
    30 #include <cmath>
    31 
    32 /// \ingroup demos
    33 /// \file
    34 /// \brief Minimal route on a planar graph with eucledian distances.
    35 ///
    36 /// Minimal route on a planar graph with eucledian distances.
    37 ///
    38 /// \include min_route.cc
    39 
    40 
    41 using namespace lemon;
    42 
    43 template <typename CoordMap>
    44 class PotentialMap {
    45 public:
    46   typedef double Value;
    47   typedef typename CoordMap::Key Key;
    48 
    49   PotentialMap(const CoordMap& _coord, const xy<double>& _target)
    50     : coord(_coord), target(_target) {}
    51 
    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));
    55   }
    56 private:
    57   const CoordMap& coord;
    58   xy<double> target;
    59 };
    60 
    61 template <typename Graph, typename LengthMap, typename PotentialMap>
    62 class ReducedLengthMap {
    63 public:
    64   typedef double Value;
    65   typedef typename LengthMap::Key Key;
    66 
    67   ReducedLengthMap(const Graph& _graph, const LengthMap& _length, 
    68 		   const PotentialMap& _pot) 
    69     : graph(_graph), length(_length), pot(_pot) {}
    70 
    71   Value operator[](const Key& edge) const {
    72     return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
    73   }
    74 
    75 private:
    76   const Graph& graph;
    77   const LengthMap& length;
    78   const PotentialMap& pot;
    79 };
    80 
    81 int main() {
    82   typedef SmartGraph Graph;
    83 
    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<xy<double> > CoordMap;
    90 
    91   SmartGraph graph;
    92 
    93   std::ifstream is("route.lgf");
    94   GraphReader<Graph> reader(is, graph);
    95   
    96   CoordMap coord(graph);
    97   XMap<CoordMap> xcoord = xMap(coord);
    98   reader.readNodeMap("coordinates_x", xcoord);
    99   YMap<CoordMap> ycoord = yMap(coord);
   100   reader.readNodeMap("coordinates_y", ycoord);
   101 
   102   LengthMap length(graph);
   103   reader.readEdgeMap("length", length);
   104 
   105   Node source, target;
   106   reader.readNode("source", source);
   107   reader.readNode("target", target);
   108 
   109   reader.run();
   110 
   111   {
   112     Timer timer;
   113     Dijkstra<Graph, LengthMap> dijkstra(graph, length);
   114     dijkstra.init();
   115     dijkstra.addSource(source);
   116     dijkstra.start(target);
   117 
   118     std::cout << dijkstra.dist(target) << std::endl;
   119     std::cout << timer << std::endl;
   120   }
   121   {
   122     Timer timer;
   123     typedef PotentialMap<CoordMap> Potential;
   124     Potential potential(coord, coord[target]);
   125 
   126     typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
   127     ReducedLength reduced(graph, length, potential);
   128 
   129     Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
   130 
   131     dijkstra.init();
   132     dijkstra.addSource(source);
   133     dijkstra.start(target);
   134   
   135     std::cout << dijkstra.dist(target) + potential[source] << std::endl;
   136     std::cout << timer << std::endl;
   137   }
   138 
   139   return 0;
   140 }