COIN-OR::LEMON - Graph Library

Changeset 894:bb70ad62c95f in lemon-1.2 for lemon


Ignore:
Timestamp:
06/24/10 09:27:53 (9 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
895:f63fd24c0aea, 901:30d5f950aa5f
Phase:
public
Message:

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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r688 r894  
    559559      _phase = true;
    560560
    561       Node n = _level->highestActive();
    562       int level = _level->highestActiveLevel();
    563       while (n != INVALID) {
     561      while (true) {
    564562        int num = _node_num;
    565563
    566         while (num > 0 && n != INVALID) {
     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         
    567573          Value excess = (*_excess)[n];
    568574          int new_level = _level->maxLevel();
     
    630636            _level->deactivate(n);
    631637          }
    632 
    633           n = _level->highestActive();
    634           level = _level->highestActiveLevel();
     638        }
     639
     640        num = _node_num * 20;
     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          }
    635652          --num;
    636         }
    637 
    638         num = _node_num * 20;
    639         while (num > 0 && n != INVALID) {
     653
    640654          Value excess = (*_excess)[n];
    641655          int new_level = _level->maxLevel();
     
    703717            _level->deactivate(n);
    704718          }
    705 
    706           while (level >= 0 && _level->activeFree(level)) {
    707             --level;
    708           }
    709           if (level == -1) {
    710             n = _level->highestActive();
    711             level = _level->highestActiveLevel();
    712           } else {
    713             n = _level->activeOn(level);
    714           }
    715           --num;
    716         }
    717       }
     719        }
     720      }
     721    first_phase_done:;
    718722    }
    719723
Note: See TracChangeset for help on using the changeset viewer.