Changeset 471:a40985a922d0 in lemon0.x
 Timestamp:
 04/29/04 17:01:52 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@624
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.h
r470 r471 44 44 #include <stack> 45 45 46 #include <graph_wrapper.h> 47 46 48 namespace hugo { 47 49 … … 66 68 FlowMap* flow; 67 69 int n; //the number of nodes of G 68 typename Graph::template NodeMap<int> level; 70 typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW; 71 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt; 72 typedef typename ResGW::Edge ResGWEdge; 73 //typedef typename ResGW::template NodeMap<bool> ReachedMap; 74 typedef typename Graph::template NodeMap<int> ReachedMap; 75 ReachedMap level; 76 //level works as a bool map in augmenting path algorithms 77 //and is used by bfs for storing reached information. 78 //In preflow, it shows levels of nodes. 79 //typename Graph::template NodeMap<int> level; 69 80 typename Graph::template NodeMap<Num> excess; 70 71 81 72 82 public: … … 92 102 } 93 103 94 void preflowPhase0( flowEnum fe ) { 95 96 int heur0=(int)(H0*n); //time while running 'bound decrease' 97 int heur1=(int)(H1*n); //time while running 'highest label' 98 int heur=heur1; //starting time interval (#of relabels) 99 int numrelabel=0; 100 101 bool what_heur=1; 102 //It is 0 in case 'bound decrease' and 1 in case 'highest label' 103 104 bool end=false; 105 //Needed for 'bound decrease', true means no active nodes are above bound b. 106 107 int k=n2; //bound on the highest level under n containing a node 108 int b=k; //bound on the highest level under n of an active node 109 110 VecStack active(n); 111 112 NNMap left(*g, INVALID); 113 NNMap right(*g, INVALID); 114 VecNode level_list(n,INVALID); 115 //List of the nodes in level i<n, set to n. 116 117 NodeIt v; 118 for(g>first(v); g>valid(v); g>next(v)) level.set(v,n); 119 //setting each node to level n 120 121 switch ( fe ) { 122 case PREFLOW: 123 { 124 //counting the excess 125 NodeIt v; 126 for(g>first(v); g>valid(v); g>next(v)) { 127 Num exc=0; 128 129 InEdgeIt e; 130 for(g>first(e,v); g>valid(e); g>next(e)) exc+=(*flow)[e]; 131 OutEdgeIt f; 132 for(g>first(f,v); g>valid(f); g>next(f)) exc=(*flow)[f]; 133 134 excess.set(v,exc); 135 136 //putting the active nodes into the stack 137 int lev=level[v]; 138 if ( exc > 0 && lev < n && v != t ) active[lev].push(v); 139 } 140 break; 141 } 142 case GEN_FLOW: 143 { 144 //Counting the excess of t 145 Num exc=0; 146 147 InEdgeIt e; 148 for(g>first(e,t); g>valid(e); g>next(e)) exc+=(*flow)[e]; 149 OutEdgeIt f; 150 for(g>first(f,t); g>valid(f); g>next(f)) exc=(*flow)[f]; 151 152 excess.set(t,exc); 153 154 break; 155 } 156 default: 157 break; 158 } 159 160 preflowPreproc( fe, active, level_list, left, right ); 161 //End of preprocessing 162 163 164 //Push/relabel on the highest level active nodes. 165 while ( true ) { 166 if ( b == 0 ) { 167 if ( !what_heur && !end && k > 0 ) { 168 b=k; 169 end=true; 170 } else break; 171 } 172 173 if ( active[b].empty() ) b; 174 else { 175 end=false; 176 Node w=active[b].top(); 177 active[b].pop(); 178 int newlevel=push(w,active); 179 if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 180 left, right, b, k, what_heur); 181 182 ++numrelabel; 183 if ( numrelabel >= heur ) { 184 numrelabel=0; 185 if ( what_heur ) { 186 what_heur=0; 187 heur=heur0; 188 end=false; 189 } else { 190 what_heur=1; 191 heur=heur1; 192 b=k; 193 } 194 } 195 } 196 } 197 } 198 199 200 void preflowPhase1() { 201 202 int k=n2; //bound on the highest level under n containing a node 203 int b=k; //bound on the highest level under n of an active node 204 205 VecStack active(n); 206 level.set(s,0); 207 std::queue<Node> bfs_queue; 208 bfs_queue.push(s); 209 210 while (!bfs_queue.empty()) { 211 212 Node v=bfs_queue.front(); 213 bfs_queue.pop(); 214 int l=level[v]+1; 215 216 InEdgeIt e; 217 for(g>first(e,v); g>valid(e); g>next(e)) { 218 if ( (*capacity)[e] <= (*flow)[e] ) continue; 219 Node u=g>tail(e); 220 if ( level[u] >= n ) { 221 bfs_queue.push(u); 222 level.set(u, l); 223 if ( excess[u] > 0 ) active[l].push(u); 224 } 225 } 226 227 OutEdgeIt f; 228 for(g>first(f,v); g>valid(f); g>next(f)) { 229 if ( 0 >= (*flow)[f] ) continue; 230 Node u=g>head(f); 231 if ( level[u] >= n ) { 232 bfs_queue.push(u); 233 level.set(u, l); 234 if ( excess[u] > 0 ) active[l].push(u); 235 } 236 } 237 } 238 b=n2; 239 240 while ( true ) { 241 242 if ( b == 0 ) break; 243 244 if ( active[b].empty() ) b; 245 else { 246 Node w=active[b].top(); 247 active[b].pop(); 248 int newlevel=push(w,active); 249 250 //relabel 251 if ( excess[w] > 0 ) { 252 level.set(w,++newlevel); 253 active[newlevel].push(w); 254 b=newlevel; 255 } 256 } // if stack[b] is nonempty 257 } // while(true) 258 } 259 104 void preflowPhase0( flowEnum fe ); 105 106 void preflowPhase1(); 107 108 bool augmentOnShortestPath(); 109 110 template<typename MutableGraph> bool augmentOnBlockingFlow(); 111 112 bool augmentOnBlockingFlow2(); 260 113 261 114 //Returns the maximum value of a flow. … … 646 499 } //relabel 647 500 648 649 501 }; 650 502 503 504 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 505 void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 506 { 507 508 int heur0=(int)(H0*n); //time while running 'bound decrease' 509 int heur1=(int)(H1*n); //time while running 'highest label' 510 int heur=heur1; //starting time interval (#of relabels) 511 int numrelabel=0; 512 513 bool what_heur=1; 514 //It is 0 in case 'bound decrease' and 1 in case 'highest label' 515 516 bool end=false; 517 //Needed for 'bound decrease', true means no active nodes are above bound b. 518 519 int k=n2; //bound on the highest level under n containing a node 520 int b=k; //bound on the highest level under n of an active node 521 522 VecStack active(n); 523 524 NNMap left(*g, INVALID); 525 NNMap right(*g, INVALID); 526 VecNode level_list(n,INVALID); 527 //List of the nodes in level i<n, set to n. 528 529 NodeIt v; 530 for(g>first(v); g>valid(v); g>next(v)) level.set(v,n); 531 //setting each node to level n 532 533 switch ( fe ) { 534 case PREFLOW: 535 { 536 //counting the excess 537 NodeIt v; 538 for(g>first(v); g>valid(v); g>next(v)) { 539 Num exc=0; 540 541 InEdgeIt e; 542 for(g>first(e,v); g>valid(e); g>next(e)) exc+=(*flow)[e]; 543 OutEdgeIt f; 544 for(g>first(f,v); g>valid(f); g>next(f)) exc=(*flow)[f]; 545 546 excess.set(v,exc); 547 548 //putting the active nodes into the stack 549 int lev=level[v]; 550 if ( exc > 0 && lev < n && v != t ) active[lev].push(v); 551 } 552 break; 553 } 554 case GEN_FLOW: 555 { 556 //Counting the excess of t 557 Num exc=0; 558 559 InEdgeIt e; 560 for(g>first(e,t); g>valid(e); g>next(e)) exc+=(*flow)[e]; 561 OutEdgeIt f; 562 for(g>first(f,t); g>valid(f); g>next(f)) exc=(*flow)[f]; 563 564 excess.set(t,exc); 565 566 break; 567 } 568 default: 569 break; 570 } 571 572 preflowPreproc( fe, active, level_list, left, right ); 573 //End of preprocessing 574 575 576 //Push/relabel on the highest level active nodes. 577 while ( true ) { 578 if ( b == 0 ) { 579 if ( !what_heur && !end && k > 0 ) { 580 b=k; 581 end=true; 582 } else break; 583 } 584 585 if ( active[b].empty() ) b; 586 else { 587 end=false; 588 Node w=active[b].top(); 589 active[b].pop(); 590 int newlevel=push(w,active); 591 if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 592 left, right, b, k, what_heur); 593 594 ++numrelabel; 595 if ( numrelabel >= heur ) { 596 numrelabel=0; 597 if ( what_heur ) { 598 what_heur=0; 599 heur=heur0; 600 end=false; 601 } else { 602 what_heur=1; 603 heur=heur1; 604 b=k; 605 } 606 } 607 } 608 } 609 } 610 611 612 613 template <typename Graph, typename Num, typename CapMap, typename FlowMap> 614 void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 615 { 616 617 int k=n2; //bound on the highest level under n containing a node 618 int b=k; //bound on the highest level under n of an active node 619 620 VecStack active(n); 621 level.set(s,0); 622 std::queue<Node> bfs_queue; 623 bfs_queue.push(s); 624 625 while (!bfs_queue.empty()) { 626 627 Node v=bfs_queue.front(); 628 bfs_queue.pop(); 629 int l=level[v]+1; 630 631 InEdgeIt e; 632 for(g>first(e,v); g>valid(e); g>next(e)) { 633 if ( (*capacity)[e] <= (*flow)[e] ) continue; 634 Node u=g>tail(e); 635 if ( level[u] >= n ) { 636 bfs_queue.push(u); 637 level.set(u, l); 638 if ( excess[u] > 0 ) active[l].push(u); 639 } 640 } 641 642 OutEdgeIt f; 643 for(g>first(f,v); g>valid(f); g>next(f)) { 644 if ( 0 >= (*flow)[f] ) continue; 645 Node u=g>head(f); 646 if ( level[u] >= n ) { 647 bfs_queue.push(u); 648 level.set(u, l); 649 if ( excess[u] > 0 ) active[l].push(u); 650 } 651 } 652 } 653 b=n2; 654 655 while ( true ) { 656 657 if ( b == 0 ) break; 658 659 if ( active[b].empty() ) b; 660 else { 661 Node w=active[b].top(); 662 active[b].pop(); 663 int newlevel=push(w,active); 664 665 //relabel 666 if ( excess[w] > 0 ) { 667 level.set(w,++newlevel); 668 active[newlevel].push(w); 669 b=newlevel; 670 } 671 } // if stack[b] is nonempty 672 } // while(true) 673 } 674 675 676 677 678 679 680 681 682 683 684 685 651 686 } //namespace hugo 652 687
Note: See TracChangeset
for help on using the changeset viewer.