# HG changeset patch
# User jacint
# Date 1077016599 0
# Node ID 15362fafaf1a2148e99263529324cc7e651692ad
# Parent  56e879edcca6be2bd7247b427e0baae84d90b51a
*** empty log message ***

diff -r 56e879edcca6 -r 15362fafaf1a src/work/jacint/preflow_push_hl.h
--- a/src/work/jacint/preflow_push_hl.h	Tue Feb 17 09:34:55 2004 +0000
+++ b/src/work/jacint/preflow_push_hl.h	Tue Feb 17 11:16:39 2004 +0000
@@ -25,11 +25,10 @@
 #ifndef PREFLOW_PUSH_HL_H
 #define PREFLOW_PUSH_HL_H
 
-#include <algorithm>
+//#include <algorithm>
 #include <vector>
 #include <stack>
 
-#include <list_graph.hh>
 #include <reverse_bfs.h>
 
 namespace marci {
@@ -67,8 +66,7 @@
  
       typename Graph::NodeMap<int> level(G);      
       typename Graph::NodeMap<T> excess(G); 
-      std::cout <<"excess s:"<<excess.get(s);      //delme
-            
+
       int n=G.nodeNum(); 
       int b=n-2; 
       /*
@@ -76,6 +74,7 @@
 	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.
 
@@ -85,7 +84,9 @@
       bfs.run();
       for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 
 	{
-	  level.set(v, bfs.dist(v)); 
+	  int dist=bfs.dist(v);
+	  level.set(v, dist);
+	  ++numb[dist];
 	}
 
       level.set(s,n);
@@ -96,9 +97,11 @@
 	{
 	  if ( capacity.get(e) > 0 ) {
 	    NodeIt w=G.head(e);
-	    if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w); 
-	    flow.set(e, capacity.get(e)); 
-	    excess.set(w, excess.get(w)+capacity.get(e));
+	    if ( w!=s ) {	  
+	      if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 
+	      flow.set(e, capacity.get(e)); 
+	      excess.set(w, excess.get(w)+capacity.get(e));
+	    }
 	  }
 	}
 
@@ -112,10 +115,10 @@
 	Push/relabel on the highest level active nodes.
       */
 	
-      /*While there exists active node.*/
+      /*While there exists an active node.*/
       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;
 	} else {
@@ -132,111 +135,119 @@
 
 	      NodeIt v=G.head(e);               /*e is the edge wv.*/
 
-	      if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme     
-
 	      if( level.get(w) == level.get(v)+1 ) {      
 		/*Push is allowed now*/
 
-		if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
+		if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v); 
+		/*v becomes active.*/
+
+		if ( capacity.get(e)-flow.get(e) > excess.get(w) ) {       
 		  /*A nonsaturating push.*/
 		  
-		  if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
 		  flow.set(e, flow.get(e)+excess.get(w));
 		  excess.set(v, excess.get(v)+excess.get(w));
 		  excess.set(w,0);
-		  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
 		  break; 
+
 		} else { 
 		  /*A saturating push.*/
 
-		  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
 		  excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
 		  excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
 		  flow.set(e, capacity.get(e));
-		  //std::cout << w<<" " <<v<<" elore elen sat pump "   << std::endl;
-		  if (excess.get(w)==0) break;
-		  /*If w is not active any more, then we go on to the next Node.*/
+		  if ( excess.get(w)==0 ) break;
+		  /*If w is not active any more, then we go on to the next node.*/
 		  
-		  //std::cout<<++i;
-		  
-		} // if (capacity.get(e)-flow.get(e) > excess.get(w))
-	      } // if(level.get(w)==level.get(v)+1)
+		}
+	      } else {
+		newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
+	      }
 	    
-	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
-	    
-	    } //if (flow.get(e)<capacity.get(e))
+	    } //if the out edge wv is in the res graph 
 	 
