Fix critical bug in preflow (#372)
authorBalazs Dezso <deba@inf.elte.hu>
Thu, 24 Jun 2010 09:27:53 +0200
changeset 732bb70ad62c95f
parent 729 5205145fabf6
child 733 949510b70df9
child 739 30d5f950aa5f
Fix critical bug in preflow (#372)

The wrong transition between the bound decrease and highest active
heuristics caused the bug. The last node chosen in bound decrease mode
is used in the first iteration in highest active mode.
lemon/preflow.h
     1.1 --- a/lemon/preflow.h	Sun May 02 18:53:56 2010 +0200
     1.2 +++ b/lemon/preflow.h	Thu Jun 24 09:27:53 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.