RhodeCode

///\brief Push-relabel algorithm for finding a feasible circulation.

  /// \tparam _Diraph Digraph type.

  /// \tparam _LCapMap Lower bound capacity map type.

  /// \tparam _UCapMap Upper bound capacity map type.

  /// \tparam _DeltaMap Delta map type.

  template <typename _Diraph, typename _LCapMap,

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

    typedef _Diraph Digraph;

    /// \brief The type of the map that stores the lower bound for

    /// the supply of the nodes.

    /// The type of the map that stores the lower bound for the supply

    /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap"

    /// \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 the algorithm.

    /// The elevator type used by the algorithm.

    /// This function instantiates an \ref Elevator.

  /**

     \brief Push-relabel algorithm for the network circulation problem.

     This class implements a push-relabel algorithm for the network

     circulation problem.

     It is to find a feasible circulation when lower and upper bounds

     are given for the flow values on the arcs and lower bounds

     are given for the supply values of the nodes.

     Let \f$G=(V,A)\f$ be a digraph,

     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,

     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation

     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that

     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)

     \geq delta(v) \quad \forall v\in V, \f]

     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]

     \note \f$delta(v)\f$ specifies a lower bound for the supply of node

     \f$v\f$. It can be either positive or negative, however note that

     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to

     have a feasible solution.

     \note A special case of this problem is when

     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$

     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.

     Thus a feasible solution for the

     \ref min_cost_flow "minimum cost flow" problem can be calculated

     in this way.

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

     \tparam _LCapMap The type of the lower bound capacity map. The default

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

     \tparam _UCapMap The type of the upper bound capacity map. The default

     map type is \c _LCapMap.

     \tparam _DeltaMap The type of the map that stores the lower bound

     for the supply of the nodes. The default map type is

     \c _Digraph::ArcMap<_UCapMap::Value>.

#ifdef DOXYGEN

template< typename _Digraph,

          typename _LCapMap,

          typename _UCapMap,

          typename _DeltaMap,

          typename _Traits >

#else

template< typename _Digraph,

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

          typename _UCapMap = _LCapMap,

          typename _DeltaMap = typename _Digraph::

                               template NodeMap<typename _UCapMap::Value>,

          typename _Traits=CirculationDefaultTraits<_Digraph, _LCapMap,

#endif

  public:

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

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

    ///The type of the flow values.

    /// The type of the lower bound capacity map.

    /// The type of the upper bound capacity map.

    /// \brief The type of the map that stores the lower bound for

    /// the supply of the nodes.

    ///The type of the flow map.

    ///The type of the elevator.

    ///The type of the tolerance.

  private:

    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);

    typedef typename Digraph::template NodeMap<Value> ExcessMap;

    ///\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

    /// \param delta The lower bound for the supply of the nodes.

    /// Destructor.

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

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

    /// Sets the lower bound map for the supply of the nodes.

    /// Sets the lower bound map for the supply of the nodes.

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

    /// \brief Sets the flow map.

    ///

    /// 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 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 Sets the tolerance used by algorithm.

    ///

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

    /// Returns a const reference to the tolerance.

    /// \name Execution Control

    /// The simplest way to execute the algorithm is to call \ref run().\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

    /// the \ref start() function.

    /// Initializes the internal data structures and sets all flow values

    /// to the lower bound.

    /// Initializes the internal data structures using a greedy approach.

    /// Initializes the internal data structures using a greedy approach

    /// to construct the initial solution.

    ///Executes the algorithm

    ///This function executes the algorithm.

    ///

    ///\return \c true if a feasible circulation is found.

    ///\sa barrierMap()

    /// Runs the algorithm.

    /// This function runs the algorithm.

    ///

    /// \return \c true if a feasible circulation is found.

    ///

    /// \note Apart from the return value, c.run() is just a shortcut of

    /// the following code.

    ///   c.greedyInit();

    ///   c.start();

    /// The results of the circulation algorithm can be obtained using

    /// these functions.\n

    /// Either \ref run() or \ref start() should be called before

    /// using them.

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

    ///

    /// Returns the flow on the given arc.

    ///

    /// \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.

    ///

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

    /// using this function.

    const FlowMap& flowMap() {

      return *_flow;

    }

       \brief Returns \c true if the given node is in a barrier.

       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -

           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]

       holds. The existence of a set with this property prooves that a

       feasible circualtion cannot exist.

       This function returns \c true if the given node is in the found

       barrier. If a feasible circulation is found, the function

       gives back \c false for every node.

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

       using this function.

       \sa barrierMap()

    /// \brief Gives back a barrier.

    /// This function sets \c bar to the characteristic vector of the

    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"

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

    ///

    /// If a feasible circulation is found, the function gives back an

    /// empty set, so \c bar[v] will be \c false for all nodes \c v.

    ///

    /// \note This function calls \ref barrier() 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.

    ///

    /// \sa barrier()

    /// \sa checkBarrier()

    template<class BarrierMap>

    void barrierMap(BarrierMap &bar)

    {

      for(NodeIt n(_g);n!=INVALID;++n)

        bar.set(n, (*_level)[n] >= _el);

    /// these functions.\n

    /// Either \ref run() or \ref start() should be called before

    /// using them.

    ///Check if the found flow is a feasible circulation

    ///Check if the found flow is a feasible circulation,

    ///

    ///Check whether or not the last execution provides a barrier.

    ///\sa barrierMap()