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, |
49 /// \ref amo93networkflows, \ref klein67primal, |
50 /// \ref goldberg89cyclecanceling. |
50 /// \ref goldberg89cyclecanceling. |
51 /// The most efficent one (both theoretically and practically) |
51 /// The most efficent one is the \ref CANCEL_AND_TIGHTEN |
52 /// is the \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" algorithm, |
52 /// "Cancel-and-Tighten" algorithm, thus it is the default method. |
53 /// thus it is the default method. |
53 /// It runs in strongly polynomial time, but in practice, it is typically |
54 /// It is strongly polynomial, but in practice, it is typically much |
54 /// orders of magnitude slower than the scaling algorithms and |
55 /// slower than the scaling algorithms and NetworkSimplex. |
55 /// \ref NetworkSimplex. |
|
56 /// (For more information, see \ref min_cost_flow_algs "the module page".) |
56 /// |
57 /// |
57 /// Most of the parameters of the problem (except for the digraph) |
58 /// Most of the parameters of the problem (except for the digraph) |
58 /// can be given using separate functions, and the algorithm can be |
59 /// can be given using separate functions, and the algorithm can be |
59 /// executed using the \ref run() function. If some parameters are not |
60 /// executed using the \ref run() function. If some parameters are not |
60 /// specified, then default values will be used. |
61 /// specified, then default values will be used. |
114 /// |
115 /// |
115 /// Enum type containing constants for selecting the used method |
116 /// Enum type containing constants for selecting the used method |
116 /// for the \ref run() function. |
117 /// for the \ref run() function. |
117 /// |
118 /// |
118 /// \ref CycleCanceling provides three different cycle-canceling |
119 /// \ref CycleCanceling provides three different cycle-canceling |
119 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" |
120 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel-and-Tighten" |
120 /// is used, which is by far the most efficient and the most robust. |
121 /// is used, which is by far the most efficient and the most robust. |
121 /// However, the other methods can be selected using the \ref run() |
122 /// However, the other methods can be selected using the \ref run() |
122 /// function with the proper parameter. |
123 /// function with the proper parameter. |
123 enum Method { |
124 enum Method { |
124 /// A simple cycle-canceling method, which uses the |
125 /// A simple cycle-canceling method, which uses the |
125 /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration |
126 /// \ref BellmanFord "Bellman-Ford" algorithm for detecting negative |
126 /// number for detecting negative cycles in the residual network. |
127 /// cycles in the residual network. |
|
128 /// The number of Bellman-Ford iterations is bounded by a successively |
|
129 /// increased limit. |
127 SIMPLE_CYCLE_CANCELING, |
130 SIMPLE_CYCLE_CANCELING, |
128 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
131 /// The "Minimum Mean Cycle-Canceling" algorithm, which is a |
129 /// well-known strongly polynomial method |
132 /// well-known strongly polynomial method |
130 /// \ref goldberg89cyclecanceling. It improves along a |
133 /// \ref goldberg89cyclecanceling. It improves along a |
131 /// \ref min_mean_cycle "minimum mean cycle" in each iteration. |
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 MINIMUM_MEAN_CYCLE_CANCELING, |
136 MINIMUM_MEAN_CYCLE_CANCELING, |
134 /// The "Cancel And Tighten" algorithm, which can be viewed as an |
137 /// The "Cancel-and-Tighten" algorithm, which can be viewed as an |
135 /// improved version of the previous method |
138 /// improved version of the previous method |
136 /// \ref goldberg89cyclecanceling. |
139 /// \ref goldberg89cyclecanceling. |
137 /// It is faster both in theory and in practice, its running time |
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 CANCEL_AND_TIGHTEN |
142 CANCEL_AND_TIGHTEN |
140 }; |
143 }; |
141 |
144 |
142 private: |
145 private: |
143 |
146 |
608 /// \pre \ref run() must be called before using this function. |
611 /// \pre \ref run() must be called before using this function. |
609 Value flow(const Arc& a) const { |
612 Value flow(const Arc& a) const { |
610 return _res_cap[_arc_idb[a]]; |
613 return _res_cap[_arc_idb[a]]; |
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 /// This function copies the flow value on each arc into the given |
619 /// This function copies the flow value on each arc into the given |
616 /// map. The \c Value type of the algorithm must be convertible to |
620 /// map. The \c Value type of the algorithm must be convertible to |
617 /// the \c Value type of the map. |
621 /// the \c Value type of the map. |
618 /// |
622 /// |
632 /// \pre \ref run() must be called before using this function. |
636 /// \pre \ref run() must be called before using this function. |
633 Cost potential(const Node& n) const { |
637 Cost potential(const Node& n) const { |
634 return static_cast<Cost>(_pi[_node_id[n]]); |
638 return static_cast<Cost>(_pi[_node_id[n]]); |
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 /// This function copies the potential (dual value) of each node |
644 /// This function copies the potential (dual value) of each node |
640 /// into the given map. |
645 /// into the given map. |
641 /// The \c Cost type of the algorithm must be convertible to the |
646 /// The \c Cost type of the algorithm must be convertible to the |
642 /// \c Value type of the map. |
647 /// \c Value type of the map. |
952 // Rebuild the residual network |
957 // Rebuild the residual network |
953 buildResidualNetwork(); |
958 buildResidualNetwork(); |
954 } |
959 } |
955 } |
960 } |
956 |
961 |
957 // Execute the "Cancel And Tighten" method |
962 // Execute the "Cancel-and-Tighten" method |
958 void startCancelAndTighten() { |
963 void startCancelAndTighten() { |
959 // Constants for the min mean cycle computations |
964 // Constants for the min mean cycle computations |
960 const double LIMIT_FACTOR = 1.0; |
965 const double LIMIT_FACTOR = 1.0; |
961 const int MIN_LIMIT = 5; |
966 const int MIN_LIMIT = 5; |
962 |
967 |