# HG changeset patch
# User jacint
# Date 1077397282 0
# Node ID fc5982b39e10d1a21fd7e432827481d8617038e0
# Parent  0351b00fd2830f7fc5a80f8a737d560c8c632b0a
Flows with test files. The best is preflow.h

diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,66 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  preflow<ListGraph, int> max_flow_test(G, s, t, cap);
+  
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+      }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << 
+    std::endl<< std::endl;
+  
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow.h	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,532 @@
+// -*- C++ -*-
+/*
+preflow.h
+by jacint. 
+Heuristics: 
+ 2 phase
+ gap
+ list 'level_list' on the nodes on level i implemented by hand
+ stack 'active' on the active nodes on level i implemented by hand
+ runs heuristic 'highest label' for H1*n relabels
+ runs heuristic 'dound decrease' for H0*n relabels, starts with 'highest label'
+ 
+Parameters H0 and H1 are initialized to 20 and 10.
+
+The best preflow I could ever write.
+
+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 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) : sets M to the characteristic vector of 
+     a min cut. M should be a map of bools initialized to false.
+
+*/
+
+#ifndef PREFLOW_H
+#define PREFLOW_H
+
+#define H0 20
+#define H1 1
+
+#include <vector>
+#include <queue>
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename FlowMap=typename Graph::EdgeMap<T>,
+    typename CapMap=typename Graph::EdgeMap<T> >
+  class preflow {
+    
+    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;  
+    T value;
+
+  public:
+    
+    preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
+    {
+
+      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
+      int n=G.nodeNum(); 
+      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)
+      bool what_heur=1;       
+      /*
+	what_heur 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 relabel=0;
+      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
+      
+      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);
+      /*
+	List of the nodes in level i<n.
+      */
+
+      /*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;
+	  
+	  if ( !what_heur && !end && k > 0 ) {
+	    b=k;
+	    end=true;
+	  } else {
+	    phase=1;
+
+	    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 {
+	  end=false;  
+
+	  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 starts
+	    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
+		
+	    //gapping starts
+	    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;
+		if ( !what_heur ) active[i]=0;
+	      }	     
+
+	      level.set(w,n);
+	      b=lev-1;
+	      k=b;
+	      //gapping ends
+	    } else {
+	      
+	      if ( newlevel == n ) level.set(w,n); 
+	      else {
+		level.set(w,++newlevel);
+		next.set(w,active[newlevel]);
+		active[newlevel]=w;
+		if ( what_heur ) 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;
+	      if ( what_heur ) {
+		what_heur=0;
+		heur=heur0;
+		end=false;
+	      } else {
+		what_heur=1;
+		heur=heur1;
+		b=k; 
+	      }
+	    }
+	  } //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) {
+      minMinCut(M);
+    }
+
+
+  };
+}//namespace marci
+#endif 
+
+
+
+
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl0.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl0.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,71 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_hl0.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_hl0 demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow_hl0<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  double pre_time=currTime();
+  preflow_hl0<ListGraph, int> max_flow_test(G, s, t, cap);
+  double post_time=currTime();
+      
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+  }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
+  std::cout << "phase 0: " << max_flow_test.time-pre_time 
+	    << " sec"<< std::endl; 
+  std::cout << "phase 1: " << post_time-max_flow_test.time 
+	    << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << std::endl;
+
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl0.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl0.h	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,508 @@
+// -*- C++ -*-
+/*
+preflow_hl0.h
+by jacint. 
+Heuristics: 
+ 2 phase
+ gap
+ list 'level_list' on the nodes on level i implemented by hand
+ stack 'active' on the active nodes on level i implemented by hand
+ bound decrease
+ 
+The bound decrease heuristic behaves unexpectedly well.
+
+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 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) : sets M to the characteristic vector of 
+     a min cut. M should be a map of bools initialized to false.
+
+*/
+
+#ifndef PREFLOW_HL0_H
+#define PREFLOW_HL0_H
+
+#include <vector>
+#include <queue>
+
+#include <time_measure.h> //for test
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename FlowMap=typename Graph::EdgeMap<T>,
+    typename CapMap=typename Graph::EdgeMap<T> >
+  class preflow_hl0 {
+    
+    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;
+    T value;
+
+  public:
+    double time;    
+    
+    preflow_hl0(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
+
+      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
+      int n=G.nodeNum(); 
+      bool end=false;     
+      /*
+	'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
+      /*
+	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);
+      /*
+	List of the nodes in level i<n.
+      */
+
+      /*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;
+	  
+	  if ( !end && k > 0 ) {
+	    b=k;
+	    end=true;
+	  } else {
+	    phase=1;
+	    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 {
+	  end=false;  
+
+	  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 starts
+	    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
+		
+	    //gapping starts
+	    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;
+		active[i]=0;
+	      }	     
+
+	      level.set(w,n);
+	      b=lev-1;
+	      k=b;
+	      //gapping ends
+	    } else {
+	      
+	      if ( newlevel == n ) level.set(w,n); 
+	      else {
+		level.set(w,++newlevel);
+		next.set(w,active[newlevel]);
+		active[newlevel]=w;
+		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;
+	      }
+	    }
+
+
+	  } //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) {
+      minMinCut(M);
+    }
+
+  };
+}//namespace marci
+#endif 
+
+
+
+
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl1.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl1.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,73 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_hl1.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_hl1 demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow_hl1<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  double pre_time=currTime();
+  preflow_hl1<ListGraph, int> max_flow_test(G, s, t, cap);
+  double post_time=currTime();
+     
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+  }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
+  std::cout << "phase 0: " << max_flow_test.time-pre_time 
+	    << " sec"<< std::endl; 
+  std::cout << "phase 1: " << post_time-max_flow_test.time 
+	    << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << 
+    std::endl<< std::endl;
+
+  
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl2.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl2.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,65 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_hl2.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_hl2 demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow_hl2<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  preflow_hl2<ListGraph, int> max_flow_test(G, s, t, cap);
+    
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+  }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << std::endl;
+
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl2.h
--- a/src/work/jacint/preflow_hl2.h	Fri Feb 20 22:01:02 2004 +0000
+++ b/src/work/jacint/preflow_hl2.h	Sat Feb 21 21:01:22 2004 +0000
@@ -3,31 +3,35 @@
 preflow_hl2.h
 by jacint. 
 Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), with the 'empty level' and with the 
-heuristic that the bound b on the active nodes is not increased 
-only when b=0, when we put b=2*n-2.
+running time O(n^2\sqrt(m)). 
 
-'A' is a parameter for the empty_level heuristic
+Heuristics:
 
-Member functions:
+  gap: we iterate through the nodes for finding the nodes above 
+       the gap and under level n. So it is quite slow.
+  numb: we maintain the number of nodes in level i.
+  highest label
+  
+'A' is a parameter for the gap, we only upgrade the nodes to level n,
+  if the gap is under A*n.
 
-void run() : runs the algorithm
+The constructor runs the algorithm.
 
- The following functions should be used after run() was already run.
+Members:
 
-T maxflow() : returns the value of a maximum flow
+T maxFlow() : returns the value of a maximum flow
 
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
 
-FlowMap allflow() : returns the fixed maximum flow x
+FlowMap Flow() : returns the fixed maximum flow x
 
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
+void minCut(CutMap& M) : sets M to the characteristic vector of a 
      minimum cut. M should be a map of bools initialized to false.
 
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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 max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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.
 
 */
@@ -35,7 +39,7 @@
 #ifndef PREFLOW_HL2_H
 #define PREFLOW_HL2_H
 
-#define A 1
+#define A .9
 
 #include <vector>
 #include <stack>
@@ -44,8 +48,8 @@
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl2 {
     
     typedef typename Graph::NodeIt NodeIt;
@@ -64,22 +68,17 @@
   public:
 
     preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
+      G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 
 
-
-    void run() {
- 
-      bool no_end=true;
       int n=G.nodeNum(); 
       int b=n-2; 
       /*
 	b is a bound on the highest level of an active node. 
-	In the beginning it is at most n-2.
       */
 
-      IntMap level(G,n);      
-      TMap excess(G); 
-      
+      typename Graph::NodeMap<int> level(G,n);      
+      typename Graph::NodeMap<T> excess(G); 
+
       std::vector<int> numb(n);    
       /*
 	The number of nodes on level i < n. It is
@@ -110,7 +109,7 @@
 	  }
 	}
       }
-      
+	
       level.set(s,n);
 
 
@@ -127,38 +126,28 @@
 	    excess.set(w, excess.get(w)+c);
 	  }
 	}
-
+      
       /* 
 	 End of preprocessing 
       */
 
 
-
       /*
 	Push/relabel on the highest level active nodes.
-      */	
+      */
       /*While there exists an active node.*/
       while (b) { 
-	if ( stack[b].empty() ) {
-	  if ( b==1 ) {
-	    if ( !no_end ) break; 
-	    else {
-	      b=2*n-2;
-	      no_end=false;
-	    }
-	  } 
+	if ( stack[b].empty() ) { 
 	  --b;
-	} else {
-	  
-	  no_end=true;
-	  
-	  NodeIt w=stack[b].top();        //w is a highest label active node.
-	  stack[b].pop();           
-	  int lev=level.get(w);
-	  int exc=excess.get(w);
-	  int newlevel=2*n;      //In newlevel we bound the next level of w.
-	  
-	  //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
+	  continue;
+	} 
+	
+	NodeIt w=stack[b].top();   
+	stack[b].pop();           
+	int lev=level.get(w);
+	T exc=excess.get(w);
+	int newlevel=2*n;      //In newlevel we bound the next level of w.
+	
 	  for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
 	    
 	    if ( flow.get(e) == capacity.get(e) ) continue; 
@@ -172,9 +161,9 @@
 		stack[level.get(v)].push(v); 
 	      /*v becomes active.*/
 	      
-	      int cap=capacity.get(e);
-	      int flo=flow.get(e);
-	      int remcap=cap-flo;
+	      T cap=capacity.get(e);
+	      T flo=flow.get(e);
+	      T remcap=cap-flo;
 	      
 	      if ( remcap >= exc ) {       
 		/*A nonsaturating push.*/
@@ -210,7 +199,7 @@
 		stack[level.get(v)].push(v); 
 	      /*v becomes active.*/
 	      
-	      int flo=flow.get(e);
+	      T flo=flow.get(e);
 	      
 	      if ( flo >= exc ) { 
 		/*A nonsaturating push.*/
@@ -231,42 +220,43 @@
 	  } //for in edges vw
 	  
 	} // if w still has excess after the out edge for cycle
-	 
-	  excess.set(w, exc);
+	
+	excess.set(w, exc);
+	
+
+	
+
+	/*
+	  Relabel
+	*/
+	
+	if ( exc > 0 ) {
+	  //now 'lev' is the old level of w
+	  level.set(w,++newlevel);
 	  
-
-	  /*
-	    Relabel
-	  */
+	  if ( lev < n ) {
+	    --numb[lev];
+	    
+	    if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
+	      
+	      for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
+		if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);  
+	      }
+	      for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
+	      if ( newlevel < n ) newlevel=n; 
+	    } else { 
+	      if ( newlevel < n ) ++numb[newlevel]; 
+	    }
+	  } 
 	  
-	  if ( exc > 0 ) {
-	    //now 'lev' is the old level of w
-	    level.set(w,++newlevel);
-	    
-	    if ( lev < n ) {
-	      --numb[lev];
-
-	      if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
-		
-		for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
-		  if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);  
-		}
-		for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
-		if ( newlevel < n ) newlevel=n; 
-	      } else { 
-		if ( newlevel < n ) ++numb[newlevel]; 
-	      }
-	    } 
-	    
-	    stack[newlevel].push(w);
-
-	  }
-
-	} // if stack[b] is nonempty
-
+	  stack[newlevel].push(w);
+	  b=newlevel;
+	  
+	}
+	
       } // while(b)
