demo/min_route.cc
changeset 2367 041878e6f388
parent 1959 264811b995f3
child 2391 14a343be7a5a
equal deleted inserted replaced
5:9543ddf1086c 6:08ef78f2faea
    20 #include <fstream>
    20 #include <fstream>
    21 
    21 
    22 #include <lemon/smart_graph.h>
    22 #include <lemon/smart_graph.h>
    23 #include <lemon/dijkstra.h>
    23 #include <lemon/dijkstra.h>
    24 #include <lemon/maps.h>
    24 #include <lemon/maps.h>
    25 #include <lemon/xy.h>
    25 #include <lemon/dim2.h>
    26 #include <lemon/graph_reader.h>
    26 #include <lemon/graph_reader.h>
    27 
    27 
    28 #include <lemon/time_measure.h>
    28 #include <lemon/time_measure.h>
    29 
    29 
    30 #include <cmath>
    30 #include <cmath>
    44 class PotentialMap {
    44 class PotentialMap {
    45 public:
    45 public:
    46   typedef double Value;
    46   typedef double Value;
    47   typedef typename CoordMap::Key Key;
    47   typedef typename CoordMap::Key Key;
    48 
    48 
    49   PotentialMap(const CoordMap& _coord, const xy<double>& _target)
    49   PotentialMap(const CoordMap& _coord, const dim2::Point<double>& _target)
    50     : coord(_coord), target(_target) {}
    50     : coord(_coord), target(_target) {}
    51 
    51 
    52   double operator[](const Key& node) const {
    52   double operator[](const Key& node) const {
    53     return std::sqrt((coord[node].x - target.x) * (coord[node].x - target.x) + 
    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));
    54 		     (coord[node].y - target.y) * (coord[node].y - target.y));
    55   }
    55   }
    56 private:
    56 private:
    57   const CoordMap& coord;
    57   const CoordMap& coord;
    58   xy<double> target;
    58   dim2::Point<double> target;
    59 };
    59 };
    60 
    60 
    61 template <typename Graph, typename LengthMap, typename PotentialMap>
    61 template <typename Graph, typename LengthMap, typename PotentialMap>
    62 class ReducedLengthMap {
    62 class ReducedLengthMap {
    63 public:
    63 public:
    84   typedef Graph::Edge Edge;
    84   typedef Graph::Edge Edge;
    85   typedef Graph::Node Node;
    85   typedef Graph::Node Node;
    86   typedef Graph::EdgeIt EdgeIt;
    86   typedef Graph::EdgeIt EdgeIt;
    87   typedef Graph::NodeIt NodeIt;
    87   typedef Graph::NodeIt NodeIt;
    88   typedef Graph::EdgeMap<double> LengthMap;
    88   typedef Graph::EdgeMap<double> LengthMap;
    89   typedef Graph::NodeMap<xy<double> > CoordMap;
    89   typedef Graph::NodeMap<dim2::Point<double> > CoordMap;
    90 
    90 
    91   SmartGraph graph;
    91   SmartGraph graph;
    92 
    92 
    93   std::ifstream is("route.lgf");
    93   std::ifstream is("route.lgf");
    94   GraphReader<Graph> reader(is, graph);
    94   GraphReader<Graph> reader(is, graph);
    95   
    95   
    96   CoordMap coord(graph);
    96   CoordMap coord(graph);
    97   XMap<CoordMap> xcoord = xMap(coord);
    97   dim2::XMap<CoordMap> xcoord = xMap(coord);
    98   reader.readNodeMap("coordinates_x", xcoord);
    98   reader.readNodeMap("coordinates_x", xcoord);
    99   YMap<CoordMap> ycoord = yMap(coord);
    99   dim2::YMap<CoordMap> ycoord = yMap(coord);
   100   reader.readNodeMap("coordinates_y", ycoord);
   100   reader.readNodeMap("coordinates_y", ycoord);
   101 
   101 
   102   LengthMap length(graph);
   102   LengthMap length(graph);
   103   reader.readEdgeMap("length", length);
   103   reader.readEdgeMap("length", length);
   104 
   104