45 /// \brief Implementation of cycle-canceling algorithms for |
45 /// \brief Implementation of cycle-canceling algorithms for |
46 /// finding a \ref min_cost_flow "minimum cost flow". |
46 /// finding a \ref min_cost_flow "minimum cost flow". |
47 /// |
47 /// |
48 /// \ref CycleCanceling implements three different cycle-canceling |
48 /// \ref CycleCanceling implements three different cycle-canceling |
49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
49 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
50 /// \ref amo93networkflows, \ref klein67primal, |
50 /// \cite amo93networkflows, \cite klein67primal, |
51 /// \ref goldberg89cyclecanceling. |
51 /// \cite goldberg89cyclecanceling. |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
52 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
53 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)), |
54 /// It runs in strongly polynomial time O(n<sup>2</sup>e<sup>2</sup>log(n)), |
55 /// but in practice, it is typically orders of magnitude slower than |
55 /// but in practice, it is typically orders of magnitude slower than |
56 /// the scaling algorithms and \ref NetworkSimplex. |
56 /// the scaling algorithms and \ref NetworkSimplex. |
129 /// The number of Bellman-Ford iterations is bounded by a successively |
129 /// The number of Bellman-Ford iterations is bounded by a successively |
130 /// increased limit. |
130 /// increased limit. |
131 SIMPLE_CYCLE_CANCELING, |
131 SIMPLE_CYCLE_CANCELING, |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
132 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
133 /// well-known strongly polynomial method |
133 /// well-known strongly polynomial method |
134 /// \ref goldberg89cyclecanceling. It improves along a |
134 /// \cite goldberg89cyclecanceling. It improves along a |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
135 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). |
136 /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)). |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
137 MINIMUM_MEAN_CYCLE_CANCELING, |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
138 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
139 /// improved version of the previous method |
139 /// improved version of the previous method |
140 /// \ref goldberg89cyclecanceling. |
140 /// \cite goldberg89cyclecanceling. |
141 /// It is faster both in theory and in practice, its running time |
141 /// It is faster both in theory and in practice, its running time |
142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). |
142 /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)). |
143 CANCEL_AND_TIGHTEN |
143 CANCEL_AND_TIGHTEN |
144 }; |
144 }; |
145 |
145 |