32 #define LIMITED_CYCLE_CANCELING |
32 #define LIMITED_CYCLE_CANCELING |
33 //#define MIN_MEAN_CYCLE_CANCELING |
33 //#define MIN_MEAN_CYCLE_CANCELING |
34 |
34 |
35 #ifdef LIMITED_CYCLE_CANCELING |
35 #ifdef LIMITED_CYCLE_CANCELING |
36 #include <lemon/bellman_ford.h> |
36 #include <lemon/bellman_ford.h> |
37 /// \brief The maximum number of iterations for the first execution |
37 // The maximum number of iterations for the first execution of the |
38 /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm. |
38 // Bellman-Ford algorithm. It should be at least 2. |
39 /// It should be at least 2. |
39 #define STARTING_LIMIT 2 |
40 #define STARTING_LIMIT 2 |
40 // The iteration limit for the Bellman-Ford algorithm is multiplied by |
41 /// \brief The iteration limit for the |
41 // <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round. |
42 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by |
42 // <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1. |
43 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round. |
43 #define ALPHA_MUL 3 |
44 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1. |
44 #define ALPHA_DIV 2 |
45 #define ALPHA_MUL 3 |
|
46 /// \brief The iteration limit for the |
|
47 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by |
|
48 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> in every round. |
|
49 /// <tt>ALPHA_MUL / ALPHA_DIV</tt> must be greater than 1. |
|
50 #define ALPHA_DIV 2 |
|
51 |
45 |
52 //#define _ONLY_ONE_CYCLE_ |
46 //#define _ONLY_ONE_CYCLE_ |
53 //#define _NO_BACK_STEP_ |
47 //#define _NO_BACK_STEP_ |
54 //#define _DEBUG_ITER_ |
|
55 #endif |
48 #endif |
56 |
49 |
57 #ifdef MIN_MEAN_CYCLE_CANCELING |
50 #ifdef MIN_MEAN_CYCLE_CANCELING |
58 #include <lemon/min_mean_cycle.h> |
51 #include <lemon/min_mean_cycle.h> |
59 #include <lemon/path.h> |
52 #include <lemon/path.h> |
60 #endif |
53 #endif |
61 |
54 |
|
55 //#define _DEBUG_ITER_ |
|
56 |
62 namespace lemon { |
57 namespace lemon { |
63 |
58 |
64 /// \addtogroup min_cost_flow |
59 /// \addtogroup min_cost_flow |
65 /// @{ |
60 /// @{ |
66 |
61 |
67 /// \brief Implementation of a cycle-canceling algorithm for finding |
62 /// \brief Implementation of a cycle-canceling algorithm for |
68 /// a minimum cost flow. |
63 /// finding a minimum cost flow. |
69 /// |
64 /// |
70 /// \ref lemon::CycleCanceling "CycleCanceling" implements a |
65 /// \ref CycleCanceling implements a cycle-canceling algorithm for |
71 /// cycle-canceling algorithm for finding a minimum cost flow. |
66 /// finding a minimum cost flow. |
72 /// |
67 /// |
73 /// \param Graph The directed graph type the algorithm runs on. |
68 /// \param Graph The directed graph type the algorithm runs on. |
74 /// \param LowerMap The type of the lower bound map. |
69 /// \param LowerMap The type of the lower bound map. |
75 /// \param CapacityMap The type of the capacity (upper bound) map. |
70 /// \param CapacityMap The type of the capacity (upper bound) map. |
76 /// \param CostMap The type of the cost (length) map. |
71 /// \param CostMap The type of the cost (length) map. |
77 /// \param SupplyMap The type of the supply map. |
72 /// \param SupplyMap The type of the supply map. |
78 /// |
73 /// |
79 /// \warning |
74 /// \warning |
80 /// - Edge capacities and costs should be nonnegative integers. |
75 /// - Edge capacities and costs should be non-negative integers. |
81 /// However \c CostMap::Value should be signed type. |
76 /// However \c CostMap::Value should be signed type. |
82 /// - Supply values should be signed integers. |
77 /// - Supply values should be signed integers. |
83 /// - \c LowerMap::Value must be convertible to |
78 /// - \c LowerMap::Value must be convertible to |
84 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
79 /// \c CapacityMap::Value and \c CapacityMap::Value must be |
85 /// convertible to \c SupplyMap::Value. |
80 /// convertible to \c SupplyMap::Value. |
86 /// |
81 /// |
87 /// \author Peter Kovacs |
82 /// \author Peter Kovacs |
88 |
83 |
89 template < typename Graph, |
84 template < typename Graph, |
90 typename LowerMap = typename Graph::template EdgeMap<int>, |
85 typename LowerMap = typename Graph::template EdgeMap<int>, |
92 typename CostMap = typename Graph::template EdgeMap<int>, |
87 typename CostMap = typename Graph::template EdgeMap<int>, |
93 typename SupplyMap = typename Graph::template NodeMap |
88 typename SupplyMap = typename Graph::template NodeMap |
94 <typename CapacityMap::Value> > |
89 <typename CapacityMap::Value> > |
95 class CycleCanceling |
90 class CycleCanceling |
96 { |
91 { |
97 typedef typename Graph::Node Node; |
92 GRAPH_TYPEDEFS(typename Graph); |
98 typedef typename Graph::NodeIt NodeIt; |
|
99 typedef typename Graph::Edge Edge; |
|
100 typedef typename Graph::EdgeIt EdgeIt; |
|
101 typedef typename Graph::InEdgeIt InEdgeIt; |
|
102 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
103 |
93 |
104 typedef typename LowerMap::Value Lower; |
94 typedef typename LowerMap::Value Lower; |
105 typedef typename CapacityMap::Value Capacity; |
95 typedef typename CapacityMap::Value Capacity; |
106 typedef typename CostMap::Value Cost; |
96 typedef typename CostMap::Value Cost; |
107 typedef typename SupplyMap::Value Supply; |
97 typedef typename SupplyMap::Value Supply; |
108 typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap; |
98 typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap; |
109 typedef typename Graph::template NodeMap<Supply> SupplyRefMap; |
99 typedef typename Graph::template NodeMap<Supply> SupplyNodeMap; |
110 |
100 |
111 typedef ResGraphAdaptor< const Graph, Capacity, |
101 typedef ResGraphAdaptor< const Graph, Capacity, |
112 CapacityRefMap, CapacityRefMap > ResGraph; |
102 CapacityEdgeMap, CapacityEdgeMap > ResGraph; |
113 typedef typename ResGraph::Node ResNode; |
103 typedef typename ResGraph::Node ResNode; |
114 typedef typename ResGraph::NodeIt ResNodeIt; |
104 typedef typename ResGraph::NodeIt ResNodeIt; |
115 typedef typename ResGraph::Edge ResEdge; |
105 typedef typename ResGraph::Edge ResEdge; |
116 typedef typename ResGraph::EdgeIt ResEdgeIt; |
106 typedef typename ResGraph::EdgeIt ResEdgeIt; |
117 |
107 |
118 public: |
108 public: |
119 |
109 |
120 /// \brief The type of the flow map. |
110 /// The type of the flow map. |
121 typedef CapacityRefMap FlowMap; |
111 typedef typename Graph::template EdgeMap<Capacity> FlowMap; |
122 |
112 |
123 protected: |
113 protected: |
124 |
114 |
125 /// \brief Map adaptor class for handling residual edge costs. |
115 /// Map adaptor class for handling residual edge costs. |
126 class ResCostMap : public MapBase<ResEdge, Cost> |
116 class ResCostMap : public MapBase<ResEdge, Cost> |
127 { |
117 { |
128 private: |
118 private: |
129 |
119 |
130 const CostMap &cost_map; |
120 const CostMap &cost_map; |
132 public: |
122 public: |
133 |
123 |
134 ResCostMap(const CostMap &_cost) : cost_map(_cost) {} |
124 ResCostMap(const CostMap &_cost) : cost_map(_cost) {} |
135 |
125 |
136 Cost operator[](const ResEdge &e) const { |
126 Cost operator[](const ResEdge &e) const { |
137 return ResGraph::forward(e) ? cost_map[e] : -cost_map[e]; |
127 return ResGraph::forward(e) ? cost_map[e] : -cost_map[e]; |
138 } |
128 } |
139 |
129 |
140 }; //class ResCostMap |
130 }; //class ResCostMap |
141 |
131 |
142 protected: |
132 protected: |
143 |
133 |
144 /// \brief The directed graph the algorithm runs on. |
134 /// The directed graph the algorithm runs on. |
145 const Graph &graph; |
135 const Graph &graph; |
146 /// \brief The original lower bound map. |
136 /// The original lower bound map. |
147 const LowerMap *lower; |
137 const LowerMap *lower; |
148 /// \brief The modified capacity map. |
138 /// The modified capacity map. |
149 CapacityRefMap capacity; |
139 CapacityEdgeMap capacity; |
150 /// \brief The cost map. |
140 /// The cost map. |
151 const CostMap &cost; |
141 const CostMap &cost; |
152 /// \brief The modified supply map. |
142 /// The modified supply map. |
153 SupplyRefMap supply; |
143 SupplyNodeMap supply; |
154 /// \brief The sum of supply values equals zero. |
|
155 bool valid_supply; |
144 bool valid_supply; |
156 |
145 |
157 /// \brief The current flow. |
146 /// The current flow. |
158 FlowMap flow; |
147 FlowMap flow; |
159 /// \brief The residual graph. |
148 /// The residual graph. |
160 ResGraph res_graph; |
149 ResGraph res_graph; |
161 /// \brief The residual cost map. |
150 /// The residual cost map. |
162 ResCostMap res_cost; |
151 ResCostMap res_cost; |
163 |
152 |
164 public : |
153 public : |
165 |
154 |
166 /// \brief General constructor of the class (with lower bounds). |
155 /// \brief General constructor of the class (with lower bounds). |
171 /// \param _lower The lower bounds of the edges. |
160 /// \param _lower The lower bounds of the edges. |
172 /// \param _capacity The capacities (upper bounds) of the edges. |
161 /// \param _capacity The capacities (upper bounds) of the edges. |
173 /// \param _cost The cost (length) values of the edges. |
162 /// \param _cost The cost (length) values of the edges. |
174 /// \param _supply The supply values of the nodes (signed). |
163 /// \param _supply The supply values of the nodes (signed). |
175 CycleCanceling( const Graph &_graph, |
164 CycleCanceling( const Graph &_graph, |
176 const LowerMap &_lower, |
165 const LowerMap &_lower, |
177 const CapacityMap &_capacity, |
166 const CapacityMap &_capacity, |
178 const CostMap &_cost, |
167 const CostMap &_cost, |
179 const SupplyMap &_supply ) : |
168 const SupplyMap &_supply ) : |
180 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
169 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
181 supply(_graph), flow(_graph, 0), |
170 supply(_graph), flow(_graph, 0), |
182 res_graph(_graph, capacity, flow), res_cost(cost) |
171 res_graph(_graph, capacity, flow), res_cost(cost) |
183 { |
172 { |
184 // Removing nonzero lower bounds |
173 // Removing non-zero lower bounds |
185 capacity = subMap(_capacity, _lower); |
174 capacity = subMap(_capacity, _lower); |
186 Supply sum = 0; |
175 Supply sum = 0; |
187 for (NodeIt n(graph); n != INVALID; ++n) { |
176 for (NodeIt n(graph); n != INVALID; ++n) { |
188 Supply s = _supply[n]; |
177 Supply s = _supply[n]; |
189 for (InEdgeIt e(graph, n); e != INVALID; ++e) |
178 for (InEdgeIt e(graph, n); e != INVALID; ++e) |
190 s += _lower[e]; |
179 s += _lower[e]; |
191 for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
180 for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
192 s -= _lower[e]; |
181 s -= _lower[e]; |
193 sum += (supply[n] = s); |
182 sum += (supply[n] = s); |
194 } |
183 } |
195 valid_supply = sum == 0; |
184 valid_supply = sum == 0; |
196 } |
185 } |
197 |
186 |
198 /// \brief General constructor of the class (without lower bounds). |
187 /// \brief General constructor of the class (without lower bounds). |
202 /// \param _graph The directed graph the algorithm runs on. |
191 /// \param _graph The directed graph the algorithm runs on. |
203 /// \param _capacity The capacities (upper bounds) of the edges. |
192 /// \param _capacity The capacities (upper bounds) of the edges. |
204 /// \param _cost The cost (length) values of the edges. |
193 /// \param _cost The cost (length) values of the edges. |
205 /// \param _supply The supply values of the nodes (signed). |
194 /// \param _supply The supply values of the nodes (signed). |
206 CycleCanceling( const Graph &_graph, |
195 CycleCanceling( const Graph &_graph, |
207 const CapacityMap &_capacity, |
196 const CapacityMap &_capacity, |
208 const CostMap &_cost, |
197 const CostMap &_cost, |
209 const SupplyMap &_supply ) : |
198 const SupplyMap &_supply ) : |
210 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
199 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
211 supply(_supply), flow(_graph, 0), |
200 supply(_supply), flow(_graph, 0), |
212 res_graph(_graph, capacity, flow), res_cost(cost) |
201 res_graph(_graph, capacity, flow), res_cost(cost) |
213 { |
202 { |
214 // Checking the sum of supply values |
203 // Checking the sum of supply values |
215 Supply sum = 0; |
204 Supply sum = 0; |
216 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
205 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
217 valid_supply = sum == 0; |
206 valid_supply = sum == 0; |
218 } |
207 } |
219 |
208 |
220 |
|
221 /// \brief Simple constructor of the class (with lower bounds). |
209 /// \brief Simple constructor of the class (with lower bounds). |
222 /// |
210 /// |
223 /// Simple constructor of the class (with lower bounds). |
211 /// Simple constructor of the class (with lower bounds). |
224 /// |
212 /// |
225 /// \param _graph The directed graph the algorithm runs on. |
213 /// \param _graph The directed graph the algorithm runs on. |
227 /// \param _capacity The capacities (upper bounds) of the edges. |
215 /// \param _capacity The capacities (upper bounds) of the edges. |
228 /// \param _cost The cost (length) values of the edges. |
216 /// \param _cost The cost (length) values of the edges. |
229 /// \param _s The source node. |
217 /// \param _s The source node. |
230 /// \param _t The target node. |
218 /// \param _t The target node. |
231 /// \param _flow_value The required amount of flow from node \c _s |
219 /// \param _flow_value The required amount of flow from node \c _s |
232 /// to node \c _t (i.e. the supply of \c _s and the demand of |
220 /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). |
233 /// \c _t). |
|
234 CycleCanceling( const Graph &_graph, |
221 CycleCanceling( const Graph &_graph, |
235 const LowerMap &_lower, |
222 const LowerMap &_lower, |
236 const CapacityMap &_capacity, |
223 const CapacityMap &_capacity, |
237 const CostMap &_cost, |
224 const CostMap &_cost, |
238 Node _s, Node _t, |
225 Node _s, Node _t, |
239 Supply _flow_value ) : |
226 Supply _flow_value ) : |
240 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
227 graph(_graph), lower(&_lower), capacity(_graph), cost(_cost), |
241 supply(_graph), flow(_graph, 0), |
228 supply(_graph), flow(_graph, 0), |
242 res_graph(_graph, capacity, flow), res_cost(cost) |
229 res_graph(_graph, capacity, flow), res_cost(cost) |
243 { |
230 { |
244 // Removing nonzero lower bounds |
231 // Removing non-zero lower bounds |
245 capacity = subMap(_capacity, _lower); |
232 capacity = subMap(_capacity, _lower); |
246 for (NodeIt n(graph); n != INVALID; ++n) { |
233 for (NodeIt n(graph); n != INVALID; ++n) { |
247 Supply s = 0; |
234 Supply s = 0; |
248 if (n == _s) s = _flow_value; |
235 if (n == _s) s = _flow_value; |
249 if (n == _t) s = -_flow_value; |
236 if (n == _t) s = -_flow_value; |
250 for (InEdgeIt e(graph, n); e != INVALID; ++e) |
237 for (InEdgeIt e(graph, n); e != INVALID; ++e) |
251 s += _lower[e]; |
238 s += _lower[e]; |
252 for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
239 for (OutEdgeIt e(graph, n); e != INVALID; ++e) |
253 s -= _lower[e]; |
240 s -= _lower[e]; |
254 supply[n] = s; |
241 supply[n] = s; |
255 } |
242 } |
256 valid_supply = true; |
243 valid_supply = true; |
257 } |
244 } |
258 |
245 |
259 /// \brief Simple constructor of the class (without lower bounds). |
246 /// \brief Simple constructor of the class (without lower bounds). |
264 /// \param _capacity The capacities (upper bounds) of the edges. |
251 /// \param _capacity The capacities (upper bounds) of the edges. |
265 /// \param _cost The cost (length) values of the edges. |
252 /// \param _cost The cost (length) values of the edges. |
266 /// \param _s The source node. |
253 /// \param _s The source node. |
267 /// \param _t The target node. |
254 /// \param _t The target node. |
268 /// \param _flow_value The required amount of flow from node \c _s |
255 /// \param _flow_value The required amount of flow from node \c _s |
269 /// to node \c _t (i.e. the supply of \c _s and the demand of |
256 /// to node \c _t (i.e. the supply of \c _s and the demand of \c _t). |
270 /// \c _t). |
|
271 CycleCanceling( const Graph &_graph, |
257 CycleCanceling( const Graph &_graph, |
272 const CapacityMap &_capacity, |
258 const CapacityMap &_capacity, |
273 const CostMap &_cost, |
259 const CostMap &_cost, |
274 Node _s, Node _t, |
260 Node _s, Node _t, |
275 Supply _flow_value ) : |
261 Supply _flow_value ) : |
276 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
262 graph(_graph), lower(NULL), capacity(_capacity), cost(_cost), |
277 supply(_graph, 0), flow(_graph, 0), |
263 supply(_graph, 0), flow(_graph, 0), |
278 res_graph(_graph, capacity, flow), res_cost(cost) |
264 res_graph(_graph, capacity, flow), res_cost(cost) |
279 { |
265 { |
280 supply[_s] = _flow_value; |
266 supply[_s] = _flow_value; |
281 supply[_t] = -_flow_value; |
267 supply[_t] = -_flow_value; |
282 valid_supply = true; |
268 valid_supply = true; |
283 } |
269 } |
284 |
270 |
|
271 /// \brief Runs the algorithm. |
|
272 /// |
|
273 /// Runs the algorithm. |
|
274 /// |
|
275 /// \return \c true if a feasible flow can be found. |
|
276 bool run() { |
|
277 return init() && start(); |
|
278 } |
|
279 |
285 /// \brief Returns a const reference to the flow map. |
280 /// \brief Returns a const reference to the flow map. |
286 /// |
281 /// |
287 /// Returns a const reference to the flow map. |
282 /// Returns a const reference to the flow map. |
288 /// |
283 /// |
289 /// \pre \ref run() must be called before using this function. |
284 /// \pre \ref run() must be called before using this function. |
298 /// |
293 /// |
299 /// \pre \ref run() must be called before using this function. |
294 /// \pre \ref run() must be called before using this function. |
300 Cost totalCost() const { |
295 Cost totalCost() const { |
301 Cost c = 0; |
296 Cost c = 0; |
302 for (EdgeIt e(graph); e != INVALID; ++e) |
297 for (EdgeIt e(graph); e != INVALID; ++e) |
303 c += flow[e] * cost[e]; |
298 c += flow[e] * cost[e]; |
304 return c; |
299 return c; |
305 } |
300 } |
306 |
301 |
307 /// \brief Runs the algorithm. |
|
308 /// |
|
309 /// Runs the algorithm. |
|
310 /// |
|
311 /// \return \c true if a feasible flow can be found. |
|
312 bool run() { |
|
313 return init() && start(); |
|
314 } |
|
315 |
|
316 protected: |
302 protected: |
317 |
303 |
318 /// \brief Initializes the algorithm. |
304 /// Initializes the algorithm. |
319 bool init() { |
305 bool init() { |
320 // Checking the sum of supply values |
306 // Checking the sum of supply values |
321 Supply sum = 0; |
307 Supply sum = 0; |
322 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
308 for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n]; |
323 if (sum != 0) return false; |
309 if (sum != 0) return false; |
324 |
310 |
325 // Finding a feasible flow |
311 // Finding a feasible flow |
326 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityRefMap, |
312 Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap, |
327 SupplyMap > |
313 SupplyMap > |
328 circulation( graph, constMap<Edge>((Capacity)0), capacity, |
314 circulation( graph, constMap<Edge>((Capacity)0), capacity, |
329 supply ); |
315 supply ); |
330 circulation.flowMap(flow); |
316 circulation.flowMap(flow); |
331 return circulation.run(); |
317 return circulation.run(); |
332 } |
318 } |
333 |
319 |
334 #ifdef LIMITED_CYCLE_CANCELING |
320 #ifdef LIMITED_CYCLE_CANCELING |
335 /// \brief Executes a cycle-canceling algorithm using |
321 /// \brief Executes a cycle-canceling algorithm using |
336 /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited |
322 /// \ref Bellman-Ford algorithm with limited iteration count. |
337 /// iteration count. |
|
338 bool start() { |
323 bool start() { |
339 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph); |
324 typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph); |
340 typename ResGraph::template NodeMap<int> visited(res_graph); |
325 typename ResGraph::template NodeMap<int> visited(res_graph); |
341 std::vector<ResEdge> cycle; |
326 std::vector<ResEdge> cycle; |
342 int node_num = countNodes(graph); |
327 int node_num = countNodes(graph); |
345 int cycle_num = 0; |
330 int cycle_num = 0; |
346 #endif |
331 #endif |
347 int length_bound = STARTING_LIMIT; |
332 int length_bound = STARTING_LIMIT; |
348 bool optimal = false; |
333 bool optimal = false; |
349 while (!optimal) { |
334 while (!optimal) { |
350 BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost); |
335 BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost); |
351 bf.predMap(pred); |
336 bf.predMap(pred); |
352 bf.init(0); |
337 bf.init(0); |
353 int iter_num = 0; |
338 int iter_num = 0; |
354 bool cycle_found = false; |
339 bool cycle_found = false; |
355 while (!cycle_found) { |
340 while (!cycle_found) { |
356 #ifdef _NO_BACK_STEP_ |
341 #ifdef _NO_BACK_STEP_ |
357 int curr_iter_num = length_bound <= node_num ? |
342 int curr_iter_num = length_bound <= node_num ? |
358 length_bound - iter_num : node_num - iter_num; |
343 length_bound - iter_num : node_num - iter_num; |
359 #else |
344 #else |
360 int curr_iter_num = iter_num + length_bound <= node_num ? |
345 int curr_iter_num = iter_num + length_bound <= node_num ? |
361 length_bound : node_num - iter_num; |
346 length_bound : node_num - iter_num; |
362 #endif |
347 #endif |
363 iter_num += curr_iter_num; |
348 iter_num += curr_iter_num; |
364 int real_iter_num = curr_iter_num; |
349 int real_iter_num = curr_iter_num; |
365 for (int i = 0; i < curr_iter_num; ++i) { |
350 for (int i = 0; i < curr_iter_num; ++i) { |
366 if (bf.processNextWeakRound()) { |
351 if (bf.processNextWeakRound()) { |
367 real_iter_num = i; |
352 real_iter_num = i; |
368 break; |
353 break; |
369 } |
354 } |
370 } |
355 } |
371 if (real_iter_num < curr_iter_num) { |
356 if (real_iter_num < curr_iter_num) { |
372 optimal = true; |
357 optimal = true; |
373 break; |
358 break; |
374 } else { |
359 } else { |
375 // Searching for node disjoint negative cycles |
360 // Searching for node disjoint negative cycles |
376 for (ResNodeIt n(res_graph); n != INVALID; ++n) |
361 for (ResNodeIt n(res_graph); n != INVALID; ++n) |
377 visited[n] = 0; |
362 visited[n] = 0; |
378 int id = 0; |
363 int id = 0; |
379 for (ResNodeIt n(res_graph); n != INVALID; ++n) { |
364 for (ResNodeIt n(res_graph); n != INVALID; ++n) { |
380 if (visited[n] > 0) continue; |
365 if (visited[n] > 0) continue; |
381 visited[n] = ++id; |
366 visited[n] = ++id; |
382 ResNode u = pred[n] == INVALID ? |
367 ResNode u = pred[n] == INVALID ? |
383 INVALID : res_graph.source(pred[n]); |
368 INVALID : res_graph.source(pred[n]); |
384 while (u != INVALID && visited[u] == 0) { |
369 while (u != INVALID && visited[u] == 0) { |
385 visited[u] = id; |
370 visited[u] = id; |
386 u = pred[u] == INVALID ? |
371 u = pred[u] == INVALID ? |
387 INVALID : res_graph.source(pred[u]); |
372 INVALID : res_graph.source(pred[u]); |
388 } |
373 } |
389 if (u != INVALID && visited[u] == id) { |
374 if (u != INVALID && visited[u] == id) { |
390 // Finding the negative cycle |
375 // Finding the negative cycle |
391 cycle_found = true; |
376 cycle_found = true; |
392 cycle.clear(); |
377 cycle.clear(); |
393 ResEdge e = pred[u]; |
378 ResEdge e = pred[u]; |
394 cycle.push_back(e); |
379 cycle.push_back(e); |
395 Capacity d = res_graph.rescap(e); |
380 Capacity d = res_graph.rescap(e); |
396 while (res_graph.source(e) != u) { |
381 while (res_graph.source(e) != u) { |
397 cycle.push_back(e = pred[res_graph.source(e)]); |
382 cycle.push_back(e = pred[res_graph.source(e)]); |
398 if (res_graph.rescap(e) < d) |
383 if (res_graph.rescap(e) < d) |
399 d = res_graph.rescap(e); |
384 d = res_graph.rescap(e); |
400 } |
385 } |
401 #ifdef _DEBUG_ITER_ |
386 #ifdef _DEBUG_ITER_ |
402 ++cycle_num; |
387 ++cycle_num; |
403 #endif |
388 #endif |
404 // Augmenting along the cycle |
389 // Augmenting along the cycle |
405 for (int i = 0; i < cycle.size(); ++i) |
390 for (int i = 0; i < cycle.size(); ++i) |
406 res_graph.augment(cycle[i], d); |
391 res_graph.augment(cycle[i], d); |
407 #ifdef _ONLY_ONE_CYCLE_ |
392 #ifdef _ONLY_ONE_CYCLE_ |
408 break; |
393 break; |
409 #endif |
394 #endif |
410 } |
395 } |
411 } |
396 } |
412 } |
397 } |
413 |
398 |
414 if (!cycle_found) |
399 if (!cycle_found) |
415 length_bound = length_bound * ALPHA_MUL / ALPHA_DIV; |
400 length_bound = length_bound * ALPHA_MUL / ALPHA_DIV; |
416 } |
401 } |
417 } |
402 } |
418 |
403 |
419 #ifdef _DEBUG_ITER_ |
404 #ifdef _DEBUG_ITER_ |
420 std::cout << "Limited cycle-canceling algorithm finished. " |
405 std::cout << "Limited cycle-canceling algorithm finished. " |
421 << "Found " << cycle_num << " negative cycles." |
406 << "Found " << cycle_num << " negative cycles." |
422 << std::endl; |
407 << std::endl; |
423 #endif |
408 #endif |
424 |
409 |
425 // Handling nonzero lower bounds |
410 // Handling non-zero lower bounds |
426 if (lower) { |
411 if (lower) { |
427 for (EdgeIt e(graph); e != INVALID; ++e) |
412 for (EdgeIt e(graph); e != INVALID; ++e) |
428 flow[e] += (*lower)[e]; |
413 flow[e] += (*lower)[e]; |
429 } |
414 } |
430 return true; |
415 return true; |
431 } |
416 } |
432 #endif |
417 #endif |
433 |
418 |
434 #ifdef MIN_MEAN_CYCLE_CANCELING |
419 #ifdef MIN_MEAN_CYCLE_CANCELING |
435 /// \brief Executes the minimum mean cycle-canceling algorithm |
420 /// \brief Executes the minimum mean cycle-canceling algorithm |
436 /// using \ref lemon::MinMeanCycle "MinMeanCycle" class. |
421 /// using \ref MinMeanCycle. |
437 bool start() { |
422 bool start() { |
438 typedef Path<ResGraph> ResPath; |
423 typedef Path<ResGraph> ResPath; |
439 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost); |
424 MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost); |
440 ResPath cycle; |
425 ResPath cycle; |
441 |
426 |
442 #ifdef _DEBUG_ITER_ |
427 #ifdef _DEBUG_ITER_ |
443 int cycle_num = 0; |
428 int cycle_num = 0; |
444 #endif |
429 #endif |
445 mmc.cyclePath(cycle).init(); |
430 mmc.cyclePath(cycle).init(); |
446 if (mmc.findMinMean()) { |
431 if (mmc.findMinMean()) { |
447 while (mmc.cycleLength() < 0) { |
432 while (mmc.cycleLength() < 0) { |
448 #ifdef _DEBUG_ITER_ |
433 #ifdef _DEBUG_ITER_ |
449 ++iter; |
434 ++cycle_num; |
450 #endif |
435 #endif |
451 // Finding the cycle |
436 // Finding the cycle |
452 mmc.findCycle(); |
437 mmc.findCycle(); |
453 |
438 |
454 // Finding the largest flow amount that can be augmented |
439 // Finding the largest flow amount that can be augmented |
455 // along the cycle |
440 // along the cycle |
456 Capacity delta = 0; |
441 Capacity delta = 0; |
457 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { |
442 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) { |
458 if (delta == 0 || res_graph.rescap(e) < delta) |
443 if (delta == 0 || res_graph.rescap(e) < delta) |
459 delta = res_graph.rescap(e); |
444 delta = res_graph.rescap(e); |
460 } |
445 } |
461 |
446 |
462 // Augmenting along the cycle |
447 // Augmenting along the cycle |
463 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) |
448 for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) |
464 res_graph.augment(e, delta); |
449 res_graph.augment(e, delta); |
465 |
450 |
466 // Finding the minimum cycle mean for the modified residual |
451 // Finding the minimum cycle mean for the modified residual |
467 // graph |
452 // graph |
468 mmc.reset(); |
453 mmc.reset(); |
469 if (!mmc.findMinMean()) break; |
454 if (!mmc.findMinMean()) break; |
470 } |
455 } |
471 } |
456 } |
472 |
457 |
473 #ifdef _DEBUG_ITER_ |
458 #ifdef _DEBUG_ITER_ |
474 std::cout << "Minimum mean cycle-canceling algorithm finished. " |
459 std::cout << "Minimum mean cycle-canceling algorithm finished. " |
475 << "Found " << cycle_num << " negative cycles." |
460 << "Found " << cycle_num << " negative cycles." |
476 << std::endl; |
461 << std::endl; |
477 #endif |
462 #endif |
478 |
463 |
479 // Handling nonzero lower bounds |
464 // Handling non-zero lower bounds |
480 if (lower) { |
465 if (lower) { |
481 for (EdgeIt e(graph); e != INVALID; ++e) |
466 for (EdgeIt e(graph); e != INVALID; ++e) |
482 flow[e] += (*lower)[e]; |
467 flow[e] += (*lower)[e]; |
483 } |
468 } |
484 return true; |
469 return true; |
485 } |
470 } |
486 #endif |
471 #endif |
487 |
472 |