RhodeCode

#include <vector>

#include <limits>

#include <lemon/bin_heap.h>

#include <lemon/path.h>

#include <lemon/list_graph.h>

#include <lemon/maps.h>

namespace lemon {

  /// \addtogroup shortest_path

  /// @{

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// having minimum total length.

  ///

  /// \ref lemon::Suurballe "Suurballe" implements an algorithm for

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  /// Note that this problem is a special case of the \ref min_cost_flow

  /// "minimum cost flow problem". This implementation is actually an

  /// efficient specialized version of the \ref CapacityScaling

  /// "Successive Shortest Path" algorithm directly for this problem.

  /// Therefore this class provides query functions for flow values and

  /// node potentials (the dual solution) just like the minimum cost flow

  /// algorithms.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

  /// \tparam LEN The type of the length map.

  /// The default value is <tt>GR::ArcMap<int></tt>.

  ///

  ///

  /// \note For finding node-disjoint paths this algorithm can be used

  /// along with the \ref SplitNodes adaptor.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int> >

#endif

  class Suurballe

  {

    TEMPLATE_DIGRAPH_TYPEDEFS(GR);

    typedef ConstMap<Arc, int> ConstArcMap;

    typedef typename GR::template NodeMap<Arc> PredMap;

  public:

    /// The type of the digraph the algorithm runs on.

    typedef GR Digraph;

    /// The type of the length map.

    typedef LEN LengthMap;

    /// The type of the lengths.

    typedef typename LengthMap::Value Length;

#ifdef DOXYGEN

    /// The type of the flow map.

    typedef GR::ArcMap<int> FlowMap;

    /// The type of the potential map.

    typedef GR::NodeMap<Length> PotentialMap;

#else

    /// The type of the flow map.

    typedef typename Digraph::template ArcMap<int> FlowMap;

    bool _local_flow;

    // Node map of the current potentials

    PotentialMap *_potential;

    bool _local_potential;

    // The source node

    Node _source;

    // The target node

    Node _target;

    // Container to store the found paths

    std::vector< SimplePath<Digraph> > paths;

    int _path_num;

    // The pred arc map

    PredMap _pred;

    // Implementation of the Dijkstra algorithm for finding augmenting

    // shortest paths in the residual network

    ResidualDijkstra *_dijkstra;

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    ///

    /// \param graph The digraph the algorithm runs on.

    /// \param length The length (cost) values of the arcs.

    Suurballe( const Digraph &graph,

               const LengthMap &length ) :

      _graph(graph), _length(length), _flow(0), _local_flow(false),

      _potential(0), _local_potential(false), _pred(graph)

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

      delete _dijkstra;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    /// If it is not used before calling \ref run() or \ref init(),

    /// an instance will be allocated automatically. The destructor

    /// deallocates this automatically allocated map, of course.

    ///

    /// The found flow contains only 0 and 1 values, since it is the

    /// union of the found arc-disjoint paths.

    ///

    /// \return <tt>(*this)</tt>

    Suurballe& flowMap(FlowMap &map) {

      if (_local_flow) {

        delete _flow;

        _local_flow = false;

      }

      _flow = ↦

      return *this;

    }

    /// \brief Set the potential map.

    ///

    /// This function sets the potential map.

    /// If it is not used before calling \ref run() or \ref init(),