441 } |
442 } |
442 } |
443 } |
443 |
444 |
444 return _augment; |
445 return _augment; |
445 } |
446 } |
|
447 bool augmentWithBlockingFlow() { |
|
448 BfsIterator4< Graph, OutEdgeIt, typename Graph::NodeMap<bool> > bfs(G); |
|
449 bfs.pushAndSetReached(s); |
|
450 typename Graph::NodeMap<int> dist(G); //filled up with 0's |
|
451 while ( !bfs.finished() ) { |
|
452 OutEdgeIt e=OutEdgeIt(bfs); |
|
453 if (e.valid() && bfs.isBNodeNewlyReached()) { |
|
454 dist.set(G.head(e), dist.get(G.tail(e))+1); |
|
455 //NodeIt v=res_graph.tail(e); |
|
456 //NodeIt w=res_graph.head(e); |
|
457 //pred.set(w, e); |
|
458 //if (pred.get(v).valid()) { |
|
459 // free.set(w, std::min(free.get(v), e.free())); |
|
460 //} else { |
|
461 // free.set(w, e.free()); |
|
462 //} |
|
463 //if (res_graph.head(e)==t) { _augment=true; break; } |
|
464 } |
|
465 |
|
466 ++bfs; |
|
467 } //end of searching augmenting path |
|
468 |
|
469 double pre_time_copy=currTime(); |
|
470 typedef Graph MutableGraph; |
|
471 MutableGraph F; |
|
472 typename Graph::NodeMap<NodeIt> G_to_F(G); |
|
473 for(typename Graph::EachNodeIt n=G.template first<typename Graph::EachNodeIt>(); n.valid(); ++n) { |
|
474 G_to_F.set(n, F.addNode()); |
|
475 } |
|
476 for(typename Graph::EachEdgeIt e=G.template first<typename Graph::EachEdgeIt>(); e.valid(); ++e) { |
|
477 if (dist.get(G.head(e))==dist.get(G.tail(e))+1) { |
|
478 F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e))); |
|
479 } |
|
480 } |
|
481 double post_time_copy=currTime(); |
|
482 std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl; |
|
483 |
|
484 return 0; |
|
485 } |
446 void run() { |
486 void run() { |
447 while (augment()) { } |
487 //int num_of_augmentations=0; |
|
488 while (augment()) { |
|
489 //std::cout << ++num_of_augmentations << " "; |
|
490 //std::cout<<std::endl; |
|
491 } |
448 } |
492 } |
449 Number flowValue() { |
493 Number flowValue() { |
450 Number a=0; |
494 Number a=0; |
451 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { |
495 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) { |
452 a+=flow.get(i); |
496 a+=flow.get(i); |