1.1 --- a/doc/groups.dox Mon Jan 30 23:24:14 2012 +0100
1.2 +++ b/doc/groups.dox Mon Jan 30 23:24:40 2012 +0100
1.3 @@ -407,7 +407,12 @@
1.4 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
1.5
1.6 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
1.7 -implementations, but the other algorithms could be faster in special cases.
1.8 +implementations.
1.9 +\ref NetworkSimplex is usually the fastest on relatively small graphs (up to
1.10 +several thousands of nodes) and on dense graphs, while \ref CostScaling is
1.11 +typically more efficient on large graphs (e.g. hundreds of thousands of
1.12 +nodes or above), especially if they are sparse.
1.13 +However, other algorithms could be faster in special cases.
1.14 For example, if the total supply and/or capacities are rather small,
1.15 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).
1.16
2.1 --- a/lemon/capacity_scaling.h Mon Jan 30 23:24:14 2012 +0100
2.2 +++ b/lemon/capacity_scaling.h Mon Jan 30 23:24:40 2012 +0100
2.3 @@ -70,6 +70,11 @@
2.4 /// \ref edmondskarp72theoretical. It is an efficient dual
2.5 /// solution method.
2.6 ///
2.7 + /// This algorithm is typically slower than \ref CostScaling and
2.8 + /// \ref NetworkSimplex, but in special cases, it can be more
2.9 + /// efficient than them.
2.10 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
2.11 + ///
2.12 /// Most of the parameters of the problem (except for the digraph)
2.13 /// can be given using separate functions, and the algorithm can be
2.14 /// executed using the \ref run() function. If some parameters are not
2.15 @@ -676,7 +681,8 @@
2.16 return _res_cap[_arc_idb[a]];
2.17 }
2.18
2.19 - /// \brief Return the flow map (the primal solution).
2.20 + /// \brief Copy the flow values (the primal solution) into the
2.21 + /// given map.
2.22 ///
2.23 /// This function copies the flow value on each arc into the given
2.24 /// map. The \c Value type of the algorithm must be convertible to
2.25 @@ -700,7 +706,8 @@
2.26 return _pi[_node_id[n]];
2.27 }
2.28
2.29 - /// \brief Return the potential map (the dual solution).
2.30 + /// \brief Copy the potential values (the dual solution) into the
2.31 + /// given map.
2.32 ///
2.33 /// This function copies the potential (dual value) of each node
2.34 /// into the given map.
3.1 --- a/lemon/cost_scaling.h Mon Jan 30 23:24:14 2012 +0100
3.2 +++ b/lemon/cost_scaling.h Mon Jan 30 23:24:40 2012 +0100
3.3 @@ -98,7 +98,8 @@
3.4 /// "preflow push-relabel" algorithm for the maximum flow problem.
3.5 ///
3.6 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
3.7 - /// implementations available in LEMON for this problem.
3.8 + /// implementations available in LEMON for solving this problem.
3.9 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
3.10 ///
3.11 /// Most of the parameters of the problem (except for the digraph)
3.12 /// can be given using separate functions, and the algorithm can be
3.13 @@ -704,7 +705,8 @@
3.14 return _res_cap[_arc_idb[a]];
3.15 }
3.16
3.17 - /// \brief Return the flow map (the primal solution).
3.18 + /// \brief Copy the flow values (the primal solution) into the
3.19 + /// given map.
3.20 ///
3.21 /// This function copies the flow value on each arc into the given
3.22 /// map. The \c Value type of the algorithm must be convertible to
3.23 @@ -728,7 +730,8 @@
3.24 return static_cast<Cost>(_pi[_node_id[n]]);
3.25 }
3.26
3.27 - /// \brief Return the potential map (the dual solution).
3.28 + /// \brief Copy the potential values (the dual solution) into the
3.29 + /// given map.
3.30 ///
3.31 /// This function copies the potential (dual value) of each node
3.32 /// into the given map.
4.1 --- a/lemon/cycle_canceling.h Mon Jan 30 23:24:14 2012 +0100
4.2 +++ b/lemon/cycle_canceling.h Mon Jan 30 23:24:40 2012 +0100
4.3 @@ -48,11 +48,12 @@
4.4 /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
4.5 /// \ref amo93networkflows, \ref klein67primal,
4.6 /// \ref goldberg89cyclecanceling.
4.7 - /// The most efficent one (both theoretically and practically)
4.8 - /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm,
4.9 - /// thus it is the default method.
4.10 - /// It is strongly polynomial, but in practice, it is typically much
4.11 - /// slower than the scaling algorithms and NetworkSimplex.
4.12 + /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
4.13 + /// "Cancel-and-Tighten" algorithm, thus it is the default method.
4.14 + /// It runs in strongly polynomial time, but in practice, it is typically
4.15 + /// orders of magnitude slower than the scaling algorithms and
4.16 + /// \ref NetworkSimplex.
4.17 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
4.18 ///
4.19 /// Most of the parameters of the problem (except for the digraph)
4.20 /// can be given using separate functions, and the algorithm can be
4.21 @@ -116,26 +117,28 @@
4.22 /// for the \ref run() function.
4.23 ///
4.24 /// \ref CycleCanceling provides three different cycle-canceling
4.25 - /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
4.26 + /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten"
4.27 /// is used, which is by far the most efficient and the most robust.
4.28 /// However, the other methods can be selected using the \ref run()
4.29 /// function with the proper parameter.
4.30 enum Method {
4.31 /// A simple cycle-canceling method, which uses the
4.32 - /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration
4.33 - /// number for detecting negative cycles in the residual network.
4.34 + /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative
4.35 + /// cycles in the residual network.
4.36 + /// The number of Bellman-Ford iterations is bounded by a successively
4.37 + /// increased limit.
4.38 SIMPLE_CYCLE_CANCELING,
4.39 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
4.40 /// well-known strongly polynomial method
4.41 /// \ref goldberg89cyclecanceling. It improves along a
4.42 /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
4.43 - /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)).
4.44 + /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
4.45 MINIMUM_MEAN_CYCLE_CANCELING,
4.46 - /// The "Cancel And Tighten" algorithm, which can be viewed as an
4.47 + /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
4.48 /// improved version of the previous method
4.49 /// \ref goldberg89cyclecanceling.
4.50 /// It is faster both in theory and in practice, its running time
4.51 - /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)).
4.52 + /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
4.53 CANCEL_AND_TIGHTEN
4.54 };
4.55
4.56 @@ -610,7 +613,8 @@
4.57 return _res_cap[_arc_idb[a]];
4.58 }
4.59
4.60 - /// \brief Return the flow map (the primal solution).
4.61 + /// \brief Copy the flow values (the primal solution) into the
4.62 + /// given map.
4.63 ///
4.64 /// This function copies the flow value on each arc into the given
4.65 /// map. The \c Value type of the algorithm must be convertible to
4.66 @@ -634,7 +638,8 @@
4.67 return static_cast<Cost>(_pi[_node_id[n]]);
4.68 }
4.69
4.70 - /// \brief Return the potential map (the dual solution).
4.71 + /// \brief Copy the potential values (the dual solution) into the
4.72 + /// given map.
4.73 ///
4.74 /// This function copies the potential (dual value) of each node
4.75 /// into the given map.
4.76 @@ -954,7 +959,7 @@
4.77 }
4.78 }
4.79
4.80 - // Execute the "Cancel And Tighten" method
4.81 + // Execute the "Cancel-and-Tighten" method
4.82 void startCancelAndTighten() {
4.83 // Constants for the min mean cycle computations
4.84 const double LIMIT_FACTOR = 1.0;
5.1 --- a/lemon/network_simplex.h Mon Jan 30 23:24:14 2012 +0100
5.2 +++ b/lemon/network_simplex.h Mon Jan 30 23:24:40 2012 +0100
5.3 @@ -48,7 +48,8 @@
5.4 /// flow problem.
5.5 ///
5.6 /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
5.7 - /// implementations available in LEMON for this problem.
5.8 + /// implementations available in LEMON for solving this problem.
5.9 + /// (For more information, see \ref min_cost_flow_algs "the module page".)
5.10 /// Furthermore, this class supports both directions of the supply/demand
5.11 /// inequality constraints. For more information, see \ref SupplyType.
5.12 ///
5.13 @@ -1006,7 +1007,8 @@
5.14 return _flow[_arc_id[a]];
5.15 }
5.16
5.17 - /// \brief Return the flow map (the primal solution).
5.18 + /// \brief Copy the flow values (the primal solution) into the
5.19 + /// given map.
5.20 ///
5.21 /// This function copies the flow value on each arc into the given
5.22 /// map. The \c Value type of the algorithm must be convertible to
5.23 @@ -1030,7 +1032,8 @@
5.24 return _pi[_node_id[n]];
5.25 }
5.26
5.27 - /// \brief Return the potential map (the dual solution).
5.28 + /// \brief Copy the potential values (the dual solution) into the
5.29 + /// given map.
5.30 ///
5.31 /// This function copies the potential (dual value) of each node
5.32 /// into the given map.