# Changeset 1165:16f55008c863 in lemon

Ignore:
Timestamp:
01/30/12 23:24:40 (8 years ago)
Branch:
default
Phase:
public
Message:

Doc improvements for min cost flow algorithms (#437)

Files:
5 edited

Unmodified
Removed
• ## doc/groups.dox

 r1164 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).
• ## lemon/capacity_scaling.h

 r1026 /// \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) } /// \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 } /// \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
• ## lemon/cost_scaling.h

 r1049 /// /// 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) } /// \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 } /// \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
• ## lemon/cycle_canceling.h

 r1026 /// \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) /// /// \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() 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 /// \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 }; } /// \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 } /// \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 } // Execute the "Cancel And Tighten" method // Execute the "Cancel-and-Tighten" method void startCancelAndTighten() { // Constants for the min mean cycle computations
• ## lemon/network_simplex.h

 r1026 /// /// 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. } /// \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 } /// \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
Note: See TracChangeset for help on using the changeset viewer.