Changeset 749:8e933219691e in lemon-0.x for src/hugo/max_flow.h

Timestamp:

07/30/04 12:24:05 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

bug fixing

File:

• src/hugo/max_flow.h (modified) (17 diffs)

src/hugo/max_flow.h

@@ -1 +1 @@
 // -*- C++ -*-
-#ifndef HUGO_MAX_FLOW_NO_STACK_H
-#define HUGO_MAX_FLOW_NO_STACK_H
+#ifndef HUGO_MAX_FLOW_H
+#define HUGO_MAX_FLOW_H
 
 #include <vector>
 #include <queue>
-//#include <stack>
 
 #include <hugo/graph_wrapper.h>
@@ -12 +11 @@
 
 /// \file
-/// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test.
 /// \ingroup galgs
 
@@ -52 +50 @@
     typedef typename Graph::InEdgeIt InEdgeIt;
 
-    //    typedef typename std::vector<std::stack<Node> > VecStack;
     typedef typename std::vector<Node> VecFirst;
     typedef typename Graph::template NodeMap<Node> NNMap;
@@ -67 +64 @@
     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     typedef typename ResGW::Edge ResGWEdge;
-    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
     typedef typename Graph::template NodeMap<int> ReachedMap;
 
@@ -111 +107 @@
     };
 
-    /// Don not needle this flag only if necessary.
+    /// Do not needle this flag only if necessary.
     StatusEnum status;
 
@@ -189 +185 @@
     ///first phase. After the first phase the maximum flow value and a
     ///minimum value cut can already be computed, though a maximum flow
-    ///is net yet obtained. So after calling this method \ref flowValue
+    ///is not yet obtained. So after calling this method \ref flowValue
     ///and \ref actMinCut gives proper results.
     ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
@@ -224 +220 @@
       //List of the nodes in level i<n, set to n.
 
-      NodeIt v;
-      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
-      //setting each node to level n
-
-      if ( fe == NO_FLOW ) {
-        EdgeIt e;
-        for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
-      }
-
-      switch (fe) { //computing the excess
-      case PRE_FLOW:
-        {
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) {
-            Num exc=0;
-
-            InEdgeIt e;
-            for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
-            OutEdgeIt f;
-            for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
-
-            excess.set(v,exc);
-
-            //putting the active nodes into the stack
-            int lev=level[v];
-            if ( exc > 0 && lev < n && v != t ) 
-              {
-                next.set(v,first[lev]);
-                first[lev]=v;
-              }
-          }
-          break;
-        }
-      case GEN_FLOW:
-        {
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
-
-          Num exc=0;
-          InEdgeIt e;
-          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
-          OutEdgeIt f;
-          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
-          excess.set(t,exc);
-          break;
-        }
-      case ZERO_FLOW:
-      case NO_FLOW:
-        {
-          NodeIt v;
-          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
-          break;
-        }
-      }
-
       preflowPreproc(fe, next, first, level_list, left, right);
       //End of preprocessing
-
 
       //Push/relabel on the highest level active nodes.
@@ -395 +335 @@
             b=newlevel;
           }
-        }  // if stack[b] is nonempty
+        } 
       } // while(true)
 
@@ -414 +354 @@
       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan   
     }
-    Num flowValue2() const {
-      return excess[t];
-//       Num a=0;
-//       for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
-//       for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
-//       return a;
-//       //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan  
-      
-    }
+
 
     ///Returns a minimum value cut after calling \ref preflowPhase1.