-
-
+      
+      
       value = excess.get(t);
       /*Max flow value.*/
 
@@ -281,17 +271,18 @@
       Returns the maximum value of a flow.
      */
 
-    T maxflow() {
+    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). 
+      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) {
+    T flowOnEdge(const EdgeIt e) {
       return flow.get(e);
     }
 
@@ -301,7 +292,7 @@
       Returns the maximum flow x found by the algorithm.
     */
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
 
@@ -313,7 +304,7 @@
     */
     
     template<typename CutMap>
-    void mincut(CutMap& M) {
+    void minCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -323,7 +314,7 @@
       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) ) {
@@ -338,10 +329,9 @@
 	    queue.push(v);
 	    M.set(v, true);
 	  }
-	} 
+	}
 
       }
-
     }
 
 
@@ -352,7 +342,7 @@
     */
     
     template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    void maxMinCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -389,14 +379,14 @@
 
 
     template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    void minMinCut(CutMap& M) {
+      minCut(M);
     }
 
 
 
   };
-}//namespace hugo
+}//namespace marci
 #endif 
 
 
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl3.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl3.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,72 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_hl3.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_hl3 demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow_hl3<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  double pre_time=currTime();
+  preflow_hl3<ListGraph, int> max_flow_test(G, s, t, cap);
+  double post_time=currTime();
+     
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+  }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;   
+  std::cout << "phase 0: " << max_flow_test.time-pre_time 
+	    << " sec"<< std::endl; 
+  std::cout << "phase 1: " << post_time-max_flow_test.time 
+	    << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << 
+    std::endl<< std::endl;
+
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl3.h
--- a/src/work/jacint/preflow_hl3.h	Fri Feb 20 22:01:02 2004 +0000
+++ b/src/work/jacint/preflow_hl3.h	Sat Feb 21 21:01:22 2004 +0000
@@ -2,35 +2,31 @@
 /*
 preflow_hl3.h
 by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), with the felszippantos 'empty level' 
-and with the two-phase heuristic: if there is no active node of
-level at most n, then we go into phase 1, do a bfs
-from s, and flow the excess back to s.
 
-In phase 1 we shift everything downwards by n.
+Heuristics: 
 
-'A' is a parameter for the empty_level heuristic
+ suck gap : if there is a gap, then we put all 
+   nodes reachable from the relabelled node to level n
+ 2 phase
+ highest label
 
-Member functions:
+The constructor runs the algorithm.
 
-void run() : runs the algorithm
+Members:
 
- The following functions should be used after run() was already run.
+T maxFlow() : returns the value of a maximum flow
 
-T maxflow() : returns the value of a maximum flow
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
 
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+FlowMap Flow() : returns the fixed maximum flow x
 
-FlowMap allflow() : returns the fixed maximum flow x
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
+void minCut(CutMap& M) : sets M to the characteristic vector of a 
      minimum cut. M should be a map of bools initialized to false.
 
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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 max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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.
 
 */
