equal
deleted
inserted
replaced
303 bfs_queue.pop(); |
303 bfs_queue.pop(); |
304 int l=level[v]+1; |
304 int l=level[v]+1; |
305 |
305 |
306 for(InEdgeIt e(*g,v); e!=INVALID; ++e) { |
306 for(InEdgeIt e(*g,v); e!=INVALID; ++e) { |
307 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
307 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
308 Node u=g->tail(e); |
308 Node u=g->source(e); |
309 if ( level[u] >= n ) { |
309 if ( level[u] >= n ) { |
310 bfs_queue.push(u); |
310 bfs_queue.push(u); |
311 level.set(u, l); |
311 level.set(u, l); |
312 if ( excess[u] > 0 ) { |
312 if ( excess[u] > 0 ) { |
313 next.set(u,first[l]); |
313 next.set(u,first[l]); |
316 } |
316 } |
317 } |
317 } |
318 |
318 |
319 for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { |
319 for(OutEdgeIt e(*g,v); e!=INVALID; ++e) { |
320 if ( 0 >= (*flow)[e] ) continue; |
320 if ( 0 >= (*flow)[e] ) continue; |
321 Node u=g->head(e); |
321 Node u=g->target(e); |
322 if ( level[u] >= n ) { |
322 if ( level[u] >= n ) { |
323 bfs_queue.push(u); |
323 bfs_queue.push(u); |
324 level.set(u, l); |
324 level.set(u, l); |
325 if ( excess[u] > 0 ) { |
325 if ( excess[u] > 0 ) { |
326 next.set(u,first[l]); |
326 next.set(u,first[l]); |
408 while (!queue.empty()) { |
408 while (!queue.empty()) { |
409 Node w=queue.front(); |
409 Node w=queue.front(); |
410 queue.pop(); |
410 queue.pop(); |
411 |
411 |
412 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
412 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
413 Node v=g->head(e); |
413 Node v=g->target(e); |
414 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { |
414 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { |
415 queue.push(v); |
415 queue.push(v); |
416 M.set(v, true); |
416 M.set(v, true); |
417 } |
417 } |
418 } |
418 } |
419 |
419 |
420 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
420 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
421 Node v=g->tail(e); |
421 Node v=g->source(e); |
422 if (!M[v] && (*flow)[e] > 0 ) { |
422 if (!M[v] && (*flow)[e] > 0 ) { |
423 queue.push(v); |
423 queue.push(v); |
424 M.set(v, true); |
424 M.set(v, true); |
425 } |
425 } |
426 } |
426 } |
446 while (!queue.empty()) { |
446 while (!queue.empty()) { |
447 Node w=queue.front(); |
447 Node w=queue.front(); |
448 queue.pop(); |
448 queue.pop(); |
449 |
449 |
450 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
450 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
451 Node v=g->tail(e); |
451 Node v=g->source(e); |
452 if (M[v] && (*flow)[e] < (*capacity)[e] ) { |
452 if (M[v] && (*flow)[e] < (*capacity)[e] ) { |
453 queue.push(v); |
453 queue.push(v); |
454 M.set(v, false); |
454 M.set(v, false); |
455 } |
455 } |
456 } |
456 } |
457 |
457 |
458 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
458 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
459 Node v=g->head(e); |
459 Node v=g->target(e); |
460 if (M[v] && (*flow)[e] > 0 ) { |
460 if (M[v] && (*flow)[e] > 0 ) { |
461 queue.push(v); |
461 queue.push(v); |
462 M.set(v, false); |
462 M.set(v, false); |
463 } |
463 } |
464 } |
464 } |
513 Num exc=excess[w]; |
513 Num exc=excess[w]; |
514 int newlevel=n; //bound on the next level of w |
514 int newlevel=n; //bound on the next level of w |
515 |
515 |
516 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
516 for(OutEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
517 if ( (*flow)[e] >= (*capacity)[e] ) continue; |
517 if ( (*flow)[e] >= (*capacity)[e] ) continue; |
518 Node v=g->head(e); |
518 Node v=g->target(e); |
519 |
519 |
520 if( lev > level[v] ) { //Push is allowed now |
520 if( lev > level[v] ) { //Push is allowed now |
521 |
521 |
522 if ( excess[v]<=0 && v!=t && v!=s ) { |
522 if ( excess[v]<=0 && v!=t && v!=s ) { |
523 next.set(v,first[level[v]]); |
523 next.set(v,first[level[v]]); |
545 |
545 |
546 if ( exc > 0 ) { |
546 if ( exc > 0 ) { |
547 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
547 for(InEdgeIt e(*g,w) ; e!=INVALID; ++e) { |
548 |
548 |
549 if( (*flow)[e] <= 0 ) continue; |
549 if( (*flow)[e] <= 0 ) continue; |
550 Node v=g->tail(e); |
550 Node v=g->source(e); |
551 |
551 |
552 if( lev > level[v] ) { //Push is allowed now |
552 if( lev > level[v] ) { //Push is allowed now |
553 |
553 |
554 if ( excess[v]<=0 && v!=t && v!=s ) { |
554 if ( excess[v]<=0 && v!=t && v!=s ) { |
555 next.set(v,first[level[v]]); |
555 next.set(v,first[level[v]]); |
600 bfs_queue.pop(); |
600 bfs_queue.pop(); |
601 int l=level[v]+1; |
601 int l=level[v]+1; |
602 |
602 |
603 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
603 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
604 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
604 if ( (*capacity)[e] <= (*flow)[e] ) continue; |
605 Node w=g->tail(e); |
605 Node w=g->source(e); |
606 if ( level[w] == n && w != s ) { |
606 if ( level[w] == n && w != s ) { |
607 bfs_queue.push(w); |
607 bfs_queue.push(w); |
608 Node z=level_list[l]; |
608 Node z=level_list[l]; |
609 if ( z!=INVALID ) left.set(z,w); |
609 if ( z!=INVALID ) left.set(z,w); |
610 right.set(w,z); |
610 right.set(w,z); |
613 } |
613 } |
614 } |
614 } |
615 |
615 |
616 for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
616 for(OutEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
617 if ( 0 >= (*flow)[e] ) continue; |
617 if ( 0 >= (*flow)[e] ) continue; |
618 Node w=g->head(e); |
618 Node w=g->target(e); |
619 if ( level[w] == n && w != s ) { |
619 if ( level[w] == n && w != s ) { |
620 bfs_queue.push(w); |
620 bfs_queue.push(w); |
621 Node z=level_list[l]; |
621 Node z=level_list[l]; |
622 if ( z!=INVALID ) left.set(z,w); |
622 if ( z!=INVALID ) left.set(z,w); |
623 right.set(w,z); |
623 right.set(w,z); |
644 Node v=bfs_queue.front(); |
644 Node v=bfs_queue.front(); |
645 bfs_queue.pop(); |
645 bfs_queue.pop(); |
646 int l=level[v]+1; |
646 int l=level[v]+1; |
647 |
647 |
648 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
648 for(InEdgeIt e(*g,v) ; e!=INVALID; ++e) { |
649 Node w=g->tail(e); |
649 Node w=g->source(e); |
650 if ( level[w] == n && w != s ) { |
650 if ( level[w] == n && w != s ) { |
651 bfs_queue.push(w); |
651 bfs_queue.push(w); |
652 Node z=level_list[l]; |
652 Node z=level_list[l]; |
653 if ( z!=INVALID ) left.set(z,w); |
653 if ( z!=INVALID ) left.set(z,w); |
654 right.set(w,z); |
654 right.set(w,z); |
660 |
660 |
661 //the starting flow |
661 //the starting flow |
662 for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
662 for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
663 Num c=(*capacity)[e]; |
663 Num c=(*capacity)[e]; |
664 if ( c <= 0 ) continue; |
664 if ( c <= 0 ) continue; |
665 Node w=g->head(e); |
665 Node w=g->target(e); |
666 if ( level[w] < n ) { |
666 if ( level[w] < n ) { |
667 if ( excess[w] <= 0 && w!=t ) { //putting into the stack |
667 if ( excess[w] <= 0 && w!=t ) { //putting into the stack |
668 next.set(w,first[level[w]]); |
668 next.set(w,first[level[w]]); |
669 first[level[w]]=w; |
669 first[level[w]]=w; |
670 } |
670 } |
685 |
685 |
686 //the starting flow |
686 //the starting flow |
687 for(OutEdgeIt e(*g,s); e!=INVALID; ++e) { |
687 for(OutEdgeIt e(*g,s); e!=INVALID; ++e) { |
688 Num rem=(*capacity)[e]-(*flow)[e]; |
688 Num rem=(*capacity)[e]-(*flow)[e]; |
689 if ( rem <= 0 ) continue; |
689 if ( rem <= 0 ) continue; |
690 Node w=g->head(e); |
690 Node w=g->target(e); |
691 if ( level[w] < n ) { |
691 if ( level[w] < n ) { |
692 if ( excess[w] <= 0 && w!=t ) { //putting into the stack |
692 if ( excess[w] <= 0 && w!=t ) { //putting into the stack |
693 next.set(w,first[level[w]]); |
693 next.set(w,first[level[w]]); |
694 first[level[w]]=w; |
694 first[level[w]]=w; |
695 } |
695 } |
698 } |
698 } |
699 } |
699 } |
700 |
700 |
701 for(InEdgeIt e(*g,s); e!=INVALID; ++e) { |
701 for(InEdgeIt e(*g,s); e!=INVALID; ++e) { |
702 if ( (*flow)[e] <= 0 ) continue; |
702 if ( (*flow)[e] <= 0 ) continue; |
703 Node w=g->tail(e); |
703 Node w=g->source(e); |
704 if ( level[w] < n ) { |
704 if ( level[w] < n ) { |
705 if ( excess[w] <= 0 && w!=t ) { |
705 if ( excess[w] <= 0 && w!=t ) { |
706 next.set(w,first[level[w]]); |
706 next.set(w,first[level[w]]); |
707 first[level[w]]=w; |
707 first[level[w]]=w; |
708 } |
708 } |
715 case PRE_FLOW: |
715 case PRE_FLOW: |
716 //the starting flow |
716 //the starting flow |
717 for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
717 for(OutEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
718 Num rem=(*capacity)[e]-(*flow)[e]; |
718 Num rem=(*capacity)[e]-(*flow)[e]; |
719 if ( rem <= 0 ) continue; |
719 if ( rem <= 0 ) continue; |
720 Node w=g->head(e); |
720 Node w=g->target(e); |
721 if ( level[w] < n ) flow->set(e, (*capacity)[e]); |
721 if ( level[w] < n ) flow->set(e, (*capacity)[e]); |
722 } |
722 } |
723 |
723 |
724 for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
724 for(InEdgeIt e(*g,s) ; e!=INVALID; ++e) { |
725 if ( (*flow)[e] <= 0 ) continue; |
725 if ( (*flow)[e] <= 0 ) continue; |
726 Node w=g->tail(e); |
726 Node w=g->source(e); |
727 if ( level[w] < n ) flow->set(e, 0); |
727 if ( level[w] < n ) flow->set(e, 0); |
728 } |
728 } |
729 |
729 |
730 //computing the excess |
730 //computing the excess |
731 for(NodeIt w(*g); w!=INVALID; ++w) { |
731 for(NodeIt w(*g); w!=INVALID; ++w) { |