Changeset 109:fc5982b39e10 in lemon-0.x

Timestamp:

02/21/04 22:01:22 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

Flows with test files. The best is preflow.h

Location:

src/work/jacint

Files:

• preflow.cc (added)
• preflow.h (added)
• preflow_hl0.cc (added)
• preflow_hl0.h (added)
• preflow_hl1.cc (added)
• preflow_hl2.cc (added)
• preflow_hl2.h (modified) (19 diffs)
• preflow_hl3.cc (added)
• preflow_hl3.h (modified) (16 diffs)
• preflow_hl4.cc (added)
• preflow_hl4.h (modified) (24 diffs)
• preflow_max_flow.cc (added)
• preflow_max_flow.h (added)
• preflow_param.cc (added)
• preflow_param.h (added)
• preflow_push_hl.h (deleted)
• preflow_push_hl.hh (deleted)
• preflow_push_max_flow.h (deleted)
• preflow_push_max_flow.hh (deleted)

src/work/jacint/preflow_hl2.h

@@ -4 +4 @@
 by jacint. 
 Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), with the 'empty level' and with the 
-heuristic that the bound b on the active nodes is not increased 
-only when b=0, when we put b=2*n-2.
-
-'A' is a parameter for the empty_level heuristic
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap allflow() : returns the fixed maximum flow x
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
+running time O(n^2\sqrt(m)). 
+
+Heuristics:
+
+  gap: we iterate through the nodes for finding the nodes above 
+       the gap and under level n. So it is quite slow.
+  numb: we maintain the number of nodes in level i.
+  highest label
+  
+'A' is a parameter for the gap, we only upgrade the nodes to level n,
+  if the gap is under A*n.
+
+The constructor runs the algorithm.
+
+Members:
+
+T maxFlow() : returns the value of a maximum flow
+
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+
+FlowMap Flow() : returns the fixed maximum flow x
+
+void minCut(CutMap& M) : sets M to the characteristic vector of a 
      minimum cut. M should be a map of bools initialized to false.
 
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
      minimum min cut. M should be a map of bools initialized to false.
 
-void max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
      maximum min cut. M should be a map of bools initialized to false.
 
@@ -36 +40 @@
 #define PREFLOW_HL2_H
 
-#define A 1
+#define A .9
 
 #include <vector>
@@ -45 +49 @@
 
   template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl2 {
     
@@ -65 +69 @@
 
     preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    void run() {
- 
-      bool no_end=true;
+      G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 
+
       int n=G.nodeNum(); 
       int b=n-2; 
       /*
         b is a bound on the highest level of an active node. 
-        In the beginning it is at most n-2.
       */
 
-      IntMap level(G,n);      
-      TMap excess(G); 
-      
+      typename Graph::NodeMap<int> level(G,n);      
+      typename Graph::NodeMap<T> excess(G); 
+
       std::vector<int> numb(n);    
       /*
@@ -111 +110 @@
         }
       }
-      
+        
       level.set(s,n);
 
@@ -128 +127 @@
           }
         }
-
+      
       /* 
          End of preprocessing 
@@ -134 +133 @@
 
 
-
       /*
         Push/relabel on the highest level active nodes.
-      */        
+      */
       /*While there exists an active node.*/
       while (b) { 
-        if ( stack[b].empty() ) {
-          if ( b==1 ) {
-            if ( !no_end ) break; 
-            else {
-              b=2*n-2;
-              no_end=false;
-            }
-          } 
+        if ( stack[b].empty() ) { 
           --b;
-        } else {
-          
-          no_end=true;
-          
-          NodeIt w=stack[b].top();        //w is a highest label active node.
-          stack[b].pop();           
-          int lev=level.get(w);
-          int exc=excess.get(w);
-          int newlevel=2*n;      //In newlevel we bound the next level of w.
-          
-          //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
+          continue;
+        } 
+        
+        NodeIt w=stack[b].top();   
+        stack[b].pop();           
+        int lev=level.get(w);
+        T exc=excess.get(w);
+        int newlevel=2*n;      //In newlevel we bound the next level of w.
+        
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
             
@@ -173 +162 @@
               /*v becomes active.*/
               
-              int cap=capacity.get(e);
-              int flo=flow.get(e);
-              int remcap=cap-flo;
+              T cap=capacity.get(e);
+              T flo=flow.get(e);
+              T remcap=cap-flo;
               
               if ( remcap >= exc ) {       
@@ -211 +200 @@
               /*v becomes active.*/
               
-              int flo=flow.get(e);
+              T flo=flow.get(e);
               
               if ( flo >= exc ) { 
@@ -232 +221 @@
           
         } // if w still has excess after the out edge for cycle
-         
-          excess.set(w, exc);
+        
+        excess.set(w, exc);
+        
+
+        
+
+        /*
+          Relabel
+        */
+        
+        if ( exc > 0 ) {
+          //now 'lev' is the old level of w
+          level.set(w,++newlevel);
           
-
-          /*
-            Relabel
-          */
+          if ( lev < n ) {
+            --numb[lev];
+            
+            if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
+              
+              for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
+                if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);  
+              }
+              for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
+              if ( newlevel < n ) newlevel=n; 
+            } else { 
+              if ( newlevel < n ) ++numb[newlevel]; 
+            }
+          } 
           
-          if ( exc > 0 ) {
-            //now 'lev' is the old level of w
-            level.set(w,++newlevel);
-            
-            if ( lev < n ) {
-              --numb[lev];
-
-              if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
-                
-                for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
-                  if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);  
-                }
-                for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
-                if ( newlevel < n ) newlevel=n; 
-              } else { 
-                if ( newlevel < n ) ++numb[newlevel]; 
-              }
-            } 
-            
-            stack[newlevel].push(w);
-
-          }
-
-        } // if stack[b] is nonempty
-
+          stack[newlevel].push(w);
+          b=newlevel;
+          
+        }
+        
       } // while(b)
