1.1 --- a/lemon/capacity_scaling.h Thu Nov 12 23:45:15 2009 +0100
1.2 +++ b/lemon/capacity_scaling.h Thu Nov 12 23:49:05 2009 +0100
1.3 @@ -35,9 +35,9 @@
1.4 ///
1.5 /// Default traits class of CapacityScaling algorithm.
1.6 /// \tparam GR Digraph type.
1.7 - /// \tparam V The value type used for flow amounts, capacity bounds
1.8 + /// \tparam V The number type used for flow amounts, capacity bounds
1.9 /// and supply values. By default it is \c int.
1.10 - /// \tparam C The value type used for costs and potentials.
1.11 + /// \tparam C The number type used for costs and potentials.
1.12 /// By default it is the same as \c V.
1.13 template <typename GR, typename V = int, typename C = V>
1.14 struct CapacityScalingDefaultTraits
1.15 @@ -75,12 +75,12 @@
1.16 /// specified, then default values will be used.
1.17 ///
1.18 /// \tparam GR The digraph type the algorithm runs on.
1.19 - /// \tparam V The value type used for flow amounts, capacity bounds
1.20 + /// \tparam V The number type used for flow amounts, capacity bounds
1.21 /// and supply values in the algorithm. By default it is \c int.
1.22 - /// \tparam C The value type used for costs and potentials in the
1.23 + /// \tparam C The number type used for costs and potentials in the
1.24 /// algorithm. By default it is the same as \c V.
1.25 ///
1.26 - /// \warning Both value types must be signed and all input data must
1.27 + /// \warning Both number types must be signed and all input data must
1.28 /// be integer.
1.29 /// \warning This algorithm does not support negative costs for such
1.30 /// arcs that have infinite upper bound.
1.31 @@ -122,7 +122,7 @@
1.32 OPTIMAL,
1.33 /// The digraph contains an arc of negative cost and infinite
1.34 /// upper bound. It means that the objective function is unbounded
1.35 - /// on that arc, however note that it could actually be bounded
1.36 + /// on that arc, however, note that it could actually be bounded
1.37 /// over the feasible flows, but this algroithm cannot handle
1.38 /// these cases.
1.39 UNBOUNDED
1.40 @@ -307,7 +307,7 @@
1.41 std::numeric_limits<Value>::infinity() :
1.42 std::numeric_limits<Value>::max())
1.43 {
1.44 - // Check the value types
1.45 + // Check the number types
1.46 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
1.47 "The flow type of CapacityScaling must be signed");
1.48 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
1.49 @@ -411,7 +411,7 @@
1.50 /// This function sets the upper bounds (capacities) on the arcs.
1.51 /// If it is not used before calling \ref run(), the upper bounds
1.52 /// will be set to \ref INF on all arcs (i.e. the flow value will be
1.53 - /// unbounded from above on each arc).
1.54 + /// unbounded from above).
1.55 ///
1.56 /// \param map An arc map storing the upper bounds.
1.57 /// Its \c Value type must be convertible to the \c Value type
1.58 @@ -514,7 +514,7 @@
1.59 /// that have been given are kept for the next call, unless
1.60 /// \ref reset() is called, thus only the modified parameters
1.61 /// have to be set again. See \ref reset() for examples.
1.62 - /// However the underlying digraph must not be modified after this
1.63 + /// However, the underlying digraph must not be modified after this
1.64 /// class have been constructed, since it copies and extends the graph.
1.65 ///
1.66 /// \param factor The capacity scaling factor. It must be larger than
1.67 @@ -527,7 +527,7 @@
1.68 /// optimal flow and node potentials (primal and dual solutions),
1.69 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
1.70 /// and infinite upper bound. It means that the objective function
1.71 - /// is unbounded on that arc, however note that it could actually be
1.72 + /// is unbounded on that arc, however, note that it could actually be
1.73 /// bounded over the feasible flows, but this algroithm cannot handle
1.74 /// these cases.
1.75 ///
2.1 --- a/lemon/cost_scaling.h Thu Nov 12 23:45:15 2009 +0100
2.2 +++ b/lemon/cost_scaling.h Thu Nov 12 23:49:05 2009 +0100
2.3 @@ -40,9 +40,9 @@
2.4 ///
2.5 /// Default traits class of CostScaling algorithm.
2.6 /// \tparam GR Digraph type.
2.7 - /// \tparam V The value type used for flow amounts, capacity bounds
2.8 + /// \tparam V The number type used for flow amounts, capacity bounds
2.9 /// and supply values. By default it is \c int.
2.10 - /// \tparam C The value type used for costs and potentials.
2.11 + /// \tparam C The number type used for costs and potentials.
2.12 /// By default it is the same as \c V.
2.13 #ifdef DOXYGEN
2.14 template <typename GR, typename V = int, typename C = V>
2.15 @@ -101,12 +101,12 @@
2.16 /// specified, then default values will be used.
2.17 ///
2.18 /// \tparam GR The digraph type the algorithm runs on.
2.19 - /// \tparam V The value type used for flow amounts, capacity bounds
2.20 + /// \tparam V The number type used for flow amounts, capacity bounds
2.21 /// and supply values in the algorithm. By default it is \c int.
2.22 - /// \tparam C The value type used for costs and potentials in the
2.23 + /// \tparam C The number type used for costs and potentials in the
2.24 /// algorithm. By default it is the same as \c V.
2.25 ///
2.26 - /// \warning Both value types must be signed and all input data must
2.27 + /// \warning Both number types must be signed and all input data must
2.28 /// be integer.
2.29 /// \warning This algorithm does not support negative costs for such
2.30 /// arcs that have infinite upper bound.
2.31 @@ -157,7 +157,7 @@
2.32 OPTIMAL,
2.33 /// The digraph contains an arc of negative cost and infinite
2.34 /// upper bound. It means that the objective function is unbounded
2.35 - /// on that arc, however note that it could actually be bounded
2.36 + /// on that arc, however, note that it could actually be bounded
2.37 /// over the feasible flows, but this algroithm cannot handle
2.38 /// these cases.
2.39 UNBOUNDED
2.40 @@ -325,7 +325,7 @@
2.41 std::numeric_limits<Value>::infinity() :
2.42 std::numeric_limits<Value>::max())
2.43 {
2.44 - // Check the value types
2.45 + // Check the number types
2.46 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
2.47 "The flow type of CostScaling must be signed");
2.48 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
2.49 @@ -433,7 +433,7 @@
2.50 /// This function sets the upper bounds (capacities) on the arcs.
2.51 /// If it is not used before calling \ref run(), the upper bounds
2.52 /// will be set to \ref INF on all arcs (i.e. the flow value will be
2.53 - /// unbounded from above on each arc).
2.54 + /// unbounded from above).
2.55 ///
2.56 /// \param map An arc map storing the upper bounds.
2.57 /// Its \c Value type must be convertible to the \c Value type
2.58 @@ -549,7 +549,7 @@
2.59 /// optimal flow and node potentials (primal and dual solutions),
2.60 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
2.61 /// and infinite upper bound. It means that the objective function
2.62 - /// is unbounded on that arc, however note that it could actually be
2.63 + /// is unbounded on that arc, however, note that it could actually be
2.64 /// bounded over the feasible flows, but this algroithm cannot handle
2.65 /// these cases.
2.66 ///
2.67 @@ -571,7 +571,7 @@
2.68 /// It is useful for multiple run() calls. If this function is not
2.69 /// used, all the parameters given before are kept for the next
2.70 /// \ref run() call.
2.71 - /// However the underlying digraph must not be modified after this
2.72 + /// However, the underlying digraph must not be modified after this
2.73 /// class have been constructed, since it copies and extends the graph.
2.74 ///
2.75 /// For example,
3.1 --- a/lemon/network_simplex.h Thu Nov 12 23:45:15 2009 +0100
3.2 +++ b/lemon/network_simplex.h Thu Nov 12 23:49:05 2009 +0100
3.3 @@ -43,13 +43,13 @@
3.4 /// for finding a \ref min_cost_flow "minimum cost flow"
3.5 /// \ref amo93networkflows, \ref dantzig63linearprog,
3.6 /// \ref kellyoneill91netsimplex.
3.7 - /// This algorithm is a specialized version of the linear programming
3.8 - /// simplex method directly for the minimum cost flow problem.
3.9 - /// It is one of the most efficient solution methods.
3.10 + /// This algorithm is a highly efficient specialized version of the
3.11 + /// linear programming simplex method directly for the minimum cost
3.12 + /// flow problem.
3.13 ///
3.14 - /// In general this class is the fastest implementation available
3.15 - /// in LEMON for the minimum cost flow problem.
3.16 - /// Moreover it supports both directions of the supply/demand inequality
3.17 + /// In general, %NetworkSimplex is the fastest implementation available
3.18 + /// in LEMON for this problem.
3.19 + /// Moreover, it supports both directions of the supply/demand inequality
3.20 /// constraints. For more information, see \ref SupplyType.
3.21 ///
3.22 /// Most of the parameters of the problem (except for the digraph)
3.23 @@ -58,12 +58,12 @@
3.24 /// specified, then default values will be used.
3.25 ///
3.26 /// \tparam GR The digraph type the algorithm runs on.
3.27 - /// \tparam V The value type used for flow amounts, capacity bounds
3.28 + /// \tparam V The number type used for flow amounts, capacity bounds
3.29 /// and supply values in the algorithm. By default, it is \c int.
3.30 - /// \tparam C The value type used for costs and potentials in the
3.31 + /// \tparam C The number type used for costs and potentials in the
3.32 /// algorithm. By default, it is the same as \c V.
3.33 ///
3.34 - /// \warning Both value types must be signed and all input data must
3.35 + /// \warning Both number types must be signed and all input data must
3.36 /// be integer.
3.37 ///
3.38 /// \note %NetworkSimplex provides five different pivot rule
3.39 @@ -126,7 +126,7 @@
3.40 /// of the algorithm.
3.41 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
3.42 /// proved to be the most efficient and the most robust on various
3.43 - /// test inputs according to our benchmark tests.
3.44 + /// test inputs.
3.45 /// However, another pivot rule can be selected using the \ref run()
3.46 /// function with the proper parameter.
3.47 enum PivotRule {
3.48 @@ -637,7 +637,7 @@
3.49 INF(std::numeric_limits<Value>::has_infinity ?
3.50 std::numeric_limits<Value>::infinity() : MAX)
3.51 {
3.52 - // Check the value types
3.53 + // Check the number types
3.54 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
3.55 "The flow type of NetworkSimplex must be signed");
3.56 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
3.57 @@ -729,7 +729,7 @@
3.58 /// This function sets the upper bounds (capacities) on the arcs.
3.59 /// If it is not used before calling \ref run(), the upper bounds
3.60 /// will be set to \ref INF on all arcs (i.e. the flow value will be
3.61 - /// unbounded from above on each arc).
3.62 + /// unbounded from above).
3.63 ///
3.64 /// \param map An arc map storing the upper bounds.
3.65 /// Its \c Value type must be convertible to the \c Value type