diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl4.h
--- a/src/work/jacint/preflow_hl4.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,602 +0,0 @@
-// -*- C++ -*-
-/*
-preflow_h5.h
-by jacint. 
-Heuristics: 
- 2 phase
- gap
- list 'level_list' on the nodes on level i implemented by hand
- highest label
- relevel: in phase 0, after BFS*n relabels, it runs a reverse 
-   bfs from t in the res graph to relevel the nodes reachable from t.
-   BFS is initialized to 20
-
-Due to the last heuristic, this algorithm is quite fast on very 
-sparse graphs, but relatively bad on even the dense graphs.
-
-'NodeMap<bool> cut' is a member, in this way we can count it fast, after
-the algorithm was run.
-
-The constructor runs the algorithm.
-
-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 Flow(FlowMap& _flow ) : returns the fixed maximum flow x
-
-void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
-     minimum min cut. M should be a map of bools initialized to false.
-
-void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
-     maximum min cut. M should be a map of bools initialized to false.
-
-void minCut(CutMap& M) : fast function, sets M to the characteristic 
-     vector of a minimum cut. 
-
-Different member from the other preflow_hl-s (here we have a member 
-'NodeMap<bool> cut').
-
-CutMap minCut() : fast function, giving the characteristic 
-     vector of a minimum cut.
-
-
-*/
-
-#ifndef PREFLOW_HL4_H
-#define PREFLOW_HL4_H
-
-#define BFS 20
-
-#include <vector>
-#include <queue>
-
-#include <time_measure.h>  //for test
-
-namespace hugo {
-
-  template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, 
-    typename CutMap=typename Graph::NodeMap<bool>,
-    typename CapMap=typename Graph::EdgeMap<T> >
-  class preflow_hl4 {
-    
-    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;  
-    CutMap cut;
-    T value;
-    
-  public:
-
-    double time;
-
-    preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
-      cut(G, false) {
-
-      bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd
-      int n=G.nodeNum(); 
-      int relabel=0;
-      int heur=(int)BFS*n;
-      int k=n-2;
-      int b=k;
-      /*
-	b is a bound on the highest level of the stack. 
-	k is a bound on the highest nonempty level i < n.
-      */
-
-      typename Graph::NodeMap<int> level(G,n);      
-      typename Graph::NodeMap<T> excess(G); 
-      
-      std::vector<NodeIt> active(n);
-      typename Graph::NodeMap<NodeIt> next(G);
-      //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);
-      /*
-	Needed for the list of the nodes in level i.
-      */
-
-      /*Reverse_bfs from t, to find the starting level.*/
-      level.set(t,0);
-      std::queue<NodeIt> bfs_queue;
-      bfs_queue.push(t);
-
-      while (!bfs_queue.empty()) {
-
-	NodeIt 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 ) {
-	    bfs_queue.push(w);
-	    NodeIt first=level_list[l];
-	    if ( first != 0 ) left.set(first,w);
-	    right.set(w,first);
-	    level_list[l]=w;
-	    level.set(w, l);
-	  }
-	}
-      }
-      
-      level.set(s,n);
-
-
-      /* Starting flow. It is everywhere 0 at the moment. */     
-      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
-	{
-	  T c=capacity.get(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;
-	    }
-	    flow.set(e, c); 
-	    excess.set(w, excess.get(w)+c);
-	  }
-	}
-      /* 
-	 End of preprocessing 
-      */
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */	
-      while ( true ) {
-
-	if ( b == 0 ) {
-	  if ( phase ) break;
-	  
-	  /*
-	    In the end of phase 0 we apply a bfs from s in
-	    the residual graph.
-	  */
-	  phase=1;
-	  
-	  //Now have a min cut.
-	  for( EachNodeIt v=G.template first<EachNodeIt>(); 
-	       v.valid(); ++v) 
-	    if (level.get(v) >= n ) cut.set(v,true);
-	  
-	  time=currTime();
-	  level.set(s,0);
-	  std::queue<NodeIt> bfs_queue;
-	  bfs_queue.push(s);
-	  
-	  while (!bfs_queue.empty()) {
-	    
-	    NodeIt 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 ) { 
-		bfs_queue.push(u);
-		level.set(u, l);
-		if ( excess.get(u) > 0 ) {
-		    next.set(u,active[l]);
-		    active[l]=u;
-		}
-	      }
-	    }
-
-	    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 ) { 
-		bfs_queue.push(u);
-		level.set(u, l);
-		if ( excess.get(u) > 0 ) {
-		    next.set(u,active[l]);
-		    active[l]=u;
-		}
-	      }
-	    }
-	  }
-	  b=n-2;
-	}
-
-
-	if ( active[b] == 0 ) --b;
-	else {
-	  
-	  NodeIt w=active[b];
-	  active[b]=next.get(w);
-	  int lev=level.get(w);
-	  T exc=excess.get(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);            
-	    //e=wv	    
-	    
-	    if( lev > level.get(v) ) {      
-	      /*Push is allowed now*/
-	      
-	      if ( excess.get(v)==0 && v!=t && v!=s )  {
-		int lev_v=level.get(v);
-		next.set(v,active[lev_v]);
-		active[lev_v]=v;
-	      }
-	      
-	      T cap=capacity.get(e);
-	      T flo=flow.get(e);
-	      T remcap=cap-flo;
-	      
-	      if ( remcap >= exc ) {       
-		/*A nonsaturating push.*/
-		
-		flow.set(e, flo+exc);
-		excess.set(v, excess.get(v)+exc);
-		exc=0;
-		break; 
-		
-	      } else { 
-		/*A saturating push.*/
-		
-		flow.set(e, cap);
-		excess.set(v, excess.get(v)+remcap);
-		exc-=remcap;
-	      }
-	    } else if ( newlevel > level.get(v) ){
-	      newlevel = level.get(v);
-	    }	    
-	    
-	  } //for out edges wv 
-	
-	
-	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);  
-	    //e=vw
-	    
-	    if( lev > level.get(v) ) {  
-	      /*Push is allowed now*/
-	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) {
-		int lev_v=level.get(v);
-		next.set(v,active[lev_v]);
-		active[lev_v]=v;
-	      }
-	      
-	      T flo=flow.get(e);
-	      
-	      if ( flo >= exc ) { 
-		/*A nonsaturating push.*/
-		
-		flow.set(e, flo-exc);
-		excess.set(v, excess.get(v)+exc);
-		exc=0;
-		break; 
-	      } else {                                               
-		/*A saturating push.*/
-		
-		excess.set(v, excess.get(v)+flo);
-		exc-=flo;
-		flow.set(e,0);
-	      }  
-	    } else if ( newlevel > level.get(v) ) {
-	      newlevel = level.get(v);
-	    }	    
-	  } //for in edges vw
-	  
-	} // if w still has excess after the out edge for cycle
-	
-	excess.set(w, exc);
-	 
-	/*
-	  Relabel
-	*/
-	
-	if ( exc > 0 ) {
-	  //now 'lev' is the old level of w
-	
-	  if ( phase ) {
-	    level.set(w,++newlevel);
-	    next.set(w,active[newlevel]);
-	    active[newlevel]=w;
-	    b=newlevel;
-	  } else {
-	    //unlacing
-	    NodeIt right_n=right.get(w);
-	    NodeIt left_n=left.get(w);
-
-	    if ( right_n != 0 ) {
-	      if ( left_n != 0 ) {
-		right.set(left_n, right_n);
-		left.set(right_n, left_n);
-	      } else {
-		level_list[lev]=right_n;
-		left.set(right_n, 0);
-	      } 
-	    } else {
-	      if ( left_n != 0 ) {
-		right.set(left_n, 0);
-	      } else { 
-		level_list[lev]=0;
-	      } 
-	    }
-	    //unlacing ends
-		
-
-	    if ( level_list[lev]==0 ) {
-
-	      for (int i=lev; i!=k ; ) {
-		NodeIt v=level_list[++i];
-		while ( v != 0 ) {
-		  level.set(v,n);
-		  v=right.get(v);
-		}
-		level_list[i]=0;
-	      }	     
-
-	      level.set(w,n);
-
-	      b=--lev;
-	      k=b;
-
-	    } else {
-
-	      if ( newlevel == n ) {
-		level.set(w,n);
-	      } else {
-		
-		level.set(w,++newlevel);
-		next.set(w,active[newlevel]);
-		active[newlevel]=w;
-		b=newlevel;
-		if ( k < newlevel ) ++k;
-		NodeIt first=level_list[newlevel];
-		if ( first != 0 ) left.set(first,w);
-		right.set(w,first);
-		left.set(w,0);
-		level_list[newlevel]=w;
-	      }
-	    }
-
-	    ++relabel;
-	    if ( relabel >= heur ) {
-	      relabel=0;
-	      b=n-2;
-	      k=b;
-		
-	      for ( int i=1; i!=n; ++i ) { 
-		active[i]=0;
-		level_list[i]=0;
-	      }
-
-	      //bfs from t in the res graph to relevel the nodes
-	      for( EachNodeIt v=G.template first<EachNodeIt>(); 
-		   v.valid(); ++v) level.set(v,n);
-
-	      level.set(t,0);
-	      std::queue<NodeIt> bfs_queue;
-	      bfs_queue.push(t);
-	      
-	      while (!bfs_queue.empty()) {
-		
-		NodeIt 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 ) { 
-		    bfs_queue.push(u);
-		    level.set(u, l);
-		    if ( excess.get(u) > 0 ) {
-		      next.set(u,active[l]);
-		      active[l]=u;
-		    }
-		    NodeIt first=level_list[l];
-		    if ( first != 0 ) left.set(first,w);
-		    right.set(w,first);
-		    left.set(w,0);
-		    level_list[l]=w;
-		  }
-		}
-		
-		
-		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 ) { 
-		    bfs_queue.push(u);
-		    level.set(u, l);
-		    if ( excess.get(u) > 0 ) {
-		      next.set(u,active[l]);
-		      active[l]=u;
-		    }
-		    NodeIt first=level_list[l];
-		    if ( first != 0 ) left.set(first,w);
-		    right.set(w,first);
-		    left.set(w,0);
-		    level_list[l]=w;
-		  }
-		}
-	      }
-	      
-	      level.set(s,n);
-	    }
-	  
-	  } //phase 0
-	} // if ( exc > 0 )
-	
-	
-	} // if stack[b] is nonempty
-	
-      } // while(true)
-
-
-      value = excess.get(t);
-      /*Max flow value.*/
-
-
-    } //void run()
-
-
-
-
-
-    /*
-      Returns the maximum value of a flow.
-     */
-
-    T maxFlow() {
-      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);
-    }
-
-
-
-    FlowMap Flow() {
-      return flow;
-    }
-
-
-    
-    void Flow(FlowMap& _flow ) {
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
-	_flow.set(v,flow.get(v));
-    }
-
-
-
-    /*
-      Returns the minimum min cut, by a bfs from s in the residual graph.
-    */
-    
-    template<typename _CutMap>
-    void minMinCut(_CutMap& M) {
-    
-      std::queue<NodeIt> queue;
-      
-      M.set(s,true);      
-      queue.push(s);
-
-      while (!queue.empty()) {
-        NodeIt 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) ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	} 
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.tail(e);
-	  if (!M.get(v) && flow.get(e) > 0 ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	} 
-
-      }
-
-    }
-
-
-
-    /*
-      Returns the maximum min cut, by a reverse bfs 
-      from t in the residual graph.
-    */
-    
-    template<typename _CutMap>
-    void maxMinCut(_CutMap& M) {
-    
-      std::queue<NodeIt> queue;
-      
-      M.set(t,true);        
-      queue.push(t);
-
-      while (!queue.empty()) {
-        NodeIt 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) ) {
-	    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 ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	}
-      }
-
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
-	M.set(v, !M.get(v));
-      }
-
-    }
-
-
-    template<typename _CutMap>
-    void minCut(_CutMap& M) {
-      for( EachNodeIt v=G.template first<EachNodeIt>(); 
-	   v.valid(); ++v) 
-	M.set(v, cut.get(v));
-    }
-
-   
-    CutMap minCut() {
-      return cut;
-    }
-
-
-  };
-}//namespace marci
-#endif 
-
-
-
-