@@ -38,17 +34,17 @@
 #ifndef PREFLOW_HL3_H
 #define PREFLOW_HL3_H
 
-#define A 1
-
 #include <vector>
 #include <stack>
 #include <queue>
 
+#include <time_measure.h> //for test
+
 namespace hugo {
 
   template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
   class preflow_hl3 {
     
     typedef typename Graph::NodeIt NodeIt;
@@ -66,12 +62,11 @@
     
   public:
 
+    double time; //for test
+
     preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    void run() {
- 
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
+      
       bool phase=0;
       int n=G.nodeNum(); 
       int b=n-2; 
@@ -80,8 +75,8 @@
 	In the beginning it is at most n-2.
       */
 
-      IntMap level(G,n);      
-      TMap excess(G); 
+      typename Graph::NodeMap<int> level(G,n);      
+      typename Graph::NodeMap<T> excess(G); 
       
       std::vector<int> numb(n);    
       /*
@@ -148,7 +143,8 @@
 	if ( b == 0 ) {
 	  if ( phase ) break; 
 	  phase=1;
-
+	  time=currTime();
+	  
 	  level.set(s,0);
 
 	  std::queue<NodeIt> bfs_queue;
@@ -187,11 +183,11 @@
 	if ( stack[b].empty() ) --b;
 	else {
 	  
-	  NodeIt w=stack[b].top();        //w is a highest label active node.
+	  NodeIt w=stack[b].top(); 
 	  stack[b].pop();           
 	  int lev=level.get(w);
-	  int exc=excess.get(w);
-	  int newlevel=n;                 //In newlevel we bound the next level of 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) {
 	    
@@ -206,9 +202,9 @@
 		stack[level.get(v)].push(v); 
 	      /*v becomes active.*/
 	      
-	      int cap=capacity.get(e);
-	      int flo=flow.get(e);
-	      int remcap=cap-flo;
+	      T cap=capacity.get(e);
+	      T flo=flow.get(e);
+	      T remcap=cap-flo;
 	      
 	      if ( remcap >= exc ) {       
 		/*A nonsaturating push.*/
@@ -244,7 +240,7 @@
 		stack[level.get(v)].push(v); 
 	      /*v becomes active.*/
 	      
-	      int flo=flow.get(e);
+	      T flo=flow.get(e);
 	      
 	      if ( flo >= exc ) { 
 		/*A nonsaturating push.*/
@@ -349,17 +345,18 @@
       Returns the maximum value of a flow.
      */
 
-    T maxflow() {
+    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). 
+      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) {
+    T flowOnEdge(EdgeIt e) {
       return flow.get(e);
     }
 
@@ -369,7 +366,7 @@
       Returns the maximum flow x found by the algorithm.
     */
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
 
@@ -381,7 +378,7 @@
     */
     
     template<typename CutMap>
-    void mincut(CutMap& M) {
+    void minCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -420,7 +417,7 @@
     */
     
     template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    void maxMinCut(CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -457,14 +454,14 @@
 
 
     template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    void minMinCut(CutMap& M) {
+      minCut(M);
     }
 
 
 
   };
-}//namespace hugo
+}//namespace
 #endif 
 
 
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl4.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_hl4.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,76 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_hl4.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+//Note, that preflow_hl4.h has a member NodeMap<bool> cut, 
+//the construction of which slowing the running time by 1-10%.
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_hl4 demo ..." << std::endl;
+  
+  double mintime=1000000;
+
+  for ( int i=1; i!=11; ++i ) {
+    double pre_time=currTime();
+    preflow_hl4<ListGraph, int> max_flow_test(G, s, t, cap);
+    double post_time=currTime();
+    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+  }
+
+  double pre_time=currTime();
+  preflow_hl4<ListGraph, int> max_flow_test(G, s, t, cap);
+  double post_time=currTime();
+     
+  ListGraph::NodeMap<bool> cut(G);
+  max_flow_test.minCut(cut); 
+  int min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut1(G);
+  max_flow_test.minMinCut(cut1); 
+  int min_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
+      min_min_cut_value+=cap.get(e);
+  }
+
+  ListGraph::NodeMap<bool> cut2(G);
+  max_flow_test.maxMinCut(cut2); 
+  int max_min_cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e))) 
+      max_min_cut_value+=cap.get(e);
+  }
+  
+  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl; 
+  std::cout << "phase 0: " << max_flow_test.time-pre_time 
+	    << " sec"<< std::endl; 
+  std::cout << "phase 1: " << post_time-max_flow_test.time 
+	    << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "min cut value: "<< min_cut_value << std::endl;
+  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
+  std::cout << "max min cut value: "<< max_min_cut_value << 
+    std::endl<< std::endl;
+
+  
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_hl4.h
--- a/src/work/jacint/preflow_hl4.h	Fri Feb 20 22:01:02 2004 +0000
+++ b/src/work/jacint/preflow_hl4.h	Sat Feb 21 21:01:22 2004 +0000
@@ -1,53 +1,67 @@
 // -*- C++ -*-
 /*
-preflow_hl4.h
+preflow_h5.h
 by jacint. 
-Runs the two phase highest label preflow push algorithm. In phase 0
-we maintain in a list the nodes in level i < n, and we maintain a 
-bound k on the max level i < n containing a node, so we can do
-the gap heuristic fast. Phase 1 is the same. (The algorithm is the 
-same as preflow.hl3, the only diff is that here we use the gap
-heuristic with the list of the nodes on level i, and not a bfs form the
-upgraded node.)
+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
 
-In phase 1 we shift everything downwards by n.
+Due to the last heuristic, this algorithm is quite fast on very 
+sparse graphs, but relatively bad on even the dense graphs.
 
-Member functions:
+'NodeMap<bool> cut' is a member, in this way we can count it fast, after
+the algorithm was run.
 
-void run() : runs the algorithm
+The constructor runs the algorithm.
 
- The following functions should be used after run() was already run.
+Members:
 
-T maxflow() : returns the value of a maximum flow
+T maxFlow() : returns the value of a maximum flow
 
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
+T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
 
-FlowMap allflow() : returns a maximum flow
+FlowMap Flow() : returns the fixed maximum flow x
 
-void allflow(FlowMap& _flow ) : returns a maximum flow
+void Flow(FlowMap& _flow ) : returns the fixed maximum flow x
 
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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 max_mincut(CutMap& M) : sets M to the characteristic vector of the 
+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 <stack>
 #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 {
     
@@ -62,18 +76,21 @@
     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) { }
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
+      cut(G, false) {
 
-
-    void run() {
- 
-      bool phase=0;
+      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;
       /*
@@ -83,7 +100,9 @@
 
       typename Graph::NodeMap<int> level(G,n);      
       typename Graph::NodeMap<T> excess(G); 
-      std::vector<std::stack<NodeIt> > stack(n);    
+      
+      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.
 
@@ -107,7 +126,7 @@
 
 	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
 	  NodeIt w=G.tail(e);
-	  if ( level.get(w) == n ) {
+	  if ( level.get(w) == n && w !=s ) {
 	    bfs_queue.push(w);
 	    NodeIt first=level_list[l];
 	    if ( first != 0 ) left.set(first,w);
@@ -128,7 +147,10 @@
 	  if ( c == 0 ) continue;
 	  NodeIt w=G.head(e);
 	  if ( level.get(w) < n ) {	  
-	    if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 
+	    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);
 	  }
@@ -151,6 +173,13 @@
 	    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);
@@ -167,7 +196,10 @@
 	      if ( level.get(u) >= n ) { 
 		bfs_queue.push(u);
 		level.set(u, l);
-		if ( excess.get(u) > 0 ) stack[l].push(u);
+		if ( excess.get(u) > 0 ) {
+		    next.set(u,active[l]);
+		    active[l]=u;
+		}
 	      }
 	    }
 
@@ -177,7 +209,10 @@
 	      if ( level.get(u) >= n ) { 
 		bfs_queue.push(u);
 		level.set(u, l);
-		if ( excess.get(u) > 0 ) stack[l].push(u);
+		if ( excess.get(u) > 0 ) {
+		    next.set(u,active[l]);
+		    active[l]=u;
+		}
 	      }
 	    }
 	  }
@@ -185,14 +220,14 @@
 	}
 
 
-	if ( stack[b].empty() ) --b;
+	if ( active[b] == 0 ) --b;
 	else {
 	  
-	  NodeIt w=stack[b].top();        //w is a highest label active node.
-	  stack[b].pop();           
+	  NodeIt w=active[b];
+	  active[b]=next.get(w);
 	  int lev=level.get(w);
 	  T exc=excess.get(w);
-	  int newlevel=n;          //In newlevel we bound the next level of w.
+	  int newlevel=n;          //bound on the next level of w.
 	  
 	  for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
 	    
@@ -203,9 +238,11 @@
 	    if( lev > level.get(v) ) {      
 	      /*Push is allowed now*/
 	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
