Changeset 656:9971eb8bfbe8 in lemon-0.x for src/work/jacint/max_flow.h

Timestamp:

05/21/04 14:40:39 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@859

Message:

max_flow.h bug correction

File:

• src/work/jacint/max_flow.h (modified) (5 diffs)

src/work/jacint/max_flow.h

@@ -123 +123 @@
       AFTER_NOTHING,
       AFTER_AUGMENTING,
+      AFTER_FAST_AUGMENTING, 
       AFTER_PRE_FLOW_PHASE_1,      
       AFTER_PRE_FLOW_PHASE_2
@@ -266 +267 @@
       NodeIt v;
       switch (status) {
-        case AFTER_PRE_FLOW_PHASE_1:
+      case AFTER_PRE_FLOW_PHASE_1:
         for(g->first(v); g->valid(v); g->next(v)) {
           if (level[v] < n) {
@@ -275 +276 @@
         }
         break;
-        case AFTER_PRE_FLOW_PHASE_2:
-        case AFTER_NOTHING:
+      case AFTER_PRE_FLOW_PHASE_2:
+      case AFTER_NOTHING:
         minMinCut(M);
         break;
-        case AFTER_AUGMENTING:
+      case AFTER_AUGMENTING:
         for(g->first(v); g->valid(v); g->next(v)) {
           if (level[v]) {
+            M.set(v, true);
+          } else {
+            M.set(v, false);
+          }
+        }
+        break;
+      case AFTER_FAST_AUGMENTING:
+        for(g->first(v); g->valid(v); g->next(v)) {
+          if (level[v]==number_of_augmentations) {
             M.set(v, true);
           } else {
@@ -945 +955 @@
     bool _augment=false;
 
-    if (status!=AFTER_AUGMENTING) {
-      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 3*n); 
-      number_of_augmentations=3*n+1;
+    if (status!=AFTER_FAST_AUGMENTING) {
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0); 
+      number_of_augmentations=1;
     } else {
       ++number_of_augmentations;
@@ -992 +1002 @@
     }
 
-    status=AFTER_AUGMENTING;
+    status=AFTER_FAST_AUGMENTING;
     return _augment;
   }