Changeset 1222:a3fb216a267d in lemon0.x for src/lemon/preflow.h
 Timestamp:
 03/17/05 11:43:57 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@1642
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/lemon/preflow.h
r1164 r1222 38 38 ///This class provides an implementation of the \e preflow \e 39 39 ///algorithm producing a flow of maximum value in a directed 40 ///graph. The preflow algorithms are the fastest max flow algorithms40 ///graph. The preflow algorithms are the fastest known max flow algorithms 41 41 ///up to now. The \e source node, the \e target node, the \e 42 42 ///capacity of the edges and the \e starting \e flow value of the 43 43 ///edges should be passed to the algorithm through the 44 44 ///constructor. It is possible to change these quantities using the 45 ///functions \ref s etSource, \ref setTarget, \ref setCap and \ref45 ///functions \ref source, \ref target, \ref setCap and \ref 46 46 ///setFlow. 47 47 /// … … 56 56 ///\param Graph The directed graph type the algorithm runs on. 57 57 ///\param Num The number type of the capacities and the flow values. 58 ///\param Cap Map The capacity map type.58 ///\param CapacityMap The capacity map type. 59 59 ///\param FlowMap The flow map type. 60 60 /// 61 61 ///\author Jacint Szabo 62 62 template <typename Graph, typename Num, 63 typename Cap Map=typename Graph::template EdgeMap<Num>,63 typename CapacityMap=typename Graph::template EdgeMap<Num>, 64 64 typename FlowMap=typename Graph::template EdgeMap<Num> > 65 65 class Preflow { … … 74 74 typedef typename std::vector<Node> VecNode; 75 75 76 const Graph* g;77 Node s;78 Node t;79 const Cap Map*capacity;80 FlowMap* flow;81 int n; //the number of nodes of G76 const Graph* _g; 77 Node _source; 78 Node _target; 79 const CapacityMap* _capacity; 80 FlowMap* _flow; 81 int _node_num; //the number of nodes of G 82 82 83 83 typename Graph::template NodeMap<int> level; … … 92 92 ///Indicates the property of the starting flow map. 93 93 94 ///Indicates the property of the starting flow map. The meanings are as follows: 94 ///Indicates the property of the starting flow map. 95 ///The meanings are as follows: 95 96 /// \c ZERO_FLOW: constant zero flow 96 97 /// \c GEN_FLOW: any flow, i.e. the sum of the inflows equals to … … 112 113 ///Indicates the state of the preflow algorithm. 113 114 114 ///Indicates the state of the preflow algorithm. The meanings are as follows: 115 /// \c AFTER_NOTHING: before running the algorithm or at an unspecified state. 115 ///Indicates the state of the preflow algorithm. 116 ///The meanings are as follows: 117 /// \c AFTER_NOTHING: before running the algorithm or 118 /// at an unspecified state. 116 119 /// \c AFTER_PREFLOW_PHASE_1: right after running \c phase1 117 120 /// \c AFTER_PREFLOW_PHASE_2: after running \ref phase2() … … 134 137 ///\param _s The source node. 135 138 ///\param _t The target node. 136 ///\param _cap acityThe capacity of the edges.137 ///\param _f lowThe flow of the edges.139 ///\param _cap The capacity of the edges. 140 ///\param _f The flow of the edges. 138 141 ///Except the graph, all of these parameters can be reset by 139 ///calling \ref s etSource, \ref setTarget, \ref setCap and \ref142 ///calling \ref source, \ref target, \ref setCap and \ref 140 143 ///setFlow, resp. 141 Preflow(const Graph& _ G, Node _s, Node _t,142 const Cap Map& _capacity, FlowMap& _flow) :143 g(&_G), s(_s), t(_t), capacity(&_capacity),144 flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0),144 Preflow(const Graph& _gr, Node _s, Node _t, 145 const CapacityMap& _cap, FlowMap& _f) : 146 _g(&_gr), _source(_s), _target(_t), _capacity(&_cap), 147 _flow(&_f), _node_num(countNodes(_gr)), level(_gr), excess(_gr,0), 145 148 flow_prop(NO_FLOW), status(AFTER_NOTHING) { } 146 149 … … 205 208 void phase1() 206 209 { 207 int heur0=(int)(H0* n); //time while running 'bound decrease'208 int heur1=(int)(H1* n); //time while running 'highest label'210 int heur0=(int)(H0*_node_num); //time while running 'bound decrease' 211 int heur1=(int)(H1*_node_num); //time while running 'highest label' 209 212 int heur=heur1; //starting time interval (#of relabels) 210 213 int numrelabel=0; … … 217 220 //nodes are above bound b. 218 221 219 int k= n2; //bound on the highest level under n containing a node222 int k=_node_num2; //bound on the highest level under n containing a node 220 223 int b=k; //bound on the highest level under n of an active node 221 224 222 VecNode first( n, INVALID);223 NNMap next(* g, INVALID);224 225 NNMap left(* g, INVALID);226 NNMap right(* g, INVALID);227 VecNode level_list( n,INVALID);225 VecNode first(_node_num, INVALID); 226 NNMap next(*_g, INVALID); 227 228 NNMap left(*_g, INVALID); 229 NNMap right(*_g, INVALID); 230 VecNode level_list(_node_num,INVALID); 228 231 //List of the nodes in level i<n, set to n. 229 232 … … 272 275 // stack 'active' on the active nodes on level i 273 276 // runs heuristic 'highest label' for H1*n relabels 274 // runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label' 277 // runs heuristic 'bound decrease' for H0*n relabels, 278 // starts with 'highest label' 275 279 // Parameters H0 and H1 are initialized to 20 and 1. 276 280 … … 288 292 { 289 293 290 int k= n2; //bound on the highest level under n containing a node294 int k=_node_num2; //bound on the highest level under n containing a node 291 295 int b=k; //bound on the highest level under n of an active node 292 296 293 297 294 VecNode first( n, INVALID);295 NNMap next(* g, INVALID);296 level.set( s,0);298 VecNode first(_node_num, INVALID); 299 NNMap next(*_g, INVALID); 300 level.set(_source,0); 297 301 std::queue<Node> bfs_queue; 298 bfs_queue.push( s);302 bfs_queue.push(_source); 299 303 300 304 while ( !bfs_queue.empty() ) { … … 304 308 int l=level[v]+1; 305 309 306 for(InEdgeIt e(* g,v); e!=INVALID; ++e) {307 if ( (* capacity)[e] <= (*flow)[e] ) continue;308 Node u= g>source(e);309 if ( level[u] >= n) {310 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) { 311 if ( (*_capacity)[e] <= (*_flow)[e] ) continue; 312 Node u=_g>source(e); 313 if ( level[u] >= _node_num ) { 310 314 bfs_queue.push(u); 311 315 level.set(u, l); … … 317 321 } 318 322 319 for(OutEdgeIt e(* g,v); e!=INVALID; ++e) {320 if ( 0 >= (* flow)[e] ) continue;321 Node u= g>target(e);322 if ( level[u] >= n) {323 for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) { 324 if ( 0 >= (*_flow)[e] ) continue; 325 Node u=_g>target(e); 326 if ( level[u] >= _node_num ) { 323 327 bfs_queue.push(u); 324 328 level.set(u, l); … … 330 334 } 331 335 } 332 b= n2;336 b=_node_num2; 333 337 334 338 while ( true ) { … … 360 364 /// the maximum flow already after running \ref phase1. 361 365 Num flowValue() const { 362 return excess[ t];366 return excess[_target]; 363 367 } 364 368 … … 376 380 switch ( status ) { 377 381 case AFTER_PREFLOW_PHASE_1: 378 for(NodeIt v(* g); v!=INVALID; ++v) {379 if (level[v] < n) {382 for(NodeIt v(*_g); v!=INVALID; ++v) { 383 if (level[v] < _node_num) { 380 384 M.set(v, false); 381 385 } else { … … 403 407 404 408 std::queue<Node> queue; 405 M.set( s,true);409 M.set(_source,true); 406 410 queue.push(s); 407 411 … … 410 414 queue.pop(); 411 415 412 for(OutEdgeIt e(* g,w) ; e!=INVALID; ++e) {413 Node v= g>target(e);414 if (!M[v] && (* flow)[e] < (*capacity)[e] ) {416 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 417 Node v=_g>target(e); 418 if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) { 415 419 queue.push(v); 416 420 M.set(v, true); … … 418 422 } 419 423 420 for(InEdgeIt e(* g,w) ; e!=INVALID; ++e) {421 Node v= g>source(e);422 if (!M[v] && (* flow)[e] > 0 ) {424 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 425 Node v=_g>source(e); 426 if (!M[v] && (*_flow)[e] > 0 ) { 423 427 queue.push(v); 424 428 M.set(v, true); … … 437 441 void maxMinCut(_CutMap& M) const { 438 442 439 for(NodeIt v(* g) ; v!=INVALID; ++v) M.set(v, true);443 for(NodeIt v(*_g) ; v!=INVALID; ++v) M.set(v, true); 440 444 441 445 std::queue<Node> queue; 442 446 443 M.set( t,false);444 queue.push( t);447 M.set(_target,false); 448 queue.push(_target); 445 449 446 450 while (!queue.empty()) { … … 448 452 queue.pop(); 449 453 450 for(InEdgeIt e(* g,w) ; e!=INVALID; ++e) {451 Node v= g>source(e);452 if (M[v] && (* flow)[e] < (*capacity)[e] ) {454 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 455 Node v=_g>source(e); 456 if (M[v] && (*_flow)[e] < (*_capacity)[e] ) { 453 457 queue.push(v); 454 458 M.set(v, false); … … 456 460 } 457 461 458 for(OutEdgeIt e(* g,w) ; e!=INVALID; ++e) {459 Node v= g>target(e);460 if (M[v] && (* flow)[e] > 0 ) {462 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 463 Node v=_g>target(e); 464 if (M[v] && (*_flow)[e] > 0 ) { 461 465 queue.push(v); 462 466 M.set(v, false); … … 470 474 ///Sets the source node to \c _s. 471 475 /// 472 void s etSource(Node _s) {473 s=_s;476 void source(Node _s) { 477 _source=_s; 474 478 if ( flow_prop != ZERO_FLOW ) flow_prop=NO_FLOW; 475 479 status=AFTER_NOTHING; 476 480 } 477 481 482 ///Returns the source node. 483 484 ///Returns the source node. 485 /// 486 Node source() const { 487 return _source; 488 } 489 478 490 ///Sets the target node to \c _t. 479 491 480 492 ///Sets the target node to \c _t. 481 493 /// 482 void setTarget(Node _t) {483 t=_t;494 void target(Node _t) { 495 _target=_t; 484 496 if ( flow_prop == GEN_FLOW ) flow_prop=PRE_FLOW; 485 497 status=AFTER_NOTHING; 486 498 } 487 499 500 ///Returns the target node. 501 502 ///Returns the target node. 503 /// 504 Node target() const { 505 return _target; 506 } 507 488 508 /// Sets the edge map of the capacities to _cap. 489 509 490 510 /// Sets the edge map of the capacities to _cap. 491 511 /// 492 void setCap(const CapMap& _cap) {493 capacity=&_cap;512 void capacityMap(const CapacityMap& _cap) { 513 _capacity=&_cap; 494 514 status=AFTER_NOTHING; 515 } 516 /// Returns a reference to to capacity map. 517 518 /// Returns a reference to to capacity map. 519 /// 520 const CapacityMap &capacityMap() const { 521 return *_capacity; 495 522 } 496 523 … … 499 526 /// Sets the edge map of the flows to _flow. 500 527 /// 501 void setFlow(FlowMap& _flow) {502 flow=&_flow;528 void flowMap(FlowMap& _f) { 529 _flow=&_f; 503 530 flow_prop=NO_FLOW; 504 531 status=AFTER_NOTHING; 505 532 } 506 533 534 /// Returns a reference to to flow map. 535 536 /// Returns a reference to to flow map. 537 /// 538 const FlowMap &flowMap() const { 539 return *_flow; 540 } 507 541 508 542 private: … … 512 546 int lev=level[w]; 513 547 Num exc=excess[w]; 514 int newlevel= n; //bound on the next level of w515 516 for(OutEdgeIt e(* g,w) ; e!=INVALID; ++e) {517 if ( (* flow)[e] >= (*capacity)[e] ) continue;518 Node v= g>target(e);548 int newlevel=_node_num; //bound on the next level of w 549 550 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 551 if ( (*_flow)[e] >= (*_capacity)[e] ) continue; 552 Node v=_g>target(e); 519 553 520 554 if( lev > level[v] ) { //Push is allowed now 521 555 522 if ( excess[v]<=0 && v!= t && v!=s) {556 if ( excess[v]<=0 && v!=_target && v!=_source ) { 523 557 next.set(v,first[level[v]]); 524 558 first[level[v]]=v; 525 559 } 526 560 527 Num cap=(* capacity)[e];528 Num flo=(* flow)[e];561 Num cap=(*_capacity)[e]; 562 Num flo=(*_flow)[e]; 529 563 Num remcap=capflo; 530 564 531 565 if ( remcap >= exc ) { //A nonsaturating push. 532 566 533 flow>set(e, flo+exc);567 _flow>set(e, flo+exc); 534 568 excess.set(v, excess[v]+exc); 535 569 exc=0; … … 537 571 538 572 } else { //A saturating push. 539 flow>set(e, cap);573 _flow>set(e, cap); 540 574 excess.set(v, excess[v]+remcap); 541 575 exc=remcap; … … 545 579 546 580 if ( exc > 0 ) { 547 for(InEdgeIt e(* g,w) ; e!=INVALID; ++e) {548 549 if( (* flow)[e] <= 0 ) continue;550 Node v= g>source(e);581 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) { 582 583 if( (*_flow)[e] <= 0 ) continue; 584 Node v=_g>source(e); 551 585 552 586 if( lev > level[v] ) { //Push is allowed now 553 587 554 if ( excess[v]<=0 && v!= t && v!=s) {588 if ( excess[v]<=0 && v!=_target && v!=_source ) { 555 589 next.set(v,first[level[v]]); 556 590 first[level[v]]=v; 557 591 } 558 592 559 Num flo=(* flow)[e];593 Num flo=(*_flow)[e]; 560 594 561 595 if ( flo >= exc ) { //A nonsaturating push. 562 596 563 flow>set(e, floexc);597 _flow>set(e, floexc); 564 598 excess.set(v, excess[v]+exc); 565 599 exc=0; … … 569 603 excess.set(v, excess[v]+flo); 570 604 exc=flo; 571 flow>set(e,0);605 _flow>set(e,0); 572 606 } 573 607 } else if ( newlevel > level[v] ) newlevel = level[v]; … … 586 620 VecNode& level_list, NNMap& left, NNMap& right) 587 621 { 588 for(NodeIt v(* g); v!=INVALID; ++v) level.set(v,n);622 for(NodeIt v(*_g); v!=INVALID; ++v) level.set(v,_node_num); 589 623 std::queue<Node> bfs_queue; 590 624 … … 592 626 //Reverse_bfs from t in the residual graph, 593 627 //to find the starting level. 594 level.set( t,0);595 bfs_queue.push( t);628 level.set(_target,0); 629 bfs_queue.push(_target); 596 630 597 631 while ( !bfs_queue.empty() ) { … … 601 635 int l=level[v]+1; 602 636 603 for(InEdgeIt e(* g,v) ; e!=INVALID; ++e) {604 if ( (* capacity)[e] <= (*flow)[e] ) continue;605 Node w= g>source(e);606 if ( level[w] == n && w != s) {637 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { 638 if ( (*_capacity)[e] <= (*_flow)[e] ) continue; 639 Node w=_g>source(e); 640 if ( level[w] == _node_num && w != _source ) { 607 641 bfs_queue.push(w); 608 642 Node z=level_list[l]; … … 614 648 } 615 649 616 for(OutEdgeIt e(* g,v) ; e!=INVALID; ++e) {617 if ( 0 >= (* flow)[e] ) continue;618 Node w= g>target(e);619 if ( level[w] == n && w != s) {650 for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) { 651 if ( 0 >= (*_flow)[e] ) continue; 652 Node w=_g>target(e); 653 if ( level[w] == _node_num && w != _source ) { 620 654 bfs_queue.push(w); 621 655 Node z=level_list[l]; … … 632 666 switch (flow_prop) { 633 667 case NO_FLOW: 634 for(EdgeIt e(* g); e!=INVALID; ++e)flow>set(e,0);668 for(EdgeIt e(*_g); e!=INVALID; ++e) _flow>set(e,0); 635 669 case ZERO_FLOW: 636 for(NodeIt v(* g); v!=INVALID; ++v) excess.set(v,0);670 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); 637 671 638 672 //Reverse_bfs from t, to find the starting level. 639 level.set( t,0);640 bfs_queue.push( t);673 level.set(_target,0); 674 bfs_queue.push(_target); 641 675 642 676 while ( !bfs_queue.empty() ) { … … 646 680 int l=level[v]+1; 647 681 648 for(InEdgeIt e(* g,v) ; e!=INVALID; ++e) {649 Node w= g>source(e);650 if ( level[w] == n && w != s) {682 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) { 683 Node w=_g>source(e); 684 if ( level[w] == _node_num && w != _source ) { 651 685 bfs_queue.push(w); 652 686 Node z=level_list[l]; … … 660 694 661 695 //the starting flow 662 for(OutEdgeIt e(* g,s) ; e!=INVALID; ++e) {663 Num c=(* capacity)[e];696 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 697 Num c=(*_capacity)[e]; 664 698 if ( c <= 0 ) continue; 665 Node w= g>target(e);666 if ( level[w] < n) {667 if ( excess[w] <= 0 && w!= t ) { //putting into the stack699 Node w=_g>target(e); 700 if ( level[w] < _node_num ) { 701 if ( excess[w] <= 0 && w!=_target ) { //putting into the stack 668 702 next.set(w,first[level[w]]); 669 703 first[level[w]]=w; 670 704 } 671 flow>set(e, c);705 _flow>set(e, c); 672 706 excess.set(w, excess[w]+c); 673 707 } … … 676 710 677 711 case GEN_FLOW: 678 for(NodeIt v(* g); v!=INVALID; ++v) excess.set(v,0);712 for(NodeIt v(*_g); v!=INVALID; ++v) excess.set(v,0); 679 713 { 680 714 Num exc=0; 681 for(InEdgeIt e(* g,t) ; e!=INVALID; ++e) exc+=(*flow)[e];682 for(OutEdgeIt e(* g,t) ; e!=INVALID; ++e) exc=(*flow)[e];683 excess.set( t,exc);715 for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e]; 716 for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc=(*_flow)[e]; 717 excess.set(_target,exc); 684 718 } 685 719 686 720 //the starting flow 687 for(OutEdgeIt e(* g,s); e!=INVALID; ++e) {688 Num rem=(* capacity)[e](*flow)[e];721 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) { 722 Num rem=(*_capacity)[e](*_flow)[e]; 689 723 if ( rem <= 0 ) continue; 690 Node w= g>target(e);691 if ( level[w] < n) {692 if ( excess[w] <= 0 && w!= t ) { //putting into the stack724 Node w=_g>target(e); 725 if ( level[w] < _node_num ) { 726 if ( excess[w] <= 0 && w!=_target ) { //putting into the stack 693 727 next.set(w,first[level[w]]); 694 728 first[level[w]]=w; 695 729 } 696 flow>set(e, (*capacity)[e]);730 _flow>set(e, (*_capacity)[e]); 697 731 excess.set(w, excess[w]+rem); 698 732 } 699 733 } 700 734 701 for(InEdgeIt e(* g,s); e!=INVALID; ++e) {702 if ( (* flow)[e] <= 0 ) continue;703 Node w= g>source(e);704 if ( level[w] < n) {705 if ( excess[w] <= 0 && w!= t ) {735 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) { 736 if ( (*_flow)[e] <= 0 ) continue; 737 Node w=_g>source(e); 738 if ( level[w] < _node_num ) { 739 if ( excess[w] <= 0 && w!=_target ) { 706 740 next.set(w,first[level[w]]); 707 741 first[level[w]]=w; 708 742 } 709 excess.set(w, excess[w]+(* flow)[e]);710 flow>set(e, 0);743 excess.set(w, excess[w]+(*_flow)[e]); 744 _flow>set(e, 0); 711 745 } 712 746 } … … 715 749 case PRE_FLOW: 716 750 //the starting flow 717 for(OutEdgeIt e(* g,s) ; e!=INVALID; ++e) {718 Num rem=(* capacity)[e](*flow)[e];751 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 752 Num rem=(*_capacity)[e](*_flow)[e]; 719 753 if ( rem <= 0 ) continue; 720 Node w= g>target(e);721 if ( level[w] < n ) flow>set(e, (*capacity)[e]);754 Node w=_g>target(e); 755 if ( level[w] < _node_num ) _flow>set(e, (*_capacity)[e]); 722 756 } 723 757 724 for(InEdgeIt e(* g,s) ; e!=INVALID; ++e) {725 if ( (* flow)[e] <= 0 ) continue;726 Node w= g>source(e);727 if ( level[w] < n )flow>set(e, 0);758 for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) { 759 if ( (*_flow)[e] <= 0 ) continue; 760 Node w=_g>source(e); 761 if ( level[w] < _node_num ) _flow>set(e, 0); 728 762 } 729 763 730 764 //computing the excess 731 for(NodeIt w(* g); w!=INVALID; ++w) {765 for(NodeIt w(*_g); w!=INVALID; ++w) { 732 766 Num exc=0; 733 for(InEdgeIt e(* g,w); e!=INVALID; ++e) exc+=(*flow)[e];734 for(OutEdgeIt e(* g,w); e!=INVALID; ++e) exc=(*flow)[e];767 for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e]; 768 for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc=(*_flow)[e]; 735 769 excess.set(w,exc); 736 770 737 771 //putting the active nodes into the stack 738 772 int lev=level[w]; 739 if ( exc > 0 && lev < n && Node(w) !=t ) {773 if ( exc > 0 && lev < _node_num && Node(w) != _target ) { 740 774 next.set(w,first[lev]); 741 775 first[lev]=w; … … 781 815 Node v=level_list[++i]; 782 816 while ( v!=INVALID ) { 783 level.set(v, n);817 level.set(v,_node_num); 784 818 v=right[v]; 785 819 } … … 788 822 } 789 823 790 level.set(w, n);824 level.set(w,_node_num); 791 825 b=lev1; 792 826 k=b; … … 795 829 } else { 796 830 797 if ( newlevel == n ) level.set(w,n);831 if ( newlevel == _node_num ) level.set(w,_node_num); 798 832 else { 799 833 level.set(w,++newlevel);
Note: See TracChangeset
for help on using the changeset viewer.