-
-
+      
+      
       value = excess.get(t);
       /*Max flow value.*/
@@ -282 +272 @@
      */
 
-    T maxflow() {
+    T maxFlow() {
       return value;
     }
@@ -289 +279 @@
 
     /*
-      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 
+      For the maximum flow x found by the algorithm, 
+      it returns the flow value on edge e, i.e. x(e). 
     */
 
-    T flowonedge(EdgeIt e) {
+    T flowOnEdge(const EdgeIt e) {
       return flow.get(e);
     }
@@ -302 +293 @@
     */
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
@@ -314 +305 @@
     
     template<typename CutMap>
-    void mincut(CutMap& M) {
+    void minCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -324 +315 @@
         NodeIt w=queue.front();
         queue.pop();
-
+        
         for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
           NodeIt v=G.head(e);
@@ -339 +330 @@
             M.set(v, true);
           }
-        } 
+        }
 
       }
-
     }
 
@@ -353 +343 @@
     
     template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    void maxMinCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -390 +380 @@
 
     template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    void minMinCut(CutMap& M) {
+      minCut(M);
     }
 
@@ -397 +387 @@
 
   };
-}//namespace hugo
+}//namespace marci
 #endif 
 

src/work/jacint/preflow_hl3.h

@@ -3 +3 @@
 preflow_hl3.h
 by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), with the felszippantos 'empty level' 
-and with the two-phase heuristic: if there is no active node of
-level at most n, then we go into phase 1, do a bfs
-from s, and flow the excess back to s.
-
-In phase 1 we shift everything downwards by n.
-
-'A' is a parameter for the empty_level heuristic
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap allflow() : returns the fixed maximum flow x
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
+
+Heuristics: 
+
+ suck gap : if there is a gap, then we put all 
+   nodes reachable from the relabelled node to level n
+ 2 phase
+ highest label
+
+The constructor runs the algorithm.
+
+Members:
+
+T maxFlow() : returns the value of a maximum flow
+
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+
+FlowMap Flow() : returns the fixed maximum flow x
+
+void minCut(CutMap& M) : sets M to the characteristic vector of a 
      minimum cut. M should be a map of bools initialized to false.
 
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
      minimum min cut. M should be a map of bools initialized to false.
 
-void max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
      maximum min cut. M should be a map of bools initialized to false.
 
@@ -38 +34 @@
 #ifndef PREFLOW_HL3_H
 #define PREFLOW_HL3_H
-
-#define A 1
 
 #include <vector>
@@ -45 +39 @@
 #include <queue>
 
