252 CapacityScaling( const Graph &graph, |
252 CapacityScaling( const Graph &graph, |
253 const LowerMap &lower, |
253 const LowerMap &lower, |
254 const CapacityMap &capacity, |
254 const CapacityMap &capacity, |
255 const CostMap &cost, |
255 const CostMap &cost, |
256 const SupplyMap &supply ) : |
256 const SupplyMap &supply ) : |
257 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
257 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), |
258 _supply(graph), _flow(NULL), _local_flow(false), |
258 _supply(supply), _flow(NULL), _local_flow(false), |
259 _potential(NULL), _local_potential(false), |
259 _potential(NULL), _local_potential(false), |
260 _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL) |
260 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) |
261 { |
261 { |
262 // Removing non-zero lower bounds |
262 // Check the sum of supply values |
263 _capacity = subMap(capacity, lower); |
|
264 _res_cap = _capacity; |
|
265 Supply sum = 0; |
263 Supply sum = 0; |
266 for (NodeIt n(_graph); n != INVALID; ++n) { |
264 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
267 Supply s = supply[n]; |
|
268 for (InEdgeIt e(_graph, n); e != INVALID; ++e) |
|
269 s += lower[e]; |
|
270 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) |
|
271 s -= lower[e]; |
|
272 _supply[n] = s; |
|
273 sum += s; |
|
274 } |
|
275 _valid_supply = sum == 0; |
265 _valid_supply = sum == 0; |
|
266 |
|
267 // Remove non-zero lower bounds |
|
268 typename LowerMap::Value lcap; |
|
269 for (EdgeIt e(_graph); e != INVALID; ++e) { |
|
270 if ((lcap = lower[e]) != 0) { |
|
271 _capacity[e] -= lcap; |
|
272 _res_cap[e] -= lcap; |
|
273 _supply[_graph.source(e)] -= lcap; |
|
274 _supply[_graph.target(e)] += lcap; |
|
275 _excess[_graph.source(e)] -= lcap; |
|
276 _excess[_graph.target(e)] += lcap; |
|
277 } |
|
278 } |
276 } |
279 } |
277 |
280 |
278 /// \brief General constructor (without lower bounds). |
281 /// \brief General constructor (without lower bounds). |
279 /// |
282 /// |
280 /// General constructor (without lower bounds). |
283 /// General constructor (without lower bounds). |
288 const CostMap &cost, |
291 const CostMap &cost, |
289 const SupplyMap &supply ) : |
292 const SupplyMap &supply ) : |
290 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
293 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
291 _supply(supply), _flow(NULL), _local_flow(false), |
294 _supply(supply), _flow(NULL), _local_flow(false), |
292 _potential(NULL), _local_potential(false), |
295 _potential(NULL), _local_potential(false), |
293 _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL) |
296 _res_cap(capacity), _excess(supply), _pred(graph), _dijkstra(NULL) |
294 { |
297 { |
295 // Checking the sum of supply values |
298 // Check the sum of supply values |
296 Supply sum = 0; |
299 Supply sum = 0; |
297 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
300 for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n]; |
298 _valid_supply = sum == 0; |
301 _valid_supply = sum == 0; |
299 } |
302 } |
300 |
303 |
314 const LowerMap &lower, |
317 const LowerMap &lower, |
315 const CapacityMap &capacity, |
318 const CapacityMap &capacity, |
316 const CostMap &cost, |
319 const CostMap &cost, |
317 Node s, Node t, |
320 Node s, Node t, |
318 Supply flow_value ) : |
321 Supply flow_value ) : |
319 _graph(graph), _lower(&lower), _capacity(graph), _cost(cost), |
322 _graph(graph), _lower(&lower), _capacity(capacity), _cost(cost), |
320 _supply(graph), _flow(NULL), _local_flow(false), |
323 _supply(graph, 0), _flow(NULL), _local_flow(false), |
321 _potential(NULL), _local_potential(false), |
324 _potential(NULL), _local_potential(false), |
322 _res_cap(graph), _excess(graph), _pred(graph), _dijkstra(NULL) |
325 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) |
323 { |
326 { |
324 // Removing non-zero lower bounds |
327 // Remove non-zero lower bounds |
325 _capacity = subMap(capacity, lower); |
328 _supply[s] = _excess[s] = flow_value; |
326 _res_cap = _capacity; |
329 _supply[t] = _excess[t] = -flow_value; |
327 for (NodeIt n(_graph); n != INVALID; ++n) { |
330 typename LowerMap::Value lcap; |
328 Supply sum = 0; |
331 for (EdgeIt e(_graph); e != INVALID; ++e) { |
329 if (n == s) sum = flow_value; |
332 if ((lcap = lower[e]) != 0) { |
330 if (n == t) sum = -flow_value; |
333 _capacity[e] -= lcap; |
331 for (InEdgeIt e(_graph, n); e != INVALID; ++e) |
334 _res_cap[e] -= lcap; |
332 sum += lower[e]; |
335 _supply[_graph.source(e)] -= lcap; |
333 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) |
336 _supply[_graph.target(e)] += lcap; |
334 sum -= lower[e]; |
337 _excess[_graph.source(e)] -= lcap; |
335 _supply[n] = sum; |
338 _excess[_graph.target(e)] += lcap; |
|
339 } |
336 } |
340 } |
337 _valid_supply = true; |
341 _valid_supply = true; |
338 } |
342 } |
339 |
343 |
340 /// \brief Simple constructor (without lower bounds). |
344 /// \brief Simple constructor (without lower bounds). |
354 Node s, Node t, |
358 Node s, Node t, |
355 Supply flow_value ) : |
359 Supply flow_value ) : |
356 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
360 _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost), |
357 _supply(graph, 0), _flow(NULL), _local_flow(false), |
361 _supply(graph, 0), _flow(NULL), _local_flow(false), |
358 _potential(NULL), _local_potential(false), |
362 _potential(NULL), _local_potential(false), |
359 _res_cap(capacity), _excess(graph), _pred(graph), _dijkstra(NULL) |
363 _res_cap(capacity), _excess(graph, 0), _pred(graph), _dijkstra(NULL) |
360 { |
364 { |
361 _supply[s] = flow_value; |
365 _supply[s] = _excess[s] = flow_value; |
362 _supply[t] = -flow_value; |
366 _supply[t] = _excess[t] = -flow_value; |
363 _valid_supply = true; |
367 _valid_supply = true; |
364 } |
368 } |
365 |
369 |
366 /// Destructor. |
370 /// Destructor. |
367 ~CapacityScaling() { |
371 ~CapacityScaling() { |
495 _potential = new PotentialMap(_graph); |
499 _potential = new PotentialMap(_graph); |
496 _local_potential = true; |
500 _local_potential = true; |
497 } |
501 } |
498 for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; |
502 for (EdgeIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; |
499 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; |
503 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; |
500 _excess = _supply; |
|
501 |
504 |
502 _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost, |
505 _dijkstra = new ResidualDijkstra( _graph, *_flow, _res_cap, _cost, |
503 _excess, *_potential, _pred ); |
506 _excess, *_potential, _pred ); |
504 |
507 |
505 // Initializing delta value |
508 // Initializing delta value |