43 |
43 |
44 /// \brief Implementation of cycle-canceling algorithms for |
44 /// \brief Implementation of cycle-canceling algorithms for |
45 /// finding a \ref min_cost_flow "minimum cost flow". |
45 /// finding a \ref min_cost_flow "minimum cost flow". |
46 /// |
46 /// |
47 /// \ref CycleCanceling implements three different cycle-canceling |
47 /// \ref CycleCanceling implements three different cycle-canceling |
48 /// algorithms for finding a \ref min_cost_flow "minimum cost flow". |
48 /// algorithms for finding a \ref min_cost_flow "minimum cost flow" |
|
49 /// \ref amo93networkflows, \ref klein67primal, |
|
50 /// \ref goldberg89cyclecanceling. |
49 /// The most efficent one (both theoretically and practically) |
51 /// The most efficent one (both theoretically and practically) |
50 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, |
52 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, |
51 /// thus it is the default method. |
53 /// thus it is the default method. |
52 /// It is strongly polynomial, but in practice, it is typically much |
54 /// It is strongly polynomial, but in practice, it is typically much |
53 /// slower than the scaling algorithms and NetworkSimplex. |
55 /// slower than the scaling algorithms and NetworkSimplex. |
122 /// A simple cycle-canceling method, which uses the |
124 /// A simple cycle-canceling method, which uses the |
123 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration |
125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration |
124 /// number for detecting negative cycles in the residual network. |
126 /// number for detecting negative cycles in the residual network. |
125 SIMPLE_CYCLE_CANCELING, |
127 SIMPLE_CYCLE_CANCELING, |
126 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
128 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
127 /// well-known strongly polynomial method. It improves along a |
129 /// well-known strongly polynomial method |
|
130 /// \ref goldberg89cyclecanceling. It improves along a |
128 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
131 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
129 /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)). |
132 /// Its running time complexity is O(n<sup>2</sup>m<sup>3</sup>log(n)). |
130 MINIMUM_MEAN_CYCLE_CANCELING, |
133 MINIMUM_MEAN_CYCLE_CANCELING, |
131 /// The "Cancel And Tighten" algorithm, which can be viewed as an |
134 /// The "Cancel And Tighten" algorithm, which can be viewed as an |
132 /// improved version of the previous method. |
135 /// improved version of the previous method |
|
136 /// \ref goldberg89cyclecanceling. |
133 /// It is faster both in theory and in practice, its running time |
137 /// It is faster both in theory and in practice, its running time |
134 /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)). |
138 /// complexity is O(n<sup>2</sup>m<sup>2</sup>log(n)). |
135 CANCEL_AND_TIGHTEN |
139 CANCEL_AND_TIGHTEN |
136 }; |
140 }; |
137 |
141 |