lemon/suurballe.h
changeset 788 c92296660262
parent 584 33c6b6e755cd
child 851 c67e235c832f
equal deleted inserted replaced
6:b7f2f856ffb2 7:2f1b555e9812
    23 ///\file
    23 ///\file
    24 ///\brief An algorithm for finding arc-disjoint paths between two
    24 ///\brief An algorithm for finding arc-disjoint paths between two
    25 /// nodes having minimum total length.
    25 /// nodes having minimum total length.
    26 
    26 
    27 #include <vector>
    27 #include <vector>
       
    28 #include <limits>
    28 #include <lemon/bin_heap.h>
    29 #include <lemon/bin_heap.h>
    29 #include <lemon/path.h>
    30 #include <lemon/path.h>
    30 #include <lemon/list_graph.h>
    31 #include <lemon/list_graph.h>
    31 #include <lemon/maps.h>
    32 #include <lemon/maps.h>
    32 
    33 
    40   ///
    41   ///
    41   /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
    42   /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
    42   /// finding arc-disjoint paths having minimum total length (cost)
    43   /// finding arc-disjoint paths having minimum total length (cost)
    43   /// from a given source node to a given target node in a digraph.
    44   /// from a given source node to a given target node in a digraph.
    44   ///
    45   ///
    45   /// In fact, this implementation is the specialization of the
    46   /// Note that this problem is a special case of the \ref min_cost_flow
    46   /// \ref CapacityScaling "successive shortest path" algorithm.
    47   /// "minimum cost flow problem". This implementation is actually an
       
    48   /// efficient specialized version of the \ref CapacityScaling
       
    49   /// "Successive Shortest Path" algorithm directly for this problem.
       
    50   /// Therefore this class provides query functions for flow values and
       
    51   /// node potentials (the dual solution) just like the minimum cost flow
       
    52   /// algorithms.
    47   ///
    53   ///
    48   /// \tparam GR The digraph type the algorithm runs on.
    54   /// \tparam GR The digraph type the algorithm runs on.
    49   /// The default value is \c ListDigraph.
    55   /// \tparam LEN The type of the length map.
    50   /// \tparam LEN The type of the length (cost) map.
    56   /// The default value is <tt>GR::ArcMap<int></tt>.
    51   /// The default value is <tt>Digraph::ArcMap<int></tt>.
       
    52   ///
    57   ///
    53   /// \warning Length values should be \e non-negative \e integers.
    58   /// \warning Length values should be \e non-negative \e integers.
    54   ///
    59   ///
    55   /// \note For finding node-disjoint paths this algorithm can be used
    60   /// \note For finding node-disjoint paths this algorithm can be used
    56   /// with \ref SplitNodes.
    61   /// along with the \ref SplitNodes adaptor.
    57 #ifdef DOXYGEN
    62 #ifdef DOXYGEN
    58   template <typename GR, typename LEN>
    63   template <typename GR, typename LEN>
    59 #else
    64 #else
    60   template < typename GR = ListDigraph,
    65   template < typename GR,
    61              typename LEN = typename GR::template ArcMap<int> >
    66              typename LEN = typename GR::template ArcMap<int> >
    62 #endif
    67 #endif
    63   class Suurballe
    68   class Suurballe
    64   {
    69   {
    65     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    70     TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    73     typedef GR Digraph;
    78     typedef GR Digraph;
    74     /// The type of the length map.
    79     /// The type of the length map.
    75     typedef LEN LengthMap;
    80     typedef LEN LengthMap;
    76     /// The type of the lengths.
    81     /// The type of the lengths.
    77     typedef typename LengthMap::Value Length;
    82     typedef typename LengthMap::Value Length;
       
    83 #ifdef DOXYGEN
       
    84     /// The type of the flow map.
       
    85     typedef GR::ArcMap<int> FlowMap;
       
    86     /// The type of the potential map.
       
    87     typedef GR::NodeMap<Length> PotentialMap;
       
    88 #else
    78     /// The type of the flow map.
    89     /// The type of the flow map.
    79     typedef typename Digraph::template ArcMap<int> FlowMap;
    90     typedef typename Digraph::template ArcMap<int> FlowMap;
    80     /// The type of the potential map.
    91     /// The type of the potential map.
    81     typedef typename Digraph::template NodeMap<Length> PotentialMap;
    92     typedef typename Digraph::template NodeMap<Length> PotentialMap;
       
    93 #endif
       
    94 
    82     /// The type of the path structures.
    95     /// The type of the path structures.
    83     typedef SimplePath<Digraph> Path;
    96     typedef SimplePath<GR> Path;
    84 
    97 
    85   private:
    98   private:
    86 
    99 
    87     /// \brief Special implementation of the Dijkstra algorithm
   100     // ResidualDijkstra is a special implementation of the
    88     /// for finding shortest paths in the residual network.
   101     // Dijkstra algorithm for finding shortest paths in the
    89     ///
   102     // residual network with respect to the reduced arc lengths
    90     /// \ref ResidualDijkstra is a special implementation of the
   103     // and modifying the node potentials according to the
    91     /// \ref Dijkstra algorithm for finding shortest paths in the
   104     // distance of the nodes.
    92     /// residual network of the digraph with respect to the reduced arc
       
    93     /// lengths and modifying the node potentials according to the
       
    94     /// distance of the nodes.
       
    95     class ResidualDijkstra
   105     class ResidualDijkstra
    96     {
   106     {
    97       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   107       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    98       typedef BinHeap<Length, HeapCrossRef> Heap;
   108       typedef BinHeap<Length, HeapCrossRef> Heap;
    99 
   109 
   118       Node _t;
   128       Node _t;
   119 
   129 
   120     public:
   130     public:
   121 
   131 
   122       /// Constructor.
   132       /// Constructor.
   123       ResidualDijkstra( const Digraph &digraph,
   133       ResidualDijkstra( const Digraph &graph,
   124                         const FlowMap &flow,
   134                         const FlowMap &flow,
   125                         const LengthMap &length,
   135                         const LengthMap &length,
   126                         PotentialMap &potential,
   136                         PotentialMap &potential,
   127                         PredMap &pred,
   137                         PredMap &pred,
   128                         Node s, Node t ) :
   138                         Node s, Node t ) :
   129         _graph(digraph), _flow(flow), _length(length), _potential(potential),
   139         _graph(graph), _flow(flow), _length(length), _potential(potential),
   130         _dist(digraph), _pred(pred), _s(s), _t(t) {}
   140         _dist(graph), _pred(pred), _s(s), _t(t) {}
   131 
   141 
   132       /// \brief Run the algorithm. It returns \c true if a path is found
   142       /// \brief Run the algorithm. It returns \c true if a path is found
   133       /// from the source node to the target node.
   143       /// from the source node to the target node.
   134       bool run() {
   144       bool run() {
   135         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
   145         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
   234 
   244 
   235     /// \brief Constructor.
   245     /// \brief Constructor.
   236     ///
   246     ///
   237     /// Constructor.
   247     /// Constructor.
   238     ///
   248     ///
   239     /// \param digraph The digraph the algorithm runs on.
   249     /// \param graph The digraph the algorithm runs on.
   240     /// \param length The length (cost) values of the arcs.
   250     /// \param length The length (cost) values of the arcs.
   241     /// \param s The source node.
   251     Suurballe( const Digraph &graph,
   242     /// \param t The target node.
   252                const LengthMap &length ) :
   243     Suurballe( const Digraph &digraph,
   253       _graph(graph), _length(length), _flow(0), _local_flow(false),
   244                const LengthMap &length,
   254       _potential(0), _local_potential(false), _pred(graph)
   245                Node s, Node t ) :
   255     {
   246       _graph(digraph), _length(length), _flow(0), _local_flow(false),
   256       LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
   247       _potential(0), _local_potential(false), _source(s), _target(t),
   257         "The length type of Suurballe must be integer");
   248       _pred(digraph) {}
   258     }
   249 
   259 
   250     /// Destructor.
   260     /// Destructor.
   251     ~Suurballe() {
   261     ~Suurballe() {
   252       if (_local_flow) delete _flow;
   262       if (_local_flow) delete _flow;
   253       if (_local_potential) delete _potential;
   263       if (_local_potential) delete _potential;
   255     }
   265     }
   256 
   266 
   257     /// \brief Set the flow map.
   267     /// \brief Set the flow map.
   258     ///
   268     ///
   259     /// This function sets the flow map.
   269     /// This function sets the flow map.
   260     ///
   270     /// If it is not used before calling \ref run() or \ref init(),
   261     /// The found flow contains only 0 and 1 values. It is the union of
   271     /// an instance will be allocated automatically. The destructor
   262     /// the found arc-disjoint paths.
   272     /// deallocates this automatically allocated map, of course.
       
   273     ///
       
   274     /// The found flow contains only 0 and 1 values, since it is the
       
   275     /// union of the found arc-disjoint paths.
   263     ///
   276     ///
   264     /// \return <tt>(*this)</tt>
   277     /// \return <tt>(*this)</tt>
   265     Suurballe& flowMap(FlowMap &map) {
   278     Suurballe& flowMap(FlowMap &map) {
   266       if (_local_flow) {
   279       if (_local_flow) {
   267         delete _flow;
   280         delete _flow;
   272     }
   285     }
   273 
   286 
   274     /// \brief Set the potential map.
   287     /// \brief Set the potential map.
   275     ///
   288     ///
   276     /// This function sets the potential map.
   289     /// This function sets the potential map.
   277     ///
   290     /// If it is not used before calling \ref run() or \ref init(),
   278     /// The potentials provide the dual solution of the underlying
   291     /// an instance will be allocated automatically. The destructor
   279     /// minimum cost flow problem.
   292     /// deallocates this automatically allocated map, of course.
       
   293     ///
       
   294     /// The node potentials provide the dual solution of the underlying
       
   295     /// \ref min_cost_flow "minimum cost flow problem".
   280     ///
   296     ///
   281     /// \return <tt>(*this)</tt>
   297     /// \return <tt>(*this)</tt>
   282     Suurballe& potentialMap(PotentialMap &map) {
   298     Suurballe& potentialMap(PotentialMap &map) {
   283       if (_local_potential) {
   299       if (_local_potential) {
   284         delete _potential;
   300         delete _potential;
   299 
   315 
   300     /// \brief Run the algorithm.
   316     /// \brief Run the algorithm.
   301     ///
   317     ///
   302     /// This function runs the algorithm.
   318     /// This function runs the algorithm.
   303     ///
   319     ///
       
   320     /// \param s The source node.
       
   321     /// \param t The target node.
   304     /// \param k The number of paths to be found.
   322     /// \param k The number of paths to be found.
   305     ///
   323     ///
   306     /// \return \c k if there are at least \c k arc-disjoint paths from
   324     /// \return \c k if there are at least \c k arc-disjoint paths from
   307     /// \c s to \c t in the digraph. Otherwise it returns the number of
   325     /// \c s to \c t in the digraph. Otherwise it returns the number of
   308     /// arc-disjoint paths found.
   326     /// arc-disjoint paths found.
   309     ///
   327     ///
   310     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
   328     /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
   311     /// shortcut of the following code.
   329     /// just a shortcut of the following code.
   312     /// \code
   330     /// \code
   313     ///   s.init();
   331     ///   s.init(s);
   314     ///   s.findFlow(k);
   332     ///   s.findFlow(t, k);
   315     ///   s.findPaths();
   333     ///   s.findPaths();
   316     /// \endcode
   334     /// \endcode
   317     int run(int k = 2) {
   335     int run(const Node& s, const Node& t, int k = 2) {
   318       init();
   336       init(s);
   319       findFlow(k);
   337       findFlow(t, k);
   320       findPaths();
   338       findPaths();
   321       return _path_num;
   339       return _path_num;
   322     }
   340     }
   323 
   341 
   324     /// \brief Initialize the algorithm.
   342     /// \brief Initialize the algorithm.
   325     ///
   343     ///
   326     /// This function initializes the algorithm.
   344     /// This function initializes the algorithm.
   327     void init() {
   345     ///
       
   346     /// \param s The source node.
       
   347     void init(const Node& s) {
       
   348       _source = s;
       
   349 
   328       // Initialize maps
   350       // Initialize maps
   329       if (!_flow) {
   351       if (!_flow) {
   330         _flow = new FlowMap(_graph);
   352         _flow = new FlowMap(_graph);
   331         _local_flow = true;
   353         _local_flow = true;
   332       }
   354       }
   334         _potential = new PotentialMap(_graph);
   356         _potential = new PotentialMap(_graph);
   335         _local_potential = true;
   357         _local_potential = true;
   336       }
   358       }
   337       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   359       for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   338       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   360       for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   339 
   361     }
   340       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
   362 
   341                                         *_potential, _pred,
   363     /// \brief Execute the algorithm to find an optimal flow.
   342                                         _source, _target );
       
   343     }
       
   344 
       
   345     /// \brief Execute the successive shortest path algorithm to find
       
   346     /// an optimal flow.
       
   347     ///
   364     ///
   348     /// This function executes the successive shortest path algorithm to
   365     /// This function executes the successive shortest path algorithm to
   349     /// find a minimum cost flow, which is the union of \c k or less
   366     /// find a minimum cost flow, which is the union of \c k (or less)
   350     /// arc-disjoint paths.
   367     /// arc-disjoint paths.
   351     ///
   368     ///
       
   369     /// \param t The target node.
       
   370     /// \param k The number of paths to be found.
       
   371     ///
   352     /// \return \c k if there are at least \c k arc-disjoint paths from
   372     /// \return \c k if there are at least \c k arc-disjoint paths from
   353     /// \c s to \c t in the digraph. Otherwise it returns the number of
   373     /// the source node to the given node \c t in the digraph.
   354     /// arc-disjoint paths found.
   374     /// Otherwise it returns the number of arc-disjoint paths found.
   355     ///
   375     ///
   356     /// \pre \ref init() must be called before using this function.
   376     /// \pre \ref init() must be called before using this function.
   357     int findFlow(int k = 2) {
   377     int findFlow(const Node& t, int k = 2) {
       
   378       _target = t;
       
   379       _dijkstra =
       
   380         new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
       
   381                               _source, _target );
       
   382 
   358       // Find shortest paths
   383       // Find shortest paths
   359       _path_num = 0;
   384       _path_num = 0;
   360       while (_path_num < k) {
   385       while (_path_num < k) {
   361         // Run Dijkstra
   386         // Run Dijkstra
   362         if (!_dijkstra->run()) break;
   387         if (!_dijkstra->run()) break;
   378       return _path_num;
   403       return _path_num;
   379     }
   404     }
   380 
   405 
   381     /// \brief Compute the paths from the flow.
   406     /// \brief Compute the paths from the flow.
   382     ///
   407     ///
   383     /// This function computes the paths from the flow.
   408     /// This function computes the paths from the found minimum cost flow,
       
   409     /// which is the union of some arc-disjoint paths.
   384     ///
   410     ///
   385     /// \pre \ref init() and \ref findFlow() must be called before using
   411     /// \pre \ref init() and \ref findFlow() must be called before using
   386     /// this function.
   412     /// this function.
   387     void findPaths() {
   413     void findPaths() {
   388       // Create the residual flow map (the union of the paths not found
       
   389       // so far)
       
   390       FlowMap res_flow(_graph);
   414       FlowMap res_flow(_graph);
   391       for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
   415       for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
   392 
   416 
   393       paths.clear();
   417       paths.clear();
   394       paths.resize(_path_num);
   418       paths.resize(_path_num);
   411     /// functions.
   435     /// functions.
   412     /// \n The algorithm should be executed before using them.
   436     /// \n The algorithm should be executed before using them.
   413 
   437 
   414     /// @{
   438     /// @{
   415 
   439 
   416     /// \brief Return a const reference to the arc map storing the
   440     /// \brief Return the total length of the found paths.
   417     /// found flow.
   441     ///
   418     ///
   442     /// This function returns the total length of the found paths, i.e.
   419     /// This function returns a const reference to the arc map storing
   443     /// the total cost of the found flow.
   420     /// the flow that is the union of the found arc-disjoint paths.
   444     /// The complexity of the function is O(e).
   421     ///
       
   422     /// \pre \ref run() or \ref findFlow() must be called before using
       
   423     /// this function.
       
   424     const FlowMap& flowMap() const {
       
   425       return *_flow;
       
   426     }
       
   427 
       
   428     /// \brief Return a const reference to the node map storing the
       
   429     /// found potentials (the dual solution).
       
   430     ///
       
   431     /// This function returns a const reference to the node map storing
       
   432     /// the found potentials that provide the dual solution of the
       
   433     /// underlying minimum cost flow problem.
       
   434     ///
       
   435     /// \pre \ref run() or \ref findFlow() must be called before using
       
   436     /// this function.
       
   437     const PotentialMap& potentialMap() const {
       
   438       return *_potential;
       
   439     }
       
   440 
       
   441     /// \brief Return the flow on the given arc.
       
   442     ///
       
   443     /// This function returns the flow on the given arc.
       
   444     /// It is \c 1 if the arc is involved in one of the found paths,
       
   445     /// otherwise it is \c 0.
       
   446     ///
       
   447     /// \pre \ref run() or \ref findFlow() must be called before using
       
   448     /// this function.
       
   449     int flow(const Arc& arc) const {
       
   450       return (*_flow)[arc];
       
   451     }
       
   452 
       
   453     /// \brief Return the potential of the given node.
       
   454     ///
       
   455     /// This function returns the potential of the given node.
       
   456     ///
       
   457     /// \pre \ref run() or \ref findFlow() must be called before using
       
   458     /// this function.
       
   459     Length potential(const Node& node) const {
       
   460       return (*_potential)[node];
       
   461     }
       
   462 
       
   463     /// \brief Return the total length (cost) of the found paths (flow).
       
   464     ///
       
   465     /// This function returns the total length (cost) of the found paths
       
   466     /// (flow). The complexity of the function is O(e).
       
   467     ///
   445     ///
   468     /// \pre \ref run() or \ref findFlow() must be called before using
   446     /// \pre \ref run() or \ref findFlow() must be called before using
   469     /// this function.
   447     /// this function.
   470     Length totalLength() const {
   448     Length totalLength() const {
   471       Length c = 0;
   449       Length c = 0;
   472       for (ArcIt e(_graph); e != INVALID; ++e)
   450       for (ArcIt e(_graph); e != INVALID; ++e)
   473         c += (*_flow)[e] * _length[e];
   451         c += (*_flow)[e] * _length[e];
   474       return c;
   452       return c;
   475     }
   453     }
   476 
   454 
       
   455     /// \brief Return the flow value on the given arc.
       
   456     ///
       
   457     /// This function returns the flow value on the given arc.
       
   458     /// It is \c 1 if the arc is involved in one of the found arc-disjoint
       
   459     /// paths, otherwise it is \c 0.
       
   460     ///
       
   461     /// \pre \ref run() or \ref findFlow() must be called before using
       
   462     /// this function.
       
   463     int flow(const Arc& arc) const {
       
   464       return (*_flow)[arc];
       
   465     }
       
   466 
       
   467     /// \brief Return a const reference to an arc map storing the
       
   468     /// found flow.
       
   469     ///
       
   470     /// This function returns a const reference to an arc map storing
       
   471     /// the flow that is the union of the found arc-disjoint paths.
       
   472     ///
       
   473     /// \pre \ref run() or \ref findFlow() must be called before using
       
   474     /// this function.
       
   475     const FlowMap& flowMap() const {
       
   476       return *_flow;
       
   477     }
       
   478 
       
   479     /// \brief Return the potential of the given node.
       
   480     ///
       
   481     /// This function returns the potential of the given node.
       
   482     /// The node potentials provide the dual solution of the
       
   483     /// underlying \ref min_cost_flow "minimum cost flow problem".
       
   484     ///
       
   485     /// \pre \ref run() or \ref findFlow() must be called before using
       
   486     /// this function.
       
   487     Length potential(const Node& node) const {
       
   488       return (*_potential)[node];
       
   489     }
       
   490 
       
   491     /// \brief Return a const reference to a node map storing the
       
   492     /// found potentials (the dual solution).
       
   493     ///
       
   494     /// This function returns a const reference to a node map storing
       
   495     /// the found potentials that provide the dual solution of the
       
   496     /// underlying \ref min_cost_flow "minimum cost flow problem".
       
   497     ///
       
   498     /// \pre \ref run() or \ref findFlow() must be called before using
       
   499     /// this function.
       
   500     const PotentialMap& potentialMap() const {
       
   501       return *_potential;
       
   502     }
       
   503 
   477     /// \brief Return the number of the found paths.
   504     /// \brief Return the number of the found paths.
   478     ///
   505     ///
   479     /// This function returns the number of the found paths.
   506     /// This function returns the number of the found paths.
   480     ///
   507     ///
   481     /// \pre \ref run() or \ref findFlow() must be called before using
   508     /// \pre \ref run() or \ref findFlow() must be called before using
   486 
   513 
   487     /// \brief Return a const reference to the specified path.
   514     /// \brief Return a const reference to the specified path.
   488     ///
   515     ///
   489     /// This function returns a const reference to the specified path.
   516     /// This function returns a const reference to the specified path.
   490     ///
   517     ///
   491     /// \param i The function returns the \c i-th path.
   518     /// \param i The function returns the <tt>i</tt>-th path.
   492     /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   519     /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   493     ///
   520     ///
   494     /// \pre \ref run() or \ref findPaths() must be called before using
   521     /// \pre \ref run() or \ref findPaths() must be called before using
   495     /// this function.
   522     /// this function.
   496     Path path(int i) const {
   523     Path path(int i) const {