Fix critical bug in preflow (#372)
authorBalazs Dezso <deba@inf.elte.hu>
Thu, 24 Jun 2010 09:27:53 +0200
changeset 891bb70ad62c95f
parent 888 5205145fabf6
child 892 a22b3f1bf83e
child 923 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.