Changeset 466:cd40ecf4d2a9 in lemon-0.x for src/work/jacint/preflow.h
- Timestamp:
- 04/29/04 12:16:46 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@617
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow.h
r465 r466 60 60 typedef typename std::vector<Node> VecNode; 61 61 62 const Graph & G;62 const Graph* g; 63 63 Node s; 64 64 Node t; … … 80 80 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 81 81 FlowMap& _flow) : 82 G(_G), s(_s), t(_t), capacity(&_capacity),82 g(&_G), s(_s), t(_t), capacity(&_capacity), 83 83 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {} 84 84 … … 110 110 VecStack active(n); 111 111 112 NNMap left( G,INVALID);113 NNMap right( G,INVALID);112 NNMap left(*g, INVALID); 113 NNMap right(*g, INVALID); 114 114 VecNode level_list(n,INVALID); 115 115 //List of the nodes in level i<n, set to n. 116 116 117 117 NodeIt v; 118 for( G.first(v); G.valid(v); G.next(v)) level.set(v,n);118 for(g->first(v); g->valid(v); g->next(v)) level.set(v,n); 119 119 //setting each node to level n 120 120 … … 124 124 //counting the excess 125 125 NodeIt v; 126 for( G.first(v); G.valid(v); G.next(v)) {126 for(g->first(v); g->valid(v); g->next(v)) { 127 127 T exc=0; 128 128 129 129 InEdgeIt e; 130 for( G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];130 for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e]; 131 131 OutEdgeIt f; 132 for( G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];132 for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f]; 133 133 134 134 excess.set(v,exc); … … 146 146 147 147 InEdgeIt e; 148 for( G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];148 for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e]; 149 149 OutEdgeIt f; 150 for( G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];150 for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f]; 151 151 152 152 excess.set(t,exc); … … 217 217 218 218 InEdgeIt e; 219 for( G.first(e,v); G.valid(e); G.next(e)) {219 for(g->first(e,v); g->valid(e); g->next(e)) { 220 220 if ( (*capacity)[e] == (*flow)[e] ) continue; 221 Node u= G.tail(e);221 Node u=g->tail(e); 222 222 if ( level[u] >= n ) { 223 223 bfs_queue.push(u); … … 228 228 229 229 OutEdgeIt f; 230 for( G.first(f,v); G.valid(f); G.next(f)) {230 for(g->first(f,v); g->valid(f); g->next(f)) { 231 231 if ( 0 == (*flow)[f] ) continue; 232 Node u= G.head(f);232 Node u=g->head(f); 233 233 if ( level[u] >= n ) { 234 234 bfs_queue.push(u); … … 270 270 void actMinCut(_CutMap& M) { 271 271 NodeIt v; 272 for(G.first(v); G.valid(v); G.next(v)) 273 if ( level[v] < n ) M.set(v,false); 274 else M.set(v,true); 272 for(g->first(v); g->valid(v); g->next(v)) 273 if ( level[v] < n ) { 274 M.set(v,false); 275 } else { 276 M.set(v,true); 277 } 275 278 } 276 279 … … 293 296 294 297 OutEdgeIt e; 295 for( G.first(e,w) ; G.valid(e); G.next(e)) {296 Node v= G.head(e);298 for(g->first(e,w) ; g->valid(e); g->next(e)) { 299 Node v=g->head(e); 297 300 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 298 301 queue.push(v); … … 302 305 303 306 InEdgeIt f; 304 for( G.first(f,w) ; G.valid(f); G.next(f)) {305 Node v= G.tail(f);307 for(g->first(f,w) ; g->valid(f); g->next(f)) { 308 Node v=g->tail(f); 306 309 if (!M[v] && (*flow)[f] > 0 ) { 307 310 queue.push(v); … … 323 326 324 327 NodeIt v; 325 for( G.first(v) ; G.valid(v); G.next(v)) {328 for(g->first(v) ; g->valid(v); g->next(v)) { 326 329 M.set(v, true); 327 330 } … … 338 341 339 342 InEdgeIt e; 340 for( G.first(e,w) ; G.valid(e); G.next(e)) {341 Node v= G.tail(e);343 for(g->first(e,w) ; g->valid(e); g->next(e)) { 344 Node v=g->tail(e); 342 345 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 343 346 queue.push(v); … … 347 350 348 351 OutEdgeIt f; 349 for( G.first(f,w) ; G.valid(f); G.next(f)) {350 Node v= G.head(f);352 for(g->first(f,w) ; g->valid(f); g->next(f)) { 353 Node v=g->head(f); 351 354 if (M[v] && (*flow)[f] > 0 ) { 352 355 queue.push(v); … … 386 389 387 390 OutEdgeIt e; 388 for( G.first(e,w); G.valid(e); G.next(e)) {391 for(g->first(e,w); g->valid(e); g->next(e)) { 389 392 390 393 if ( (*flow)[e] == (*capacity)[e] ) continue; 391 Node v= G.head(e);394 Node v=g->head(e); 392 395 393 396 if( lev > level[v] ) { //Push is allowed now … … 419 422 if ( exc > 0 ) { 420 423 InEdgeIt e; 421 for( G.first(e,w); G.valid(e); G.next(e)) {424 for(g->first(e,w); g->valid(e); g->next(e)) { 422 425 423 426 if( (*flow)[e] == 0 ) continue; 424 Node v= G.tail(e);427 Node v=g->tail(e); 425 428 426 429 if( lev > level[v] ) { //Push is allowed now … … 475 478 476 479 InEdgeIt e; 477 for( G.first(e,v); G.valid(e); G.next(e)) {478 Node w= G.tail(e);480 for(g->first(e,v); g->valid(e); g->next(e)) { 481 Node w=g->tail(e); 479 482 if ( level[w] == n && w != s ) { 480 483 bfs_queue.push(w); 481 484 Node first=level_list[l]; 482 if ( G.valid(first) ) left.set(first,w);485 if ( g->valid(first) ) left.set(first,w); 483 486 right.set(w,first); 484 487 level_list[l]=w; … … 490 493 //the starting flow 491 494 OutEdgeIt e; 492 for( G.first(e,s); G.valid(e); G.next(e))495 for(g->first(e,s); g->valid(e); g->next(e)) 493 496 { 494 497 T c=(*capacity)[e]; 495 498 if ( c == 0 ) continue; 496 Node w= G.head(e);499 Node w=g->head(e); 497 500 if ( level[w] < n ) { 498 501 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 519 522 520 523 InEdgeIt e; 521 for( G.first(e,v); G.valid(e); G.next(e)) {524 for(g->first(e,v); g->valid(e); g->next(e)) { 522 525 if ( (*capacity)[e] == (*flow)[e] ) continue; 523 Node w= G.tail(e);526 Node w=g->tail(e); 524 527 if ( level[w] == n && w != s ) { 525 528 bfs_queue.push(w); 526 529 Node first=level_list[l]; 527 if ( G.valid(first) ) left.set(first,w);530 if ( g->valid(first) ) left.set(first,w); 528 531 right.set(w,first); 529 532 level_list[l]=w; … … 533 536 534 537 OutEdgeIt f; 535 for( G.first(f,v); G.valid(f); G.next(f)) {538 for(g->first(f,v); g->valid(f); g->next(f)) { 536 539 if ( 0 == (*flow)[f] ) continue; 537 Node w= G.head(f);540 Node w=g->head(f); 538 541 if ( level[w] == n && w != s ) { 539 542 bfs_queue.push(w); 540 543 Node first=level_list[l]; 541 if ( G.valid(first) ) left.set(first,w);544 if ( g->valid(first) ) left.set(first,w); 542 545 right.set(w,first); 543 546 level_list[l]=w; … … 550 553 //the starting flow 551 554 OutEdgeIt e; 552 for( G.first(e,s); G.valid(e); G.next(e))555 for(g->first(e,s); g->valid(e); g->next(e)) 553 556 { 554 557 T rem=(*capacity)[e]-(*flow)[e]; 555 558 if ( rem == 0 ) continue; 556 Node w= G.head(e);559 Node w=g->head(e); 557 560 if ( level[w] < n ) { 558 561 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 563 566 564 567 InEdgeIt f; 565 for( G.first(f,s); G.valid(f); G.next(f))568 for(g->first(f,s); g->valid(f); g->next(f)) 566 569 { 567 570 if ( (*flow)[f] == 0 ) continue; 568 Node w= G.tail(f);571 Node w=g->tail(f); 569 572 if ( level[w] < n ) { 570 573 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w); … … 590 593 591 594 //unlacing starts 592 if ( G.valid(right_n) ) {593 if ( G.valid(left_n) ) {595 if ( g->valid(right_n) ) { 596 if ( g->valid(left_n) ) { 594 597 right.set(left_n, right_n); 595 598 left.set(right_n, left_n); … … 599 602 } 600 603 } else { 601 if ( G.valid(left_n) ) {604 if ( g->valid(left_n) ) { 602 605 right.set(left_n, INVALID); 603 606 } else { … … 607 610 //unlacing ends 608 611 609 if ( ! G.valid(level_list[lev]) ) {612 if ( !g->valid(level_list[lev]) ) { 610 613 611 614 //gapping starts 612 615 for (int i=lev; i!=k ; ) { 613 616 Node v=level_list[++i]; 614 while ( G.valid(v) ) {617 while ( g->valid(v) ) { 615 618 level.set(v,n); 616 619 v=right[v]; … … 638 641 if ( k < newlevel ) ++k; //now k=newlevel 639 642 Node first=level_list[newlevel]; 640 if ( G.valid(first) ) left.set(first,w);643 if ( g->valid(first) ) left.set(first,w); 641 644 right.set(w,first); 642 645 left.set(w,INVALID);
Note: See TracChangeset
for help on using the changeset viewer.