lemon/hao_orlin.h
changeset 917 4980b05606bd
parent 877 141f9c0db4a3
child 1092 dceba191c00d
     1.1 --- a/lemon/hao_orlin.h	Mon Nov 15 22:23:35 2010 +0100
     1.2 +++ b/lemon/hao_orlin.h	Tue Nov 16 07:46:01 2010 +0100
     1.3 @@ -53,8 +53,8 @@
     1.4    /// minimum cut of \f$ D \f$. The algorithm is a modified
     1.5    /// preflow push-relabel algorithm. Our implementation calculates
     1.6    /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
     1.7 -  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
     1.8 -  /// purpose of such algorithm is e.g. testing network reliability.
     1.9 +  /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
    1.10 +  /// use of this algorithm is testing network reliability.
    1.11    ///
    1.12    /// For an undirected graph you can run just the first phase of the
    1.13    /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
    1.14 @@ -912,6 +912,8 @@
    1.15      /// This function calculates a minimum cut with \f$ source \f$ on the
    1.16      /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
    1.17      /// \f$ source \in X \f$ and minimal outgoing capacity).
    1.18 +    /// It updates the stored cut if (and only if) the newly found one
    1.19 +    /// is better.
    1.20      ///
    1.21      /// \pre \ref init() must be called before using this function.
    1.22      void calculateOut() {
    1.23 @@ -924,6 +926,8 @@
    1.24      /// This function calculates a minimum cut with \f$ source \f$ on the
    1.25      /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
    1.26      /// \f$ source \notin X \f$ and minimal outgoing capacity).
    1.27 +    /// It updates the stored cut if (and only if) the newly found one
    1.28 +    /// is better.
    1.29      ///
    1.30      /// \pre \ref init() must be called before using this function.
    1.31      void calculateIn() {
    1.32 @@ -933,8 +937,8 @@
    1.33  
    1.34      /// \brief Run the algorithm.
    1.35      ///
    1.36 -    /// This function runs the algorithm. It finds nodes \c source and
    1.37 -    /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
    1.38 +    /// This function runs the algorithm. It chooses source node,
    1.39 +    /// then calls \ref init(), \ref calculateOut()
    1.40      /// and \ref calculateIn().
    1.41      void run() {
    1.42        init();
    1.43 @@ -944,9 +948,9 @@
    1.44  
    1.45      /// \brief Run the algorithm.
    1.46      ///
    1.47 -    /// This function runs the algorithm. It uses the given \c source node,
    1.48 -    /// finds a proper \c target node and then calls the \ref init(),
    1.49 -    /// \ref calculateOut() and \ref calculateIn().
    1.50 +    /// This function runs the algorithm. It calls \ref init(),
    1.51 +    /// \ref calculateOut() and \ref calculateIn() with the given
    1.52 +    /// source node.
    1.53      void run(const Node& s) {
    1.54        init(s);
    1.55        calculateOut();
    1.56 @@ -965,7 +969,9 @@
    1.57  
    1.58      /// \brief Return the value of the minimum cut.
    1.59      ///
    1.60 -    /// This function returns the value of the minimum cut.
    1.61 +    /// This function returns the value of the best cut found by the
    1.62 +    /// previously called \ref run(), \ref calculateOut() or \ref
    1.63 +    /// calculateIn().
    1.64      ///
    1.65      /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
    1.66      /// must be called before using this function.
    1.67 @@ -976,9 +982,13 @@
    1.68  
    1.69      /// \brief Return a minimum cut.
    1.70      ///
    1.71 -    /// This function sets \c cutMap to the characteristic vector of a
    1.72 -    /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
    1.73 -    /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
    1.74 +    /// This function gives the best cut found by the
    1.75 +    /// previously called \ref run(), \ref calculateOut() or \ref
    1.76 +    /// calculateIn().
    1.77 +    ///
    1.78 +    /// It sets \c cutMap to the characteristic vector of the found
    1.79 +    /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
    1.80 +    /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
    1.81      /// for the nodes of \f$ X \f$).
    1.82      ///
    1.83      /// \param cutMap A \ref concepts::WriteMap "writable" node map with