@@ -653 +585 @@
 
 
+
     void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
                         VecNode& level_list, NNMap& left, NNMap& right)
     {
+      switch (fe) { //setting excess
+        case NO_FLOW: 
+        {
+          EdgeIt e;
+          for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
+          
+          NodeIt v;
+          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+          break;
+        }
+        case ZERO_FLOW: 
+        {
+          NodeIt v;
+          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+          break;
+        }
+        case GEN_FLOW:
+        {
+          NodeIt v;
+          for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
+
+          Num exc=0;
+          InEdgeIt e;
+          for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
+          OutEdgeIt f;
+          for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
+          excess.set(t,exc);
+          break;
+        }
+        default: break;
+      }
+
+      NodeIt v;
+      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
+      //setting each node to level n
+      
       std::queue<Node> bfs_queue;
 
+
       switch (fe) {
-      case NO_FLOW:   //flow is already set to const zero in this case
+      case NO_FLOW:   //flow is already set to const zero
       case ZERO_FLOW:
         {
@@ -694 +664 @@
               Node w=g->head(e);
               if ( level[w] < n ) {
-                if ( excess[w] <= 0 && w!=t ) 
-                  {
+                if ( excess[w] <= 0 && w!=t ) //putting into the stack
+                  { 
                     next.set(w,first[level[w]]);
                     first[level[w]]=w;
@@ -707 +677 @@
 
       case GEN_FLOW:
-      case PRE_FLOW:
         {
           //Reverse_bfs from t in the residual graph,
@@ -749 +718 @@
           }
 
-
           //the starting flow
           OutEdgeIt e;
@@ -758 +726 @@
               Node w=g->head(e);
               if ( level[w] < n ) {
-                if ( excess[w] <= 0 && w!=t )
+                if ( excess[w] <= 0 && w!=t ) //putting into the stack
                   {
                     next.set(w,first[level[w]]);
@@ -778 +746 @@
                     next.set(w,first[level[w]]);
                     first[level[w]]=w;
-                  }   
+                  }  
                 excess.set(w, excess[w]+(*flow)[f]);
                 flow->set(f, 0);
@@ -784 +752 @@
             }
           break;
+        } //case GEN_FLOW
+    
+      case PRE_FLOW:
+        {
+          //Reverse_bfs from t in the residual graph,
+          //to find the starting level.
+          level.set(t,0);
+          bfs_queue.push(t);
+
+          while (!bfs_queue.empty()) {
+
+            Node v=bfs_queue.front();
+            bfs_queue.pop();
+            int l=level[v]+1;
+
+            InEdgeIt e;
+            for(g->first(e,v); g->valid(e); g->next(e)) {
+              if ( (*capacity)[e] <= (*flow)[e] ) continue;
+              Node w=g->tail(e);
+              if ( level[w] == n && w != s ) {
+                bfs_queue.push(w);
+                Node z=level_list[l];
+                if ( g->valid(z) ) left.set(z,w);
+                right.set(w,z);
+                level_list[l]=w;
+                level.set(w, l);
+              }
+            }
+
+            OutEdgeIt f;
+            for(g->first(f,v); g->valid(f); g->next(f)) {
+              if ( 0 >= (*flow)[f] ) continue;
+              Node w=g->head(f);
+              if ( level[w] == n && w != s ) {
+                bfs_queue.push(w);
+                Node z=level_list[l];
+                if ( g->valid(z) ) left.set(z,w);
+                right.set(w,z);
+                level_list[l]=w;
+                level.set(w, l);
+              }
+            }
+          }
+
+
+          //the starting flow
+          OutEdgeIt e;
+          for(g->first(e,s); g->valid(e); g->next(e))
+            {
+              Num rem=(*capacity)[e]-(*flow)[e];
+              if ( rem <= 0 ) continue;
+              Node w=g->head(e);
+              if ( level[w] < n ) {
+                flow->set(e, (*capacity)[e]);
+                excess.set(w, excess[w]+rem);
+              }
+            }
+
+          InEdgeIt f;
+          for(g->first(f,s); g->valid(f); g->next(f))
+            {
+              if ( (*flow)[f] <= 0 ) continue;
+              Node w=g->tail(f);
+              if ( level[w] < n ) {
+                excess.set(w, excess[w]+(*flow)[f]);
+                flow->set(f, 0);
+              }
+            }
+          
+          NodeIt w; //computing the excess
+          for(g->first(w); g->valid(w); g->next(w)) {
+            Num exc=0;
+
+            InEdgeIt e;
+            for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
+            OutEdgeIt f;
+            for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
+
+            excess.set(w,exc);
+
+            //putting the active nodes into the stack
+            int lev=level[w];
+            if ( exc > 0 && lev < n && w != t ) 
+              {
+                next.set(w,first[lev]);
+                first[lev]=w;
+              }
+          }
+          break;
         } //case PRE_FLOW
       }
     } //preflowPreproc
-
 
 
@@ -853 +909 @@
       }
     } //relabel
+
+    void printexcess() {////
+      std::cout << "Excesses:" <<std::endl;
+
+      NodeIt v;
+      for(g->first(v); g->valid(v); g->next(v)) {
+        std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl; 
+      }
+    }
+
+ void printlevel() {////
+      std::cout << "Levels:" <<std::endl;
+
+      NodeIt v;
+      for(g->first(v); g->valid(v); g->next(v)) {
+        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 
+      }
+    }
+
+void printactive() {////
+      std::cout << "Levels:" <<std::endl;
+
+      NodeIt v;
+      for(g->first(v); g->valid(v); g->next(v)) {
+        std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl; 
+      }
+    }
+
+
   };  //class MaxFlow
 } //namespace hugo