RhodeCode

  /// \tparam _Digraph Digraph type.

  /// \tparam _CapacityMap Capacity map type.

  template <typename _Digraph, typename _CapacityMap>

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

    typedef _Digraph Digraph;

    /// \brief The type of the flow values.

    /// \brief The type of the map that stores the flow values.

    /// The type of the map that stores the flow values.

    /// \brief The elevator type used by Preflow algorithm.

    /// This function instantiates an \ref Elevator.

  /// \brief %Preflow algorithm class.

  /// This class provides an implementation of Goldberg-Tarjan's \e preflow

  /// \e push-relabel algorithm producing a flow of maximum value in a

  /// digraph. The preflow algorithms are the fastest known maximum

  /// The algorithm consists of two phases. After the first phase

  /// the maximum flow value and the minimum cut is obtained. The

  /// second phase constructs a feasible maximum flow on each arc.

  /// \tparam _Digraph The type of the digraph the algorithm runs on.

  /// \tparam _CapacityMap The type of the capacity map. The default map

  /// type is \ref concepts::Digraph::ArcMap "_Digraph::ArcMap<int>".

  template <typename _Digraph, typename _CapacityMap, typename _Traits>

  template <typename _Digraph,

            typename _CapacityMap = typename _Digraph::template ArcMap<int>,

            typename _Traits = PreflowDefaultTraits<_Digraph, _CapacityMap> >

    ///The \ref PreflowDefaultTraits "traits class" of the algorithm.

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

    ///The type of the capacity map.

    ///The type of the flow values.

    ///The type of the flow map.

    ///The type of the elevator.

    ///The type of the tolerance.

    ///\name Named Template Parameters

    /// type.

    /// type. If this named parameter is used, then an external

    /// elevator object must be passed to the algorithm using the

    /// \ref elevator(Elevator&) "elevator()" function before calling

    /// \ref run() or \ref init().

    /// \sa SetStandardElevator

    /// Elevator type with automatic allocation

    /// type with automatic allocation.

    /// The Elevator should have standard constructor interface to be

    /// able to automatically created by the algorithm (i.e. the

    /// digraph and the maximum level should be passed to it).

    /// However an external elevator object could also be passed to the

    /// algorithm with the \ref elevator(Elevator&) "elevator()" function

    /// before calling \ref run() or \ref init().

    /// \sa SetElevator

    /// \brief Destructor.

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

    /// If you don't use this function before calling \ref run() or

    /// \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

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

    /// \brief Sets the source node.

    /// Sets the source node.

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

    Preflow& source(const Node& node) {

      _source = node;

      return *this;

    /// \brief Sets the target node.

    /// Sets the target node.

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

    Preflow& target(const Node& node) {

      _target = node;

      return *this;

    }

    /// \brief Sets the elevator used by algorithm.

    ///

    /// Sets the elevator used by algorithm.

    /// If you don't use this function before calling \ref run() or

    /// \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated elevator,

    /// of course.

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

    /// \brief Returns a const reference to the elevator.

    /// Returns a const reference to the elevator.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    /// \brief Returns a const reference to the tolerance.

    /// Returns a const reference to the tolerance.

    /// \name Execution Control

    /// The simplest way to execute the preflow algorithm is to use

    /// \ref run() or \ref runMinCut().\n

    /// If you need more control on the initial solution or the execution,

    /// first you have to call one of the \ref init() functions, then

    /// \ref startFirstPhase() and if you need it \ref startSecondPhase().

    /// Initializes the internal data structures and sets the initial

    /// flow to zero on each arc.

    /// \brief Initializes the internal data structures using the

    /// given flow map.

    /// flow or at least a preflow, i.e. at each node excluding the

    /// source node the incoming flow should greater or equal to the

    /// \return \c false if the given \c flowMap is not a preflow.

    /// \pre One of the \ref init() functions must be called before

    /// using this function.

    /// the second phase. After calling one of the \ref init() functions

    /// and \ref startFirstPhase() and then \ref startSecondPhase(),

    /// \ref flowMap() returns a maximum flow, \ref flowValue() returns the

    /// \pre One of the \ref init() functions and \ref startFirstPhase()

    /// must be called before using this function.

    /// The results of the preflow algorithm can be obtained using these

    /// Either one of the \ref run() "run*()" functions or one of the

    /// \ref startFirstPhase() "start*()" functions should be called

    /// before using them.

    /// of the target node. This value equals to the value of

    /// the maximum flow already after the first phase of the algorithm.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    /// \brief Returns the flow on the given arc.

    /// Returns the flow on the given arc. This method can

    /// be called after the second phase of the algorithm.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    Value flow(const Arc& arc) const {

      return (*_flow)[arc];

    }

    /// \brief Returns a const reference to the flow map.

    ///

    /// Returns a const reference to the arc map storing the found flow.

    /// This method can be called after the second phase of the algorithm.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    const FlowMap& flowMap() {

      return *_flow;

    }

    /// \brief Returns \c true when the node is on the source side of the

    /// minimum cut.

    ///

    /// Returns true when the node is on the source side of the found

    /// minimum cut. This method can be called both after running \ref

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    /// \brief Gives back a minimum value cut.

    /// Sets \c cutMap to the characteristic vector of a minimum value

    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"

    /// node map with \c bool (or convertible) value type.

    ///

    /// This method can be called both after running \ref startFirstPhase()

    /// and \ref startSecondPhase(). The result after the second phase

    /// could be slightly different if inexact computation is used.

    ///

    /// \note This function calls \ref minCut() for each node, so it runs in

    /// \f$O(n)\f$ time.

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.