Changeset 749:8e933219691e in lemon-0.x
- Timestamp:
- 07/30/04 12:24:05 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1009
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/hugo/max_flow.h
r745 r749 1 1 // -*- C++ -*- 2 #ifndef HUGO_MAX_FLOW_ NO_STACK_H3 #define HUGO_MAX_FLOW_ NO_STACK_H2 #ifndef HUGO_MAX_FLOW_H 3 #define HUGO_MAX_FLOW_H 4 4 5 5 #include <vector> 6 6 #include <queue> 7 //#include <stack>8 7 9 8 #include <hugo/graph_wrapper.h> … … 12 11 13 12 /// \file 14 /// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test.15 13 /// \ingroup galgs 16 14 … … 52 50 typedef typename Graph::InEdgeIt InEdgeIt; 53 51 54 // typedef typename std::vector<std::stack<Node> > VecStack;55 52 typedef typename std::vector<Node> VecFirst; 56 53 typedef typename Graph::template NodeMap<Node> NNMap; … … 67 64 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 68 65 typedef typename ResGW::Edge ResGWEdge; 69 //typedef typename ResGW::template NodeMap<bool> ReachedMap;70 66 typedef typename Graph::template NodeMap<int> ReachedMap; 71 67 … … 111 107 }; 112 108 113 /// Do nnot needle this flag only if necessary.109 /// Do not needle this flag only if necessary. 114 110 StatusEnum status; 115 111 … … 189 185 ///first phase. After the first phase the maximum flow value and a 190 186 ///minimum value cut can already be computed, though a maximum flow 191 ///is n et yet obtained. So after calling this method \ref flowValue187 ///is not yet obtained. So after calling this method \ref flowValue 192 188 ///and \ref actMinCut gives proper results. 193 189 ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not … … 224 220 //List of the nodes in level i<n, set to n. 225 221 226 NodeIt v;227 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);228 //setting each node to level n229 230 if ( fe == NO_FLOW ) {231 EdgeIt e;232 for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);233 }234 235 switch (fe) { //computing the excess236 case PRE_FLOW:237 {238 NodeIt v;239 for(g->first(v); g->valid(v); g->next(v)) {240 Num exc=0;241 242 InEdgeIt e;243 for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];244 OutEdgeIt f;245 for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];246 247 excess.set(v,exc);248 249 //putting the active nodes into the stack250 int lev=level[v];251 if ( exc > 0 && lev < n && v != t )252 {253 next.set(v,first[lev]);254 first[lev]=v;255 }256 }257 break;258 }259 case GEN_FLOW:260 {261 NodeIt v;262 for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);263 264 Num exc=0;265 InEdgeIt e;266 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];267 OutEdgeIt f;268 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];269 excess.set(t,exc);270 break;271 }272 case ZERO_FLOW:273 case NO_FLOW:274 {275 NodeIt v;276 for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);277 break;278 }279 }280 281 222 preflowPreproc(fe, next, first, level_list, left, right); 282 223 //End of preprocessing 283 284 224 285 225 //Push/relabel on the highest level active nodes. … … 395 335 b=newlevel; 396 336 } 397 } // if stack[b] is nonempty337 } 398 338 } // while(true) 399 339 … … 414 354 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan 415 355 } 416 Num flowValue2() const { 417 return excess[t]; 418 // Num a=0; 419 // for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e]; 420 // for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e]; 421 // return a; 422 // //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan 423 424 } 356 425 357 426 358 ///Returns a minimum value cut after calling \ref preflowPhase1. … … 653 585 654 586 587 655 588 void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first, 656 589 VecNode& level_list, NNMap& left, NNMap& right) 657 590 { 591 switch (fe) { //setting excess 592 case NO_FLOW: 593 { 594 EdgeIt e; 595 for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0); 596 597 NodeIt v; 598 for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); 599 break; 600 } 601 case ZERO_FLOW: 602 { 603 NodeIt v; 604 for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); 605 break; 606 } 607 case GEN_FLOW: 608 { 609 NodeIt v; 610 for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0); 611 612 Num exc=0; 613 InEdgeIt e; 614 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; 615 OutEdgeIt f; 616 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; 617 excess.set(t,exc); 618 break; 619 } 620 default: break; 621 } 622 623 NodeIt v; 624 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n); 625 //setting each node to level n 626 658 627 std::queue<Node> bfs_queue; 659 628 629 660 630 switch (fe) { 661 case NO_FLOW: //flow is already set to const zero in this case631 case NO_FLOW: //flow is already set to const zero 662 632 case ZERO_FLOW: 663 633 { … … 694 664 Node w=g->head(e); 695 665 if ( level[w] < n ) { 696 if ( excess[w] <= 0 && w!=t ) 697 { 666 if ( excess[w] <= 0 && w!=t ) //putting into the stack 667 { 698 668 next.set(w,first[level[w]]); 699 669 first[level[w]]=w; … … 707 677 708 678 case GEN_FLOW: 709 case PRE_FLOW:710 679 { 711 680 //Reverse_bfs from t in the residual graph, … … 749 718 } 750 719 751 752 720 //the starting flow 753 721 OutEdgeIt e; … … 758 726 Node w=g->head(e); 759 727 if ( level[w] < n ) { 760 if ( excess[w] <= 0 && w!=t ) 728 if ( excess[w] <= 0 && w!=t ) //putting into the stack 761 729 { 762 730 next.set(w,first[level[w]]); … … 778 746 next.set(w,first[level[w]]); 779 747 first[level[w]]=w; 780 } 748 } 781 749 excess.set(w, excess[w]+(*flow)[f]); 782 750 flow->set(f, 0); … … 784 752 } 785 753 break; 754 } //case GEN_FLOW 755 756 case PRE_FLOW: 757 { 758 //Reverse_bfs from t in the residual graph, 759 //to find the starting level. 760 level.set(t,0); 761 bfs_queue.push(t); 762 763 while (!bfs_queue.empty()) { 764 765 Node v=bfs_queue.front(); 766 bfs_queue.pop(); 767 int l=level[v]+1; 768 769 InEdgeIt e; 770 for(g->first(e,v); g->valid(e); g->next(e)) { 771 if ( (*capacity)[e] <= (*flow)[e] ) continue; 772 Node w=g->tail(e); 773 if ( level[w] == n && w != s ) { 774 bfs_queue.push(w); 775 Node z=level_list[l]; 776 if ( g->valid(z) ) left.set(z,w); 777 right.set(w,z); 778 level_list[l]=w; 779 level.set(w, l); 780 } 781 } 782 783 OutEdgeIt f; 784 for(g->first(f,v); g->valid(f); g->next(f)) { 785 if ( 0 >= (*flow)[f] ) continue; 786 Node w=g->head(f); 787 if ( level[w] == n && w != s ) { 788 bfs_queue.push(w); 789 Node z=level_list[l]; 790 if ( g->valid(z) ) left.set(z,w); 791 right.set(w,z); 792 level_list[l]=w; 793 level.set(w, l); 794 } 795 } 796 } 797 798 799 //the starting flow 800 OutEdgeIt e; 801 for(g->first(e,s); g->valid(e); g->next(e)) 802 { 803 Num rem=(*capacity)[e]-(*flow)[e]; 804 if ( rem <= 0 ) continue; 805 Node w=g->head(e); 806 if ( level[w] < n ) { 807 flow->set(e, (*capacity)[e]); 808 excess.set(w, excess[w]+rem); 809 } 810 } 811 812 InEdgeIt f; 813 for(g->first(f,s); g->valid(f); g->next(f)) 814 { 815 if ( (*flow)[f] <= 0 ) continue; 816 Node w=g->tail(f); 817 if ( level[w] < n ) { 818 excess.set(w, excess[w]+(*flow)[f]); 819 flow->set(f, 0); 820 } 821 } 822 823 NodeIt w; //computing the excess 824 for(g->first(w); g->valid(w); g->next(w)) { 825 Num exc=0; 826 827 InEdgeIt e; 828 for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e]; 829 OutEdgeIt f; 830 for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f]; 831 832 excess.set(w,exc); 833 834 //putting the active nodes into the stack 835 int lev=level[w]; 836 if ( exc > 0 && lev < n && w != t ) 837 { 838 next.set(w,first[lev]); 839 first[lev]=w; 840 } 841 } 842 break; 786 843 } //case PRE_FLOW 787 844 } 788 845 } //preflowPreproc 789 790 846 791 847 … … 853 909 } 854 910 } //relabel 911 912 void printexcess() {//// 913 std::cout << "Excesses:" <<std::endl; 914 915 NodeIt v; 916 for(g->first(v); g->valid(v); g->next(v)) { 917 std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl; 918 } 919 } 920 921 void printlevel() {//// 922 std::cout << "Levels:" <<std::endl; 923 924 NodeIt v; 925 for(g->first(v); g->valid(v); g->next(v)) { 926 std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 927 } 928 } 929 930 void printactive() {//// 931 std::cout << "Levels:" <<std::endl; 932 933 NodeIt v; 934 for(g->first(v); g->valid(v); g->next(v)) { 935 std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 936 } 937 } 938 939 855 940 }; //class MaxFlow 856 941 } //namespace hugo
Note: See TracChangeset
for help on using the changeset viewer.