1.1 --- a/lemon/hao_orlin.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/hao_orlin.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -53,8 +53,8 @@
1.13 /// minimum cut of \f$ D \f$. The algorithm is a modified
1.14 /// preflow push-relabel algorithm. Our implementation calculates
1.15 /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the
1.16 - /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The
1.17 - /// purpose of such algorithm is e.g. testing network reliability.
1.18 + /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable
1.19 + /// use of this algorithm is testing network reliability.
1.20 ///
1.21 /// For an undirected graph you can run just the first phase of the
1.22 /// algorithm or you can use the algorithm of Nagamochi and Ibaraki,
1.23 @@ -912,6 +912,8 @@
1.24 /// This function calculates a minimum cut with \f$ source \f$ on the
1.25 /// source-side (i.e. a set \f$ X\subsetneq V \f$ with
1.26 /// \f$ source \in 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 calculateOut() {
1.32 @@ -924,6 +926,8 @@
1.33 /// This function calculates a minimum cut with \f$ source \f$ on the
1.34 /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with
1.35 /// \f$ source \notin X \f$ and minimal outgoing capacity).
1.36 + /// It updates the stored cut if (and only if) the newly found one
1.37 + /// is better.
1.38 ///
1.39 /// \pre \ref init() must be called before using this function.
1.40 void calculateIn() {
1.41 @@ -933,8 +937,8 @@
1.42
1.43 /// \brief Run the algorithm.
1.44 ///
1.45 - /// This function runs the algorithm. It finds nodes \c source and
1.46 - /// \c target arbitrarily and then calls \ref init(), \ref calculateOut()
1.47 + /// This function runs the algorithm. It chooses source node,
1.48 + /// then calls \ref init(), \ref calculateOut()
1.49 /// and \ref calculateIn().
1.50 void run() {
1.51 init();
1.52 @@ -944,9 +948,9 @@
1.53
1.54 /// \brief Run the algorithm.
1.55 ///
1.56 - /// This function runs the algorithm. It uses the given \c source node,
1.57 - /// finds a proper \c target node and then calls the \ref init(),
1.58 - /// \ref calculateOut() and \ref calculateIn().
1.59 + /// This function runs the algorithm. It calls \ref init(),
1.60 + /// \ref calculateOut() and \ref calculateIn() with the given
1.61 + /// source node.
1.62 void run(const Node& s) {
1.63 init(s);
1.64 calculateOut();
1.65 @@ -965,7 +969,9 @@
1.66
1.67 /// \brief Return the value of the minimum cut.
1.68 ///
1.69 - /// This function returns the value of the minimum cut.
1.70 + /// This function returns the value of the best cut found by the
1.71 + /// previously called \ref run(), \ref calculateOut() or \ref
1.72 + /// calculateIn().
1.73 ///
1.74 /// \pre \ref run(), \ref calculateOut() or \ref calculateIn()
1.75 /// must be called before using this function.
1.76 @@ -976,9 +982,13 @@
1.77
1.78 /// \brief Return a minimum cut.
1.79 ///
1.80 - /// This function sets \c cutMap to the characteristic vector of a
1.81 - /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$
1.82 - /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly
1.83 + /// This function gives the best cut found by the
1.84 + /// previously called \ref run(), \ref calculateOut() or \ref
1.85 + /// calculateIn().
1.86 + ///
1.87 + /// It sets \c cutMap to the characteristic vector of the found
1.88 + /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$
1.89 + /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly
1.90 /// for the nodes of \f$ X \f$).
1.91 ///
1.92 /// \param cutMap A \ref concepts::WriteMap "writable" node map with