r891:bb70ad62c95f
Thu, 24 Jun 2010 09:27:53
[Not Reviewed]
0 comments (0 inline)
0
1
0
24
20
| ... | ... |
@@ -555,18 +555,24 @@ |
| 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; |
| ... | ... |
@@ -626,20 +632,28 @@ |
| 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; |
| ... | ... |
@@ -699,25 +713,15 @@ |
| 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 | 719 |
} |
| 709 |
if (level == -1) {
|
|
| 710 |
n = _level->highestActive(); |
|
| 711 |
level = _level->highestActiveLevel(); |
|
| 712 |
} else {
|
|
| 713 |
n = _level->activeOn(level); |
|
| 714 | 720 |
} |
| 715 |
--num; |
|
| 716 |
} |
|
| 717 |
|
|
| 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 |
0 comments (0 inline)