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,

                                                    _UCapMap, _DeltaMap> >

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

    bool barrier(const Node& node)

    {

      return (*_level)[node] >= _el;

    }

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

    /// The feasibility of the results can be checked using

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