Changeset 2330:9dccb1abc721 in lemon-0.x for lemon
- Timestamp:
- 12/18/06 11:12:07 (17 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3116
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/preflow.h
r2151 r2330 275 275 first[b]=next[w]; 276 276 int newlevel=push(w, next, first); 277 if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, 278 left, right, b, k, what_heur); 277 if ( excess[w] != 0 ) { 278 relabel(w, newlevel, first, next, level_list, 279 left, right, b, k, what_heur); 280 } 279 281 280 282 ++numrelabel; … … 317 319 ///maxMinCut return the inclusionwise minimum and maximum cuts of 318 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 325 void phase2() 320 326 { … … 337 343 338 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 346 Node u=_g->source(e); 341 347 if ( level[u] >= _node_num ) { 342 348 bfs_queue.push(u); 343 349 level.set(u, l); 344 if ( _surely.positive(excess[u])) {350 if ( excess[u] != 0 ) { 345 351 next.set(u,first[l]); 346 352 first[l]=u; … … 355 361 bfs_queue.push(u); 356 362 level.set(u, l); 357 if ( _surely.positive(excess[u])) {363 if ( excess[u] != 0 ) { 358 364 next.set(u,first[l]); 359 365 first[l]=u; … … 373 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 385 //relabel 376 if ( _surely.positive(excess[w])) {386 if ( excess[w] != 0 ) { 377 387 level.set(w,++newlevel); 378 388 next.set(w,first[newlevel]); … … 444 454 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 445 455 Node v=_g->target(e); 446 if (!M[v] && _surely. less((*_flow)[e] , (*_capacity)[e]) ) {456 if (!M[v] && _surely.positive((*_capacity)[e] -(*_flow)[e]) ) { 447 457 queue.push(v); 448 458 M.set(v, true); … … 482 492 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 483 493 Node v=_g->source(e); 484 if (M[v] && _surely. less((*_flow)[e], (*_capacity)[e]) ) {494 if (M[v] && _surely.positive((*_capacity)[e] - (*_flow)[e]) ) { 485 495 queue.push(v); 486 496 M.set(v, false); … … 577 587 578 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 590 Node v=_g->target(e); 581 591 582 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 595 next.set(v,first[level[v]]); 586 596 first[level[v]]=v; … … 606 616 } //for out edges wv 607 617 608 if ( _surely.positive(exc)) {618 if ( exc != 0 ) { 609 619 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 610 620 … … 614 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 627 next.set(v,first[level[v]]); 618 628 first[level[v]]=v; … … 664 674 665 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 677 Node w=_g->source(e); 668 678 if ( level[w] == _node_num && w != _source ) { … … 727 737 Node w=_g->target(e); 728 738 if ( level[w] < _node_num ) { 729 if ( !_surely.positive(excess[w])&& w!=_target ) { //putting into the stack739 if ( excess[w] == 0 && w!=_target ) { //putting into the stack 730 740 next.set(w,first[level[w]]); 731 741 first[level[w]]=w; … … 743 753 for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e]; 744 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 … … 752 765 Node w=_g->target(e); 753 766 if ( level[w] < _node_num ) { 754 if ( !_surely.positive(excess[w])&& w!=_target ) { //putting into the stack767 if ( excess[w] == 0 && w!=_target ) { //putting into the stack 755 768 next.set(w,first[level[w]]); 756 769 first[level[w]]=w; … … 765 778 Node w=_g->source(e); 766 779 if ( level[w] < _node_num ) { 767 if ( !_surely.positive(excess[w])&& w!=_target ) {780 if ( excess[w] == 0 && w!=_target ) { 768 781 next.set(w,first[level[w]]); 769 782 first[level[w]]=w; … … 795 808 for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e]; 796 809 for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e]; 810 if (!_surely.positive(exc)) { 811 exc = 0; 812 } 797 813 excess.set(w,exc); 798 814 799 815 //putting the active nodes into the stack 800 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 818 next.set(w,first[lev]); 803 819 first[lev]=w;
Note: See TracChangeset
for help on using the changeset viewer.