Changeset 471:a40985a922d0 in lemon-0.x for src/work

Timestamp:

04/29/04 17:01:52 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

misc

File:

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

src/work/jacint/preflow.h

@@ -44 +44 @@
 #include <stack>
 
+#include <graph_wrapper.h>
+
 namespace hugo {
 
@@ -66 +68 @@
     FlowMap* flow;
     int n;      //the number of nodes of G
-    typename Graph::template NodeMap<int> level;      
+    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
+    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
+    typedef typename ResGW::Edge ResGWEdge;
+    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
+    typedef typename Graph::template NodeMap<int> ReachedMap;
+    ReachedMap level;
+    //level works as a bool map in augmenting path algorithms 
+    //and is used by bfs for storing reached information.
+    //In preflow, it shows levels of nodes.
+    //typename Graph::template NodeMap<int> level;    
     typename Graph::template NodeMap<Num> excess; 
-
 
   public:
@@ -92 +102 @@
     }
 
-    void preflowPhase0( flowEnum fe ) {
-      
-      int heur0=(int)(H0*n);  //time while running 'bound decrease' 
-      int heur1=(int)(H1*n);  //time while running 'highest label'
-      int heur=heur1;         //starting time interval (#of relabels)
-      int numrelabel=0;
-     
-      bool what_heur=1;       
-      //It is 0 in case 'bound decrease' and 1 in case 'highest label'
-
-      bool end=false;     
-      //Needed for 'bound decrease', true means no active nodes are above bound b.
-
-      int k=n-2;  //bound on the highest level under n containing a node
-      int b=k;    //bound on the highest level under n of an active node
-      
-      VecStack active(n);
-      
-      NNMap left(*g, INVALID);
-      NNMap right(*g, INVALID);
-      VecNode level_list(n,INVALID);
-      //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
-      
-      switch ( fe ) {
-      case PREFLOW:
-        {
-          //counting the excess
-          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 ) active[lev].push(v);
-          }
-          break;
-        }
-      case GEN_FLOW:
-        {
-          //Counting the excess of t
-          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;
-      }
-      
-      preflowPreproc( fe, active, level_list, left, right );
-      //End of preprocessing 
-      
-      
-      //Push/relabel on the highest level active nodes.
-      while ( true ) {
-        if ( b == 0 ) {
-          if ( !what_heur && !end && k > 0 ) {
-            b=k;
-            end=true;
-          } else break;
-        }
-        
-        if ( active[b].empty() ) --b; 
-        else {
-          end=false;  
-          Node w=active[b].top();
-          active[b].pop();
-          int newlevel=push(w,active);
-          if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 
-                                       left, right, b, k, what_heur);
-          
-          ++numrelabel; 
-          if ( numrelabel >= heur ) {
-            numrelabel=0;
-            if ( what_heur ) {
-              what_heur=0;
-              heur=heur0;
-              end=false;
-            } else {
-              what_heur=1;
-              heur=heur1;
-              b=k; 
-            }
-          }
-        } 
-      } 
-    }
-
-
-    void preflowPhase1() {
-      
-      int k=n-2;  //bound on the highest level under n containing a node
-      int b=k;    //bound on the highest level under n of an active node
-      
-      VecStack active(n);
-      level.set(s,0);
-      std::queue<Node> bfs_queue;
-      bfs_queue.push(s);
-            
-      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 u=g->tail(e);
-          if ( level[u] >= n ) { 
-            bfs_queue.push(u);
-            level.set(u, l);
-            if ( excess[u] > 0 ) active[l].push(u);
-          }
-        }
-        
-        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[u] > 0 ) active[l].push(u);
-          }
-        }
-      }
-      b=n-2;
-
-      while ( true ) {
-        
-        if ( b == 0 ) break;
-
-        if ( active[b].empty() ) --b; 
-        else {
-          Node w=active[b].top();
-          active[b].pop();
-          int newlevel=push(w,active);    
-
-          //relabel
-          if ( excess[w] > 0 ) {
-            level.set(w,++newlevel);
-            active[newlevel].push(w);
-            b=newlevel;
-          }
-        }  // if stack[b] is nonempty
-      } // while(true)
-    }
-
+    void preflowPhase0( flowEnum fe );
+
+    void preflowPhase1();
+
+    bool augmentOnShortestPath();
+
+    template<typename MutableGraph> bool augmentOnBlockingFlow();
+
+    bool augmentOnBlockingFlow2();
 
     //Returns the maximum value of a flow.
