r985:f63fd24c0aea
Fri, 25 Jun 2010 05:54:56
[Not Reviewed]
0 comments (0 inline)
0
1
0
24
20
| ... | ... |
@@ -483,349 +483,353 @@ |
| 483 | 483 |
bool init(const FlowMap& flowMap) {
|
| 484 | 484 |
createStructures(); |
| 485 | 485 |
|
| 486 | 486 |
for (ArcIt e(_graph); e != INVALID; ++e) {
|
| 487 | 487 |
_flow->set(e, flowMap[e]); |
| 488 | 488 |
} |
| 489 | 489 |
|
| 490 | 490 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 491 | 491 |
Value excess = 0; |
| 492 | 492 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 493 | 493 |
excess += (*_flow)[e]; |
| 494 | 494 |
} |
| 495 | 495 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 496 | 496 |
excess -= (*_flow)[e]; |
| 497 | 497 |
} |
| 498 | 498 |
if (excess < 0 && n != _source) return false; |
| 499 | 499 |
(*_excess)[n] = excess; |
| 500 | 500 |
} |
| 501 | 501 |
|
| 502 | 502 |
typename Digraph::template NodeMap<bool> reached(_graph, false); |
| 503 | 503 |
|
| 504 | 504 |
_level->initStart(); |
| 505 | 505 |
_level->initAddItem(_target); |
| 506 | 506 |
|
| 507 | 507 |
std::vector<Node> queue; |
| 508 | 508 |
reached[_source] = true; |
| 509 | 509 |
|
| 510 | 510 |
queue.push_back(_target); |
| 511 | 511 |
reached[_target] = true; |
| 512 | 512 |
while (!queue.empty()) {
|
| 513 | 513 |
_level->initNewLevel(); |
| 514 | 514 |
std::vector<Node> nqueue; |
| 515 | 515 |
for (int i = 0; i < int(queue.size()); ++i) {
|
| 516 | 516 |
Node n = queue[i]; |
| 517 | 517 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 518 | 518 |
Node u = _graph.source(e); |
| 519 | 519 |
if (!reached[u] && |
| 520 | 520 |
_tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
|
| 521 | 521 |
reached[u] = true; |
| 522 | 522 |
_level->initAddItem(u); |
| 523 | 523 |
nqueue.push_back(u); |
| 524 | 524 |
} |
| 525 | 525 |
} |
| 526 | 526 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 527 | 527 |
Node v = _graph.target(e); |
| 528 | 528 |
if (!reached[v] && _tolerance.positive((*_flow)[e])) {
|
| 529 | 529 |
reached[v] = true; |
| 530 | 530 |
_level->initAddItem(v); |
| 531 | 531 |
nqueue.push_back(v); |
| 532 | 532 |
} |
| 533 | 533 |
} |
| 534 | 534 |
} |
| 535 | 535 |
queue.swap(nqueue); |
| 536 | 536 |
} |
| 537 | 537 |
_level->initFinish(); |
| 538 | 538 |
|
| 539 | 539 |
for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
|
| 540 | 540 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 541 | 541 |
if (_tolerance.positive(rem)) {
|
| 542 | 542 |
Node u = _graph.target(e); |
| 543 | 543 |
if ((*_level)[u] == _level->maxLevel()) continue; |
| 544 | 544 |
_flow->set(e, (*_capacity)[e]); |
| 545 | 545 |
(*_excess)[u] += rem; |
| 546 | 546 |
if (u != _target && !_level->active(u)) {
|
| 547 | 547 |
_level->activate(u); |
| 548 | 548 |
} |
| 549 | 549 |
} |
| 550 | 550 |
} |
| 551 | 551 |
for (InArcIt e(_graph, _source); e != INVALID; ++e) {
|
| 552 | 552 |
Value rem = (*_flow)[e]; |
| 553 | 553 |
if (_tolerance.positive(rem)) {
|
| 554 | 554 |
Node v = _graph.source(e); |
| 555 | 555 |
if ((*_level)[v] == _level->maxLevel()) continue; |
| 556 | 556 |
_flow->set(e, 0); |
| 557 | 557 |
(*_excess)[v] += rem; |
| 558 | 558 |
if (v != _target && !_level->active(v)) {
|
| 559 | 559 |
_level->activate(v); |
| 560 | 560 |
} |
| 561 | 561 |
} |
| 562 | 562 |
} |
| 563 | 563 |
return true; |
| 564 | 564 |
} |
| 565 | 565 |
|
| 566 | 566 |
/// \brief Starts the first phase of the preflow algorithm. |
| 567 | 567 |
/// |
| 568 | 568 |
/// The preflow algorithm consists of two phases, this method runs |
| 569 | 569 |
/// the first phase. After the first phase the maximum flow value |
| 570 | 570 |
/// and a minimum value cut can already be computed, although a |
| 571 | 571 |
/// maximum flow is not yet obtained. So after calling this method |
| 572 | 572 |
/// \ref flowValue() returns the value of a maximum flow and \ref |
| 573 | 573 |
/// minCut() returns a minimum cut. |
| 574 | 574 |
/// \pre One of the \ref init() functions must be called before |
| 575 | 575 |
/// using this function. |
| 576 | 576 |
void startFirstPhase() {
|
| 577 | 577 |
_phase = true; |
| 578 | 578 |
|
| 579 |
Node n = _level->highestActive(); |
|
| 580 |
int level = _level->highestActiveLevel(); |
|
| 581 |
while ( |
|
| 579 |
while (true) {
|
|
| 582 | 580 |
int num = _node_num; |
| 583 | 581 |
|
| 584 |
|
|
| 582 |
Node n = INVALID; |
|
| 583 |
int level = -1; |
|
| 584 |
|
|
| 585 |
while (num > 0) {
|
|
| 586 |
n = _level->highestActive(); |
|
| 587 |
if (n == INVALID) goto first_phase_done; |
|
| 588 |
level = _level->highestActiveLevel(); |
|
| 589 |
--num; |
|
| 590 |
|
|
| 585 | 591 |
Value excess = (*_excess)[n]; |
| 586 | 592 |
int new_level = _level->maxLevel(); |
| 587 | 593 |
|
| 588 | 594 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 589 | 595 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 590 | 596 |
if (!_tolerance.positive(rem)) continue; |
| 591 | 597 |
Node v = _graph.target(e); |
| 592 | 598 |
if ((*_level)[v] < level) {
|
| 593 | 599 |
if (!_level->active(v) && v != _target) {
|
| 594 | 600 |
_level->activate(v); |
| 595 | 601 |
} |
| 596 | 602 |
if (!_tolerance.less(rem, excess)) {
|
| 597 | 603 |
_flow->set(e, (*_flow)[e] + excess); |
| 598 | 604 |
(*_excess)[v] += excess; |
| 599 | 605 |
excess = 0; |
| 600 | 606 |
goto no_more_push_1; |
| 601 | 607 |
} else {
|
| 602 | 608 |
excess -= rem; |
| 603 | 609 |
(*_excess)[v] += rem; |
| 604 | 610 |
_flow->set(e, (*_capacity)[e]); |
| 605 | 611 |
} |
| 606 | 612 |
} else if (new_level > (*_level)[v]) {
|
| 607 | 613 |
new_level = (*_level)[v]; |
| 608 | 614 |
} |
| 609 | 615 |
} |
| 610 | 616 |
|
| 611 | 617 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 612 | 618 |
Value rem = (*_flow)[e]; |
| 613 | 619 |
if (!_tolerance.positive(rem)) continue; |
| 614 | 620 |
Node v = _graph.source(e); |
| 615 | 621 |
if ((*_level)[v] < level) {
|
| 616 | 622 |
if (!_level->active(v) && v != _target) {
|
| 617 | 623 |
_level->activate(v); |
| 618 | 624 |
} |
| 619 | 625 |
if (!_tolerance.less(rem, excess)) {
|
| 620 | 626 |
_flow->set(e, (*_flow)[e] - excess); |
| 621 | 627 |
(*_excess)[v] += excess; |
| 622 | 628 |
excess = 0; |
| 623 | 629 |
goto no_more_push_1; |
| 624 | 630 |
} else {
|
| 625 | 631 |
excess -= rem; |
| 626 | 632 |
(*_excess)[v] += rem; |
| 627 | 633 |
_flow->set(e, 0); |
| 628 | 634 |
} |
| 629 | 635 |
} else if (new_level > (*_level)[v]) {
|
| 630 | 636 |
new_level = (*_level)[v]; |
| 631 | 637 |
} |
| 632 | 638 |
} |
| 633 | 639 |
|
| 634 | 640 |
no_more_push_1: |
| 635 | 641 |
|
| 636 | 642 |
(*_excess)[n] = excess; |
| 637 | 643 |
|
| 638 | 644 |
if (excess != 0) {
|
| 639 | 645 |
if (new_level + 1 < _level->maxLevel()) {
|
| 640 | 646 |
_level->liftHighestActive(new_level + 1); |
| 641 | 647 |
} else {
|
| 642 | 648 |
_level->liftHighestActiveToTop(); |
| 643 | 649 |
} |
| 644 | 650 |
if (_level->emptyLevel(level)) {
|
| 645 | 651 |
_level->liftToTop(level); |
| 646 | 652 |
} |
| 647 | 653 |
} else {
|
| 648 | 654 |
_level->deactivate(n); |
| 649 | 655 |
} |
| 650 |
|
|
| 651 |
n = _level->highestActive(); |
|
| 652 |
level = _level->highestActiveLevel(); |
|
| 653 |
--num; |
|
| 654 | 656 |
} |
| 655 | 657 |
|
| 656 | 658 |
num = _node_num * 20; |
| 657 |
while (num > 0 |
|
| 659 |
while (num > 0) {
|
|
| 660 |
while (level >= 0 && _level->activeFree(level)) {
|
|
| 661 |
--level; |
|
| 662 |
} |
|
| 663 |
if (level == -1) {
|
|
| 664 |
n = _level->highestActive(); |
|
| 665 |
level = _level->highestActiveLevel(); |
|
| 666 |
if (n == INVALID) goto first_phase_done; |
|
| 667 |
} else {
|
|
| 668 |
n = _level->activeOn(level); |
|
| 669 |
} |
|
| 670 |
--num; |
|
| 671 |
|
|
| 658 | 672 |
Value excess = (*_excess)[n]; |
| 659 | 673 |
int new_level = _level->maxLevel(); |
| 660 | 674 |
|
| 661 | 675 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 662 | 676 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 663 | 677 |
if (!_tolerance.positive(rem)) continue; |
| 664 | 678 |
Node v = _graph.target(e); |
| 665 | 679 |
if ((*_level)[v] < level) {
|
| 666 | 680 |
if (!_level->active(v) && v != _target) {
|
| 667 | 681 |
_level->activate(v); |
| 668 | 682 |
} |
| 669 | 683 |
if (!_tolerance.less(rem, excess)) {
|
| 670 | 684 |
_flow->set(e, (*_flow)[e] + excess); |
| 671 | 685 |
(*_excess)[v] += excess; |
| 672 | 686 |
excess = 0; |
| 673 | 687 |
goto no_more_push_2; |
| 674 | 688 |
} else {
|
| 675 | 689 |
excess -= rem; |
| 676 | 690 |
(*_excess)[v] += rem; |
| 677 | 691 |
_flow->set(e, (*_capacity)[e]); |
| 678 | 692 |
} |
| 679 | 693 |
} else if (new_level > (*_level)[v]) {
|
| 680 | 694 |
new_level = (*_level)[v]; |
| 681 | 695 |
} |
| 682 | 696 |
} |
| 683 | 697 |
|
| 684 | 698 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 685 | 699 |
Value rem = (*_flow)[e]; |
| 686 | 700 |
if (!_tolerance.positive(rem)) continue; |
| 687 | 701 |
Node v = _graph.source(e); |
| 688 | 702 |
if ((*_level)[v] < level) {
|
| 689 | 703 |
if (!_level->active(v) && v != _target) {
|
| 690 | 704 |
_level->activate(v); |
| 691 | 705 |
} |
| 692 | 706 |
if (!_tolerance.less(rem, excess)) {
|
| 693 | 707 |
_flow->set(e, (*_flow)[e] - excess); |
| 694 | 708 |
(*_excess)[v] += excess; |
| 695 | 709 |
excess = 0; |
| 696 | 710 |
goto no_more_push_2; |
| 697 | 711 |
} else {
|
| 698 | 712 |
excess -= rem; |
| 699 | 713 |
(*_excess)[v] += rem; |
| 700 | 714 |
_flow->set(e, 0); |
| 701 | 715 |
} |
| 702 | 716 |
} else if (new_level > (*_level)[v]) {
|
| 703 | 717 |
new_level = (*_level)[v]; |
| 704 | 718 |
} |
| 705 | 719 |
} |
| 706 | 720 |
|
| 707 | 721 |
no_more_push_2: |
| 708 | 722 |
|
| 709 | 723 |
(*_excess)[n] = excess; |
| 710 | 724 |
|
| 711 | 725 |
if (excess != 0) {
|
| 712 | 726 |
if (new_level + 1 < _level->maxLevel()) {
|
| 713 | 727 |
_level->liftActiveOn(level, new_level + 1); |
| 714 | 728 |
} else {
|
| 715 | 729 |
_level->liftActiveToTop(level); |
| 716 | 730 |
} |
| 717 | 731 |
if (_level->emptyLevel(level)) {
|
| 718 | 732 |
_level->liftToTop(level); |
| 719 | 733 |
} |
| 720 | 734 |
} else {
|
| 721 | 735 |
_level->deactivate(n); |
| 722 | 736 |
} |
| 723 |
|
|
| 724 |
while (level >= 0 && _level->activeFree(level)) {
|
|
| 725 |
--level; |
|
| 726 |
} |
|
| 727 |
if (level == -1) {
|
|
| 728 |
n = _level->highestActive(); |
|
| 729 |
level = _level->highestActiveLevel(); |
|
| 730 |
} else {
|
|
| 731 |
n = _level->activeOn(level); |
|
| 732 |
} |
|
| 733 |
--num; |
|
| 734 | 737 |
} |
| 735 | 738 |
} |
| 739 |
first_phase_done:; |
|
| 736 | 740 |
} |
| 737 | 741 |
|
| 738 | 742 |
/// \brief Starts the second phase of the preflow algorithm. |
| 739 | 743 |
/// |
| 740 | 744 |
/// The preflow algorithm consists of two phases, this method runs |
| 741 | 745 |
/// the second phase. After calling one of the \ref init() functions |
| 742 | 746 |
/// and \ref startFirstPhase() and then \ref startSecondPhase(), |
| 743 | 747 |
/// \ref flowMap() returns a maximum flow, \ref flowValue() returns the |
| 744 | 748 |
/// value of a maximum flow, \ref minCut() returns a minimum cut |
| 745 | 749 |
/// \pre One of the \ref init() functions and \ref startFirstPhase() |
| 746 | 750 |
/// must be called before using this function. |
| 747 | 751 |
void startSecondPhase() {
|
| 748 | 752 |
_phase = false; |
| 749 | 753 |
|
| 750 | 754 |
typename Digraph::template NodeMap<bool> reached(_graph); |
| 751 | 755 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 752 | 756 |
reached[n] = (*_level)[n] < _level->maxLevel(); |
| 753 | 757 |
} |
| 754 | 758 |
|
| 755 | 759 |
_level->initStart(); |
| 756 | 760 |
_level->initAddItem(_source); |
| 757 | 761 |
|
| 758 | 762 |
std::vector<Node> queue; |
| 759 | 763 |
queue.push_back(_source); |
| 760 | 764 |
reached[_source] = true; |
| 761 | 765 |
|
| 762 | 766 |
while (!queue.empty()) {
|
| 763 | 767 |
_level->initNewLevel(); |
| 764 | 768 |
std::vector<Node> nqueue; |
| 765 | 769 |
for (int i = 0; i < int(queue.size()); ++i) {
|
| 766 | 770 |
Node n = queue[i]; |
| 767 | 771 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 768 | 772 |
Node v = _graph.target(e); |
| 769 | 773 |
if (!reached[v] && _tolerance.positive((*_flow)[e])) {
|
| 770 | 774 |
reached[v] = true; |
| 771 | 775 |
_level->initAddItem(v); |
| 772 | 776 |
nqueue.push_back(v); |
| 773 | 777 |
} |
| 774 | 778 |
} |
| 775 | 779 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 776 | 780 |
Node u = _graph.source(e); |
| 777 | 781 |
if (!reached[u] && |
| 778 | 782 |
_tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
|
| 779 | 783 |
reached[u] = true; |
| 780 | 784 |
_level->initAddItem(u); |
| 781 | 785 |
nqueue.push_back(u); |
| 782 | 786 |
} |
| 783 | 787 |
} |
| 784 | 788 |
} |
| 785 | 789 |
queue.swap(nqueue); |
| 786 | 790 |
} |
| 787 | 791 |
_level->initFinish(); |
| 788 | 792 |
|
| 789 | 793 |
for (NodeIt n(_graph); n != INVALID; ++n) {
|
| 790 | 794 |
if (!reached[n]) {
|
| 791 | 795 |
_level->dirtyTopButOne(n); |
| 792 | 796 |
} else if ((*_excess)[n] > 0 && _target != n) {
|
| 793 | 797 |
_level->activate(n); |
| 794 | 798 |
} |
| 795 | 799 |
} |
| 796 | 800 |
|
| 797 | 801 |
Node n; |
| 798 | 802 |
while ((n = _level->highestActive()) != INVALID) {
|
| 799 | 803 |
Value excess = (*_excess)[n]; |
| 800 | 804 |
int level = _level->highestActiveLevel(); |
| 801 | 805 |
int new_level = _level->maxLevel(); |
| 802 | 806 |
|
| 803 | 807 |
for (OutArcIt e(_graph, n); e != INVALID; ++e) {
|
| 804 | 808 |
Value rem = (*_capacity)[e] - (*_flow)[e]; |
| 805 | 809 |
if (!_tolerance.positive(rem)) continue; |
| 806 | 810 |
Node v = _graph.target(e); |
| 807 | 811 |
if ((*_level)[v] < level) {
|
| 808 | 812 |
if (!_level->active(v) && v != _source) {
|
| 809 | 813 |
_level->activate(v); |
| 810 | 814 |
} |
| 811 | 815 |
if (!_tolerance.less(rem, excess)) {
|
| 812 | 816 |
_flow->set(e, (*_flow)[e] + excess); |
| 813 | 817 |
(*_excess)[v] += excess; |
| 814 | 818 |
excess = 0; |
| 815 | 819 |
goto no_more_push; |
| 816 | 820 |
} else {
|
| 817 | 821 |
excess -= rem; |
| 818 | 822 |
(*_excess)[v] += rem; |
| 819 | 823 |
_flow->set(e, (*_capacity)[e]); |
| 820 | 824 |
} |
| 821 | 825 |
} else if (new_level > (*_level)[v]) {
|
| 822 | 826 |
new_level = (*_level)[v]; |
| 823 | 827 |
} |
| 824 | 828 |
} |
| 825 | 829 |
|
| 826 | 830 |
for (InArcIt e(_graph, n); e != INVALID; ++e) {
|
| 827 | 831 |
Value rem = (*_flow)[e]; |
| 828 | 832 |
if (!_tolerance.positive(rem)) continue; |
| 829 | 833 |
Node v = _graph.source(e); |
| 830 | 834 |
if ((*_level)[v] < level) {
|
| 831 | 835 |
if (!_level->active(v) && v != _source) {
|
0 comments (0 inline)