272 else { |
272 else { |
273 end=false; |
273 end=false; |
274 Node w=first[b]; |
274 Node w=first[b]; |
275 first[b]=next[w]; |
275 first[b]=next[w]; |
276 int newlevel=push(w, next, first); |
276 int newlevel=push(w, next, first); |
277 if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, |
277 if ( excess[w] != 0 ) { |
278 left, right, b, k, what_heur); |
278 relabel(w, newlevel, first, next, level_list, |
|
279 left, right, b, k, what_heur); |
|
280 } |
279 |
281 |
280 ++numrelabel; |
282 ++numrelabel; |
281 if ( numrelabel >= heur ) { |
283 if ( numrelabel >= heur ) { |
282 numrelabel=0; |
284 numrelabel=0; |
283 if ( what_heur ) { |
285 if ( what_heur ) { |
314 /// \ref flowMap() return a maximum flow, \ref flowValue |
316 /// \ref flowMap() return a maximum flow, \ref flowValue |
315 ///returns the value of a maximum flow, \ref minCut returns a |
317 ///returns the value of a maximum flow, \ref minCut returns a |
316 ///minimum cut, while the methods \ref minMinCut and \ref |
318 ///minimum cut, while the methods \ref minMinCut and \ref |
317 ///maxMinCut return the inclusionwise minimum and maximum cuts of |
319 ///maxMinCut return the inclusionwise minimum and maximum cuts of |
318 ///minimum value, resp. \pre \ref phase1 must be called before. |
320 ///minimum value, resp. \pre \ref phase1 must be called before. |
|
321 /// |
|
322 /// \todo The inexact computation can cause positive excess on a set of |
|
323 /// unpushable nodes. We may have to watch the empty level in this case |
|
324 /// due to avoid the terrible long running time. |
319 void phase2() |
325 void phase2() |
320 { |
326 { |
321 |
327 |
322 int k=_node_num-2; //bound on the highest level under n containing a node |
328 int k=_node_num-2; //bound on the highest level under n containing a node |
323 int b=k; //bound on the highest level under n of an active node |
329 int b=k; //bound on the highest level under n of an active node |
334 Node v=bfs_queue.front(); |
340 Node v=bfs_queue.front(); |
335 bfs_queue.pop(); |
341 bfs_queue.pop(); |
336 int l=level[v]+1; |
342 int l=level[v]+1; |
337 |
343 |
338 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) { |
344 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) { |
339 if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue; |
345 if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue; |
340 Node u=_g->source(e); |
346 Node u=_g->source(e); |
341 if ( level[u] >= _node_num ) { |
347 if ( level[u] >= _node_num ) { |
342 bfs_queue.push(u); |
348 bfs_queue.push(u); |
343 level.set(u, l); |
349 level.set(u, l); |
344 if ( _surely.positive(excess[u]) ) { |
350 if ( excess[u] != 0 ) { |
345 next.set(u,first[l]); |
351 next.set(u,first[l]); |
346 first[l]=u; |
352 first[l]=u; |
347 } |
353 } |
348 } |
354 } |
349 } |
355 } |
352 if ( !_surely.positive((*_flow)[e]) ) continue; |
358 if ( !_surely.positive((*_flow)[e]) ) continue; |
353 Node u=_g->target(e); |
359 Node u=_g->target(e); |
354 if ( level[u] >= _node_num ) { |
360 if ( level[u] >= _node_num ) { |
355 bfs_queue.push(u); |
361 bfs_queue.push(u); |
356 level.set(u, l); |
362 level.set(u, l); |
357 if ( _surely.positive(excess[u]) ) { |
363 if ( excess[u] != 0 ) { |
358 next.set(u,first[l]); |
364 next.set(u,first[l]); |
359 first[l]=u; |
365 first[l]=u; |
360 } |
366 } |
361 } |
367 } |
362 } |
368 } |
370 else { |
376 else { |
371 Node w=first[b]; |
377 Node w=first[b]; |
372 first[b]=next[w]; |
378 first[b]=next[w]; |
373 int newlevel=push(w,next, first); |
379 int newlevel=push(w,next, first); |
374 |
380 |
|
381 if ( newlevel == _node_num) { |
|
382 excess.set(w, 0); |
|
383 level.set(w,_node_num); |
|
384 } |
375 //relabel |
385 //relabel |
376 if ( _surely.positive(excess[w]) ) { |
386 if ( excess[w] != 0 ) { |
377 level.set(w,++newlevel); |
387 level.set(w,++newlevel); |
378 next.set(w,first[newlevel]); |
388 next.set(w,first[newlevel]); |
379 first[newlevel]=w; |
389 first[newlevel]=w; |
380 b=newlevel; |
390 b=newlevel; |
381 } |
391 } |
574 int lev=level[w]; |
584 int lev=level[w]; |
575 Num exc=excess[w]; |
585 Num exc=excess[w]; |
576 int newlevel=_node_num; //bound on the next level of w |
586 int newlevel=_node_num; //bound on the next level of w |
577 |
587 |
578 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { |
588 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { |
579 if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue; |
589 if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue; |
580 Node v=_g->target(e); |
590 Node v=_g->target(e); |
581 |
591 |
582 if( lev > level[v] ) { //Push is allowed now |
592 if( lev > level[v] ) { //Push is allowed now |
583 |
593 |
584 if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) { |
594 if ( excess[v] == 0 && v!=_target && v!=_source ) { |
585 next.set(v,first[level[v]]); |
595 next.set(v,first[level[v]]); |
586 first[level[v]]=v; |
596 first[level[v]]=v; |
587 } |
597 } |
588 |
598 |
589 Num cap=(*_capacity)[e]; |
599 Num cap=(*_capacity)[e]; |
603 exc-=remcap; |
613 exc-=remcap; |
604 } |
614 } |
605 } else if ( newlevel > level[v] ) newlevel = level[v]; |
615 } else if ( newlevel > level[v] ) newlevel = level[v]; |
606 } //for out edges wv |
616 } //for out edges wv |
607 |
617 |
608 if ( _surely.positive(exc) ) { |
618 if ( exc != 0 ) { |
609 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { |
619 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { |
610 |
620 |
611 if ( !_surely.positive((*_flow)[e]) ) continue; |
621 if ( !_surely.positive((*_flow)[e]) ) continue; |
612 Node v=_g->source(e); |
622 Node v=_g->source(e); |
613 |
623 |
614 if( lev > level[v] ) { //Push is allowed now |
624 if( lev > level[v] ) { //Push is allowed now |
615 |
625 |
616 if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) { |
626 if ( excess[v] == 0 && v!=_target && v!=_source ) { |
617 next.set(v,first[level[v]]); |
627 next.set(v,first[level[v]]); |
618 first[level[v]]=v; |
628 first[level[v]]=v; |
619 } |
629 } |
620 |
630 |
621 Num flo=(*_flow)[e]; |
631 Num flo=(*_flow)[e]; |
661 Node v=bfs_queue.front(); |
671 Node v=bfs_queue.front(); |
662 bfs_queue.pop(); |
672 bfs_queue.pop(); |
663 int l=level[v]+1; |
673 int l=level[v]+1; |
664 |
674 |
665 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { |
675 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { |
666 if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue; |
676 if ( !_surely.positive((*_capacity)[e] - (*_flow)[e] )) continue; |
667 Node w=_g->source(e); |
677 Node w=_g->source(e); |
668 if ( level[w] == _node_num && w != _source ) { |
678 if ( level[w] == _node_num && w != _source ) { |
669 bfs_queue.push(w); |
679 bfs_queue.push(w); |
670 Node z=level_list[l]; |
680 Node z=level_list[l]; |
671 if ( z!=INVALID ) left.set(z,w); |
681 if ( z!=INVALID ) left.set(z,w); |
724 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { |
734 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { |
725 Num c=(*_capacity)[e]; |
735 Num c=(*_capacity)[e]; |
726 if ( !_surely.positive(c) ) continue; |
736 if ( !_surely.positive(c) ) continue; |
727 Node w=_g->target(e); |
737 Node w=_g->target(e); |
728 if ( level[w] < _node_num ) { |
738 if ( level[w] < _node_num ) { |
729 if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack |
739 if ( excess[w] == 0 && w!=_target ) { //putting into the stack |
730 next.set(w,first[level[w]]); |
740 next.set(w,first[level[w]]); |
731 first[level[w]]=w; |
741 first[level[w]]=w; |
732 } |
742 } |
733 _flow->set(e, c); |
743 _flow->set(e, c); |
734 excess.set(w, excess[w]+c); |
744 excess.set(w, excess[w]+c); |
740 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); |
750 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); |
741 { |
751 { |
742 Num exc=0; |
752 Num exc=0; |
743 for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e]; |
753 for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e]; |
744 for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e]; |
754 for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e]; |
745 excess.set(_target,exc); |
755 if (!_surely.positive(exc)) { |
|
756 exc = 0; |
|
757 } |
|
758 excess.set(_target,exc); |
746 } |
759 } |
747 |
760 |
748 //the starting flow |
761 //the starting flow |
749 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) { |
762 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) { |
750 Num rem=(*_capacity)[e]-(*_flow)[e]; |
763 Num rem=(*_capacity)[e]-(*_flow)[e]; |
751 if ( !_surely.positive(rem) ) continue; |
764 if ( !_surely.positive(rem) ) continue; |
752 Node w=_g->target(e); |
765 Node w=_g->target(e); |
753 if ( level[w] < _node_num ) { |
766 if ( level[w] < _node_num ) { |
754 if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack |
767 if ( excess[w] == 0 && w!=_target ) { //putting into the stack |
755 next.set(w,first[level[w]]); |
768 next.set(w,first[level[w]]); |
756 first[level[w]]=w; |
769 first[level[w]]=w; |
757 } |
770 } |
758 _flow->set(e, (*_capacity)[e]); |
771 _flow->set(e, (*_capacity)[e]); |
759 excess.set(w, excess[w]+rem); |
772 excess.set(w, excess[w]+rem); |
762 |
775 |
763 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) { |
776 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) { |
764 if ( !_surely.positive((*_flow)[e]) ) continue; |
777 if ( !_surely.positive((*_flow)[e]) ) continue; |
765 Node w=_g->source(e); |
778 Node w=_g->source(e); |
766 if ( level[w] < _node_num ) { |
779 if ( level[w] < _node_num ) { |
767 if ( !_surely.positive(excess[w]) && w!=_target ) { |
780 if ( excess[w] == 0 && w!=_target ) { |
768 next.set(w,first[level[w]]); |
781 next.set(w,first[level[w]]); |
769 first[level[w]]=w; |
782 first[level[w]]=w; |
770 } |
783 } |
771 excess.set(w, excess[w]+(*_flow)[e]); |
784 excess.set(w, excess[w]+(*_flow)[e]); |
772 _flow->set(e, 0); |
785 _flow->set(e, 0); |
792 //computing the excess |
805 //computing the excess |
793 for(NodeIt w(*_g); w!=INVALID; ++w) { |
806 for(NodeIt w(*_g); w!=INVALID; ++w) { |
794 Num exc=0; |
807 Num exc=0; |
795 for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e]; |
808 for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e]; |
796 for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e]; |
809 for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e]; |
|
810 if (!_surely.positive(exc)) { |
|
811 exc = 0; |
|
812 } |
797 excess.set(w,exc); |
813 excess.set(w,exc); |
798 |
814 |
799 //putting the active nodes into the stack |
815 //putting the active nodes into the stack |
800 int lev=level[w]; |
816 int lev=level[w]; |
801 if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) { |
817 if ( exc != 0 && lev < _node_num && Node(w) != _target ) { |
802 next.set(w,first[lev]); |
818 next.set(w,first[lev]); |
803 first[lev]=w; |
819 first[lev]=w; |
804 } |
820 } |
805 } |
821 } |
806 break; |
822 break; |