# HG changeset patch
# User Balazs Dezso <deba@inf.elte.hu>
# Date 1277364473 -7200
# 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 -r 5205145fabf6 -r bb70ad62c95f lemon/preflow.h
--- a/lemon/preflow.h	Sun May 02 18:53:56 2010 +0200
+++ b/lemon/preflow.h	Thu Jun 24 09:27:53 2010 +0200
@@ -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.