+#include <time_measure.h> //for test
+
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl3 {
     
@@ -67 +63 @@
   public:
 
+    double time; //for test
+
     preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    void run() {
- 
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
+      
       bool phase=0;
       int n=G.nodeNum(); 
@@ -81 +76 @@
       */
 
-      IntMap level(G,n);      
-      TMap excess(G); 
+      typename Graph::NodeMap<int> level(G,n);      
+      typename Graph::NodeMap<T> excess(G); 
       
       std::vector<int> numb(n);    
@@ -149 +144 @@
           if ( phase ) break; 
           phase=1;
-
+          time=currTime();
+          
           level.set(s,0);
 
@@ -188 +184 @@
         else {
           
-          NodeIt w=stack[b].top();        //w is a highest label active node.
+          NodeIt w=stack[b].top(); 
           stack[b].pop();           
           int lev=level.get(w);
-          int exc=excess.get(w);
-          int newlevel=n;                 //In newlevel we bound the next level of w.
+          T exc=excess.get(w);
+          int newlevel=n;          //bound on the next level of w.
           
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
@@ -207 +203 @@
               /*v becomes active.*/
               
-              int cap=capacity.get(e);
-              int flo=flow.get(e);
-              int remcap=cap-flo;
+              T cap=capacity.get(e);
+              T flo=flow.get(e);
+              T remcap=cap-flo;
               
               if ( remcap >= exc ) {       
@@ -245 +241 @@
               /*v becomes active.*/
               
-              int flo=flow.get(e);
+              T flo=flow.get(e);
               
               if ( flo >= exc ) { 
@@ -350 +346 @@
      */
 
-    T maxflow() {
+    T maxFlow() {
       return value;
     }
@@ -357 +353 @@
 
     /*
-      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 
+      For the maximum flow x found by the algorithm, 
+      it returns the flow value on edge e, i.e. x(e). 
     */
 
-    T flowonedge(EdgeIt e) {
+    T flowOnEdge(EdgeIt e) {
       return flow.get(e);
     }
@@ -370 +367 @@
     */
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
@@ -382 +379 @@
     
     template<typename CutMap>
-    void mincut(CutMap& M) {
+    void minCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -421 +418 @@
     
     template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    void maxMinCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -458 +455 @@
 
     template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    void minMinCut(CutMap& M) {
+      minCut(M);
     }
 
@@ -465 +462 @@
 
   };
-}//namespace hugo
+}//namespace
 #endif 
 

src/work/jacint/preflow_hl4.h

@@ -1 +1 @@
 // -*- C++ -*-
 /*
-preflow_hl4.h
+preflow_h5.h
 by jacint. 
-Runs the two phase highest label preflow push algorithm. In phase 0
-we maintain in a list the nodes in level i < n, and we maintain a 
-bound k on the max level i < n containing a node, so we can do
-the gap heuristic fast. Phase 1 is the same. (The algorithm is the 
-same as preflow.hl3, the only diff is that here we use the gap
-heuristic with the list of the nodes on level i, and not a bfs form the
-upgraded node.)
-
-In phase 1 we shift everything downwards by n.
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap allflow() : returns a maximum flow
-
-void allflow(FlowMap& _flow ) : returns a maximum flow
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+Heuristics: 
+ 2 phase
+ gap
+ list 'level_list' on the nodes on level i implemented by hand
+ highest label
+ relevel: in phase 0, after BFS*n relabels, it runs a reverse 
+   bfs from t in the res graph to relevel the nodes reachable from t.
+   BFS is initialized to 20
+
+Due to the last heuristic, this algorithm is quite fast on very 
+sparse graphs, but relatively bad on even the dense graphs.
+
+'NodeMap<bool> cut' is a member, in this way we can count it fast, after
+the algorithm was run.
+
+The constructor runs the algorithm.
+
+Members:
+
+T maxFlow() : returns the value of a maximum flow
+
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+
+FlowMap Flow() : returns the fixed maximum flow x
+
+void Flow(FlowMap& _flow ) : returns the fixed maximum flow x
+
+void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
      minimum min cut. M should be a map of bools initialized to false.
 
-void max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
      maximum min cut. M should be a map of bools initialized to false.
+
+void minCut(CutMap& M) : fast function, sets M to the characteristic 
+     vector of a minimum cut. 
+
+Different member from the other preflow_hl-s (here we have a member 
+'NodeMap<bool> cut').
+
+CutMap minCut() : fast function, giving the characteristic 
+     vector of a minimum cut.
+
 
 */
@@ -41 +51 @@
 #define PREFLOW_HL4_H
 
+#define BFS 20
+
 #include <vector>
-#include <stack>
 #include <queue>
+
+#include <time_measure.h>  //for test
 
 namespace hugo {
@@ -49 +62 @@
   template <typename Graph, typename T, 
     typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CutMap=typename Graph::NodeMap<bool>,
     typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl4 {
@@ -63 +77 @@
     FlowMap flow;
     CapMap& capacity;  
+    CutMap cut;
     T value;
     
   public:
 
+    double time;
+
     preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    void run() {
- 
-      bool phase=0;
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
+      cut(G, false) {
+
+      bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd
       int n=G.nodeNum(); 
+      int relabel=0;
+      int heur=(int)BFS*n;
       int k=n-2;
       int b=k;
@@ -84 +101 @@
       typename Graph::NodeMap<int> level(G,n);      
       typename Graph::NodeMap<T> excess(G); 
-      std::vector<std::stack<NodeIt> > stack(n);    
+      
+      std::vector<NodeIt> active(n);
+      typename Graph::NodeMap<NodeIt> next(G);
       //Stack of the active nodes in level i < n.
       //We use it in both phases.
@@ -108 +127 @@
         for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
           NodeIt w=G.tail(e);
-          if ( level.get(w) == n ) {
+          if ( level.get(w) == n && w !=s ) {
             bfs_queue.push(w);
             NodeIt first=level_list[l];
@@ -129 +148 @@
           NodeIt w=G.head(e);
           if ( level.get(w) < n ) {       
-            if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 
+            if ( excess.get(w) == 0 && w!=t ) {
+              next.set(w,active[level.get(w)]);
+              active[level.get(w)]=w;
+            }
             flow.set(e, c); 
             excess.set(w, excess.get(w)+c);
@@ -152 +174 @@
           */
           phase=1;
+          
+          //Now have a min cut.
+          for( EachNodeIt v=G.template first<EachNodeIt>(); 
+               v.valid(); ++v) 
+            if (level.get(v) >= n ) cut.set(v,true);
+          
+          time=currTime();
           level.set(s,0);
           std::queue<NodeIt> bfs_queue;
@@ -168 +197 @@
                 bfs_queue.push(u);
                 level.set(u, l);
-                if ( excess.get(u) > 0 ) stack[l].push(u);
+                if ( excess.get(u) > 0 ) {
+                    next.set(u,active[l]);
+                    active[l]=u;
+                }
               }
             }
@@ -178 +210 @@
                 bfs_queue.push(u);
                 level.set(u, l);
-                if ( excess.get(u) > 0 ) stack[l].push(u);
+                if ( excess.get(u) > 0 ) {
+                    next.set(u,active[l]);
+                    active[l]=u;
+                }
               }
             }
@@ -186 +221 @@
 
 
-        if ( stack[b].empty() ) --b;
+        if ( active[b] == 0 ) --b;
         else {
           
-          NodeIt w=stack[b].top();        //w is a highest label active node.
-          stack[b].pop();           
+          NodeIt w=active[b];
+          active[b]=next.get(w);
           int lev=level.get(w);
           T exc=excess.get(w);
-          int newlevel=n;          //In newlevel we bound the next level of w.
+          int newlevel=n;          //bound on the next level of w.
           
           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
@@ -204 +239 @@
               /*Push is allowed now*/
               
-              if ( excess.get(v)==0 && v!=t && v!=s ) 
-                stack[level.get(v)].push(v); 
-              /*v becomes active.*/
+              if ( excess.get(v)==0 && v!=t && v!=s )  {
+                int lev_v=level.get(v);
+                next.set(v,active[lev_v]);
+                active[lev_v]=v;
+              }
               
               T cap=capacity.get(e);
@@ -244 +281 @@
               /*Push is allowed now*/
               
-              if ( excess.get(v)==0 && v!=t && v!=s ) 
-                stack[level.get(v)].push(v); 
-              /*v becomes active.*/
+              if ( excess.get(v)==0 && v!=t && v!=s ) {
+                int lev_v=level.get(v);
+                next.set(v,active[lev_v]);
+                active[lev_v]=v;
+              }
               
               T flo=flow.get(e);
@@ -282 +321 @@
           if ( phase ) {
             level.set(w,++newlevel);
-            stack[newlevel].push(w);
+            next.set(w,active[newlevel]);
+            active[newlevel]=w;
             b=newlevel;
           } else {
@@ -304 +344 @@
               } 
             }
+            //unlacing ends
                 
 
@@ -329 +370 @@
                 
                 level.set(w,++newlevel);
-                stack[newlevel].push(w);
+                next.set(w,active[newlevel]);
+                active[newlevel]=w;
                 b=newlevel;
                 if ( k < newlevel ) ++k;
@@ -339 +381 @@
               }
             }
+
+            ++relabel;
+            if ( relabel >= heur ) {
+              relabel=0;
+              b=n-2;
+              k=b;
+                
+              for ( int i=1; i!=n; ++i ) { 
+                active[i]=0;
+                level_list[i]=0;
+              }
+
+              //bfs from t in the res graph to relevel the nodes
+              for( EachNodeIt v=G.template first<EachNodeIt>(); 
+                   v.valid(); ++v) level.set(v,n);
+
+              level.set(t,0);
+              std::queue<NodeIt> bfs_queue;
+              bfs_queue.push(t);
+              
+              while (!bfs_queue.empty()) {
+                
+                NodeIt v=bfs_queue.front();     
+                bfs_queue.pop();
+                int l=level.get(v)+1;
+                
+                for(InEdgeIt e=G.template first<InEdgeIt>(v); 
+                    e.valid(); ++e) {
+                  if ( capacity.get(e) == flow.get(e) ) continue;
+                  NodeIt u=G.tail(e);
+                  if ( level.get(u) == n ) { 
+                    bfs_queue.push(u);
+                    level.set(u, l);
+                    if ( excess.get(u) > 0 ) {
+                      next.set(u,active[l]);
+                      active[l]=u;
+                    }
+                    NodeIt first=level_list[l];
+                    if ( first != 0 ) left.set(first,w);
+                    right.set(w,first);
+                    left.set(w,0);
+                    level_list[l]=w;
+                  }
+                }
+                
+                
+                for(OutEdgeIt e=G.template first<OutEdgeIt>(v); 
+                    e.valid(); ++e) {
+                  if ( 0 == flow.get(e) ) continue;
+                  NodeIt u=G.head(e);
+                  if ( level.get(u) == n ) { 
+                    bfs_queue.push(u);
+                    level.set(u, l);
+                    if ( excess.get(u) > 0 ) {
+                      next.set(u,active[l]);
+                      active[l]=u;
+                    }
+                    NodeIt first=level_list[l];
+                    if ( first != 0 ) left.set(first,w);
+                    right.set(w,first);
+                    left.set(w,0);
+                    level_list[l]=w;
+                  }
+                }
+              }
+              
+              level.set(s,n);
+            }
+          
           } //phase 0
         } // if ( exc > 0 )
- 
+        
         
         } // if stack[b] is nonempty
@@ -362 +473 @@
      */
 
-    T maxflow() {
+    T maxFlow() {
       return value;
     }
@@ -372 +483 @@
     */
 
-    T flowonedge(EdgeIt e) {
+    T flowOnEdge(EdgeIt e) {
       return flow.get(e);
     }
@@ -378 +489 @@
 
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
@@ -384 +495 @@
 
     
-    void allflow(FlowMap& _flow ) {
+    void Flow(FlowMap& _flow ) {
       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
         _flow.set(v,flow.get(v));
@@ -395 +506 @@
     */
     
-    template<typename CutMap>
-    void mincut(CutMap& M) {
+    template<typename _CutMap>
+    void minMinCut(_CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -434 +545 @@
     */
     
-    template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    template<typename _CutMap>
+    void maxMinCut(_CutMap& M) {
     
       std::queue<NodeIt> queue;
@@ -470 +581 @@
 
 
-
-    template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
-    }
-
+    template<typename _CutMap>
+    void minCut(_CutMap& M) {
+      for( EachNodeIt v=G.template first<EachNodeIt>(); 
+           v.valid(); ++v) 
+        M.set(v, cut.get(v));
+    }
+
+   
+    CutMap minCut() {
+      return cut;
+    }
 
 
   };
-}//namespace hugo
+}//namespace marci
 #endif