lemon/preflow.h
changeset 692 33f417de9e70
parent 688 1f08e846df29
child 715 ece80147fb08
equal deleted inserted replaced
13:1646da5e2922 14:02e85a1e1711
    95   ///
    95   ///
    96   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    96   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
    97   /// \e push-relabel algorithm producing a \ref max_flow
    97   /// \e push-relabel algorithm producing a \ref max_flow
    98   /// "flow of maximum value" in a digraph.
    98   /// "flow of maximum value" in a digraph.
    99   /// The preflow algorithms are the fastest known maximum
    99   /// The preflow algorithms are the fastest known maximum
   100   /// flow algorithms. The current implementation use a mixture of the
   100   /// flow algorithms. The current implementation uses a mixture of the
   101   /// \e "highest label" and the \e "bound decrease" heuristics.
   101   /// \e "highest label" and the \e "bound decrease" heuristics.
   102   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   102   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   103   ///
   103   ///
   104   /// The algorithm consists of two phases. After the first phase
   104   /// The algorithm consists of two phases. After the first phase
   105   /// the maximum flow value and the minimum cut is obtained. The
   105   /// the maximum flow value and the minimum cut is obtained. The
   369     /// using this function.
   369     /// using this function.
   370     const Elevator& elevator() const {
   370     const Elevator& elevator() const {
   371       return *_level;
   371       return *_level;
   372     }
   372     }
   373 
   373 
   374     /// \brief Sets the tolerance used by algorithm.
   374     /// \brief Sets the tolerance used by the algorithm.
   375     ///
   375     ///
   376     /// Sets the tolerance used by algorithm.
   376     /// Sets the tolerance object used by the algorithm.
       
   377     /// \return <tt>(*this)</tt>
   377     Preflow& tolerance(const Tolerance& tolerance) {
   378     Preflow& tolerance(const Tolerance& tolerance) {
   378       _tolerance = tolerance;
   379       _tolerance = tolerance;
   379       return *this;
   380       return *this;
   380     }
   381     }
   381 
   382 
   382     /// \brief Returns a const reference to the tolerance.
   383     /// \brief Returns a const reference to the tolerance.
   383     ///
   384     ///
   384     /// Returns a const reference to the tolerance.
   385     /// Returns a const reference to the tolerance object used by
       
   386     /// the algorithm.
   385     const Tolerance& tolerance() const {
   387     const Tolerance& tolerance() const {
   386       return _tolerance;
   388       return _tolerance;
   387     }
   389     }
   388 
   390 
   389     /// \name Execution Control
   391     /// \name Execution Control