r891:bb70ad62c95f
Thu, 24 Jun 2010 09:27:53
[Not Reviewed]
0 comments (0 inline)
0
1
0
24
20
| ... | ... |
@@ -537,54 +537,60 @@ |
| 537 | 537 |
if ((*_level)[v] == _level->maxLevel()) continue; |
| 538 | 538 |
_flow->set(e, 0); |
| 539 | 539 |
(*_excess)[v] += rem; |
| 540 | 540 |
if (v != _target && !_level->active(v)) {
|
| 541 | 541 |
_level->activate(v); |
| 542 | 542 |
} |
| 543 | 543 |
} |
| 544 | 544 |
} |
| 545 | 545 |
return true; |
| 546 | 546 |
} |
| 547 | 547 |
|
| 548 | 548 |
/// \brief Starts the first phase of the preflow algorithm. |
| 549 | 549 |
/// |
| 550 | 550 |
/// The preflow algorithm consists of two phases, this method runs |
| 551 | 551 |
/// the first phase. After the first phase the maximum flow value |
| 552 | 552 |
/// and a minimum value cut can already be computed, although a |
| 553 | 553 |
/// maximum flow is not yet obtained. So after calling this method |
| 554 | 554 |
/// \ref flowValue() returns the value of a maximum flow and \ref |
| 555 | 555 |
/// minCut() returns a minimum cut. |
| 556 | 556 |
/// \pre One of the \ref init() functions must be called before |
| 557 | 557 |
/// using this function. |
| 558 | 558 |
void startFirstPhase() {
|
| 559 | 559 |
_phase = true; |
| 560 | 560 |
|
| 561 |
Node n = _level->highestActive(); |
|
| 562 |
int level = _level->highestActiveLevel(); |
|
| 563 |
while ( |
|
| 561 |
while (true) {
|
|
| 564 | 562 |
int num = _node_num; |
| 565 | 563 |
|
| 566 |
|
|
| 564 |
Node n = INVALID; |
|
| 565 |
int level = -1; |
|
| 566 |
|
|
| 567 |
while (num > 0) {
|
|
| 568 |
n = _level->highestActive(); |
|
| 569 |
if (n == INVALID) goto first_phase_done; |
|
| 570 |
level = _level->highestActiveLevel(); |
|
| 571 |
--num; |
|
| 572 |
|
|
| 567 | 573 |
Value excess = (*_excess)[n]; |
| 568 | 574 |
int new_level = _level->maxLevel(); |
| 569 | 575 |
|
| 570 | 576 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 571 | 577 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 572 | 578 |
if (!_tolerance.positive(rem)) continue; |
| 573 | 579 |
Node v = _graph.target(e); |
| 574 | 580 |
if ((*_level)[v] < level) {
|
| 575 | 581 |
if (!_level->active(v) && v != _target) {
|
| 576 | 582 |
_level->activate(v); |
| 577 | 583 |
} |
| 578 | 584 |
if (!_tolerance.less(rem, excess)) {
|
| 579 | 585 |
_flow->set(e, (*_flow)[e] + excess); |
| 580 | 586 |
(*_excess)[v] += excess; |
| 581 | 587 |
excess = 0; |
| 582 | 588 |
goto no_more_push_1; |
| 583 | 589 |
} else {
|
| 584 | 590 |
excess -= rem; |
| 585 | 591 |
(*_excess)[v] += rem; |
| 586 | 592 |
_flow->set(e, (*_capacity)[e]); |
| 587 | 593 |
} |
| 588 | 594 |
} else if (new_level > (*_level)[v]) {
|
| 589 | 595 |
new_level = (*_level)[v]; |
| 590 | 596 |
} |
| ... | ... |
@@ -608,56 +614,64 @@ |
| 608 | 614 |
(*_excess)[v] += rem; |
| 609 | 615 |
_flow->set(e, 0); |
| 610 | 616 |
} |
| 611 | 617 |
} else if (new_level > (*_level)[v]) {
|
| 612 | 618 |
new_level = (*_level)[v]; |
| 613 | 619 |
} |
| 614 | 620 |
} |
| 615 | 621 |
|
| 616 | 622 |
no_more_push_1: |
| 617 | 623 |
|
| 618 | 624 |
(*_excess)[n] = excess; |
| 619 | 625 |
|
| 620 | 626 |
if (excess != 0) {
|
| 621 | 627 |
if (new_level + 1 < _level->maxLevel()) {
|
| 622 | 628 |
_level->liftHighestActive(new_level + 1); |
| 623 | 629 |
} else {
|
| 624 | 630 |
_level->liftHighestActiveToTop(); |
| 625 | 631 |
} |
| 626 | 632 |
if (_level->emptyLevel(level)) {
|
| 627 | 633 |
_level->liftToTop(level); |
| 628 | 634 |
} |
| 629 | 635 |
} else {
|
| 630 | 636 |
_level->deactivate(n); |
| 631 | 637 |
} |
| 632 |
|
|
| 633 |
n = _level->highestActive(); |
|
| 634 |
level = _level->highestActiveLevel(); |
|
| 635 |
--num; |
|
| 636 | 638 |
} |
| 637 | 639 |
|
| 638 | 640 |
num = _node_num * 20; |
| 639 |
while (num > 0 |
|
| 641 |
while (num > 0) {
|
|
| 642 |
while (level >= 0 && _level->activeFree(level)) {
|
|
| 643 |
--level; |
|
| 644 |
} |
|
| 645 |
if (level == -1) {
|
|
| 646 |
n = _level->highestActive(); |
|
| 647 |
level = _level->highestActiveLevel(); |
|
| 648 |
if (n == INVALID) goto first_phase_done; |
|
| 649 |
} else {
|
|
| 650 |
n = _level->activeOn(level); |
|
| 651 |
} |
|
| 652 |
--num; |
|
| 653 |
|
|
| 640 | 654 |
Value excess = (*_excess)[n]; |
| 641 | 655 |
int new_level = _level->maxLevel(); |
| 642 | 656 |
|
| 643 | 657 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 644 | 658 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 645 | 659 |
if (!_tolerance.positive(rem)) continue; |
| 646 | 660 |
Node v = _graph.target(e); |
| 647 | 661 |
if ((*_level)[v] < level) {
|
| 648 | 662 |
if (!_level->active(v) && v != _target) {
|
| 649 | 663 |
_level->activate(v); |
| 650 | 664 |
} |
| 651 | 665 |
if (!_tolerance.less(rem, excess)) {
|
| 652 | 666 |
_flow->set(e, (*_flow)[e] + excess); |
| 653 | 667 |
(*_excess)[v] += excess; |
| 654 | 668 |
excess = 0; |
| 655 | 669 |
goto no_more_push_2; |
| 656 | 670 |
} else {
|
| 657 | 671 |
excess -= rem; |
| 658 | 672 |
(*_excess)[v] += rem; |
| 659 | 673 |
_flow->set(e, (*_capacity)[e]); |
| 660 | 674 |
} |
| 661 | 675 |
} else if (new_level > (*_level)[v]) {
|
| 662 | 676 |
new_level = (*_level)[v]; |
| 663 | 677 |
} |
| ... | ... |
@@ -681,61 +695,51 @@ |
| 681 | 695 |
(*_excess)[v] += rem; |
| 682 | 696 |
_flow->set(e, 0); |
| 683 | 697 |
} |
| 684 | 698 |
} else if (new_level > (*_level)[v]) {
|
| 685 | 699 |
new_level = (*_level)[v]; |
| 686 | 700 |
} |
| 687 | 701 |
} |
| 688 | 702 |
|
| 689 | 703 |
no_more_push_2: |
| 690 | 704 |
|
| 691 | 705 |
(*_excess)[n] = excess; |
| 692 | 706 |
|
| 693 | 707 |
if (excess != 0) {
|
| 694 | 708 |
if (new_level + 1 < _level->maxLevel()) {
|
| 695 | 709 |
_level->liftActiveOn(level, new_level + 1); |
| 696 | 710 |
} else {
|
| 697 | 711 |
_level->liftActiveToTop(level); |
| 698 | 712 |
} |
| 699 | 713 |
if (_level->emptyLevel(level)) {
|
| 700 | 714 |
_level->liftToTop(level); |
| 701 | 715 |
} |
| 702 | 716 |
} else {
|
| 703 | 717 |
_level->deactivate(n); |
| 704 | 718 |
} |
| 705 |
|
|
| 706 |
while (level >= 0 && _level->activeFree(level)) {
|
|
| 707 |
--level; |
|
| 708 |
} |
|
| 709 |
if (level == -1) {
|
|
| 710 |
n = _level->highestActive(); |
|
| 711 |
level = _level->highestActiveLevel(); |
|
| 712 |
} else {
|
|
| 713 |
n = _level->activeOn(level); |
|
| 714 |
} |
|
| 715 |
--num; |
|
| 716 | 719 |
} |
| 717 | 720 |
} |
| 721 |
first_phase_done:; |
|
| 718 | 722 |
} |
| 719 | 723 |
|
| 720 | 724 |
/// \brief Starts the second phase of the preflow algorithm. |
| 721 | 725 |
/// |
| 722 | 726 |
/// The preflow algorithm consists of two phases, this method runs |
| 723 | 727 |
/// the second phase. After calling one of the \ref init() functions |
| 724 | 728 |
/// and \ref startFirstPhase() and then \ref startSecondPhase(), |
| 725 | 729 |
/// \ref flowMap() returns a maximum flow, \ref flowValue() returns the |
| 726 | 730 |
/// value of a maximum flow, \ref minCut() returns a minimum cut |
| 727 | 731 |
/// \pre One of the \ref init() functions and \ref startFirstPhase() |
| 728 | 732 |
/// must be called before using this function. |
| 729 | 733 |
void startSecondPhase() {
|
| 730 | 734 |
_phase = false; |
| 731 | 735 |
|
| 732 | 736 |
typename Digraph::template NodeMap<bool> reached(_graph); |
| 733 | 737 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 734 | 738 |
reached[n] = (*_level)[n] < _level->maxLevel(); |
| 735 | 739 |
} |
| 736 | 740 |
|
| 737 | 741 |
_level->initStart(); |
| 738 | 742 |
_level->initAddItem(_source); |
| 739 | 743 |
|
| 740 | 744 |
std::vector<Node> queue; |
| 741 | 745 |
queue.push_back(_source); |
0 comments (0 inline)