# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 2010-06-24 09:27:53
# Node ID bb70ad62c95fd75d6bd134451a406df9bd0eda12
# Parent  5205145fabf68906e789911c2fc39968fd655f6e

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.

diff --git a/lemon/preflow.h b/lemon/preflow.h
--- a/lemon/preflow.h
+++ b/lemon/preflow.h
@@ -558,12 +558,18 @@
     void startFirstPhase() {
       _phase = true;
 
-      Node n = _level->highestActive();
-      int level = _level->highestActiveLevel();
-      while (n != INVALID) {
+      while (true) {
         int num = _node_num;
 
-        while (num > 0 && n != INVALID) {
+        Node n = INVALID;
+        int level = -1;
+
+        while (num > 0) {
+          n = _level->highestActive();
+          if (n == INVALID) goto first_phase_done;
+          level = _level->highestActiveLevel();
+          --num;
+          
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
@@ -629,14 +635,22 @@
           } else {
             _level->deactivate(n);
           }
-
-          n = _level->highestActive();
-          level = _level->highestActiveLevel();
-          --num;
         }
 
         num = _node_num * 20;
-        while (num > 0 && n != INVALID) {
+        while (num > 0) {
+          while (level >= 0 && _level->activeFree(level)) {
+            --level;
+          }
+          if (level == -1) {
+            n = _level->highestActive();
+            level = _level->highestActiveLevel();
+            if (n == INVALID) goto first_phase_done;
+          } else {
+            n = _level->activeOn(level);
+          }
+          --num;
+
           Value excess = (*_excess)[n];
           int new_level = _level->maxLevel();
 
@@ -702,19 +716,9 @@
           } else {
             _level->deactivate(n);
           }
-
-          while (level >= 0 && _level->activeFree(level)) {
-            --level;
-          }
-          if (level == -1) {
-            n = _level->highestActive();
-            level = _level->highestActiveLevel();
-          } else {
-            n = _level->activeOn(level);
-          }
-          --num;
         }
       }
+    first_phase_done:;
     }
 
     /// \brief Starts the second phase of the preflow algorithm.