Changeset 211:9222a9b8b323 in lemon-0.x for src/work/jacint/preflow.h

Timestamp:

03/19/04 23:16:05 (21 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

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

Message:

updating

File:

• src/work/jacint/preflow.h (modified) (28 diffs)

src/work/jacint/preflow.h

@@ -1 +1 @@
 // -*- C++ -*-
 /*
-preflow.h
-by jacint. 
 Heuristics: 
  2 phase
@@ -13 +11 @@
 Parameters H0 and H1 are initialized to 20 and 10.
 
-The best preflow I could ever write.
-
-The constructor runs the algorithm.
+Constructors:
+
+Preflow(Graph, Node, Node, CapMap, FlowMap)
 
 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 run()
+
+T flowValue() : returns the value of a maximum flow
 
 void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
@@ -36 +32 @@
 */
 
-#ifndef PREFLOW_H
-#define PREFLOW_H
+#ifndef HUGO_PREFLOW_H
+#define HUGO_PREFLOW_H
 
 #define H0 20
@@ -44 +40 @@
 #include <vector>
 #include <queue>
-
-#include <time_measure.h>
 
 namespace hugo {
@@ -52 +46 @@
     typename FlowMap=typename Graph::EdgeMap<T>,
     typename CapMap=typename Graph::EdgeMap<T> >
-  class preflow {
+  class Preflow {
     
+    typedef typename Graph::Node Node;
+    typedef typename Graph::Edge Edge;
     typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::InEdgeIt InEdgeIt;
     
-    Graph& G;
-    NodeIt s;
-    NodeIt t;
-    FlowMap flow;
-    CapMap& capacity;  
+    const Graph& G;
+    Node s;
+    Node t;
+    FlowMap& flow;
+    const CapMap& capacity;  
     T value;
 
   public:
-    double time;
-    preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
-    {
+    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) :
+      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
+
+
+    void run() {
 
       bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
@@ -95 +90 @@
       typename Graph::NodeMap<T> excess(G); 
 
-      std::vector<NodeIt> active(n);
-      typename Graph::NodeMap<NodeIt> next(G);
+      std::vector<Node> active(n,INVALID);
+      typename Graph::NodeMap<Node> next(G,INVALID);
       //Stack of the active nodes in level i < n.
       //We use it in both phases.
 
-      typename Graph::NodeMap<NodeIt> left(G);
-      typename Graph::NodeMap<NodeIt> right(G);
-      std::vector<NodeIt> level_list(n);
+      typename Graph::NodeMap<Node> left(G,INVALID);
+      typename Graph::NodeMap<Node> right(G,INVALID);
+      std::vector<Node> level_list(n,INVALID);
       /*
         List of the nodes in level i<n.
@@ -109 +104 @@
       /*Reverse_bfs from t, to find the starting level.*/
       level.set(t,0);
-      std::queue<NodeIt> bfs_queue;
+      std::queue<Node> bfs_queue;
       bfs_queue.push(t);
 
       while (!bfs_queue.empty()) {
 
-        NodeIt v=bfs_queue.front();     
+        Node v=bfs_queue.front();       
         bfs_queue.pop();
-        int l=level.get(v)+1;
-
-        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-          NodeIt w=G.tail(e);
-          if ( level.get(w) == n && w != s ) {
+        int l=level[v]+1;
+
+        InEdgeIt e;
+        for(G.first(e,v); G.valid(e); G.next(e)) {
+          Node w=G.tail(e);
+          if ( level[w] == n && w != s ) {
             bfs_queue.push(w);
-            NodeIt first=level_list[l];
-            if ( first != 0 ) left.set(first,w);
+            Node first=level_list[l];
+            if ( G.valid(first) ) left.set(first,w);
             right.set(w,first);
             level_list[l]=w;
@@ -135 +131 @@
 
       /* Starting flow. It is everywhere 0 at the moment. */     
-      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
+      OutEdgeIt e;
+      for(G.first(e,s); G.valid(e); G.next(e)) 
         {
-          T c=capacity.get(e);
+          T c=capacity[e];
           if ( c == 0 ) continue;
-          NodeIt w=G.head(e);
-          if ( level.get(w) < n ) {       
-            if ( excess.get(w) == 0 && w!=t ) {
-              next.set(w,active[level.get(w)]);
-              active[level.get(w)]=w;
+          Node w=G.head(e);
+          if ( level[w] < n ) {   
+            if ( excess[w] == 0 && w!=t ) {
+              next.set(w,active[level[w]]);
+              active[level[w]]=w;
             }
             flow.set(e, c); 
-            excess.set(w, excess.get(w)+c);
+            excess.set(w, excess[w]+c);
           }
         }
@@ -169 +166 @@
           } else {
             phase=1;
-            time=currTime();
             level.set(s,0);
-            std::queue<NodeIt> bfs_queue;
+            std::queue<Node> bfs_queue;
             bfs_queue.push(s);
             
             while (!bfs_queue.empty()) {
               
-              NodeIt v=bfs_queue.front();       
+              Node 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 ) { 
+              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 u=G.tail(e);
+                if ( level[u] >= n ) { 
                   bfs_queue.push(u);
                   level.set(u, l);
-                  if ( excess.get(u) > 0 ) {
+                  if ( excess[u] > 0 ) {
                     next.set(u,active[l]);
                     active[l]=u;
@@ -193 +190 @@
               }
             
-              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 ) { 
+              OutEdgeIt f;
+              for(G.first(f,v); G.valid(f); G.next(f)) {
+                if ( 0 == flow[f] ) continue;
+                Node u=G.head(f);
+                if ( level[u] >= n ) { 
                   bfs_queue.push(u);
                   level.set(u, l);
-                  if ( excess.get(u) > 0 ) {
+                  if ( excess[u] > 0 ) {
                     next.set(u,active[l]);
                     active[l]=u;
@@ -212 +210 @@
           
           
-        if ( active[b] == 0 ) --b; 
+        if ( !G.valid(active[b]) ) --b; 
         else {
           end=false;  
 
-          NodeIt w=active[b];
-          active[b]=next.get(w);
-          int lev=level.get(w);
-          T exc=excess.get(w);
+          Node w=active[b];
+          active[b]=next[w];
+          int lev=level[w];
+          T exc=excess[w];
           int newlevel=n;       //bound on the next level of w
           
-          for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
-            
-            if ( flow.get(e) == capacity.get(e) ) continue; 
-            NodeIt v=G.head(e);            
+          OutEdgeIt e;
+          for(G.first(e,w); G.valid(e); G.next(e)) {
+            
+            if ( flow[e] == capacity[e] ) continue; 
+            Node v=G.head(e);            
             //e=wv          
             
-            if( lev > level.get(v) ) {      
+            if( lev > level[v] ) {      
               /*Push is allowed now*/
               
-              if ( excess.get(v)==0 && v!=t && v!=s ) {
-                int lev_v=level.get(v);
+              if ( excess[v]==0 && v!=t && v!=s ) {
+                int lev_v=level[v];
                 next.set(v,active[lev_v]);
                 active[lev_v]=v;
               }
               
-              T cap=capacity.get(e);
-              T flo=flow.get(e);
+              T cap=capacity[e];
+              T flo=flow[e];
               T remcap=cap-flo;
               
@@ -245 +244 @@
                 
                 flow.set(e, flo+exc);
-                excess.set(v, excess.get(v)+exc);
+                excess.set(v, excess[v]+exc);
                 exc=0;
                 break; 
@@ -253 +252 @@
                 
                 flow.set(e, cap);
-                excess.set(v, excess.get(v)+remcap);
+                excess.set(v, excess[v]+remcap);
                 exc-=remcap;
               }
-            } else if ( newlevel > level.get(v) ){
-              newlevel = level.get(v);
+            } else if ( newlevel > level[v] ){
+              newlevel = level[v];
             }       
             
@@ -264 +263 @@
         
         if ( exc > 0 ) {        
-          for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
-            
-            if( flow.get(e) == 0 ) continue; 
-            NodeIt v=G.tail(e);  
+          InEdgeIt e;
+          for(G.first(e,w); G.valid(e); G.next(e)) {
+            
+            if( flow[e] == 0 ) continue; 
+            Node v=G.tail(e);  
             //e=vw
             
-            if( lev > level.get(v) ) {  
+            if( lev > level[v] ) {  
               /*Push is allowed now*/
               
-              if ( excess.get(v)==0 && v!=t && v!=s ) {
-                int lev_v=level.get(v);
+              if ( excess[v]==0 && v!=t && v!=s ) {
+                int lev_v=level[v];
                 next.set(v,active[lev_v]);
                 active[lev_v]=v;
               }
               
-              T flo=flow.get(e);
+              T flo=flow[e];
               
               if ( flo >= exc ) { 
@@ -285 +285 @@
                 
                 flow.set(e, flo-exc);
-                excess.set(v, excess.get(v)+exc);
+                excess.set(v, excess[v]+exc);
                 exc=0;
                 break; 
@@ -291 +291 @@
                 /*A saturating push.*/
                 
-                excess.set(v, excess.get(v)+flo);
+                excess.set(v, excess[v]+flo);
                 exc-=flo;
                 flow.set(e,0);
               }  
-            } else if ( newlevel > level.get(v) ) {
-              newlevel = level.get(v);
+            } else if ( newlevel > level[v] ) {
+              newlevel = level[v];
             }       
           } //for in edges vw
@@ -319 +319 @@
           } else {
             //unlacing starts
-            NodeIt right_n=right.get(w);
-            NodeIt left_n=left.get(w);
-
-            if ( right_n != 0 ) {
-              if ( left_n != 0 ) {
+            Node right_n=right[w];
+            Node left_n=left[w];
+
+            if ( G.valid(right_n) ) {
+              if ( G.valid(left_n) ) {
                 right.set(left_n, right_n);
                 left.set(right_n, left_n);
               } else {
                 level_list[lev]=right_n;   
-                left.set(right_n, 0);
+                left.set(right_n, INVALID);
               } 
             } else {
-              if ( left_n != 0 ) {
-                right.set(left_n, 0);
+              if ( G.valid(left_n) ) {
+                right.set(left_n, INVALID);
               } else { 
-                level_list[lev]=0;   
-
+                level_list[lev]=INVALID;   
               } 
             } 
@@ -341 +340 @@
                 
             //gapping starts
-            if ( level_list[lev]==0 ) {
+            if ( !G.valid(level_list[lev]) ) {
               
               for (int i=lev; i!=k ; ) {
-                NodeIt v=level_list[++i];
-                while ( v != 0 ) {
+                Node v=level_list[++i];
+                while ( G.valid(v) ) {
                   level.set(v,n);
-                  v=right.get(v);
+                  v=right[v];
                 }
-                level_list[i]=0;
-                if ( !what_heur ) active[i]=0;
+                level_list[i]=INVALID;
+                if ( !what_heur ) active[i]=INVALID;
               }      
 
@@ -366 +365 @@
                 if ( what_heur ) b=newlevel;
                 if ( k < newlevel ) ++k;
-                NodeIt first=level_list[newlevel];
-                if ( first != 0 ) left.set(first,w);
+                Node first=level_list[newlevel];
+                if ( G.valid(first) ) left.set(first,w);
                 right.set(w,first);
-                left.set(w,0);
+                left.set(w,INVALID);
                 level_list[newlevel]=w;
               }
@@ -399 +398 @@
 
 
-      value = excess.get(t);
+      value = excess[t];
       /*Max flow value.*/
      
@@ -412 +411 @@
      */
 
-    T maxFlow() {
+    T flowValue() {
       return value;
     }
-
-
-
-    /*
-      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) {
-      return flow.get(e);
-    }
-
 
 
@@ -436 +423 @@
     
     void Flow(FlowMap& _flow ) {
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
-        _flow.set(v,flow.get(v));
-        }
+      NodeIt v;
+      for(G.first(v) ; G.valid(v); G.next(v))
+        _flow.set(v,flow[v]);
+    }
 
 
@@ -449 +437 @@
     void minMinCut(_CutMap& M) {
     
-      std::queue<NodeIt> queue;
+      std::queue<Node> queue;
       
       M.set(s,true);      
@@ -455 +443 @@
 
       while (!queue.empty()) {
-        NodeIt w=queue.front();
+        Node w=queue.front();
         queue.pop();
 
-        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-          NodeIt v=G.head(e);
-          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
+        OutEdgeIt e;
+        for(G.first(e,w) ; G.valid(e); G.next(e)) {
+          Node v=G.head(e);
+          if (!M[v] && flow[e] < capacity[e] ) {
             queue.push(v);
             M.set(v, true);
@@ -466 +455 @@
         } 
 
-        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-          NodeIt v=G.tail(e);
-          if (!M.get(v) && flow.get(e) > 0 ) {
+        InEdgeIt f;
+        for(G.first(f,w) ; G.valid(f); G.next(f)) {
+          Node v=G.tail(f);
+          if (!M[v] && flow[f] > 0 ) {
             queue.push(v);
             M.set(v, true);
@@ -486 +476 @@
     void maxMinCut(_CutMap& M) {
     
-      std::queue<NodeIt> queue;
+      std::queue<Node> queue;
       
       M.set(t,true);        
@@ -492 +482 @@
 
       while (!queue.empty()) {
-        NodeIt w=queue.front();
+        Node w=queue.front();
         queue.pop();
 
-        for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-          NodeIt v=G.tail(e);
-          if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
+
+        InEdgeIt e;
+        for(G.first(e,w) ; G.valid(e); G.next(e)) {
+          Node v=G.tail(e);
+          if (!M[v] && flow[e] < capacity[e] ) {
             queue.push(v);
             M.set(v, true);
           }
         }
-
-        for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-          NodeIt v=G.head(e);
-          if (!M.get(v) && flow.get(e) > 0 ) {
+        
+        OutEdgeIt f;
+        for(G.first(f,w) ; G.valid(f); G.next(f)) {
+          Node v=G.head(f);
+          if (!M[v] && flow[f] > 0 ) {
             queue.push(v);
             M.set(v, true);
@@ -512 +505 @@
       }
 
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
-        M.set(v, !M.get(v));
+      NodeIt v;
+      for(G.first(v) ; G.valid(v); G.next(v)) {
+        M.set(v, !M[v]);
       }