Merge bugfix #372 to branch 1.1 1.1
authorAlpar Juttner <alpar@cs.elte.hu>
Fri, 25 Jun 2010 05:48:27 +0200
branch1.1
changeset 733949510b70df9
parent 730 4f8b22521b4a
parent 732 bb70ad62c95f
child 734 9f22c22fe227
Merge bugfix #372 to branch 1.1
     1.1 --- a/lemon/preflow.h	Mon May 03 10:16:01 2010 +0200
     1.2 +++ b/lemon/preflow.h	Fri Jun 25 05:48:27 2010 +0200
     1.3 @@ -558,12 +558,18 @@
     1.4      void startFirstPhase() {
     1.5        _phase = true;
     1.6  
     1.7 -      Node n = _level->highestActive();
     1.8 -      int level = _level->highestActiveLevel();
     1.9 -      while (n != INVALID) {
    1.10 +      while (true) {
    1.11          int num = _node_num;
    1.12  
    1.13 -        while (num > 0 && n != INVALID) {
    1.14 +        Node n = INVALID;
    1.15 +        int level = -1;
    1.16 +
    1.17 +        while (num > 0) {
    1.18 +          n = _level->highestActive();
    1.19 +          if (n == INVALID) goto first_phase_done;
    1.20 +          level = _level->highestActiveLevel();
    1.21 +          --num;
    1.22 +          
    1.23            Value excess = (*_excess)[n];
    1.24            int new_level = _level->maxLevel();
    1.25  
    1.26 @@ -629,14 +635,22 @@
    1.27            } else {
    1.28              _level->deactivate(n);
    1.29            }
    1.30 -
    1.31 -          n = _level->highestActive();
    1.32 -          level = _level->highestActiveLevel();
    1.33 -          --num;
    1.34          }
    1.35  
    1.36          num = _node_num * 20;
    1.37 -        while (num > 0 && n != INVALID) {
    1.38 +        while (num > 0) {
    1.39 +          while (level >= 0 && _level->activeFree(level)) {
    1.40 +            --level;
    1.41 +          }
    1.42 +          if (level == -1) {
    1.43 +            n = _level->highestActive();
    1.44 +            level = _level->highestActiveLevel();
    1.45 +            if (n == INVALID) goto first_phase_done;
    1.46 +          } else {
    1.47 +            n = _level->activeOn(level);
    1.48 +          }
    1.49 +          --num;
    1.50 +
    1.51            Value excess = (*_excess)[n];
    1.52            int new_level = _level->maxLevel();
    1.53  
    1.54 @@ -702,19 +716,9 @@
    1.55            } else {
    1.56              _level->deactivate(n);
    1.57            }
    1.58 -
    1.59 -          while (level >= 0 && _level->activeFree(level)) {
    1.60 -            --level;
    1.61 -          }
    1.62 -          if (level == -1) {
    1.63 -            n = _level->highestActive();
    1.64 -            level = _level->highestActiveLevel();
    1.65 -          } else {
    1.66 -            n = _level->activeOn(level);
    1.67 -          }
    1.68 -          --num;
    1.69          }
    1.70        }
    1.71 +    first_phase_done:;
    1.72      }
    1.73  
    1.74      /// \brief Starts the second phase of the preflow algorithm.