demo/min_route.cc
author ladanyi
Tue, 12 Jul 2005 13:36:01 +0000
changeset 1545 e8378402f97e
parent 1410 dcfad73b3965
child 1636 260ac104190f
permissions -rw-r--r--
Added the individual png files to EXTRA_DIST instead of the icons directory. This way the .svn directories do not get in the tarball. An alternative solution would be to delete these in a dist-hook target.
     1 #include <iostream>
     2 #include <fstream>
     3 
     4 #include <lemon/smart_graph.h>
     5 #include <lemon/dijkstra.h>
     6 #include <lemon/maps.h>
     7 #include <lemon/xy.h>
     8 #include <lemon/graph_reader.h>
     9 
    10 #include <lemon/time_measure.h>
    11 
    12 #include <cmath>
    13 
    14 
    15 using namespace lemon;
    16 
    17 template <typename CoordMap>
    18 class PotentialMap {
    19 public:
    20   typedef double Value;
    21   typedef typename CoordMap::Key Key;
    22 
    23   PotentialMap(const CoordMap& _coord, const xy<double>& _target)
    24     : coord(_coord), target(_target) {}
    25 
    26   double operator[](const Key& node) const {
    27     return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + 
    28 		     (coord[node].y - target.y) * (coord[node].y - target.y));
    29   }
    30 private:
    31   const CoordMap& coord;
    32   xy<double> target;
    33 };
    34 
    35 template <typename Graph, typename LengthMap, typename PotentialMap>
    36 class ReducedLengthMap {
    37 public:
    38   typedef double Value;
    39   typedef typename LengthMap::Key Key;
    40 
    41   ReducedLengthMap(const Graph& _graph, const LengthMap& _length, 
    42 		   const PotentialMap& _pot) 
    43     : graph(_graph), length(_length), pot(_pot) {}
    44 
    45   Value operator[](const Key& edge) const {
    46     return length[edge] - (pot[graph.source(edge)] - pot[graph.target(edge)]);
    47   }
    48 
    49 private:
    50   const Graph& graph;
    51   const LengthMap& length;
    52   const PotentialMap& pot;
    53 };
    54 
    55 int main() {
    56   typedef SmartGraph Graph;
    57 
    58   typedef Graph::Edge Edge;
    59   typedef Graph::Node Node;
    60   typedef Graph::EdgeIt EdgeIt;
    61   typedef Graph::NodeIt NodeIt;
    62   typedef Graph::EdgeMap<double> LengthMap;
    63   typedef Graph::NodeMap<xy<double> > CoordMap;
    64 
    65   SmartGraph graph;
    66 
    67   std::ifstream is("route.lgf");
    68   GraphReader<Graph> reader(is, graph);
    69   
    70   CoordMap coord(graph);
    71   XMap<CoordMap> xcoord = xMap(coord);
    72   reader.readNodeMap("coordinates_x", xcoord);
    73   YMap<CoordMap> ycoord = yMap(coord);
    74   reader.readNodeMap("coordinates_y", ycoord);
    75 
    76   LengthMap length(graph);
    77   reader.readEdgeMap("length", length);
    78 
    79   Node source, target;
    80   reader.readNode("source", source);
    81   reader.readNode("target", target);
    82 
    83   reader.run();
    84 
    85   {
    86     Timer timer;
    87     Dijkstra<Graph, LengthMap> dijkstra(graph, length);
    88     dijkstra.init();
    89     dijkstra.addSource(source);
    90     dijkstra.start(target);
    91 
    92     std::cout << dijkstra.dist(target) << std::endl;
    93     std::cout << timer << std::endl;
    94   }
    95   {
    96     Timer timer;
    97     typedef PotentialMap<CoordMap> Potential;
    98     Potential potential(coord, coord[target]);
    99 
   100     typedef ReducedLengthMap<Graph, LengthMap, Potential> ReducedLength;
   101     ReducedLength reduced(graph, length, potential);
   102 
   103     Dijkstra<Graph, ReducedLength> dijkstra(graph, reduced);
   104 
   105     dijkstra.init();
   106     dijkstra.addSource(source);
   107     dijkstra.start(target);
   108   
   109     std::cout << dijkstra.dist(target) + potential[source] << std::endl;
   110     std::cout << timer << std::endl;
   111   }
   112 
   113   return 0;
   114 }