Changeset 2024:4ab8a25def3c in lemon-0.x
- Timestamp:
- 03/30/06 17:34:56 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2663
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/preflow.h
r2019 r2024 40 40 ///This class provides an implementation of the \e preflow \e 41 41 ///algorithm producing a flow of maximum value in a directed 42 ///graph. The preflow algorithms are the fastest known max flow algorithms 43 /// up to now.The \e source node, the \e target node, the \e42 ///graph. The preflow algorithms are the fastest known max flow algorithms. 43 ///The \e source node, the \e target node, the \e 44 44 ///capacity of the edges and the \e starting \e flow value of the 45 45 ///edges should be passed to the algorithm through the … … 60 60 ///\param CapacityMap The capacity map type. 61 61 ///\param FlowMap The flow map type. 62 ///\param Tolerance The tolerance type. 62 63 /// 63 64 ///\author Jacint Szabo 64 65 ///\todo Second template parameter is superfluous 65 ///\todo Using tolerance66 66 template <typename Graph, typename Num, 67 67 typename CapacityMap=typename Graph::template EdgeMap<Num>, … … 248 248 249 249 int k=_node_num-2; //bound on the highest level under n containing a node 250 int b=k; //bound on the highest level under n ofan active node250 int b=k; //bound on the highest level under n containing an active node 251 251 252 252 VecNode first(_node_num, INVALID); … … 275 275 first[b]=next[w]; 276 276 int newlevel=push(w, next, first); 277 if ( excess[w] > 0) relabel(w, newlevel, first, next, level_list,277 if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, 278 278 left, right, b, k, what_heur); 279 279 … … 337 337 338 338 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) { 339 if ( (*_capacity)[e] <= (*_flow)[e]) continue;339 if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue; 340 340 Node u=_g->source(e); 341 341 if ( level[u] >= _node_num ) { 342 342 bfs_queue.push(u); 343 343 level.set(u, l); 344 if ( excess[u] > 0) {344 if ( _surely.positive(excess[u]) ) { 345 345 next.set(u,first[l]); 346 346 first[l]=u; … … 350 350 351 351 for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) { 352 if ( 0 >= (*_flow)[e]) continue;352 if ( !_surely.positive((*_flow)[e]) ) continue; 353 353 Node u=_g->target(e); 354 354 if ( level[u] >= _node_num ) { 355 355 bfs_queue.push(u); 356 356 level.set(u, l); 357 if ( excess[u] > 0) {357 if ( _surely.positive(excess[u]) ) { 358 358 next.set(u,first[l]); 359 359 first[l]=u; … … 374 374 375 375 //relabel 376 if ( excess[w] > 0) {376 if ( _surely.positive(excess[w]) ) { 377 377 level.set(w,++newlevel); 378 378 next.set(w,first[newlevel]); … … 444 444 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 445 445 Node v=_g->target(e); 446 if (!M[v] && (*_flow)[e] < (*_capacity)[e]) {446 if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) { 447 447 queue.push(v); 448 448 M.set(v, true); … … 452 452 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 453 453 Node v=_g->source(e); 454 if (!M[v] && (*_flow)[e] > 0) {454 if (!M[v] && _surely.positive((*_flow)[e]) ) { 455 455 queue.push(v); 456 456 M.set(v, true); … … 482 482 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 483 483 Node v=_g->source(e); 484 if (M[v] && (*_flow)[e] < (*_capacity)[e]) {484 if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) { 485 485 queue.push(v); 486 486 M.set(v, false); … … 490 490 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 491 491 Node v=_g->target(e); 492 if (M[v] && (*_flow)[e] > 0) {492 if (M[v] && _surely.positive((*_flow)[e]) ) { 493 493 queue.push(v); 494 494 M.set(v, false); … … 577 577 578 578 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 579 if ( (*_flow)[e] >= (*_capacity)[e]) continue;579 if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue; 580 580 Node v=_g->target(e); 581 581 582 582 if( lev > level[v] ) { //Push is allowed now 583 583 584 if ( excess[v]<=0&& v!=_target && v!=_source ) {584 if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) { 585 585 next.set(v,first[level[v]]); 586 586 first[level[v]]=v; … … 591 591 Num remcap=cap-flo; 592 592 593 if ( remcap >= exc) { //A nonsaturating push.593 if ( ! _surely.less(remcap, exc) ) { //A nonsaturating push. 594 594 595 595 _flow->set(e, flo+exc); … … 606 606 } //for out edges wv 607 607 608 if ( exc > 0) {608 if ( _surely.positive(exc) ) { 609 609 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 610 610 611 if ( (*_flow)[e] <= 0) continue;611 if ( !_surely.positive((*_flow)[e]) ) continue; 612 612 Node v=_g->source(e); 613 613 614 614 if( lev > level[v] ) { //Push is allowed now 615 615 616 if ( excess[v]<=0&& v!=_target && v!=_source ) {616 if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) { 617 617 next.set(v,first[level[v]]); 618 618 first[level[v]]=v; … … 621 621 Num flo=(*_flow)[e]; 622 622 623 if ( flo >= exc) { //A nonsaturating push.623 if ( !_surely.less(flo, exc) ) { //A nonsaturating push. 624 624 625 625 _flow->set(e, flo-exc); … … 664 664 665 665 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { 666 if ( (*_capacity)[e] <= (*_flow)[e]) continue;666 if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue; 667 667 Node w=_g->source(e); 668 668 if ( level[w] == _node_num && w != _source ) { … … 677 677 678 678 for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) { 679 if ( 0 >= (*_flow)[e]) continue;679 if ( !_surely.positive((*_flow)[e]) ) continue; 680 680 Node w=_g->target(e); 681 681 if ( level[w] == _node_num && w != _source ) { … … 724 724 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 725 725 Num c=(*_capacity)[e]; 726 if ( c <= 0) continue;726 if ( !_surely.positive(c) ) continue; 727 727 Node w=_g->target(e); 728 728 if ( level[w] < _node_num ) { 729 if ( excess[w] <= 0&& w!=_target ) { //putting into the stack729 if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack 730 730 next.set(w,first[level[w]]); 731 731 first[level[w]]=w; … … 749 749 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) { 750 750 Num rem=(*_capacity)[e]-(*_flow)[e]; 751 if ( rem <= 0) continue;751 if ( !_surely.positive(rem) ) continue; 752 752 Node w=_g->target(e); 753 753 if ( level[w] < _node_num ) { 754 if ( excess[w] <= 0&& w!=_target ) { //putting into the stack754 if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack 755 755 next.set(w,first[level[w]]); 756 756 first[level[w]]=w; … … 762 762 763 763 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) { 764 if ( (*_flow)[e] <= 0) continue;764 if ( !_surely.positive((*_flow)[e]) ) continue; 765 765 Node w=_g->source(e); 766 766 if ( level[w] < _node_num ) { 767 if ( excess[w] <= 0&& w!=_target ) {767 if ( !_surely.positive(excess[w]) && w!=_target ) { 768 768 next.set(w,first[level[w]]); 769 769 first[level[w]]=w; … … 779 779 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 780 780 Num rem=(*_capacity)[e]-(*_flow)[e]; 781 if ( rem <= 0) continue;781 if ( !_surely.positive(rem) ) continue; 782 782 Node w=_g->target(e); 783 783 if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]); … … 785 785 786 786 for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 787 if ( (*_flow)[e] <= 0) continue;787 if ( !_surely.positive((*_flow)[e]) ) continue; 788 788 Node w=_g->source(e); 789 789 if ( level[w] < _node_num ) _flow->set(e, 0); … … 799 799 //putting the active nodes into the stack 800 800 int lev=level[w]; 801 if ( exc > 0&& lev < _node_num && Node(w) != _target ) {801 if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) { 802 802 next.set(w,first[lev]); 803 803 first[lev]=w;
Note: See TracChangeset
for help on using the changeset viewer.