Changeset 1003:16f55008c863 in lemon-main for lemon/cycle_canceling.h
- Timestamp:
- 01/30/12 23:24:40 (12 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/cycle_canceling.h
r922 r1003 49 49 /// \ref amo93networkflows, \ref klein67primal, 50 50 /// \ref goldberg89cyclecanceling. 51 /// The most efficent one (both theoretically and practically) 52 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, 53 /// thus it is the default method. 54 /// It is strongly polynomial, but in practice, it is typically much 55 /// slower than the scaling algorithms and NetworkSimplex. 51 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN 52 /// "Cancel-and-Tighten" algorithm, thus it is the default method. 53 /// It runs in strongly polynomial time, but in practice, it is typically 54 /// orders of magnitude slower than the scaling algorithms and 55 /// \ref NetworkSimplex. 56 /// (For more information, see \ref min_cost_flow_algs "the module page".) 56 57 /// 57 58 /// Most of the parameters of the problem (except for the digraph) … … 117 118 /// 118 119 /// \ref CycleCanceling provides three different cycle-canceling 119 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel andTighten"120 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten" 120 121 /// is used, which is by far the most efficient and the most robust. 121 122 /// However, the other methods can be selected using the \ref run() … … 123 124 enum Method { 124 125 /// A simple cycle-canceling method, which uses the 125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration 126 /// number for detecting negative cycles in the residual network. 126 /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative 127 /// cycles in the residual network. 128 /// The number of Bellman-Ford iterations is bounded by a successively 129 /// increased limit. 127 130 SIMPLE_CYCLE_CANCELING, 128 131 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a … … 130 133 /// \ref goldberg89cyclecanceling. It improves along a 131 134 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. 132 /// Its running time complexity is O(n<sup>2</sup> m<sup>3</sup>log(n)).135 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). 133 136 MINIMUM_MEAN_CYCLE_CANCELING, 134 /// The "Cancel AndTighten" algorithm, which can be viewed as an137 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an 135 138 /// improved version of the previous method 136 139 /// \ref goldberg89cyclecanceling. 137 140 /// It is faster both in theory and in practice, its running time 138 /// complexity is O(n<sup>2</sup> m<sup>2</sup>log(n)).141 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). 139 142 CANCEL_AND_TIGHTEN 140 143 }; … … 611 614 } 612 615 613 /// \brief Return the flow map (the primal solution). 616 /// \brief Copy the flow values (the primal solution) into the 617 /// given map. 614 618 /// 615 619 /// This function copies the flow value on each arc into the given … … 635 639 } 636 640 637 /// \brief Return the potential map (the dual solution). 641 /// \brief Copy the potential values (the dual solution) into the 642 /// given map. 638 643 /// 639 644 /// This function copies the potential (dual value) of each node … … 955 960 } 956 961 957 // Execute the "Cancel AndTighten" method962 // Execute the "Cancel-and-Tighten" method 958 963 void startCancelAndTighten() { 959 964 // Constants for the min mean cycle computations
Note: See TracChangeset
for help on using the changeset viewer.