RhodeCode

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

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

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

        }

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

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

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