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