@@ -646 +499 @@
     } //relabel
     
-
   };
 
+
+  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
+  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe ) 
+  {
+      
+      int heur0=(int)(H0*n);  //time while running 'bound decrease' 
+      int heur1=(int)(H1*n);  //time while running 'highest label'
+      int heur=heur1;         //starting time interval (#of relabels)
+      int numrelabel=0;
+     
+      bool what_heur=1;       
+      //It is 0 in case 'bound decrease' and 1 in case 'highest label'
+
+      bool end=false;     
+      //Needed for 'bound decrease', true means no active nodes are above bound b.
+
+      int k=n-2;  //bound on the highest level under n containing a node
+      int b=k;    //bound on the highest level under n of an active node
+      
+      VecStack active(n);
+      
+      NNMap left(*g, INVALID);
+      NNMap right(*g, INVALID);
+      VecNode level_list(n,INVALID);
+      //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
+      
+      switch ( fe ) {
+      case PREFLOW:
+        {
+          //counting the excess
+          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 ) active[lev].push(v);
+          }
+          break;
+        }
+      case GEN_FLOW:
+        {
+          //Counting the excess of t
+          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;
+      }
+      
+      preflowPreproc( fe, active, level_list, left, right );
+      //End of preprocessing 
+      
+      
+      //Push/relabel on the highest level active nodes.
+      while ( true ) {
+        if ( b == 0 ) {
+          if ( !what_heur && !end && k > 0 ) {
+            b=k;
+            end=true;
+          } else break;
+        }
+        
+        if ( active[b].empty() ) --b; 
+        else {
+          end=false;  
+          Node w=active[b].top();
+          active[b].pop();
+          int newlevel=push(w,active);
+          if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list, 
+                                       left, right, b, k, what_heur);
+          
+          ++numrelabel; 
+          if ( numrelabel >= heur ) {
+            numrelabel=0;
+            if ( what_heur ) {
+              what_heur=0;
+              heur=heur0;
+              end=false;
+            } else {
+              what_heur=1;
+              heur=heur1;
+              b=k; 
+            }
+          }
+        } 
+      } 
+    }
+
+
+
+  template <typename Graph, typename Num, typename CapMap, typename FlowMap>
+  void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1() 
+  {
+      
+      int k=n-2;  //bound on the highest level under n containing a node
+      int b=k;    //bound on the highest level under n of an active node
+      
+      VecStack active(n);
+      level.set(s,0);
+      std::queue<Node> bfs_queue;
+      bfs_queue.push(s);
+            
+      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 u=g->tail(e);
+          if ( level[u] >= n ) { 
+            bfs_queue.push(u);
+            level.set(u, l);
+            if ( excess[u] > 0 ) active[l].push(u);
+          }
+        }
+        
+        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[u] > 0 ) active[l].push(u);
+          }
+        }
+      }
+      b=n-2;
+
+      while ( true ) {
+        
+        if ( b == 0 ) break;
+
+        if ( active[b].empty() ) --b; 
+        else {
+          Node w=active[b].top();
+          active[b].pop();
+          int newlevel=push(w,active);    
+
+          //relabel
+          if ( excess[w] > 0 ) {
+            level.set(w,++newlevel);
+            active[newlevel].push(w);
+            b=newlevel;
+          }
+        }  // if stack[b] is nonempty
+      } // while(true)
+    }
+
+
+
+
+
+
+
+
+
+
+
+
 } //namespace hugo