lemon/preflow.h
changeset 715 ece80147fb08
parent 713 4ac30454f1c1
parent 689 86c49553fea5
child 755 134852d7fb0a
child 786 e20173729589
equal deleted inserted replaced
15:4494339d77b4 16:535eb53dc0b2
   102   ///
   102   ///
   103   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   103   /// This class provides an implementation of Goldberg-Tarjan's \e preflow
   104   /// \e push-relabel algorithm producing a \ref max_flow
   104   /// \e push-relabel algorithm producing a \ref max_flow
   105   /// "flow of maximum value" in a digraph.
   105   /// "flow of maximum value" in a digraph.
   106   /// The preflow algorithms are the fastest known maximum
   106   /// The preflow algorithms are the fastest known maximum
   107   /// flow algorithms. The current implementation use a mixture of the
   107   /// flow algorithms. The current implementation uses a mixture of the
   108   /// \e "highest label" and the \e "bound decrease" heuristics.
   108   /// \e "highest label" and the \e "bound decrease" heuristics.
   109   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   109   /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$.
   110   ///
   110   ///
   111   /// The algorithm consists of two phases. After the first phase
   111   /// The algorithm consists of two phases. After the first phase
   112   /// the maximum flow value and the minimum cut is obtained. The
   112   /// the maximum flow value and the minimum cut is obtained. The
   376     /// using this function.
   376     /// using this function.
   377     const Elevator& elevator() const {
   377     const Elevator& elevator() const {
   378       return *_level;
   378       return *_level;
   379     }
   379     }
   380 
   380 
   381     /// \brief Sets the tolerance used by algorithm.
   381     /// \brief Sets the tolerance used by the algorithm.
   382     ///
   382     ///
   383     /// Sets the tolerance used by algorithm.
   383     /// Sets the tolerance object used by the algorithm.
   384     Preflow& tolerance(const Tolerance& tolerance) const {
   384     /// \return <tt>(*this)</tt>
       
   385     Preflow& tolerance(const Tolerance& tolerance) {
   385       _tolerance = tolerance;
   386       _tolerance = tolerance;
   386       return *this;
   387       return *this;
   387     }
   388     }
   388 
   389 
   389     /// \brief Returns a const reference to the tolerance.
   390     /// \brief Returns a const reference to the tolerance.
   390     ///
   391     ///
   391     /// Returns a const reference to the tolerance.
   392     /// Returns a const reference to the tolerance object used by
       
   393     /// the algorithm.
   392     const Tolerance& tolerance() const {
   394     const Tolerance& tolerance() const {
   393       return tolerance;
   395       return _tolerance;
   394     }
   396     }
   395 
   397 
   396     /// \name Execution Control
   398     /// \name Execution Control
   397     /// The simplest way to execute the preflow algorithm is to use
   399     /// The simplest way to execute the preflow algorithm is to use
   398     /// \ref run() or \ref runMinCut().\n
   400     /// \ref run() or \ref runMinCut().\n