264 const CapacityMap* capacity; |
264 const CapacityMap* capacity; |
265 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
265 typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph; |
266 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
266 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; |
267 typedef typename AugGraph::Edge AugEdge; |
267 typedef typename AugGraph::Edge AugEdge; |
268 |
268 |
269 //AugGraph res_graph; |
|
270 //typedef typename AugGraph::NodeMap<bool> ReachedMap; |
|
271 //typename AugGraph::NodeMap<AugEdge> pred; |
|
272 //typename AugGraph::NodeMap<Number> free; |
|
273 public: |
269 public: |
274 MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
270 MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : |
275 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, |
271 G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { } |
276 //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) |
|
277 { } |
|
278 bool augmentOnShortestPath() { |
272 bool augmentOnShortestPath() { |
279 AugGraph res_graph(*G, *flow, *capacity); |
273 AugGraph res_graph(*G, *flow, *capacity); |
280 bool _augment=false; |
274 bool _augment=false; |
281 |
275 |
282 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
276 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
288 |
282 |
289 typename AugGraph::NodeMap<Number> free(res_graph); |
283 typename AugGraph::NodeMap<Number> free(res_graph); |
290 |
284 |
291 //searching for augmenting path |
285 //searching for augmenting path |
292 while ( !res_bfs.finished() ) { |
286 while ( !res_bfs.finished() ) { |
293 AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs); |
287 AugOutEdgeIt e=res_bfs; |
294 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
288 if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) { |
295 Node v=res_graph.tail(e); |
289 Node v=res_graph.tail(e); |
296 Node w=res_graph.head(e); |
290 Node w=res_graph.head(e); |
297 pred.set(w, e); |
291 pred.set(w, e); |
298 if (res_graph.valid(pred.get(v))) { |
292 if (res_graph.valid(pred.get(v))) { |
310 Node n=t; |
304 Node n=t; |
311 Number augment_value=free.get(t); |
305 Number augment_value=free.get(t); |
312 while (res_graph.valid(pred.get(n))) { |
306 while (res_graph.valid(pred.get(n))) { |
313 AugEdge e=pred.get(n); |
307 AugEdge e=pred.get(n); |
314 res_graph.augment(e, augment_value); |
308 res_graph.augment(e, augment_value); |
315 //e.augment(augment_value); |
|
316 n=res_graph.tail(e); |
309 n=res_graph.tail(e); |
317 } |
310 } |
318 } |
311 } |
319 |
312 |
320 return _augment; |
313 return _augment; |
321 } |
314 } |
322 |
315 |
323 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
316 template<typename MutableGraph> bool augmentOnBlockingFlow() { |
324 |
|
325 // std::cout << "number of nodes: " << G->nodeNum() << std::endl; |
|
326 // typename Graph::NodeIt n; |
|
327 // G->first(n); |
|
328 // for( ; G->valid(n); G->next(n)) { |
|
329 // std::cout << G->id(n) << std::endl; |
|
330 // } |
|
331 // std::cout << "meg elek 1"; |
|
332 |
|
333 // for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) { |
|
334 // std::cout << G->id(n) << std::endl; |
|
335 // } |
|
336 // std::cout << "meg elek 2"; |
|
337 |
|
338 bool _augment=false; |
317 bool _augment=false; |
339 |
318 |
340 AugGraph res_graph(*G, *flow, *capacity); |
319 AugGraph res_graph(*G, *flow, *capacity); |
341 |
320 |
342 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
321 typedef typename AugGraph::NodeMap<bool> ReachedMap; |
343 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
322 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); |
344 |
323 |
345 bfs.pushAndSetReached(s); |
324 bfs.pushAndSetReached(s); |
346 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
347 while ( !bfs.finished() ) { |
326 while ( !bfs.finished() ) { |
348 AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
327 AugOutEdgeIt e=bfs; |
349 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
328 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
350 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
329 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
351 } |
330 } |
352 |
331 |
353 ++bfs; |
332 ++bfs; |
354 } //computing distances from s in the residual graph |
333 } //computing distances from s in the residual graph |
355 |
|
356 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
357 // std::cout << res_graph.id(n) << std::endl; |
|
358 // } |
|
359 // std::cout << "meg elek"; |
|
360 |
334 |
361 MutableGraph F; |
335 MutableGraph F; |
362 typename AugGraph::NodeMap<typename MutableGraph::Node> |
336 typename AugGraph::NodeMap<typename MutableGraph::Node> |
363 res_graph_to_F(res_graph); |
337 res_graph_to_F(res_graph); |
364 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
338 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
403 dfs.pushAndSetReached(sF); |
373 dfs.pushAndSetReached(sF); |
404 while (!dfs.finished()) { |
374 while (!dfs.finished()) { |
405 ++dfs; |
375 ++dfs; |
406 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { |
407 if (dfs.isBNodeNewlyReached()) { |
377 if (dfs.isBNodeNewlyReached()) { |
408 // std::cout << "OutEdgeIt: " << dfs; |
|
409 // std::cout << " aNode: " << F.aNode(dfs); |
|
410 // std::cout << " bNode: " << F.bNode(dfs) << " "; |
|
411 |
|
412 typename MutableGraph::Node v=F.aNode(dfs); |
378 typename MutableGraph::Node v=F.aNode(dfs); |
413 typename MutableGraph::Node w=F.bNode(dfs); |
379 typename MutableGraph::Node w=F.bNode(dfs); |
414 pred.set(w, dfs); |
380 pred.set(w, dfs); |
415 if (F.valid(pred.get(v))) { |
381 if (F.valid(pred.get(v))) { |
416 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
382 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); |
417 } else { |
383 } else { |
418 free.set(w, residual_capacity.get(dfs)); |
384 free.set(w, residual_capacity.get(dfs)); |
419 } |
385 } |
420 if (w==tF) { |
386 if (w==tF) { |
421 //std::cout << "AUGMENTATION"<<std::endl; |
|
422 __augment=true; |
387 __augment=true; |
423 _augment=true; |
388 _augment=true; |
424 break; |
389 break; |
425 } |
390 } |
426 |
391 |
434 typename MutableGraph::Node n=tF; |
399 typename MutableGraph::Node n=tF; |
435 Number augment_value=free.get(tF); |
400 Number augment_value=free.get(tF); |
436 while (F.valid(pred.get(n))) { |
401 while (F.valid(pred.get(n))) { |
437 typename MutableGraph::Edge e=pred.get(n); |
402 typename MutableGraph::Edge e=pred.get(n); |
438 res_graph.augment(original_edge.get(e), augment_value); |
403 res_graph.augment(original_edge.get(e), augment_value); |
439 //original_edge.get(e).augment(augment_value); |
|
440 n=F.tail(e); |
404 n=F.tail(e); |
441 if (residual_capacity.get(e)==augment_value) |
405 if (residual_capacity.get(e)==augment_value) |
442 F.erase(e); |
406 F.erase(e); |
443 else |
407 else |
444 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
408 residual_capacity.set(e, residual_capacity.get(e)-augment_value); |
457 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
421 typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt; |
458 typedef typename EAugGraph::Edge EAugEdge; |
422 typedef typename EAugGraph::Edge EAugEdge; |
459 |
423 |
460 EAugGraph res_graph(*G, *flow, *capacity); |
424 EAugGraph res_graph(*G, *flow, *capacity); |
461 |
425 |
462 //std::cout << "meg jo1" << std::endl; |
|
463 |
|
464 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
426 //typedef typename EAugGraph::NodeMap<bool> ReachedMap; |
465 BfsIterator4< |
427 BfsIterator4< |
466 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
428 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, |
467 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
429 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, |
468 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
430 ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph); |
469 |
431 |
470 //std::cout << "meg jo2" << std::endl; |
|
471 |
|
472 bfs.pushAndSetReached(s); |
432 bfs.pushAndSetReached(s); |
473 //std::cout << "meg jo2.5" << std::endl; |
433 |
474 |
|
475 //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's |
|
476 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
434 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>:: |
477 NodeMap<int>& dist=res_graph.dist; |
435 NodeMap<int>& dist=res_graph.dist; |
478 //std::cout << "meg jo2.6" << std::endl; |
|
479 |
436 |
480 while ( !bfs.finished() ) { |
437 while ( !bfs.finished() ) { |
481 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
438 typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; |
482 // EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); |
|
483 //if (res_graph.valid(e)) { |
|
484 // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl; |
|
485 //} |
|
486 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
439 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { |
487 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
440 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); |
488 } |
441 } |
489 |
|
490 ++bfs; |
442 ++bfs; |
491 } //computing distances from s in the residual graph |
443 } //computing distances from s in the residual graph |
492 |
444 |
493 |
|
494 //std::cout << "meg jo3" << std::endl; |
|
495 |
|
496 // typedef typename EAugGraph::NodeIt EAugNodeIt; |
|
497 // for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) { |
|
498 // std::cout << "dist: " << dist.get(n) << std::endl; |
|
499 // } |
|
500 |
|
501 bool __augment=true; |
445 bool __augment=true; |
502 |
446 |
503 while (__augment) { |
447 while (__augment) { |
504 // std::cout << "new iteration"<< std::endl; |
|
505 |
448 |
506 __augment=false; |
449 __augment=false; |
507 //computing blocking flow with dfs |
450 //computing blocking flow with dfs |
508 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
451 typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap; |
509 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
452 DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > |
517 dfs.pushAndSetReached(s); |
460 dfs.pushAndSetReached(s); |
518 while (!dfs.finished()) { |
461 while (!dfs.finished()) { |
519 ++dfs; |
462 ++dfs; |
520 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
463 if (res_graph.valid(EAugOutEdgeIt(dfs))) { |
521 if (dfs.isBNodeNewlyReached()) { |
464 if (dfs.isBNodeNewlyReached()) { |
522 // std::cout << "OutEdgeIt: " << dfs; |
|
523 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
524 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
525 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
526 |
465 |
527 typename EAugGraph::Node v=res_graph.aNode(dfs); |
466 typename EAugGraph::Node v=res_graph.aNode(dfs); |
528 typename EAugGraph::Node w=res_graph.bNode(dfs); |
467 typename EAugGraph::Node w=res_graph.bNode(dfs); |
529 |
468 |
530 pred.set(w, EAugOutEdgeIt(dfs)); |
469 pred.set(w, EAugOutEdgeIt(dfs)); |
531 |
|
532 //std::cout << EAugOutEdgeIt(dfs).free() << std::endl; |
|
533 if (res_graph.valid(pred.get(v))) { |
470 if (res_graph.valid(pred.get(v))) { |
534 free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs)))); |
471 free.set(w, std::min(free.get(v), res_graph.free(dfs))); |
535 } else { |
472 } else { |
536 free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); |
473 free.set(w, res_graph.free(dfs)); |
537 } |
474 } |
538 |
475 |
539 if (w==t) { |
476 if (w==t) { |
540 // std::cout << "t is reached, AUGMENTATION"<<std::endl; |
|
541 __augment=true; |
477 __augment=true; |
542 _augment=true; |
478 _augment=true; |
543 break; |
479 break; |
544 } |
480 } |
545 } else { |
481 } else { |
546 // std::cout << "<<DELETE "; |
|
547 // std::cout << " aNode: " << res_graph.aNode(dfs); |
|
548 // std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); |
|
549 // std::cout << " bNode: " << res_graph.bNode(dfs) << " "; |
|
550 // std::cout << "DELETE>> "; |
|
551 |
|
552 res_graph.erase(dfs); |
482 res_graph.erase(dfs); |
553 } |
483 } |
554 } |
484 } |
555 |
485 |
556 } |
486 } |
557 |
487 |
558 if (__augment) { |
488 if (__augment) { |
559 typename EAugGraph::Node n=t; |
489 typename EAugGraph::Node n=t; |
560 Number augment_value=free.get(t); |
490 Number augment_value=free.get(t); |
561 // std::cout << "av:" << augment_value << std::endl; |
|
562 while (res_graph.valid(pred.get(n))) { |
491 while (res_graph.valid(pred.get(n))) { |
563 EAugEdge e=pred.get(n); |
492 EAugEdge e=pred.get(n); |
564 res_graph.augment(e, augment_value); |
493 res_graph.augment(e, augment_value); |
565 //e.augment(augment_value); |
|
566 n=res_graph.tail(e); |
494 n=res_graph.tail(e); |
567 if (res_graph.free(e)==0) |
495 if (res_graph.free(e)==0) |
568 res_graph.erase(e); |
496 res_graph.erase(e); |
569 } |
497 } |
570 } |
498 } |