# HG changeset patch # User Peter Kovacs # Date 1327962280 -3600 # Node ID 16f55008c8633f73db3183859734c6981a223cf4 # Parent f63ba40a60f442278dc74a741050b29857a6daa9 Doc improvements for min cost flow algorithms (#437) diff -r f63ba40a60f4 -r 16f55008c863 doc/groups.dox --- a/doc/groups.dox Mon Jan 30 23:24:14 2012 +0100 +++ b/doc/groups.dox Mon Jan 30 23:24:40 2012 +0100 @@ -407,7 +407,12 @@ strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general, \ref NetworkSimplex and \ref CostScaling are the most efficient -implementations, but the other algorithms could be faster in special cases. +implementations. +\ref NetworkSimplex is usually the fastest on relatively small graphs (up to +several thousands of nodes) and on dense graphs, while \ref CostScaling is +typically more efficient on large graphs (e.g. hundreds of thousands of +nodes or above), especially if they are sparse. +However, other algorithms could be faster in special cases. For example, if the total supply and/or capacities are rather small, \ref CapacityScaling is usually the fastest algorithm (without effective scaling). diff -r f63ba40a60f4 -r 16f55008c863 lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h Mon Jan 30 23:24:14 2012 +0100 +++ b/lemon/capacity_scaling.h Mon Jan 30 23:24:40 2012 +0100 @@ -70,6 +70,11 @@ /// \ref edmondskarp72theoretical. It is an efficient dual /// solution method. /// + /// This algorithm is typically slower than \ref CostScaling and + /// \ref NetworkSimplex, but in special cases, it can be more + /// efficient than them. + /// (For more information, see \ref min_cost_flow_algs "the module page".) + /// /// Most of the parameters of the problem (except for the digraph) /// can be given using separate functions, and the algorithm can be /// executed using the \ref run() function. If some parameters are not @@ -676,7 +681,8 @@ return _res_cap[_arc_idb[a]]; } - /// \brief Return the flow map (the primal solution). + /// \brief Copy the flow values (the primal solution) into the + /// given map. /// /// This function copies the flow value on each arc into the given /// map. The \c Value type of the algorithm must be convertible to @@ -700,7 +706,8 @@ return _pi[_node_id[n]]; } - /// \brief Return the potential map (the dual solution). + /// \brief Copy the potential values (the dual solution) into the + /// given map. /// /// This function copies the potential (dual value) of each node /// into the given map. diff -r f63ba40a60f4 -r 16f55008c863 lemon/cost_scaling.h --- a/lemon/cost_scaling.h Mon Jan 30 23:24:14 2012 +0100 +++ b/lemon/cost_scaling.h Mon Jan 30 23:24:40 2012 +0100 @@ -98,7 +98,8 @@ /// "preflow push-relabel" algorithm for the maximum flow problem. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest - /// implementations available in LEMON for this problem. + /// implementations available in LEMON for solving this problem. + /// (For more information, see \ref min_cost_flow_algs "the module page".) /// /// Most of the parameters of the problem (except for the digraph) /// can be given using separate functions, and the algorithm can be @@ -704,7 +705,8 @@ return _res_cap[_arc_idb[a]]; } - /// \brief Return the flow map (the primal solution). + /// \brief Copy the flow values (the primal solution) into the + /// given map. /// /// This function copies the flow value on each arc into the given /// map. The \c Value type of the algorithm must be convertible to @@ -728,7 +730,8 @@ return static_cast(_pi[_node_id[n]]); } - /// \brief Return the potential map (the dual solution). + /// \brief Copy the potential values (the dual solution) into the + /// given map. /// /// This function copies the potential (dual value) of each node /// into the given map. diff -r f63ba40a60f4 -r 16f55008c863 lemon/cycle_canceling.h --- a/lemon/cycle_canceling.h Mon Jan 30 23:24:14 2012 +0100 +++ b/lemon/cycle_canceling.h Mon Jan 30 23:24:40 2012 +0100 @@ -48,11 +48,12 @@ /// algorithms for finding a \ref min_cost_flow "minimum cost flow" /// \ref amo93networkflows, \ref klein67primal, /// \ref goldberg89cyclecanceling. - /// The most efficent one (both theoretically and practically) - /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, - /// thus it is the default method. - /// It is strongly polynomial, but in practice, it is typically much - /// slower than the scaling algorithms and NetworkSimplex. + /// The most efficent one is the \ref CANCEL_AND_TIGHTEN + /// "Cancel-and-Tighten" algorithm, thus it is the default method. + /// It runs in strongly polynomial time, but in practice, it is typically + /// orders of magnitude slower than the scaling algorithms and + /// \ref NetworkSimplex. + /// (For more information, see \ref min_cost_flow_algs "the module page".) /// /// Most of the parameters of the problem (except for the digraph) /// can be given using separate functions, and the algorithm can be @@ -116,26 +117,28 @@ /// for the \ref run() function. /// /// \ref CycleCanceling provides three different cycle-canceling - /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" + /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten" /// is used, which is by far the most efficient and the most robust. /// However, the other methods can be selected using the \ref run() /// function with the proper parameter. enum Method { /// A simple cycle-canceling method, which uses the - /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration - /// number for detecting negative cycles in the residual network. + /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative + /// cycles in the residual network. + /// The number of Bellman-Ford iterations is bounded by a successively + /// increased limit. SIMPLE_CYCLE_CANCELING, /// The "Minimum Mean Cycle-Canceling" algorithm, which is a /// well-known strongly polynomial method /// \ref goldberg89cyclecanceling. It improves along a /// \ref min_mean_cycle "minimum mean cycle" in each iteration. - /// Its running time complexity is O(n2m3log(n)). + /// Its running time complexity is O(n2e3log(n)). MINIMUM_MEAN_CYCLE_CANCELING, - /// The "Cancel And Tighten" algorithm, which can be viewed as an + /// The "Cancel-and-Tighten" algorithm, which can be viewed as an /// improved version of the previous method /// \ref goldberg89cyclecanceling. /// It is faster both in theory and in practice, its running time - /// complexity is O(n2m2log(n)). + /// complexity is O(n2e2log(n)). CANCEL_AND_TIGHTEN }; @@ -610,7 +613,8 @@ return _res_cap[_arc_idb[a]]; } - /// \brief Return the flow map (the primal solution). + /// \brief Copy the flow values (the primal solution) into the + /// given map. /// /// This function copies the flow value on each arc into the given /// map. The \c Value type of the algorithm must be convertible to @@ -634,7 +638,8 @@ return static_cast(_pi[_node_id[n]]); } - /// \brief Return the potential map (the dual solution). + /// \brief Copy the potential values (the dual solution) into the + /// given map. /// /// This function copies the potential (dual value) of each node /// into the given map. @@ -954,7 +959,7 @@ } } - // Execute the "Cancel And Tighten" method + // Execute the "Cancel-and-Tighten" method void startCancelAndTighten() { // Constants for the min mean cycle computations const double LIMIT_FACTOR = 1.0; diff -r f63ba40a60f4 -r 16f55008c863 lemon/network_simplex.h --- a/lemon/network_simplex.h Mon Jan 30 23:24:14 2012 +0100 +++ b/lemon/network_simplex.h Mon Jan 30 23:24:40 2012 +0100 @@ -48,7 +48,8 @@ /// flow problem. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest - /// implementations available in LEMON for this problem. + /// implementations available in LEMON for solving this problem. + /// (For more information, see \ref min_cost_flow_algs "the module page".) /// Furthermore, this class supports both directions of the supply/demand /// inequality constraints. For more information, see \ref SupplyType. /// @@ -1006,7 +1007,8 @@ return _flow[_arc_id[a]]; } - /// \brief Return the flow map (the primal solution). + /// \brief Copy the flow values (the primal solution) into the + /// given map. /// /// This function copies the flow value on each arc into the given /// map. The \c Value type of the algorithm must be convertible to @@ -1030,7 +1032,8 @@ return _pi[_node_id[n]]; } - /// \brief Return the potential map (the dual solution). + /// \brief Copy the potential values (the dual solution) into the + /// given map. /// /// This function copies the potential (dual value) of each node /// into the given map.