-	  } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e) 
+	  } //for out edges wv 
 	  
 
+	  if ( excess.get(w) > 0 ) {	
+	    
+	    for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
+	      NodeIt v=G.tail(e);  /*e is the edge vw.*/
 
-	  for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
-	    NodeIt v=G.tail(e);
-	    /*e is the Edge vw.*/
+	      if( flow.get(e) > 0 ) {             
+		/*e is an edge of the residual graph */
 
-	    if (excess.get(w)==0) break;
-	    /*It may happen, that w became inactive in the first for cycle.*/		
-	    if(flow.get(e)>0) {             
-	      /*e is an Edge of the residual graph */
-
-	      if(level.get(w)==level.get(v)+1) {  
-		/*Push is allowed now*/
+		if( level.get(w)==level.get(v)+1 ) {  
+		  /*Push is allowed now*/
 		
-		if (flow.get(e) > excess.get(w)) { 
-		  /*A nonsaturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
+		  if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v); 
 		  /*v becomes active.*/
 
-		  flow.set(e, flow.get(e)-excess.get(w));
-		  excess.set(v, excess.get(v)+excess.get(w));
-		  excess.set(w,0);
-		  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
-		  break; 
-		} else {                                               
-		  /*A saturating push.*/
+		  if ( flow.get(e) > excess.get(w) ) { 
+		    /*A nonsaturating push.*/
 		  
-		  if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-		  
-		  excess.set(v, excess.get(v)+flow.get(e));
-		  excess.set(w, excess.get(w)-flow.get(e));
-		  flow.set(e,0);
-		  //std::cout << v <<" " << w << " vissza elen sat pump "     << std::endl;
-		  if (excess.get(w)==0) { break;}
-		} //if (flow.get(e) > excess.get(v)) 
-	      } //if(level.get(w)==level.get(v)+1)
-	      
-	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
-	      
+		    flow.set(e, flow.get(e)-excess.get(w));
+		    excess.set(v, excess.get(v)+excess.get(w));
+		    excess.set(w,0);
+		    break; 
+		  } else {                                               
+		    /*A saturating push.*/
+		    
+		    excess.set(v, excess.get(v)+flow.get(e));
+		    excess.set(w, excess.get(w)-flow.get(e));
+		    flow.set(e,0);
+		    if ( excess.get(w)==0 ) break;
+		  }  
+		} else {
+		  newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
+		}
+		
+	      } //if in edge vw is in the res graph 
 
-	    } //if (flow.get(e)>0)
+	    } //for in edges vw
 
-	  } //for
+	  } // if w still has excess after the out edge for cycle
 
 
-	  if (excess.get(w)>0) {
+	  /*
+	    Relabel
+	  */
+	  
+	  if ( excess.get(w) > 0 ) {
+	    
+	    int oldlevel=level.get(w);	    
 	    level.set(w,++newlevel);
+
+	    if ( oldlevel < n ) {
+	      --numb[oldlevel];
+
+	      if ( !numb[oldlevel] ) {  //If the level of w gets empty. 
+		
+		for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
+		  if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n);  
+		}
+		for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0; 
+		if ( newlevel < n ) newlevel=n; 
+	      } else { 
+		if ( newlevel < n ) ++numb[newlevel]; 
+	      }
+	    } else { 
+	    if ( newlevel < n ) ++numb[newlevel];
+	    }
+	    
 	    stack[newlevel].push(w);
 	    b=newlevel;
-	    //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl; 
+
 	  }
 
+	} // if stack[b] is nonempty
 
-	} //else
-       
-      } //while(b)
+      } // while(b)
+
 
       value = excess.get(t);
       /*Max flow value.*/
 
 
-
-
     } //void run()
 
 
diff -r 56e879edcca6 -r 15362fafaf1a src/work/jacint/preflow_push_max_flow.h
--- a/src/work/jacint/preflow_push_max_flow.h	Tue Feb 17 09:34:55 2004 +0000
+++ b/src/work/jacint/preflow_push_max_flow.h	Tue Feb 17 11:16:39 2004 +0000
@@ -26,7 +26,6 @@
 #include <vector>
 #include <stack>
 
-#include <list_graph.hh>
 #include <reverse_bfs.h>