# HG changeset patch
# User marci
# Date 1083250912 0
# Node ID a40985a922d038d8863581ef19ed48ecad09317f
# Parent  b64956c701c9b7a0352dce16fdab9d4ac767d07a
misc

diff -r b64956c701c9 -r a40985a922d0 src/work/jacint/preflow.h
--- a/src/work/jacint/preflow.h	Thu Apr 29 11:09:12 2004 +0000
+++ b/src/work/jacint/preflow.h	Thu Apr 29 15:01:52 2004 +0000
@@ -43,6 +43,8 @@
 #include <queue>
 #include <stack>
 
+#include <graph_wrapper.h>
+
 namespace hugo {
 
   template <typename Graph, typename Num, 
@@ -65,10 +67,18 @@
     const CapMap* capacity;  
     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:
  
     enum flowEnum{
@@ -91,172 +101,15 @@
       preflowPhase1();
     }
 
-    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'
+    void preflowPhase0( flowEnum fe );
 
-      bool end=false;     
-      //Needed for 'bound decrease', true means no active nodes are above bound b.
+    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);
-      
-      NNMap left(*g, INVALID);
-      NNMap right(*g, INVALID);
-      VecNode level_list(n,INVALID);
-      //List of the nodes in level i<n, set to n.
+    bool augmentOnShortestPath();
 
-      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 MutableGraph> bool augmentOnBlockingFlow();
 
-
-    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)
-    }
-
+    bool augmentOnBlockingFlow2();
 
     //Returns the maximum value of a flow.
     Num flowValue() {
@@ -645,8 +498,190 @@
       
     } //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