RhodeCode

    ///@}

    /// \name Query Functions

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

    /// functions.\n

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

    /// before using them.

    ///@{

    /// \brief Checks if a node is reached from the root(s).

    ///

    /// Returns \c true if \c v is reached from the root(s).

    ///

    /// \pre Either \ref run(Node) "run()" or \ref init()

    /// must be called before using this function.

    ///@}

  };

} //END OF NAMESPACE LEMON

#endif

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

    Circulation& elevator(Elevator& elevator) {

      if (_local_level) {

        delete _level;

        _local_level = false;

      }

      _level = &elevator;

      return *this;

    }

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

      return *_level;

    }

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

    ///

    /// Sets the tolerance used by algorithm.

    Circulation& tolerance(const Tolerance& tolerance) const {

      _tol = tolerance;

      return *this;

    }

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

    ///

    /// Returns a const reference to the tolerance.

    const Tolerance& tolerance() const {

      return tolerance;

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

      return *_flow;

    }

    /**

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

       Barrier is a set \e B of nodes for which

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

       \sa checkBarrier()

    */

    {

      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>

    {

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

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

    }

    /// @}

    /// \name Checker Functions

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

    ///

      for(ArcIt e(_g);e!=INVALID;++e)

        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;

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

        {

          Value dif=-(*_delta)[n];

          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];

          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];

          if(_tol.negative(dif)) return false;

        }

      return true;

    }

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

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

    ///\sa barrier()

    ///\sa barrierMap()

    {

      Value delta=0;

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

        if(barrier(n))

          delta-=(*_delta)[n];

      for(ArcIt e(_g);e!=INVALID;++e)

        {

          Node s=_g.source(e);

          Node t=_g.target(e);

          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];

          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];

        }

      return _tol.negative(delta);

    }

    /// @}

    ///@}

    /// \name Query Functions

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

    /// functions.\n

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

    /// before using them.

    ///@{

    /// \brief Checks if a node is reached from the root(s).

    ///

    /// Returns \c true if \c v is reached from the root(s).

    ///

    /// \pre Either \ref run(Node) "run()" or \ref init()

    /// must be called before using this function.

    ///@}

  };

} //END OF NAMESPACE LEMON

#endif

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

    Preflow& elevator(Elevator& elevator) {

      if (_local_level) {

        delete _level;

        _local_level = false;

      }

      _level = &elevator;

      return *this;

    }

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

      return *_level;

    }

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

    ///

    /// Sets the tolerance used by algorithm.

    Preflow& tolerance(const Tolerance& tolerance) const {

      _tolerance = tolerance;

      return *this;

    }

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

    ///

    /// Returns a const reference to the tolerance.

    const Tolerance& tolerance() const {

      return tolerance;

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

      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

    /// startFirstPhase() and \ref startSecondPhase().

    ///

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

    /// using this function.

    bool minCut(const Node& node) const {

      return ((*_level)[node] == _level->maxLevel()) == _phase;

    }