demo/min_route.cc
author kpeter
Mon, 18 Feb 2008 03:32:06 +0000
changeset 2575 e866e288cba6
parent 2553 bfced05fa852
permissions -rw-r--r--
Major improvements in NetworkSimplex.

Main changes:
- Use -potenital[] instead of potential[] to conform to the usual
terminology.
- Use function parameter instead of #define commands to select pivot rule.
- Use much faster implementation for the candidate list pivot rule.
It is about 5-20 times faster now.
- Add a new pivot rule called "Limited Search" that is a modified
version of "Block Search". It is about 25 percent faster on rather
sparse graphs.
- By default "Limited Search" is used for sparse graphs and
"Block Search" is used otherwise. This combined method is the most
efficient on every input class.
- Change the name of private members to start with "_".
- Change the name of function parameters not to start with "_".
- Remove unnecessary documentation for private members.
- Many doc improvements.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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/dim2.h>
    26 #include <lemon/graph_reader.h>
    27 
    28 #include <lemon/time_measure.h>
    29 
    30 #include <lemon/math.h>
    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 dim2::Point<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   dim2::Point<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<dim2::Point<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   dim2::XMap<CoordMap> xcoord = xMap(coord);
    98   reader.readNodeMap("coordinates_x", xcoord);
    99   dim2::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 }