demo/min_route.cc
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1956 a055123339d5
child 2207 75a29ac69c19
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

The ResGraphAdaptor is based on this composition.
     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 }