+	      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);
@@ -243,9 +280,11 @@
 	    if( lev > level.get(v) ) {  
 	      /*Push is allowed now*/
 	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
+	      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);
 	      
@@ -281,7 +320,8 @@
 	
 	  if ( phase ) {
 	    level.set(w,++newlevel);
-	    stack[newlevel].push(w);
+	    next.set(w,active[newlevel]);
+	    active[newlevel]=w;
 	    b=newlevel;
 	  } else {
 	    //unlacing
@@ -303,6 +343,7 @@
 		level_list[lev]=0;
 	      } 
 	    }
+	    //unlacing ends
 		
 
 	    if ( level_list[lev]==0 ) {
@@ -328,7 +369,8 @@
 	      } else {
 		
 		level.set(w,++newlevel);
-		stack[newlevel].push(w);
+		next.set(w,active[newlevel]);
+		active[newlevel]=w;
 		b=newlevel;
 		if ( k < newlevel ) ++k;
 		NodeIt first=level_list[newlevel];
@@ -338,9 +380,78 @@
 		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
 	
@@ -361,7 +472,7 @@
       Returns the maximum value of a flow.
      */
 
-    T maxflow() {
+    T maxFlow() {
       return value;
     }
 
@@ -371,19 +482,19 @@
       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) {
+    T flowOnEdge(EdgeIt e) {
       return flow.get(e);
     }
 
 
 
-    FlowMap allflow() {
+    FlowMap Flow() {
       return flow;
     }
 
 
     
-    void allflow(FlowMap& _flow ) {
+    void Flow(FlowMap& _flow ) {
       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
 	_flow.set(v,flow.get(v));
     }
@@ -394,8 +505,8 @@
       Returns the minimum min cut, by a bfs from s in the residual graph.
     */
     
-    template<typename CutMap>
-    void mincut(CutMap& M) {
+    template<typename _CutMap>
+    void minMinCut(_CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -433,8 +544,8 @@
       from t in the residual graph.
     */
     
-    template<typename CutMap>
-    void max_mincut(CutMap& M) {
+    template<typename _CutMap>
+    void maxMinCut(_CutMap& M) {
     
       std::queue<NodeIt> queue;
       
@@ -469,16 +580,21 @@
     }
 
 
-
-    template<typename CutMap>
-    void min_mincut(CutMap& M) {
-      mincut(M);
+    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 hugo
+}//namespace marci
 #endif 
 
 
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_max_flow.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_max_flow.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,40 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_max_flow.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+typedef ListGraph::EachNodeIt EachNodeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow_max_flow demo ..." << std::endl;
+  
+  double pre_time=currTime();
+  preflow_max_flow<ListGraph, int> max_flow_test(G, s, t, cap);
+  ListGraph::NodeMap<bool> cut=max_flow_test.minCut();
+  double post_time=currTime();
+  
+  int cut_value=0;
+  for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
+    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) cut_value+=cap.get(e);
+  }
+  
+  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
+  std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
+  std::cout << "cut value: "<< cut_value << std::endl;
+
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_max_flow.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_max_flow.h	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,358 @@
+// -*- C++ -*-
+/*
+preflow_max_flow.h
+by jacint. 
+Runs the first phase of preflow.h
+
+The constructor runs the algorithm.
+
+Members:
+
+T maxFlow() : returns the value of a maximum flow
+
+CutMap minCut() : returns the characteristic vector of a min cut. 
+*/
+
+#ifndef PREFLOW_MAX_FLOW_H
+#define PREFLOW_MAX_FLOW_H
+
+#define H0 20
+#define H1 1
+
+#include <vector>
+#include <queue>
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename FlowMap=typename Graph::EdgeMap<T>,
+    typename CapMap=typename Graph::EdgeMap<T>, 
+    typename CutMap=typename Graph::NodeMap<bool> >
+  class preflow_max_flow {
+    
+    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:
+    
+    preflow_max_flow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), cut(_G, false)
+    {
+
+      int n=G.nodeNum(); 
+      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)
+      bool what_heur=1;       
+      /*
+	what_heur 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 relabel=0;
+      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
+      
+      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);
+      /*
+	List of the nodes in level i<n.
+      */
+
+      /*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 ( !what_heur && !end && k > 0 ) {
+	    b=k;
+	    end=true;
+	  } else break;
+	}
+	  
+	  
+	if ( active[b] == 0 ) --b; 
+	else {
+	  end=false;  
+
+	  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
+	
+	  //unlacing starts
+	  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
+	  
+	  //gapping starts
+	  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;
+	      if ( !what_heur ) active[i]=0;
+	    }	     
+	    
+	    level.set(w,n);
+	    b=lev-1;
+	    k=b;
+	    //gapping ends
+	  } else {
+	    
+	    if ( newlevel == n ) level.set(w,n); 
+	    else {
+	      level.set(w,++newlevel);
+	      next.set(w,active[newlevel]);
+	      active[newlevel]=w;
+	      if ( what_heur ) 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;
+	    if ( what_heur ) {
+	      what_heur=0;
+	      heur=heur0;
+	      end=false;
+	    } else {
+	      what_heur=1;
+	      heur=heur1;
+	      b=k; 
+	    }
+	  }
+	  
+  
+	} // if ( exc > 0 )
+	
+	
+	}  // if stack[b] is nonempty
+	
+      } // while(true)
+
+
+      
+      for( EachNodeIt v=G.template first<EachNodeIt>(); 
+	   v.valid(); ++v) 
+	if (level.get(v) >= n ) cut.set(v,true);
+      
+      value = excess.get(t);
+      /*Max flow value.*/
+     
+    } //void run()
+
+
+
+
+    T maxFlow() {
+      return value;
+    }
+
+
+
+    CutMap minCut() {
+      return cut;
+    }
+
+
+  };
+}//namespace 
+#endif 
+
+
+
+
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_param.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_param.cc	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,47 @@
+#include <iostream>
+#include <fstream>
+
+#include <list_graph.hh>
+#include <dimacs.hh>
+#include <preflow_param.h>
+#include <time_measure.h>
+
+using namespace hugo;
+
+// Use a DIMACS max flow file as stdin.
+// read_dimacs_demo < dimacs_max_flow_file
+int main(int, char **) {
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+
+  ListGraph G;
+  NodeIt s, t;
+  ListGraph::EdgeMap<int> cap(G);
+  readDimacsMaxFlow(std::cin, G, s, t, cap);
+
+  std::cout << "preflow parameters test ..." << std::endl;
+
+  double min=1000000;  
+
+  int _j=0;
+  int _k=0;
+
+  for (int j=1; j!=40; ++j ){
+    for (int k=1; k!=j; ++k ){
+      
+      double mintime=1000000;
+
+      for ( int i=1; i!=4; ++i ) {
+	double pre_time=currTime();
+	preflow_param<ListGraph, int> max_flow_test(G, s, t, cap, j, k);
+	double post_time=currTime();
+	if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
+      }
+      if (min > mintime ) {min=mintime; _j=j; _k=k;}
+    }
+  }
+
+  std::cout<<"Min. at ("<<_j<<","<<_k<<") in time "<<min<<std::endl;
+  
+  return 0;
+}
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_param.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_param.h	Sat Feb 21 21:01:22 2004 +0000
@@ -0,0 +1,541 @@
+// -*- C++ -*-
+/*
+preflow_param.h
+by jacint. 
+
+For testing the parameters H0, H1 of preflow.h
+
+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 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_PARAM_H
+#define PREFLOW_PARAM_H
+
+#include <vector>
+#include <queue>
+
+#include <time_measure.h> //for test
+
+namespace hugo {
+
+  template <typename Graph, typename T, 
+    typename FlowMap=typename Graph::EdgeMap<T>, 
+    typename CapMap=typename Graph::EdgeMap<T> >
+  class preflow_param {
+    
+    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;  
+    T value;
+    int H0;
+    int H1;
+
+  public:
+    double time;    
+    
+    preflow_param(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity, 
+		int _H0, int _H1) :
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), H0(_H0), H1(_H1) {
+
+      bool phase=0;       //phase 0 is the 1st phase, phase 1 is the 2nd
+      int n=G.nodeNum(); 
+      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)
+      bool what_heur=1;
+      /*
+	what_heur is 0 in case 'bound decrease' 
+	and 1 in case 'highest label'
+      */
+      bool end=false;   //for the 0 case
+      /*
+	Needed for 'bound decrease', 'true'
+	means no active nodes are above bound b.
+      */
+      int relabel=0;
+      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;
+	  
+	  if ( !what_heur && !end && k > 0 ) {
+	    b=k;
+	    end=true;
+	  } else {
+	    time=currTime();
+	    phase=1;
+	    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 {
+	  end=false;                      //needed only for phase 0, case hl2
+
+	  NodeIt w=active[b];        //w is a highest label active node.
+	  active[b]=next.get(w);
+	  int lev=level.get(w);
+	  T exc=excess.get(w);
+	  int newlevel=n;          //In newlevel we bound 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;
+	      }
+	      /*v becomes active.*/
+	      
+	      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;
+		/*v becomes active.*/
+	      }
+	      
+	      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;   
+
+	      } 
+	    }
+		
+	    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;
+		if ( !what_heur ) active[i]=0;
+	      }	     
+
+	      level.set(w,n);
+	      b=lev-1;
+	      k=b;
+
+	    } else {
+	      
+	      if ( newlevel == n ) level.set(w,n); 
+	      else {
+		level.set(w,++newlevel);
+		next.set(w,active[newlevel]);
+		active[newlevel]=w;
+		if ( what_heur ) 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;
+	      if ( what_heur ) {
+		what_heur=0;
+		heur=heur0;
+		end=false;
+	      } else {
+		what_heur=1;
+		heur=heur1;
+		b=k; 
+	      }
+	    }
+	  } //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 minCut(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 minMinCut(CutMap& M) {
+      minCut(M);
+    }
+
+
+
+  };
+}//namespace
+#endif 
+
+
+
+
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_push_hl.h
--- a/src/work/jacint/preflow_push_hl.h	Fri Feb 20 22:01:02 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,398 +0,0 @@
-// -*- C++ -*-
-
-//kerdesek: nem tudom lehet-e a 
-//kieleket csak a legf n szintu pontokra nezni.
-
-/*
-preflow_push_hl.h
-by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)), and with the 'empty level' heuristic. 
-
-'A' is a parameter for the empty_level heuristic
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap allflow() : returns the fixed maximum flow x
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-void min_mincut(CutMap& M) : sets M to the characteristic vector of the 
-     minimum min cut. M should be a map of bools initialized to false.
-
-void max_mincut(CutMap& M) : sets M to the characteristic vector of the 
-     maximum min cut. M should be a map of bools initialized to false.
-
-*/
-
-#ifndef PREFLOW_PUSH_HL_H
-#define PREFLOW_PUSH_HL_H
-
-#define A 1
-
-#include <vector>
-#include <stack>
-#include <queue>
-
-namespace hugo {
-
-  template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
-  class preflow_push_hl {
-    
-    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;  
-    T value;
-    
-  public:
-
-    preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { }
-
-
-    
-
-    void run() {
- 
-      int n=G.nodeNum(); 
-      int b=n-2; 
-      /*
-	b is a bound on the highest level of an active node. 
-      */
-
-      IntMap level(G,n);      
-      TMap excess(G); 
-
-      std::vector<int> numb(n);    
-      /*
-	The number of nodes on level i < n. It is
-	initialized to n+1, because of the reverse_bfs-part.
-      */
-
-      std::vector<std::stack<NodeIt> > stack(2*n-1);    
-      //Stack of the active 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 ) {
-	    bfs_queue.push(w);
-	    ++numb[l];
-	    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 ( w!=s ) {	  
-	    if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); 
-	    flow.set(e, c); 
-	    excess.set(w, excess.get(w)+c);
-	  }
-	}
-      
-      /* 
-	 End of preprocessing 
-      */
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */
-      /*While there exists an active node.*/
-      while (b) { 
-	if ( stack[b].empty() ) { 
-	  --b;
-	  continue;
-	} 
-	
-	NodeIt w=stack[b].top();        //w is a highest label active node.
-	stack[b].pop();           
-	int lev=level.get(w);
-	int exc=excess.get(w);
-	int newlevel=2*n;      //In newlevel we bound the next level of w.
-	//vagy MAXINT	
-
-	//  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
-	  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 != s && v !=t ) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
-	      
-	      int cap=capacity.get(e);
-	      int flo=flow.get(e);
-	      int 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 != s && v !=t) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
-	      
-	      int 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
-	  level.set(w,++newlevel);
-	  
-	  if ( lev < n ) {
-	    --numb[lev];
-	    
-	    if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
-	      
-	      for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
-		if (level.get(v) > lev && level.get(v) < n ) level.set(v,n);  
-	      }
-	      for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
-	      if ( newlevel < n ) newlevel=n; 
-	    } else { 
-	      if ( newlevel < n ) ++numb[newlevel]; 
-	    }
-	  } 
-	  
-	  stack[newlevel].push(w);
-	  b=newlevel;
-	  
-	}
-	
-      } // while(b)
-      
-      
-      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(const EdgeIt e) {
-      return flow.get(e);
-    }
-
-
-
-    /*
-      Returns the maximum flow x found by the algorithm.
-    */
-
-    FlowMap allflow() {
-      return flow;
-    }
-
-
-
-
-    /*
-      Returns the minimum min cut, by a bfs from s in the residual graph.
-    */
-    
-    template<typename CutMap>
-    void mincut(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 max_mincut(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 min_mincut(CutMap& M) {
-      mincut(M);
-    }
-
-
-
-  };
-}//namespace hugo
-#endif 
-
-
-
-
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_push_hl.hh
--- a/src/work/jacint/preflow_push_hl.hh	Fri Feb 20 22:01:02 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,320 +0,0 @@
-/*
-preflow_push_hl.hh
-by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)). 
-
-Member functions:
-
-void run() : runs the algorithm
-
- The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-T flowonedge(edge_iterator e) : for a fixed maximum flow x it returns x(e) 
-
-edge_property_vector<graph_type, T> allflow() : returns the fixed maximum flow x
-
-node_property_vector<graph_type, bool> mincut() : returns a 
-     characteristic vector of a minimum cut. (An empty level 
-     in the algorithm gives a minimum cut.)
-*/
-
-#ifndef PREFLOW_PUSH_HL_HH
-#define PREFLOW_PUSH_HL_HH
-
-#include <algorithm>
-#include <vector>
-#include <stack>
-
-#include <marci_graph_traits.hh>
-#include <marci_property_vector.hh>
-#include <reverse_bfs.hh>
-
-namespace hugo {
-
-  template <typename graph_type, typename T>
-  class preflow_push_hl {
-    
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
-    typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
-    
-
-    graph_type& G;
-    node_iterator s;
-    node_iterator t;
-    edge_property_vector<graph_type, T> flow;
-    edge_property_vector<graph_type, T>& capacity; 
-    T value;
-    node_property_vector<graph_type, bool> mincutvector;
-
-   
-  public:
-
-    preflow_push_hl(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
-
-
-
-
-    /*
-      The run() function runs the highest label preflow-push, 
-      running time: O(n^2\sqrt(m))
-    */
-    void run() {
- 
-      node_property_vector<graph_type, int> level(G);         //level of node
-      node_property_vector<graph_type, T> excess(G);          //excess of node
-            
-      int n=number_of(G.first_node());                        //number of nodes 
-      int b=n; 
-      /*b is a bound on the highest level of an active node. In the beginning it is at most n-2.*/
-
-      std::vector<std::stack<node_iterator> > stack(2*n-1);    //Stack of the active nodes in level i.
-
-
-
-
-      /*Reverse_bfs from t, to find the starting level.*/
-
-      reverse_bfs<list_graph> bfs(G, t);
-      bfs.run();
-      for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
-	level.put(v, bfs.dist(v)); 
-	//std::cout << "the level of " << v << " is " << bfs.dist(v);
-      }
-
-      /*The level of s is fixed to n*/ 
-      level.put(s,n);
-
-
-
-
-
-      /* Starting flow. It is everywhere 0 at the moment. */
-     
-      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
-	{
-	  node_iterator w=G.head(i);
-	  flow.put(i, capacity.get(i)); 
-	  stack[bfs.dist(w)].push(w); 
-	  excess.put(w, capacity.get(i));
-	}
-
-
-      /* 
-	 End of preprocessing 
-      */
-
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */
-	
-      /*While there exists active node.*/
-      while (b) { 
-
-	/*We decrease the bound if there is no active node of level b.*/
-	if (stack[b].empty()) {
-	  --b;
-	} else {
-
-	  node_iterator w=stack[b].top();    //w is the highest label active node.
-	  stack[b].pop();                    //We delete w from the stack.
-	
-	  int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
-	
-	  for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
-	    node_iterator v=G.head(e);
-	    /*e is the edge wv.*/
-
-	    if (flow.get(e)<capacity.get(e)) {              
-	      /*e is an edge of the residual graph */
-
-	      if(level.get(w)==level.get(v)+1) {      
-		/*Push is allowed now*/
-
-		if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
-		  /*A nonsaturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-		  
-		  flow.put(e, flow.get(e)+excess.get(w));
-		  excess.put(v, excess.get(v)+excess.get(w));
-		  excess.put(w,0);
-		  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
-		  break; 
-		} else { 
-		  /*A saturating push.*/
-
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
-		  excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
-		  excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
-		  flow.put(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 (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);}
-	    
-	    } //if (flow.get(e)<capacity.get(e))
-	 
-	  } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
-	  
-
-
-	  for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
-	    node_iterator v=G.tail(e);
-	    /*e is the edge vw.*/
-
-	    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 (flow.get(e) > excess.get(w)) { 
-		  /*A nonsaturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
-		  flow.put(e, flow.get(e)-excess.get(w));
-		  excess.put(v, excess.get(v)+excess.get(w));
-		  excess.put(w,0);
-		  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
-		  break; 
-		} else {                                               
-		  /*A saturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-		  
-		  excess.put(v, excess.get(v)+flow.get(e));
-		  excess.put(w, excess.get(w)-flow.get(e));
-		  flow.put(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);}
-	      
-
-	    } //if (flow.get(e)>0)
-
-	  } //for
-
-
-	  if (excess.get(w)>0) {
-	    level.put(w,++newlevel);
-	    stack[newlevel].push(w);
-	    b=newlevel;
-	    //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl; 
-	  }
-
-
-	} //else
-       
-      } //while(b)
-
-      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(edge_iterator e) {
-      return flow.get(e);
-    }
-
-
-
-    /*
-      Returns the maximum flow x found by the algorithm.
-    */
-
-    edge_property_vector<graph_type, T> allflow() {
-      return flow;
-    }
-
-
-
-    /*
-      Returns a minimum cut by using a reverse bfs from t in the residual graph.
-    */
-    
-    node_property_vector<graph_type, bool> mincut() {
-    
-      std::queue<node_iterator> queue;
-      
-      mincutvector.put(t,false);      
-      queue.push(t);
-
-      while (!queue.empty()) {
-        node_iterator w=queue.front();
-	queue.pop();
-
-	for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
-	  node_iterator v=G.tail(e);
-	  if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
-	    queue.push(v);
-	    mincutvector.put(v, false);
-	  }
-	} // for
-
-	for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
-	  node_iterator v=G.head(e);
-	  if (mincutvector.get(v) && flow.get(e) > 0 ) {
-	    queue.push(v);
-	    mincutvector.put(v, false);
-	  }
-	} // for
-
-      }
-
-      return mincutvector;
-    
-    }
-
-
-  };
-}//namespace hugo
-#endif 
-
-
-
-
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_push_max_flow.h
--- a/src/work/jacint/preflow_push_max_flow.h	Fri Feb 20 22:01:02 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,296 +0,0 @@
-// -*- C++ -*-
-/*
-preflow_push_max_flow_h
-by jacint. 
-Runs a preflow push algorithm with the modification, 
-that we do not push on nodes with level at least n. 
-Moreover, if a level gets empty, we set all nodes above that
-level to level n. Hence, in the end, we arrive at a maximum preflow 
-with value of a max flow value. An empty level gives a minimum cut.
-
-Member functions:
-
-void run() : runs the algorithm
-
-  The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-void mincut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-*/
-
-#ifndef PREFLOW_PUSH_MAX_FLOW_H
-#define PREFLOW_PUSH_MAX_FLOW_H
-
-#define A 1
-
-#include <algorithm>
-#include <vector>
-#include <stack>
-
-#include <reverse_bfs.h>
-
-
-namespace hugo {
-
-  template <typename Graph, typename T,  
-    typename FlowMap=typename Graph::EdgeMap<T>, typename CapMap=typename Graph::EdgeMap<T>, 
-    typename IntMap=typename Graph::NodeMap<int>, typename TMap=typename Graph::NodeMap<T> >
-  class preflow_push_max_flow {
-    
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-    
-    Graph& G;
-    NodeIt s;
-    NodeIt t;
-    IntMap level;
-    CapMap& capacity;  
-    int empty_level;    //an empty level in the end of run()
-    T value; 
-    
-  public:
-      
-    preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), level(_G), capacity(_capacity) { }
-
-
-    /*
-      The run() function runs a modified version of the 
-      highest label preflow-push, which only 
-      finds a maximum preflow, hence giving the value of a maximum flow.
-    */
-    void run() {
- 
-      int n=G.nodeNum(); 
-      int b=n-2; 
-      /*
-	b is a bound on the highest level of an active node. 
-      */
-
-      IntMap level(G,n);      
-      TMap excess(G); 
-      FlowMap flow(G,0);
-
-      std::vector<int> numb(n);    
-      /*
-	The number of nodes on level i < n. It is
-	initialized to n+1, because of the reverse_bfs-part.
-      */
-
-      std::vector<std::stack<NodeIt> > stack(n);    
-      //Stack of the active 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 ) {
-	    bfs_queue.push(w);
-	    ++numb[l];
-	    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) 
-	{
-	  if ( capacity.get(e) == 0 ) continue;
-	  NodeIt w=G.head(e);
-	  if ( level.get(w) < n ) {	  
-	    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));
-	  }
-	}
-      
-      /* 
-	 End of preprocessing 
-      */
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */
-      /*While there exists an active node.*/
-      while (b) { 
-	if ( stack[b].empty() ) { 
-	  --b;
-	  continue;
-	} 
-	
-	NodeIt w=stack[b].top();        //w is a highest label active node.
-	stack[b].pop();           
-	int lev=level.get(w);
-	int exc=excess.get(w);
-	int newlevel=2*n-2;      //In newlevel we bound the next level of w.
-	
-	//  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e
-	  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 != s && v !=t ) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
-	      
-	      int cap=capacity.get(e);
-	      int flo=flow.get(e);
-	      int 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 != s && v !=t) 
-		stack[level.get(v)].push(v); 
-	      /*v becomes active.*/
-	      
-	      int 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
-	  level.set(w,++newlevel);
-	  --numb[lev];
-	    
-	  if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. 
-	      
-	    for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
-	      if (level.get(v) > lev ) level.set(v,n);  
-	    }
-	    for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; 
-	    if ( newlevel < n ) newlevel=n; 
-	  } else if ( newlevel < n ) {
-	    ++numb[newlevel]; 
-	    stack[newlevel].push(w);
-	    b=newlevel;
-	  }
-	}
-
-
-
-      } //while(b)
-
-      value=excess.get(t);
-      /*Max flow value.*/
-      
-
-      /* 
-	 We count empty_level. The nodes above this level is a mincut.
-      */
-      while(true) {
-	if(numb[empty_level]) ++empty_level;
-	else break;
-      } 
-      
-    } // void run()
-
-
-
-    /*
-      Returns the maximum value of a flow.
-     */
-
-    T maxflow() {
-      return value;
-    }
-
-
-
-    /*
-      Returns a minimum cut.
-    */    
-    template<typename CutMap>
-    void mincut(CutMap& M) {
-
-      for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
-	if ( level.get(v) > empty_level ) M.set(v, true);
-      }
-    }
-
-
-  };
-}//namespace hugo
-#endif 
-
-
-
-
-
diff -r 0351b00fd283 -r fc5982b39e10 src/work/jacint/preflow_push_max_flow.hh
--- a/src/work/jacint/preflow_push_max_flow.hh	Fri Feb 20 22:01:02 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,315 +0,0 @@
-/*
-preflow_push_max_flow_hh
-by jacint. 
-Runs a preflow push algorithm with the modification, 
-that we do not push on nodes with level at least n. 
-Moreover, if a level gets empty, we put all nodes above that
-level to level n. Hence, in the end, we arrive at a maximum preflow 
-with value of a max flow value. An empty level gives a minimum cut.
-
-Member functions:
-
-void run() : runs the algorithm
-
-  The following functions should be used after run() was already run.
-
-T maxflow() : returns the value of a maximum flow
-
-node_property_vector<graph_type, bool> mincut(): returns a 
-     characteristic vector of a minimum cut.
-*/
-
-#ifndef PREFLOW_PUSH_MAX_FLOW_HH
-#define PREFLOW_PUSH_MAX_FLOW_HH
-
-#include <algorithm>
-#include <vector>
-#include <stack>
-
-#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
-#include <marci_property_vector.hh>
-#include <reverse_bfs.hh>
-
-
-namespace hugo {
-
-  template <typename graph_type, typename T>
-  class preflow_push_max_flow {
-    
-    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
-    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
-    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
-    
-    graph_type& G;
-    node_iterator s;
-    node_iterator t;
-    edge_property_vector<graph_type, T>& capacity; 
-    T value;
-    node_property_vector<graph_type, bool> mincutvector;    
-
-
-     
-  public:
-        
-    preflow_push_max_flow(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
-
-
-    /*
-      The run() function runs a modified version of the highest label preflow-push, which only 
-      finds a maximum preflow, hence giving the value of a maximum flow.
-    */
-    void run() {
- 
-      edge_property_vector<graph_type, T> flow(G, 0);         //the flow value, 0 everywhere  
-      node_property_vector<graph_type, int> level(G);         //level of node
-      node_property_vector<graph_type, T> excess(G);          //excess of node
-            
-      int n=number_of(G.first_node());                        //number of nodes 
-      int b=n-2; 
-      /*b is a bound on the highest level of an active node. 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<node_iterator> > stack(2*n-1);    //Stack of the active nodes in level i.
-
-
-
-      /*Reverse_bfs from t, to find the starting level.*/
-
-      reverse_bfs<list_graph> bfs(G, t);
-      bfs.run();
-      for(each_node_iterator v=G.first_node(); v.valid(); ++v) 
-	{
-	  int dist=bfs.dist(v);
-	  level.put(v, dist); 
-	  ++numb[dist];
-	}
-
-      /*The level of s is fixed to n*/ 
-      level.put(s,n);
-
-
-      /* Starting flow. It is everywhere 0 at the moment. */
-     
-      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
-	{
-	  node_iterator w=G.head(i);
-	  flow.put(i, capacity.get(i)); 
-	  stack[bfs.dist(w)].push(w); 
-	  excess.put(w, capacity.get(i));
-	}
-
-
-      /* 
-	 End of preprocessing 
-      */
-
-
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */
-	
-      /*While there exists an active node.*/
-      while (b) { 
-
-	/*We decrease the bound if there is no active node of level b.*/
-	if (stack[b].empty()) {
-	  --b;
-	} else {
-
-	  node_iterator w=stack[b].top();    //w is the highest label active node.
-	  stack[b].pop();                    //We delete w from the stack.
-	
-	  int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
-	
-	  for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
-	    node_iterator v=G.head(e);
-	    /*e is the edge wv.*/
-
-	    if (flow.get(e)<capacity.get(e)) {              
-	      /*e is an edge of the residual graph */
-
-	      if(level.get(w)==level.get(v)+1) {      
-		/*Push is allowed now*/
-
-		if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
-		  /*A nonsaturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-		  
-		  flow.put(e, flow.get(e)+excess.get(w));
-		  excess.put(v, excess.get(v)+excess.get(w));
-		  excess.put(w,0);
-		  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
-		  break; 
-		} else { 
-		  /*A saturating push.*/
-
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
-		  excess.put(v, excess.get(v)+capacity.get(e)-flow.get(e));
-		  excess.put(w, excess.get(w)-capacity.get(e)+flow.get(e));
-		  flow.put(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 (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);}
-	    
-	    } //if (flow.get(e)<capacity.get(e))
-	 
-	  } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
-	  
-
-
-	  for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
-	    node_iterator v=G.tail(e);
-	    /*e is the edge vw.*/
-
-	    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 (flow.get(e) > excess.get(w)) { 
-		  /*A nonsaturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-
-		  flow.put(e, flow.get(e)-excess.get(w));
-		  excess.put(v, excess.get(v)+excess.get(w));
-		  excess.put(w,0);
-		  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
-		  break; 
-		} else {                                               
-		  /*A saturating push.*/
-		  
-		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
-		  /*v becomes active.*/
-		  
-		  flow.put(e,0);
-		  excess.put(v, excess.get(v)+flow.get(e));
-		  excess.put(w, excess.get(w)-flow.get(e));
-		  //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);}
-	      //std::cout << "Leveldecrease of node " << w << " to " << newlevel << std::endl; 
-
-	    } //if (flow.get(e)>0)
-
-	  } //for in-edge
-
-
-
-
-	  /*
-	    Relabel
-	  */
-	  if (excess.get(w)>0) {
-	    /*Now newlevel <= n*/
-
-	    int l=level.get(w);	        //l is the old level of w.
-	    --numb[l];
-	   
-	    if (newlevel == n) {
-	      level.put(w,n);
-	      
-	    } else {
-	      
-	      if (numb[l]) {
-		/*If the level of w remains nonempty.*/
-		
-		level.put(w,++newlevel);
-		++numb[newlevel];
-		stack[newlevel].push(w);
-		b=newlevel;
-	      } else { 
-		/*If the level of w gets empty.*/
-	      
-		for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
-		  if (level.get(v) >= l ) { 
-		    level.put(v,n);  
-		  }
-		}
-		
-		for (int i=l+1 ; i!=n ; ++i) numb[i]=0; 
-	      } //if (numb[l])
-	
-	    } // if (newlevel = n)
-	 
-	  } // if (excess.get(w)>0)
-
-
-	} //else
-       
-      } //while(b)
-
-      value=excess.get(t);
-      /*Max flow value.*/
-      
-
-
-      /*
-	We find an empty level, e. The nodes above this level give 
-	a minimum cut.
-      */
-      
-      int e=1;
-      
-      while(e) {
-	if(numb[e]) ++e;
-	else break;
-      } 
-      for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
-	if (level.get(v) > e) mincutvector.put(v, true);
-      }
-      
-
-    } // void run()
-
-
-
-    /*
-      Returns the maximum value of a flow.
-     */
-
-    T maxflow() {
-      return value;
-    }
-
-
-
-    /*
-      Returns a minimum cut.
-    */
-    
-    node_property_vector<graph_type, bool> mincut() {
-      return mincutvector;
-    }
-    
-
-  };
-}//namespace hugo
-#endif 
-
-
-
-
-