247 }; |
247 }; |
248 |
248 |
249 |
249 |
250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> |
250 template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap> |
251 class MaxFlow { |
251 class MaxFlow { |
252 public: |
252 protected: |
253 typedef typename GraphWrapper::Node Node; |
253 typedef GraphWrapper GW; |
254 typedef typename GraphWrapper::Edge Edge; |
254 typedef typename GW::Node Node; |
255 typedef typename GraphWrapper::EdgeIt EdgeIt; |
255 typedef typename GW::Edge Edge; |
256 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
256 typedef typename GW::EdgeIt EdgeIt; |
257 typedef typename GraphWrapper::InEdgeIt InEdgeIt; |
257 typedef typename GW::OutEdgeIt OutEdgeIt; |
258 |
258 typedef typename GW::InEdgeIt InEdgeIt; |
259 private: |
|
260 //const Graph* G; |
259 //const Graph* G; |
261 GraphWrapper gw; |
260 GW gw; |
262 Node s; |
261 Node s; |
263 Node t; |
262 Node t; |
264 FlowMap* flow; |
263 FlowMap* flow; |
265 const CapacityMap* capacity; |
264 const CapacityMap* capacity; |
266 typedef ResGraphWrapper<GraphWrapper, Number, FlowMap, CapacityMap > |
265 typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW; |
267 AugGraph; |
266 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; |
268 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
267 typedef typename ResGW::Edge ResGWEdge; |
269 typedef typename AugGraph::Edge AugEdge; |
|
270 |
|
271 public: |
268 public: |
272 MaxFlow(const GraphWrapper& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
269 |
|
270 MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
273 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
271 gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
|
272 |
274 bool augmentOnShortestPath() { |
273 bool augmentOnShortestPath() { |
275 AugGraph res_graph(gw, *flow, *capacity); |
274 ResGW res_graph(gw, *flow, *capacity); |
276 bool _augment=false; |
275 bool _augment=false; |
277 |
276 |
278 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
277 typedef typename ResGW::NodeMap<bool> ReachedMap; |
279 BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
278 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
280 res_bfs.pushAndSetReached(s); |
279 bfs.pushAndSetReached(s); |
281 |
280 |
282 typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
281 typename ResGW::NodeMap<ResGWEdge> pred(res_graph); |
283 pred.set(s, AugEdge(INVALID)); |
282 pred.set(s, INVALID); |
284 |
283 |
285 typename AugGraph::NodeMap<Number> free(res_graph); |
284 typename ResGW::NodeMap<Number> free(res_graph); |
286 |
285 |
287 //searching for augmenting path |
286 //searching for augmenting path |
288 while ( !res_bfs.finished() ) { |
287 while ( !bfs.finished() ) { |
289 AugOutEdgeIt e=res_bfs; |
288 ResGWOutEdgeIt e=bfs; |
290 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
289 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
291 Node v=res_graph.tail(e); |
290 Node v=res_graph.tail(e); |
292 Node w=res_graph.head(e); |
291 Node w=res_graph.head(e); |
293 pred.set(w, e); |
292 pred.set(w, e); |
294 if (res_graph.valid(pred.get(v))) { |
293 if (res_graph.valid(pred.get(v))) { |
295 free.set(w, std::min(free.get(v), res_graph.free(e))); |
294 free.set(w, std::min(free.get(v), res_graph.resCap(e))); |
296 } else { |
295 } else { |
297 free.set(w, res_graph.free(e)); |
296 free.set(w, res_graph.resCap(e)); |
298 } |
297 } |
299 if (res_graph.head(e)==t) { _augment=true; break; } |
298 if (res_graph.head(e)==t) { _augment=true; break; } |
300 } |
299 } |
301 |
300 |
302 ++res_bfs; |
301 ++bfs; |
303 } //end of searching augmenting path |
302 } //end of searching augmenting path |
304 |
303 |
305 if (_augment) { |
304 if (_augment) { |
306 Node n=t; |
305 Node n=t; |
307 Number augment_value=free.get(t); |
306 Number augment_value=free.get(t); |
308 while (res_graph.valid(pred.get(n))) { |
307 while (res_graph.valid(pred.get(n))) { |
309 AugEdge e=pred.get(n); |
308 ResGWEdge e=pred.get(n); |
310 res_graph.augment(e, augment_value); |
309 res_graph.augment(e, augment_value); |
311 n=res_graph.tail(e); |
310 n=res_graph.tail(e); |
312 } |
311 } |
313 } |
312 } |
314 |
313 |
328 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); |
327 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); |
329 } |
328 } |
330 }; |
329 }; |
331 |
330 |
332 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
331 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
|
332 typedef MutableGraph MG; |
333 bool _augment=false; |
333 bool _augment=false; |
334 |
334 |
335 AugGraph res_graph(gw, *flow, *capacity); |
335 ResGW res_graph(gw, *flow, *capacity); |
336 |
336 |
337 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
337 typedef typename ResGW::NodeMap<bool> ReachedMap; |
338 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
338 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
339 |
339 |
340 bfs.pushAndSetReached(s); |
340 bfs.pushAndSetReached(s); |
341 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
341 //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
342 DistanceMap<AugGraph> dist(res_graph); |
342 DistanceMap<ResGW> dist(res_graph); |
343 while ( !bfs.finished() ) { |
343 while ( !bfs.finished() ) { |
344 AugOutEdgeIt e=bfs; |
344 ResGWOutEdgeIt e=bfs; |
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
346 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
347 } |
347 } |
348 ++bfs; |
348 ++bfs; |
349 } //computing distances from s in the residual graph |
349 } //computing distances from s in the residual graph |
350 |
350 |
351 MutableGraph F; |
351 MG F; |
352 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; |
352 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; |
353 FilterResGraph filter_res_graph(res_graph, dist); |
353 FilterResGW filter_res_graph(res_graph, dist); |
354 typename AugGraph::NodeMap<typename MutableGraph::Node> |
354 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
355 res_graph_to_F(res_graph); |
355 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
356 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
357 res_graph_to_F.set(n, F.addNode()); |
356 res_graph_to_F.set(n, F.addNode()); |
358 } |
357 } |
359 |
358 |
360 typename MutableGraph::Node sF=res_graph_to_F.get(s); |
359 typename MG::Node sF=res_graph_to_F.get(s); |
361 typename MutableGraph::Node tF=res_graph_to_F.get(t); |
360 typename MG::Node tF=res_graph_to_F.get(t); |
362 |
361 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
363 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
362 typename MG::EdgeMap<Number> residual_capacity(F); |
364 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
|
365 |
363 |
366 //Making F to the graph containing the edges of the residual graph |
364 //Making F to the graph containing the edges of the residual graph |
367 //which are in some shortest paths |
365 //which are in some shortest paths |
368 for(typename FilterResGraph::EdgeIt e=filter_res_graph.template first<typename FilterResGraph::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
366 for(typename FilterResGW::EdgeIt e=filter_res_graph.template first<typename FilterResGW::EdgeIt>(); filter_res_graph.valid(e); filter_res_graph.next(e)) { |
369 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
367 //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { |
370 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
368 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
371 original_edge.update(); |
369 original_edge.update(); |
372 original_edge.set(f, e); |
370 original_edge.set(f, e); |
373 residual_capacity.update(); |
371 residual_capacity.update(); |
374 residual_capacity.set(f, res_graph.free(e)); |
372 residual_capacity.set(f, res_graph.resCap(e)); |
375 //} |
373 //} |
376 } |
374 } |
377 |
375 |
378 bool __augment=true; |
376 bool __augment=true; |
379 |
377 |
380 while (__augment) { |
378 while (__augment) { |
381 __augment=false; |
379 __augment=false; |
382 //computing blocking flow with dfs |
380 //computing blocking flow with dfs |
383 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
381 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; |
384 DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F); |
382 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); |
385 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
383 typename MG::NodeMap<typename MG::Edge> pred(F); |
386 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
384 pred.set(sF, INVALID); |
387 //invalid iterators for sources |
385 //invalid iterators for sources |
388 |
386 |
389 typename MutableGraph::NodeMap<Number> free(F); |
387 typename MG::NodeMap<Number> free(F); |
390 |
388 |
391 dfs.pushAndSetReached(sF); |
389 dfs.pushAndSetReached(sF); |
392 while (!dfs.finished()) { |
390 while (!dfs.finished()) { |
393 ++dfs; |
391 ++dfs; |
394 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
392 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
395 if (dfs.isBNodeNewlyReached()) { |
393 if (dfs.isBNodeNewlyReached()) { |
396 typename MutableGraph::Node v=F.aNode(dfs); |
394 typename MG::Node v=F.aNode(dfs); |
397 typename MutableGraph::Node w=F.bNode(dfs); |
395 typename MG::Node w=F.bNode(dfs); |
398 pred.set(w, dfs); |
396 pred.set(w, dfs); |
399 if (F.valid(pred.get(v))) { |
397 if (F.valid(pred.get(v))) { |
400 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
398 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
401 } else { |
399 } else { |
402 free.set(w, residual_capacity.get(dfs)); |
400 free.set(w, residual_capacity.get(dfs)); |
431 |
429 |
432 return _augment; |
430 return _augment; |
433 } |
431 } |
434 |
432 |
435 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
433 template<typename MutableGraph> bool augmentOnBlockingFlow1() { |
|
434 typedef MutableGraph MG; |
436 bool _augment=false; |
435 bool _augment=false; |
437 |
436 |
438 AugGraph res_graph(gw, *flow, *capacity); |
437 ResGW res_graph(gw, *flow, *capacity); |
439 |
438 |
440 //bfs for distances on the residual graph |
439 //bfs for distances on the residual graph |
441 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
440 typedef typename ResGW::NodeMap<bool> ReachedMap; |
442 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); |
441 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
443 bfs.pushAndSetReached(s); |
442 bfs.pushAndSetReached(s); |
444 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
443 typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's |
445 |
444 |
446 //F will contain the physical copy of the residual graph |
445 //F will contain the physical copy of the residual graph |
447 //with the set of edges which areon shortest paths |
446 //with the set of edges which are on shortest paths |
448 MutableGraph F; |
447 MG F; |
449 typename AugGraph::NodeMap<typename MutableGraph::Node> |
448 typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph); |
450 res_graph_to_F(res_graph); |
449 for(typename ResGW::NodeIt n=res_graph.template first<typename ResGW::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
451 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
452 res_graph_to_F.set(n, F.addNode()); |
450 res_graph_to_F.set(n, F.addNode()); |
453 } |
451 } |
454 typename MutableGraph::Node sF=res_graph_to_F.get(s); |
452 |
455 typename MutableGraph::Node tF=res_graph_to_F.get(t); |
453 typename MG::Node sF=res_graph_to_F.get(s); |
456 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); |
454 typename MG::Node tF=res_graph_to_F.get(t); |
457 typename MutableGraph::EdgeMap<Number> residual_capacity(F); |
455 typename MG::EdgeMap<ResGWEdge> original_edge(F); |
|
456 typename MG::EdgeMap<Number> residual_capacity(F); |
458 |
457 |
459 while ( !bfs.finished() ) { |
458 while ( !bfs.finished() ) { |
460 AugOutEdgeIt e=bfs; |
459 ResGWOutEdgeIt e=bfs; |
461 if (res_graph.valid(e)) { |
460 if (res_graph.valid(e)) { |
462 if (bfs.isBNodeNewlyReached()) { |
461 if (bfs.isBNodeNewlyReached()) { |
463 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
462 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
464 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
463 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
465 original_edge.update(); |
464 original_edge.update(); |
466 original_edge.set(f, e); |
465 original_edge.set(f, e); |
467 residual_capacity.update(); |
466 residual_capacity.update(); |
468 residual_capacity.set(f, res_graph.free(e)); |
467 residual_capacity.set(f, res_graph.resCap(e)); |
469 } else { |
468 } else { |
470 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
469 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { |
471 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
470 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); |
472 original_edge.update(); |
471 original_edge.update(); |
473 original_edge.set(f, e); |
472 original_edge.set(f, e); |
474 residual_capacity.update(); |
473 residual_capacity.update(); |
475 residual_capacity.set(f, res_graph.free(e)); |
474 residual_capacity.set(f, res_graph.resCap(e)); |
476 } |
475 } |
477 } |
476 } |
478 } |
477 } |
479 ++bfs; |
478 ++bfs; |
480 } //computing distances from s in the residual graph |
479 } //computing distances from s in the residual graph |
482 bool __augment=true; |
481 bool __augment=true; |
483 |
482 |
484 while (__augment) { |
483 while (__augment) { |
485 __augment=false; |
484 __augment=false; |
486 //computing blocking flow with dfs |
485 //computing blocking flow with dfs |
487 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; |
486 typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap; |
488 DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F); |
487 DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F); |
489 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); |
488 typename MG::NodeMap<typename MG::Edge> pred(F); |
490 pred.set(sF, typename MutableGraph::Edge(INVALID)); |
489 pred.set(sF, INVALID); |
491 //invalid iterators for sources |
490 //invalid iterators for sources |
492 |
491 |
493 typename MutableGraph::NodeMap<Number> free(F); |
492 typename MG::NodeMap<Number> free(F); |
494 |
493 |
495 dfs.pushAndSetReached(sF); |
494 dfs.pushAndSetReached(sF); |
496 while (!dfs.finished()) { |
495 while (!dfs.finished()) { |
497 ++dfs; |
496 ++dfs; |
498 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
497 if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) { |
499 if (dfs.isBNodeNewlyReached()) { |
498 if (dfs.isBNodeNewlyReached()) { |
500 typename MutableGraph::Node v=F.aNode(dfs); |
499 typename MG::Node v=F.aNode(dfs); |
501 typename MutableGraph::Node w=F.bNode(dfs); |
500 typename MG::Node w=F.bNode(dfs); |
502 pred.set(w, dfs); |
501 pred.set(w, dfs); |
503 if (F.valid(pred.get(v))) { |
502 if (F.valid(pred.get(v))) { |
504 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
503 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
505 } else { |
504 } else { |
506 free.set(w, residual_capacity.get(dfs)); |
505 free.set(w, residual_capacity.get(dfs)); |
510 _augment=true; |
509 _augment=true; |
511 break; |
510 break; |
512 } |
511 } |
513 |
512 |
514 } else { |
513 } else { |
515 F.erase(typename MutableGraph::OutEdgeIt(dfs)); |
514 F.erase(/*typename MG::OutEdgeIt*/(dfs)); |
516 } |
515 } |
517 } |
516 } |
518 } |
517 } |
519 |
518 |
520 if (__augment) { |
519 if (__augment) { |
521 typename MutableGraph::Node n=tF; |
520 typename MG::Node n=tF; |
522 Number augment_value=free.get(tF); |
521 Number augment_value=free.get(tF); |
523 while (F.valid(pred.get(n))) { |
522 while (F.valid(pred.get(n))) { |
524 typename MutableGraph::Edge e=pred.get(n); |
523 typename MG::Edge e=pred.get(n); |
525 res_graph.augment(original_edge.get(e), augment_value); |
524 res_graph.augment(original_edge.get(e), augment_value); |
526 n=F.tail(e); |
525 n=F.tail(e); |
527 if (residual_capacity.get(e)==augment_value) |
526 if (residual_capacity.get(e)==augment_value) |
528 F.erase(e); |
527 F.erase(e); |
529 else |
528 else |
530 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
529 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
531 } |
530 } |
532 } |
531 } |
533 |
532 |
534 } |
533 } |
|
534 |
|
535 return _augment; |
|
536 } |
|
537 |
|
538 bool augmentOnBlockingFlow2() { |
|
539 bool _augment=false; |
|
540 |
|
541 ResGW res_graph(gw, *flow, *capacity); |
|
542 |
|
543 typedef typename ResGW::NodeMap<bool> ReachedMap; |
|
544 BfsIterator5< ResGW, ReachedMap > bfs(res_graph); |
|
545 |
|
546 bfs.pushAndSetReached(s); |
|
547 DistanceMap<ResGW> dist(res_graph); |
|
548 while ( !bfs.finished() ) { |
|
549 ResGWOutEdgeIt e=bfs; |
|
550 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
|
551 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
|
552 } |
|
553 ++bfs; |
|
554 } //computing distances from s in the residual graph |
|
555 |
|
556 //Subgraph containing the edges on some shortest paths |
|
557 typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW; |
|
558 FilterResGW filter_res_graph(res_graph, dist); |
|
559 |
|
560 //Subgraph, which is able to delete edges which are already |
|
561 //met by the dfs |
|
562 typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt> |
|
563 first_out_edges(filter_res_graph); |
|
564 typename FilterResGW::NodeIt v; |
|
565 for(filter_res_graph.first(v); filter_res_graph.valid(v); |
|
566 filter_res_graph.next(v)) |
|
567 { |
|
568 typename FilterResGW::OutEdgeIt e; |
|
569 filter_res_graph.first(e, v); |
|
570 first_out_edges.set(v, e); |
|
571 } |
|
572 typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW:: |
|
573 NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW; |
|
574 ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges); |
|
575 |
|
576 bool __augment=true; |
|
577 |
|
578 while (__augment) { |
|
579 |
|
580 __augment=false; |
|
581 //computing blocking flow with dfs |
|
582 typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap; |
|
583 DfsIterator5< ErasingResGW, BlockingReachedMap > |
|
584 dfs(erasing_res_graph); |
|
585 typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt> |
|
586 pred(erasing_res_graph); |
|
587 pred.set(s, INVALID); |
|
588 //invalid iterators for sources |
|
589 |
|
590 typename ErasingResGW::NodeMap<Number> free(erasing_res_graph); |
|
591 |
|
592 dfs.pushAndSetReached(s); |
|
593 while (!dfs.finished()) { |
|
594 ++dfs; |
|
595 if (erasing_res_graph.valid( |
|
596 /*typename ErasingResGW::OutEdgeIt*/(dfs))) |
|
597 { |
|
598 if (dfs.isBNodeNewlyReached()) { |
|
599 |
|
600 typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs); |
|
601 typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs); |
|
602 |
|
603 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs)); |
|
604 if (erasing_res_graph.valid(pred.get(v))) { |
|
605 free.set(w, std::min(free.get(v), res_graph.resCap(dfs))); |
|
606 } else { |
|
607 free.set(w, res_graph.resCap(dfs)); |
|
608 } |
|
609 |
|
610 if (w==t) { |
|
611 __augment=true; |
|
612 _augment=true; |
|
613 break; |
|
614 } |
|
615 } else { |
|
616 erasing_res_graph.erase(dfs); |
|
617 } |
|
618 } |
|
619 } |
|
620 |
|
621 if (__augment) { |
|
622 typename ErasingResGW::Node n=t; |
|
623 Number augment_value=free.get(n); |
|
624 while (erasing_res_graph.valid(pred.get(n))) { |
|
625 typename ErasingResGW::OutEdgeIt e=pred.get(n); |
|
626 res_graph.augment(e, augment_value); |
|
627 n=erasing_res_graph.tail(e); |
|
628 if (res_graph.resCap(e)==0) |
|
629 erasing_res_graph.erase(e); |
|
630 } |
|
631 } |
|
632 |
|
633 } //while (__augment) |
535 |
634 |
536 return _augment; |
635 return _augment; |
537 } |
636 } |
538 |
637 |
539 // bool augmentOnBlockingFlow2() { |
638 // bool augmentOnBlockingFlow2() { |
622 |
721 |
623 // } |
722 // } |
624 |
723 |
625 // return _augment; |
724 // return _augment; |
626 // } |
725 // } |
627 // void run() { |
726 |
628 // //int num_of_augmentations=0; |
727 void run() { |
629 // while (augmentOnShortestPath()) { |
728 //int num_of_augmentations=0; |
630 // //while (augmentOnBlockingFlow<MutableGraph>()) { |
729 while (augmentOnShortestPath()) { |
631 // //std::cout << ++num_of_augmentations << " "; |
730 //while (augmentOnBlockingFlow<MutableGraph>()) { |
632 // //std::cout<<std::endl; |
731 //std::cout << ++num_of_augmentations << " "; |
633 // } |
732 //std::cout<<std::endl; |
634 // } |
733 } |
635 // template<typename MutableGraph> void run() { |
734 } |
636 // //int num_of_augmentations=0; |
735 |
637 // //while (augmentOnShortestPath()) { |
736 template<typename MutableGraph> void run() { |
638 // while (augmentOnBlockingFlow<MutableGraph>()) { |
737 //int num_of_augmentations=0; |
639 // //std::cout << ++num_of_augmentations << " "; |
738 //while (augmentOnShortestPath()) { |
640 // //std::cout<<std::endl; |
739 while (augmentOnBlockingFlow<MutableGraph>()) { |
641 // } |
740 //std::cout << ++num_of_augmentations << " "; |
642 // } |
741 //std::cout<<std::endl; |
|
742 } |
|
743 } |
|
744 |
643 Number flowValue() { |
745 Number flowValue() { |
644 Number a=0; |
746 Number a=0; |
645 OutEdgeIt e; |
747 OutEdgeIt e; |
646 for(gw.first(e, s); gw.valid(e); gw.next(e)) { |
748 for(gw.first(e, s); gw.valid(e); gw.next(e)) { |
647 a+=flow->get(e); |
749 a+=flow->get(e); |
648 } |
750 } |
649 return a; |
751 return a; |
650 } |
752 } |
|
753 |
651 }; |
754 }; |
652 |
755 |
653 |
756 |
654 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
757 // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap> |
655 // class MaxMatching { |
758 // class MaxMatching { |
682 // bool augmentOnShortestPath() { |
785 // bool augmentOnShortestPath() { |
683 // AugGraph res_graph(*G, *flow, *capacity); |
786 // AugGraph res_graph(*G, *flow, *capacity); |
684 // bool _augment=false; |
787 // bool _augment=false; |
685 |
788 |
686 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
789 // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
687 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph); |
790 // BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph); |
688 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
791 // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
689 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
792 // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) { |
690 // if ((S->get(s)) && (used.get(s)<1) ) { |
793 // if ((S->get(s)) && (used.get(s)<1) ) { |
691 // //Number u=0; |
794 // //Number u=0; |
692 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
795 // //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e)) |
693 // //u+=flow->get(e); |
796 // //u+=flow->get(e); |
694 // //if (u<1) { |
797 // //if (u<1) { |
695 // res_bfs.pushAndSetReached(s); |
798 // bfs.pushAndSetReached(s); |
696 // pred.set(s, AugEdge(INVALID)); |
799 // pred.set(s, AugEdge(INVALID)); |
697 // //} |
800 // //} |
698 // } |
801 // } |
699 // } |
802 // } |
700 |
803 |
701 // typename AugGraph::NodeMap<Number> free(res_graph); |
804 // typename AugGraph::NodeMap<Number> free(res_graph); |
702 |
805 |
703 // Node n; |
806 // Node n; |
704 // //searching for augmenting path |
807 // //searching for augmenting path |
705 // while ( !res_bfs.finished() ) { |
808 // while ( !bfs.finished() ) { |
706 // AugOutEdgeIt e=res_bfs; |
809 // AugOutEdgeIt e=bfs; |
707 // if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
810 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
708 // Node v=res_graph.tail(e); |
811 // Node v=res_graph.tail(e); |
709 // Node w=res_graph.head(e); |
812 // Node w=res_graph.head(e); |
710 // pred.set(w, e); |
813 // pred.set(w, e); |
711 // if (res_graph.valid(pred.get(v))) { |
814 // if (res_graph.valid(pred.get(v))) { |
712 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
815 // free.set(w, std::min(free.get(v), res_graph.free(e))); |
1054 // // AugGraph res_graph(G, flow, capacity); |
1157 // // AugGraph res_graph(G, flow, capacity); |
1055 // // bool _augment=false; |
1158 // // bool _augment=false; |
1056 // // Node reached_t_node; |
1159 // // Node reached_t_node; |
1057 |
1160 |
1058 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
1161 // // typedef typename AugGraph::NodeMap<bool> ReachedMap; |
1059 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph); |
1162 // // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
1060 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
1163 // // for(typename std::list<Node>::const_iterator i=S.begin(); |
1061 // // i!=S.end(); ++i) { |
1164 // // i!=S.end(); ++i) { |
1062 // // res_bfs.pushAndSetReached(*i); |
1165 // // bfs.pushAndSetReached(*i); |
1063 // // } |
1166 // // } |
1064 // // //res_bfs.pushAndSetReached(s); |
1167 // // //bfs.pushAndSetReached(s); |
1065 |
1168 |
1066 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
1169 // // typename AugGraph::NodeMap<AugEdge> pred(res_graph); |
1067 // // //filled up with invalid iterators |
1170 // // //filled up with invalid iterators |
1068 |
1171 |
1069 // // typename AugGraph::NodeMap<Number> free(res_graph); |
1172 // // typename AugGraph::NodeMap<Number> free(res_graph); |
1070 |
1173 |
1071 // // //searching for augmenting path |
1174 // // //searching for augmenting path |
1072 // // while ( !res_bfs.finished() ) { |
1175 // // while ( !bfs.finished() ) { |
1073 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
1176 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
1074 // // if (e.valid() && res_bfs.isBNodeNewlyReached()) { |
1177 // // if (e.valid() && bfs.isBNodeNewlyReached()) { |
1075 // // Node v=res_graph.tail(e); |
1178 // // Node v=res_graph.tail(e); |
1076 // // Node w=res_graph.head(e); |
1179 // // Node w=res_graph.head(e); |
1077 // // pred.set(w, e); |
1180 // // pred.set(w, e); |
1078 // // if (pred.get(v).valid()) { |
1181 // // if (pred.get(v).valid()) { |
1079 // // free.set(w, std::min(free.get(v), e.free())); |
1182 // // free.set(w, std::min(free.get(v), e.free())); |