1.1 --- a/lemon/cycle_canceling.h Thu Sep 13 12:23:46 2012 +0200
1.2 +++ b/lemon/cycle_canceling.h Wed Nov 07 17:39:39 2012 +0100
1.3 @@ -48,11 +48,12 @@
1.4 /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
1.5 /// \ref amo93networkflows, \ref klein67primal,
1.6 /// \ref goldberg89cyclecanceling.
1.7 - /// The most efficent one (both theoretically and practically)
1.8 - /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
1.9 - /// thus it is the default method.
1.10 - /// It is strongly polynomial, but in practice, it is typically much
1.11 - /// slower than the scaling algorithms and NetworkSimplex.
1.12 + /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
1.13 + /// "Cancel-and-Tighten" algorithm, thus it is the default method.
1.14 + /// It runs in strongly polynomial time, but in practice, it is typically
1.15 + /// orders of magnitude slower than the scaling algorithms and
1.16 + /// \ref NetworkSimplex.
1.17 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
1.18 ///
1.19 /// Most of the parameters of the problem (except for the digraph)
1.20 /// can be given using separate functions, and the algorithm can be
1.21 @@ -116,26 +117,28 @@
1.22 /// for the \ref run() function.
1.23 ///
1.24 /// \ref CycleCanceling provides three different cycle-canceling
1.25 - /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
1.26 + /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
1.27 /// is used, which is by far the most efficient and the most robust.
1.28 /// However, the other methods can be selected using the \ref run()
1.29 /// function with the proper parameter.
1.30 enum Method {
1.31 /// A simple cycle-canceling method, which uses the
1.32 - /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
1.33 - /// number for detecting negative cycles in the residual network.
1.34 + /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
1.35 + /// cycles in the residual network.
1.36 + /// The number of Bellman-Ford iterations is bounded by a successively
1.37 + /// increased limit.
1.38 SIMPLE_CYCLE_CANCELING,
1.39 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
1.40 /// well-known strongly polynomial method
1.41 /// \ref goldberg89cyclecanceling. It improves along a
1.42 /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
1.43 - /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
1.44 + /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
1.45 MINIMUM_MEAN_CYCLE_CANCELING,
1.46 - /// The "Cancel And Tighten" algorithm, which can be viewed as an
1.47 + /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
1.48 /// improved version of the previous method
1.49 /// \ref goldberg89cyclecanceling.
1.50 /// It is faster both in theory and in practice, its running time
1.51 - /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
1.52 + /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
1.53 CANCEL_AND_TIGHTEN
1.54 };
1.55
1.56 @@ -610,7 +613,8 @@
1.57 return _res_cap[_arc_idb[a]];
1.58 }
1.59
1.60 - /// \brief Return the flow map (the primal solution).
1.61 + /// \brief Copy the flow values (the primal solution) into the
1.62 + /// given map.
1.63 ///
1.64 /// This function copies the flow value on each arc into the given
1.65 /// map. The \c Value type of the algorithm must be convertible to
1.66 @@ -634,7 +638,8 @@
1.67 return static_cast<Cost>(_pi[_node_id[n]]);
1.68 }
1.69
1.70 - /// \brief Return the potential map (the dual solution).
1.71 + /// \brief Copy the potential values (the dual solution) into the
1.72 + /// given map.
1.73 ///
1.74 /// This function copies the potential (dual value) of each node
1.75 /// into the given map.
1.76 @@ -954,7 +959,7 @@
1.77 }
1.78 }
1.79
1.80 - // Execute the "Cancel And Tighten" method
1.81 + // Execute the "Cancel-and-Tighten" method
1.82 void startCancelAndTighten() {
1.83 // Constants for the min mean cycle computations
1.84 const double LIMIT_FACTOR = 1.0;