Changeset 109:fc5982b39e10 in lemon-0.x for src/work/jacint/preflow_hl2.h

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

File:

• src/work/jacint/preflow_hl2.h (modified) (19 diffs)

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