lemon/suurballe.h
changeset 398 532f34ea9cf3
parent 345 2f64c4a692a8
child 425 cace3206223b
equal deleted inserted replaced
0:e8c3a05d4fac 1:5afe6771ab07
    31 namespace lemon {
    31 namespace lemon {
    32 
    32 
    33   /// \addtogroup shortest_path
    33   /// \addtogroup shortest_path
    34   /// @{
    34   /// @{
    35 
    35 
    36   /// \brief Implementation of an algorithm for finding arc-disjoint
    36   /// \brief Algorithm for finding arc-disjoint paths between two nodes
    37   /// paths between two nodes having minimum total length.
    37   /// having minimum total length.
    38   ///
    38   ///
    39   /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
    39   /// \ref lemon::Suurballe "Suurballe" implements an algorithm for
    40   /// finding arc-disjoint paths having minimum total length (cost)
    40   /// finding arc-disjoint paths having minimum total length (cost)
    41   /// from a given source node to a given target node in a directed
    41   /// from a given source node to a given target node in a digraph.
    42   /// digraph.
       
    43   ///
    42   ///
    44   /// In fact, this implementation is the specialization of the
    43   /// In fact, this implementation is the specialization of the
    45   /// \ref CapacityScaling "successive shortest path" algorithm.
    44   /// \ref CapacityScaling "successive shortest path" algorithm.
    46   ///
    45   ///
    47   /// \tparam Digraph The directed digraph type the algorithm runs on.
    46   /// \tparam Digraph The digraph type the algorithm runs on.
       
    47   /// The default value is \c ListDigraph.
    48   /// \tparam LengthMap The type of the length (cost) map.
    48   /// \tparam LengthMap The type of the length (cost) map.
       
    49   /// The default value is <tt>Digraph::ArcMap<int></tt>.
    49   ///
    50   ///
    50   /// \warning Length values should be \e non-negative \e integers.
    51   /// \warning Length values should be \e non-negative \e integers.
    51   ///
    52   ///
    52   /// \note For finding node-disjoint paths this algorithm can be used
    53   /// \note For finding node-disjoint paths this algorithm can be used
    53   /// with \ref SplitDigraphAdaptor.
    54   /// with \ref SplitDigraphAdaptor.
    54   ///
    55 #ifdef DOXYGEN
    55   /// \author Attila Bernath and Peter Kovacs
    56   template <typename Digraph, typename LengthMap>
    56   
    57 #else
    57   template < typename Digraph, 
    58   template < typename Digraph = ListDigraph,
    58              typename LengthMap = typename Digraph::template ArcMap<int> >
    59              typename LengthMap = typename Digraph::template ArcMap<int> >
       
    60 #endif
    59   class Suurballe
    61   class Suurballe
    60   {
    62   {
    61     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    63     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    62 
    64 
    63     typedef typename LengthMap::Value Length;
    65     typedef typename LengthMap::Value Length;
    73     /// The type of the path structures.
    75     /// The type of the path structures.
    74     typedef SimplePath<Digraph> Path;
    76     typedef SimplePath<Digraph> Path;
    75 
    77 
    76   private:
    78   private:
    77   
    79   
    78     /// \brief Special implementation of the \ref Dijkstra algorithm
    80     /// \brief Special implementation of the Dijkstra algorithm
    79     /// for finding shortest paths in the residual network.
    81     /// for finding shortest paths in the residual network.
    80     ///
    82     ///
    81     /// \ref ResidualDijkstra is a special implementation of the
    83     /// \ref ResidualDijkstra is a special implementation of the
    82     /// \ref Dijkstra algorithm for finding shortest paths in the
    84     /// \ref Dijkstra algorithm for finding shortest paths in the
    83     /// residual network of the digraph with respect to the reduced arc
    85     /// residual network of the digraph with respect to the reduced arc
    88       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    90       typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    89       typedef BinHeap<Length, HeapCrossRef> Heap;
    91       typedef BinHeap<Length, HeapCrossRef> Heap;
    90 
    92 
    91     private:
    93     private:
    92 
    94 
    93       // The directed digraph the algorithm runs on
    95       // The digraph the algorithm runs on
    94       const Digraph &_graph;
    96       const Digraph &_graph;
    95 
    97 
    96       // The main maps
    98       // The main maps
    97       const FlowMap &_flow;
    99       const FlowMap &_flow;
    98       const LengthMap &_length;
   100       const LengthMap &_length;
   118                         PredMap &pred,
   120                         PredMap &pred,
   119                         Node s, Node t ) :
   121                         Node s, Node t ) :
   120         _graph(digraph), _flow(flow), _length(length), _potential(potential),
   122         _graph(digraph), _flow(flow), _length(length), _potential(potential),
   121         _dist(digraph), _pred(pred), _s(s), _t(t) {}
   123         _dist(digraph), _pred(pred), _s(s), _t(t) {}
   122 
   124 
   123       /// \brief Runs the algorithm. Returns \c true if a path is found
   125       /// \brief Run the algorithm. It returns \c true if a path is found
   124       /// from the source node to the target node.
   126       /// from the source node to the target node.
   125       bool run() {
   127       bool run() {
   126         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
   128         HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);
   127         Heap heap(heap_cross_ref);
   129         Heap heap(heap_cross_ref);
   128         heap.push(_s, 0);
   130         heap.push(_s, 0);
   129         _pred[_s] = INVALID;
   131         _pred[_s] = INVALID;
   130         _proc_nodes.clear();
   132         _proc_nodes.clear();
   131 
   133 
   132         // Processing nodes
   134         // Process nodes
   133         while (!heap.empty() && heap.top() != _t) {
   135         while (!heap.empty() && heap.top() != _t) {
   134           Node u = heap.top(), v;
   136           Node u = heap.top(), v;
   135           Length d = heap.prio() + _potential[u], nd;
   137           Length d = heap.prio() + _potential[u], nd;
   136           _dist[u] = heap.prio();
   138           _dist[u] = heap.prio();
   137           heap.pop();
   139           heap.pop();
   138           _proc_nodes.push_back(u);
   140           _proc_nodes.push_back(u);
   139 
   141 
   140           // Traversing outgoing arcs
   142           // Traverse outgoing arcs
   141           for (OutArcIt e(_graph, u); e != INVALID; ++e) {
   143           for (OutArcIt e(_graph, u); e != INVALID; ++e) {
   142             if (_flow[e] == 0) {
   144             if (_flow[e] == 0) {
   143               v = _graph.target(e);
   145               v = _graph.target(e);
   144               switch(heap.state(v)) {
   146               switch(heap.state(v)) {
   145               case Heap::PRE_HEAP:
   147               case Heap::PRE_HEAP:
   157                 break;
   159                 break;
   158               }
   160               }
   159             }
   161             }
   160           }
   162           }
   161 
   163 
   162           // Traversing incoming arcs
   164           // Traverse incoming arcs
   163           for (InArcIt e(_graph, u); e != INVALID; ++e) {
   165           for (InArcIt e(_graph, u); e != INVALID; ++e) {
   164             if (_flow[e] == 1) {
   166             if (_flow[e] == 1) {
   165               v = _graph.source(e);
   167               v = _graph.source(e);
   166               switch(heap.state(v)) {
   168               switch(heap.state(v)) {
   167               case Heap::PRE_HEAP:
   169               case Heap::PRE_HEAP:
   181             }
   183             }
   182           }
   184           }
   183         }
   185         }
   184         if (heap.empty()) return false;
   186         if (heap.empty()) return false;
   185 
   187 
   186         // Updating potentials of processed nodes
   188         // Update potentials of processed nodes
   187         Length t_dist = heap.prio();
   189         Length t_dist = heap.prio();
   188         for (int i = 0; i < int(_proc_nodes.size()); ++i)
   190         for (int i = 0; i < int(_proc_nodes.size()); ++i)
   189           _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
   191           _potential[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;
   190         return true;
   192         return true;
   191       }
   193       }
   192 
   194 
   193     }; //class ResidualDijkstra
   195     }; //class ResidualDijkstra
   194 
   196 
   195   private:
   197   private:
   196 
   198 
   197     // The directed digraph the algorithm runs on
   199     // The digraph the algorithm runs on
   198     const Digraph &_graph;
   200     const Digraph &_graph;
   199     // The length map
   201     // The length map
   200     const LengthMap &_length;
   202     const LengthMap &_length;
   201     
   203     
   202     // Arc map of the current flow
   204     // Arc map of the current flow
   225 
   227 
   226     /// \brief Constructor.
   228     /// \brief Constructor.
   227     ///
   229     ///
   228     /// Constructor.
   230     /// Constructor.
   229     ///
   231     ///
   230     /// \param digraph The directed digraph the algorithm runs on.
   232     /// \param digraph The digraph the algorithm runs on.
   231     /// \param length The length (cost) values of the arcs.
   233     /// \param length The length (cost) values of the arcs.
   232     /// \param s The source node.
   234     /// \param s The source node.
   233     /// \param t The target node.
   235     /// \param t The target node.
   234     Suurballe( const Digraph &digraph,
   236     Suurballe( const Digraph &digraph,
   235                const LengthMap &length,
   237                const LengthMap &length,
   243       if (_local_flow) delete _flow;
   245       if (_local_flow) delete _flow;
   244       if (_local_potential) delete _potential;
   246       if (_local_potential) delete _potential;
   245       delete _dijkstra;
   247       delete _dijkstra;
   246     }
   248     }
   247 
   249 
   248     /// \brief Sets the flow map.
   250     /// \brief Set the flow map.
   249     ///
   251     ///
   250     /// Sets the flow map.
   252     /// This function sets the flow map.
   251     ///
   253     ///
   252     /// The found flow contains only 0 and 1 values. It is the union of
   254     /// The found flow contains only 0 and 1 values. It is the union of
   253     /// the found arc-disjoint paths.
   255     /// the found arc-disjoint paths.
   254     ///
   256     ///
   255     /// \return \c (*this)
   257     /// \return \c (*this)
   260       }
   262       }
   261       _flow = &map;
   263       _flow = &map;
   262       return *this;
   264       return *this;
   263     }
   265     }
   264 
   266 
   265     /// \brief Sets the potential map.
   267     /// \brief Set the potential map.
   266     ///
   268     ///
   267     /// Sets the potential map.
   269     /// This function sets the potential map.
   268     ///
   270     ///
   269     /// The potentials provide the dual solution of the underlying 
   271     /// The potentials provide the dual solution of the underlying 
   270     /// minimum cost flow problem.
   272     /// minimum cost flow problem.
   271     ///
   273     ///
   272     /// \return \c (*this)
   274     /// \return \c (*this)
   286     /// If you only need the flow that is the union of the found
   288     /// If you only need the flow that is the union of the found
   287     /// arc-disjoint paths, you may call init() and findFlow().
   289     /// arc-disjoint paths, you may call init() and findFlow().
   288 
   290 
   289     /// @{
   291     /// @{
   290 
   292 
   291     /// \brief Runs the algorithm.
   293     /// \brief Run the algorithm.
   292     ///
   294     ///
   293     /// Runs the algorithm.
   295     /// This function runs the algorithm.
   294     ///
   296     ///
   295     /// \param k The number of paths to be found.
   297     /// \param k The number of paths to be found.
   296     ///
   298     ///
   297     /// \return \c k if there are at least \c k arc-disjoint paths
   299     /// \return \c k if there are at least \c k arc-disjoint paths from
   298     /// from \c s to \c t. Otherwise it returns the number of
   300     /// \c s to \c t in the digraph. Otherwise it returns the number of
   299     /// arc-disjoint paths found.
   301     /// arc-disjoint paths found.
   300     ///
   302     ///
   301     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
   303     /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
   302     /// shortcut of the following code.
   304     /// shortcut of the following code.
   303     /// \code
   305     /// \code
   310       findFlow(k);
   312       findFlow(k);
   311       findPaths();
   313       findPaths();
   312       return _path_num;
   314       return _path_num;
   313     }
   315     }
   314 
   316 
   315     /// \brief Initializes the algorithm.
   317     /// \brief Initialize the algorithm.
   316     ///
   318     ///
   317     /// Initializes the algorithm.
   319     /// This function initializes the algorithm.
   318     void init() {
   320     void init() {
   319       // Initializing maps
   321       // Initialize maps
   320       if (!_flow) {
   322       if (!_flow) {
   321         _flow = new FlowMap(_graph);
   323         _flow = new FlowMap(_graph);
   322         _local_flow = true;
   324         _local_flow = true;
   323       }
   325       }
   324       if (!_potential) {
   326       if (!_potential) {
   331       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 
   333       _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 
   332                                         *_potential, _pred,
   334                                         *_potential, _pred,
   333                                         _source, _target );
   335                                         _source, _target );
   334     }
   336     }
   335 
   337 
   336     /// \brief Executes the successive shortest path algorithm to find
   338     /// \brief Execute the successive shortest path algorithm to find
   337     /// an optimal flow.
   339     /// an optimal flow.
   338     ///
   340     ///
   339     /// Executes the successive shortest path algorithm to find a
   341     /// This function executes the successive shortest path algorithm to
   340     /// minimum cost flow, which is the union of \c k or less
   342     /// find a minimum cost flow, which is the union of \c k or less
   341     /// arc-disjoint paths.
   343     /// arc-disjoint paths.
   342     ///
   344     ///
   343     /// \return \c k if there are at least \c k arc-disjoint paths
   345     /// \return \c k if there are at least \c k arc-disjoint paths from
   344     /// from \c s to \c t. Otherwise it returns the number of
   346     /// \c s to \c t in the digraph. Otherwise it returns the number of
   345     /// arc-disjoint paths found.
   347     /// arc-disjoint paths found.
   346     ///
   348     ///
   347     /// \pre \ref init() must be called before using this function.
   349     /// \pre \ref init() must be called before using this function.
   348     int findFlow(int k = 2) {
   350     int findFlow(int k = 2) {
   349       // Finding shortest paths
   351       // Find shortest paths
   350       _path_num = 0;
   352       _path_num = 0;
   351       while (_path_num < k) {
   353       while (_path_num < k) {
   352         // Running Dijkstra
   354         // Run Dijkstra
   353         if (!_dijkstra->run()) break;
   355         if (!_dijkstra->run()) break;
   354         ++_path_num;
   356         ++_path_num;
   355 
   357 
   356         // Setting the flow along the found shortest path
   358         // Set the flow along the found shortest path
   357         Node u = _target;
   359         Node u = _target;
   358         Arc e;
   360         Arc e;
   359         while ((e = _pred[u]) != INVALID) {
   361         while ((e = _pred[u]) != INVALID) {
   360           if (u == _graph.target(e)) {
   362           if (u == _graph.target(e)) {
   361             (*_flow)[e] = 1;
   363             (*_flow)[e] = 1;
   367         }
   369         }
   368       }
   370       }
   369       return _path_num;
   371       return _path_num;
   370     }
   372     }
   371     
   373     
   372     /// \brief Computes the paths from the flow.
   374     /// \brief Compute the paths from the flow.
   373     ///
   375     ///
   374     /// Computes the paths from the flow.
   376     /// This function computes the paths from the flow.
   375     ///
   377     ///
   376     /// \pre \ref init() and \ref findFlow() must be called before using
   378     /// \pre \ref init() and \ref findFlow() must be called before using
   377     /// this function.
   379     /// this function.
   378     void findPaths() {
   380     void findPaths() {
   379       // Creating the residual flow map (the union of the paths not
   381       // Create the residual flow map (the union of the paths not found
   380       // found so far)
   382       // so far)
   381       FlowMap res_flow(_graph);
   383       FlowMap res_flow(_graph);
   382       for(ArcIt a(_graph);a!=INVALID;++a) res_flow[a]=(*_flow)[a];
   384       for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
   383 
   385 
   384       paths.clear();
   386       paths.clear();
   385       paths.resize(_path_num);
   387       paths.resize(_path_num);
   386       for (int i = 0; i < _path_num; ++i) {
   388       for (int i = 0; i < _path_num; ++i) {
   387         Node n = _source;
   389         Node n = _source;
   396     }
   398     }
   397 
   399 
   398     /// @}
   400     /// @}
   399 
   401 
   400     /// \name Query Functions
   402     /// \name Query Functions
   401     /// The result of the algorithm can be obtained using these
   403     /// The results of the algorithm can be obtained using these
   402     /// functions.
   404     /// functions.
   403     /// \n The algorithm should be executed before using them.
   405     /// \n The algorithm should be executed before using them.
   404 
   406 
   405     /// @{
   407     /// @{
   406 
   408 
   407     /// \brief Returns a const reference to the arc map storing the
   409     /// \brief Return a const reference to the arc map storing the
   408     /// found flow.
   410     /// found flow.
   409     ///
   411     ///
   410     /// Returns a const reference to the arc map storing the flow that
   412     /// This function returns a const reference to the arc map storing
   411     /// is the union of the found arc-disjoint paths.
   413     /// the flow that is the union of the found arc-disjoint paths.
   412     ///
   414     ///
   413     /// \pre \ref run() or findFlow() must be called before using this
   415     /// \pre \ref run() or \ref findFlow() must be called before using
   414     /// function.
   416     /// this function.
   415     const FlowMap& flowMap() const {
   417     const FlowMap& flowMap() const {
   416       return *_flow;
   418       return *_flow;
   417     }
   419     }
   418 
   420 
   419     /// \brief Returns a const reference to the node map storing the
   421     /// \brief Return a const reference to the node map storing the
   420     /// found potentials (the dual solution).
   422     /// found potentials (the dual solution).
   421     ///
   423     ///
   422     /// Returns a const reference to the node map storing the found
   424     /// This function returns a const reference to the node map storing
   423     /// potentials that provide the dual solution of the underlying 
   425     /// the found potentials that provide the dual solution of the
   424     /// minimum cost flow problem.
   426     /// underlying minimum cost flow problem.
   425     ///
   427     ///
   426     /// \pre \ref run() or findFlow() must be called before using this
   428     /// \pre \ref run() or \ref findFlow() must be called before using
   427     /// function.
   429     /// this function.
   428     const PotentialMap& potentialMap() const {
   430     const PotentialMap& potentialMap() const {
   429       return *_potential;
   431       return *_potential;
   430     }
   432     }
   431 
   433 
   432     /// \brief Returns the flow on the given arc.
   434     /// \brief Return the flow on the given arc.
   433     ///
   435     ///
   434     /// Returns the flow on the given arc.
   436     /// This function returns the flow on the given arc.
   435     /// It is \c 1 if the arc is involved in one of the found paths,
   437     /// It is \c 1 if the arc is involved in one of the found paths,
   436     /// otherwise it is \c 0.
   438     /// otherwise it is \c 0.
   437     ///
   439     ///
   438     /// \pre \ref run() or findFlow() must be called before using this
   440     /// \pre \ref run() or \ref findFlow() must be called before using
   439     /// function.
   441     /// this function.
   440     int flow(const Arc& arc) const {
   442     int flow(const Arc& arc) const {
   441       return (*_flow)[arc];
   443       return (*_flow)[arc];
   442     }
   444     }
   443 
   445 
   444     /// \brief Returns the potential of the given node.
   446     /// \brief Return the potential of the given node.
   445     ///
   447     ///
   446     /// Returns the potential of the given node.
   448     /// This function returns the potential of the given node.
   447     ///
   449     ///
   448     /// \pre \ref run() or findFlow() must be called before using this
   450     /// \pre \ref run() or \ref findFlow() must be called before using
   449     /// function.
   451     /// this function.
   450     Length potential(const Node& node) const {
   452     Length potential(const Node& node) const {
   451       return (*_potential)[node];
   453       return (*_potential)[node];
   452     }
   454     }
   453 
   455 
   454     /// \brief Returns the total length (cost) of the found paths (flow).
   456     /// \brief Return the total length (cost) of the found paths (flow).
   455     ///
   457     ///
   456     /// Returns the total length (cost) of the found paths (flow).
   458     /// This function returns the total length (cost) of the found paths
   457     /// The complexity of the function is \f$ O(e) \f$.
   459     /// (flow). The complexity of the function is \f$ O(e) \f$.
   458     ///
   460     ///
   459     /// \pre \ref run() or findFlow() must be called before using this
   461     /// \pre \ref run() or \ref findFlow() must be called before using
   460     /// function.
   462     /// this function.
   461     Length totalLength() const {
   463     Length totalLength() const {
   462       Length c = 0;
   464       Length c = 0;
   463       for (ArcIt e(_graph); e != INVALID; ++e)
   465       for (ArcIt e(_graph); e != INVALID; ++e)
   464         c += (*_flow)[e] * _length[e];
   466         c += (*_flow)[e] * _length[e];
   465       return c;
   467       return c;
   466     }
   468     }
   467 
   469 
   468     /// \brief Returns the number of the found paths.
   470     /// \brief Return the number of the found paths.
   469     ///
   471     ///
   470     /// Returns the number of the found paths.
   472     /// This function returns the number of the found paths.
   471     ///
   473     ///
   472     /// \pre \ref run() or findFlow() must be called before using this
   474     /// \pre \ref run() or \ref findFlow() must be called before using
   473     /// function.
   475     /// this function.
   474     int pathNum() const {
   476     int pathNum() const {
   475       return _path_num;
   477       return _path_num;
   476     }
   478     }
   477 
   479 
   478     /// \brief Returns a const reference to the specified path.
   480     /// \brief Return a const reference to the specified path.
   479     ///
   481     ///
   480     /// Returns a const reference to the specified path.
   482     /// This function returns a const reference to the specified path.
   481     ///
   483     ///
   482     /// \param i The function returns the \c i-th path.
   484     /// \param i The function returns the \c i-th path.
   483     /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   485     /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   484     ///
   486     ///
   485     /// \pre \ref run() or findPaths() must be called before using this
   487     /// \pre \ref run() or \ref findPaths() must be called before using
   486     /// function.
   488     /// this function.
   487     Path path(int i) const {
   489     Path path(int i) const {
   488       return paths[i];
   490       return paths[i];
   489     }
   491     }
   490 
   492 
   491     /// @}
   493     /// @}