RhodeCode

  /// 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 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);

  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(),

      return _path_num;

    }

    /// \brief Return a const reference to the specified path.

    ///

    /// This function returns a const reference to the specified path.

    ///

    /// \param i The function returns the <tt>i</tt>-th path.

    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.

    ///

    /// \pre \ref run() or \ref findPaths() must be called before using

    /// this function.

      return paths[i];

    }

    /// @}

  }; //class Suurballe

  ///@}

} //namespace lemon

#endif //LEMON_SUURBALLE_H