Changeset 83:efafe79a88d3 in lemon-0.x for src/work/jacint/preflow_push_max_flow.h

Timestamp:

02/17/04 09:59:49 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

debuggolt valtozatok

File:

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

src/work/jacint/preflow_push_max_flow.h

@@ -3 +3 @@
 by jacint. 
 Runs a preflow push algorithm with the modification, 
-that we do not push on Nodes with level at least n. 
-Moreover, if a level gets empty, we.set all Nodes above that
+that we do not push on nodes with level at least n. 
+Moreover, if a level gets empty, we set all nodes above that
 level to level n. Hence, in the end, we arrive at a maximum preflow 
 with value of a max flow value. An empty level gives a minimum cut.
@@ -16 +16 @@
 T maxflow() : returns the value of a maximum flow
 
-NodeMap<Graph, bool> mincut(): returns a 
+NodeMap<bool> mincut(): returns a 
      characteristic vector of a minimum cut.
 */
@@ -52 +52 @@
   public:
         
-    preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
+    preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t, 
+                            typename Graph::EdgeMap<T>& _capacity) : 
+      G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
 
 
     /*
-      The run() function runs a modified version of the highest label preflow-push, which only 
+      The run() function runs a modified version of the 
+      highest label preflow-push, which only 
       finds a maximum preflow, hence giving the value of a maximum flow.
     */
     void run() {
  
-      typename Graph::EdgeMap<T> flow(G, 0);         //the flow value, 0 everywhere  
-      typename Graph::NodeMap<int> level(G);         //level of Node
-      typename Graph::NodeMap<T> excess(G);          //excess of Node
+      typename Graph::EdgeMap<T> flow(G, 0); 
+      typename Graph::NodeMap<int> level(G);   
+      typename Graph::NodeMap<T> excess(G);    
             
-      int n=G.nodeNum();                        //number of Nodes 
+      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.*/
-      
-      std::vector<int> numb(n);                                //The number of Nodes on level i < n.
-
-      std::vector<std::stack<NodeIt> > stack(2*n-1);    //Stack of the active Nodes in level i.
-
-
+      /*
+        b is a bound on the highest level of an active Node. 
+        In the beginning it is at most n-2.
+      */
+      
+      std::vector<int> numb(n);     //The number of Nodes on level i < n.
+      std::vector<std::stack<NodeIt> > stack(2*n-1);    
+      //Stack of the active Nodes in level i.
 
       /*Reverse_bfs from t, to find the starting level.*/
-
       reverse_bfs<Graph> bfs(G, t);
       bfs.run();
@@ -86 +89 @@
         }
 
-      /*The level of s is fixed to n*/ 
       level.set(s,n);
 
-
       /* Starting flow. It is everywhere 0 at the moment. */
-     
-      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 
+      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
         {
-          NodeIt w=G.head(i);
-          flow.set(i, capacity.get(i)); 
-          stack[bfs.dist(w)].push(w); 
-          excess.set(w, capacity.get(i));
+          if ( capacity.get(e) > 0 ) {
+            NodeIt w=G.head(e);
+            flow.set(e, capacity.get(e)); 
+            stack[level.get(w)].push(w); 
+            excess.set(w, excess.get(w)+capacity.get(e));
+          }
         }
-
 
       /* 
          End of preprocessing 
       */
-
 
 
@@ -115 +115 @@
       while (b) { 
 
-        /*We decrease the bound if there is no active Node of level b.*/
+        /*We decrease the bound if there is no active node of level b.*/
         if (stack[b].empty()) {
           --b;