# HG changeset patch
# User jacint
# Date 1078162477 0
# Node ID c1ec00df3b3abbc26cf4d405525680fff2d1172b
# Parent  01d47457aff3b950dc8534f3f7fb796e438f3ead
nagytakaritas

diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/dimacs_jgraph.hh
--- a/src/work/jacint/dimacs_jgraph.hh	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,61 +0,0 @@
-#ifndef DIMACS_HH
-#define DIMACS_HH
-
-#include <iostream>
-#include <string>
-#include <vector>
-
-namespace hugo {
-
-  template<typename Graph, typename CapacityMap>
-  void readDimacsMaxFlow(std::istream& is, Graph &G, typename Graph::TrivNodeIt &s, typename Graph::TrivNodeIt &t, CapacityMap& capacity) {
-    G.clear();
-    int cap;
-    char d;
-    std::string problem;
-    char c;
-    int i, j;
-    std::string str;
-    int n, m; 
-    std::vector<typename Graph::TrivNodeIt> nodes;
-    while (is>>c) {
-      switch (c) {
-      case 'c': //comment
-	getline(is, str);
-	break;
-      case 't': //type
-	getline(is, str);
-	break;
-      case 'p': //problem definition
-	is >> problem >> n >> m;
-	getline(is, str);
-	nodes.resize(n+1);
-	for (int k=1; k<=n; ++k) nodes[k]=G.addNode();
-	break;
-      case 'n': //node definition
-	if (problem=="sp") { //shortest path problem
-	  is >> i;
-	  getline(is, str);
-	  s=nodes[i];
-	}
-	if (problem=="max") { //max flow problem
-	  is >> i >> d;
-	  getline(is, str);
-	  if (d=='s') s=nodes[i];
-	  if (d=='t') t=nodes[i];
-	}
-	break;
-      case 'a':
-	is >> i >> j >> cap;
-	getline(is, str);
-	typename Graph::TrivEdgeIt e=G.addEdge(nodes[i], nodes[j]);
-	capacity.update();
-	capacity.set(e, cap);
-	break;
-      }
-    }
-  }
-  
-} //namespace marci
-
-#endif //DIMACS_HH
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/flow_test.cc
--- a/src/work/jacint/flow_test.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,244 +0,0 @@
-#include <iostream>
-#include <vector>
-#include <string>
-
-#include <list_graph.hh>
-#include <preflow_push_hl.h>
-#include <preflow_push_max_flow.h>
-#include <reverse_bfs.h>
-//#include <dijkstra.h>
-
-using namespace hugo;
-
-
-int main (int, char*[])
-{
-  typedef ListGraph::NodeIt NodeIt;
-  typedef ListGraph::EdgeIt EdgeIt;
-  typedef ListGraph::EachNodeIt EachNodeIt;
-  typedef ListGraph::EachEdgeIt EachEdgeIt;
-  typedef ListGraph::OutEdgeIt OutEdgeIt;
-  typedef ListGraph::InEdgeIt InEdgeIt;
-  
-  ListGraph flow_test;
- 
-    //Ahuja könyv példája, maxflowvalue=13
-  NodeIt s=flow_test.addNode();
-  NodeIt v1=flow_test.addNode();
-  NodeIt v2=flow_test.addNode();
-  NodeIt v3=flow_test.addNode();
-  NodeIt v4=flow_test.addNode();
-  NodeIt v5=flow_test.addNode();
-  NodeIt t=flow_test.addNode();
-  
-  ListGraph::NodeMap<std::string> Node_name(flow_test);
-  Node_name.set(s, "s");
-  Node_name.set(v1, "v1");
-  Node_name.set(v2, "v2");
-  Node_name.set(v3, "v3");
-  Node_name.set(v4, "v4");
-  Node_name.set(v5, "v5");
-  Node_name.set(t, "t");
-
-  EdgeIt s_v1=flow_test.addEdge(s, v1);
-  EdgeIt s_v2=flow_test.addEdge(s, v2);
-  EdgeIt s_v3=flow_test.addEdge(s, v3);
-  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
-  EdgeIt v2_v5=flow_test.addEdge(v2, v5);
-  EdgeIt v3_v5=flow_test.addEdge(v3, v5);
-  EdgeIt v4_t=flow_test.addEdge(v4, t);
-  EdgeIt v5_t=flow_test.addEdge(v5, t);
-  EdgeIt v2_s=flow_test.addEdge(v2, s);
-  
-   ListGraph::EdgeMap<int> cap(flow_test);  
-  cap.set(s_v1, 0);
-  cap.set(s_v2, 10);
-  cap.set(s_v3, 10);
-  cap.set(v2_v4, 5);
-  cap.set(v2_v5, 8);
-  cap.set(v3_v5, 5);
-  cap.set(v4_t, 8);
-  cap.set(v5_t, 8);
-  cap.set(v2_s, 0);
-
-
-  
-  //Marci példája, maxflowvalue=23
-  /*  NodeIt s=flow_test.addNode();
-  NodeIt v1=flow_test.addNode();
-  NodeIt v2=flow_test.addNode();
-  NodeIt v3=flow_test.addNode();
-  NodeIt v4=flow_test.addNode();
-  NodeIt t=flow_test.addNode();
-  NodeIt w=flow_test.addNode();
-
-  
-  NodeMap<ListGraph, std::string> Node_name(flow_test);
-  Node_name.set(s, "s");
-  Node_name.set(v1, "v1");
-  Node_name.set(v2, "v2");
-  Node_name.set(v3, "v3");
-  Node_name.set(v4, "v4");
-  Node_name.set(t, "t");
-  Node_name.set(w, "w");
-
-  EdgeIt s_v1=flow_test.addEdge(s, v1);
-  EdgeIt s_v2=flow_test.addEdge(s, v2);
-  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
-  EdgeIt v2_v1=flow_test.addEdge(v2, v1);
-  EdgeIt v1_v3=flow_test.addEdge(v1, v3);
-  EdgeIt v3_v2=flow_test.addEdge(v3, v2);
-  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
-  EdgeIt v4_v3=flow_test.addEdge(v4, v3);
-  EdgeIt v3_t=flow_test.addEdge(v3, t);
-  EdgeIt v4_t=flow_test.addEdge(v4, t);
-  EdgeIt v3_v3=flow_test.addEdge(v3, v3);
-  EdgeIt s_w=flow_test.addEdge(s, w);
-  //  EdgeIt v2_s=flow_test.addEdge(v2, s);
-  
-
-
-  EdgeMap<ListGraph, int> cap(flow_test);  //serves as length in dijkstra
-  cap.set(s_v1, 16);
-  cap.set(s_v2, 13);
-  cap.set(v1_v2, 10);
-  cap.set(v2_v1, 4);
-  cap.set(v1_v3, 12);
-  cap.set(v3_v2, 9);
-  cap.set(v2_v4, 14);
-  cap.set(v4_v3, 7);
-  cap.set(v3_t, 20);
-  cap.set(v4_t, 4);
-  cap.set(v3_v3, 4);
-  cap.set(s_w, 4);
-  //  cap.set(v2_s, 0);
-
-*/
-
-  //pelda 3, maxflowvalue=4
-  /*      NodeIt s=flow_test.addNode();
-  NodeIt v1=flow_test.addNode();
-  NodeIt v2=flow_test.addNode();
-  NodeIt t=flow_test.addNode();
-  NodeIt w=flow_test.addNode();
-  
-  NodeMap<ListGraph, std::string> Node_name(flow_test);
-  Node_name.set(s, "s");
-  Node_name.set(v1, "v1");
-  Node_name.set(v2, "v2");
-  Node_name.set(t, "t");
-  Node_name.set(w, "w");
-
-  EdgeIt s_v1=flow_test.addEdge(s, v1);
-  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
-  EdgeIt v2_t=flow_test.addEdge(v2, t);
-  EdgeIt v1_v1=flow_test.addEdge(v1, v1);
-  EdgeIt s_w=flow_test.addEdge(s, w);
-
-
-  EdgeMap<ListGraph, int> cap(flow_test); 
-    
-  cap.set(s_v1, 16);
-  cap.set(v1_v2, 10);
-  cap.set(v2_t, 4);
-  cap.set(v1_v1, 3);
-  cap.set(s_w, 5);
-  */
-  
-
-
-  /*
-  std::cout << "Testing reverse_bfs..." << std::endl;
-  
-  reverse_bfs<ListGraph> bfs_test(flow_test, t);
-
-  bfs_test.run();
-
-  for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
-    std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
-    }
-
-  */
-
-
-
-  std::cout << "Testing preflow_push_hl..." << std::endl;
-  
-  preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
-
-  preflow_push_test.run();
-
-  std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
-
-  std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
-
-   ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();  
-  for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
-    std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
-    }
-
-  std::cout << "A minimum cut: " <<std::endl;  
-   ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
-
-  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
-      if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
-    }
-  
-  std::cout<<"\n\n"<<std::endl;
-
-
-
-
-  std::cout << "Testing preflow_push_max_flow..." << std::endl;
- 
-  preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
-
-  max_flow_test.run();
-
-  std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
-
-  std::cout << "A minimum cut: " <<std::endl;  
-   ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
-
-  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
-    if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
-  }
-  
-  std::cout << std::endl <<std::endl;
-
-
-  /*
-    std::cout << "Testing dijkstra..." << std::endl;
-  
-    NodeIt root=v2;
-
-    dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
-
-    dijkstra_test.run();
-
-    for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
-      if (dijkstra_test.reach(w)) {
-      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
-      if (dijkstra_test.pred(w).valid()) {
-      std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl; 
-      } else {
-       std::cout <<", this is the root."<<std::endl; }
-      
-      } else {
-	cout << w << " is not reachable from " << root <<std::endl;
-      }
-    }
-
-  */
-
-  return 0;
-}
-
-
-
-
-
-
-
-
-
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_aug.h
--- a/src/work/jacint/preflow_aug.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,588 +0,0 @@
-// -*- C++ -*-
-
-//hogy kell azt megcsinalni hogy a konstruktorban a FlowMap-nek legyen default erteke (a 0 map)
-
-/*
-preflow_aug.h
-by jacint. 
-
-The same as preflow.h, the only difference is that here 
-we start from a given flow. 
-
-
-The constructor runs the algorithm: 
-
-template <typename Graph, typename T, 
-    typename Graph_EdgeMap_T_1=typename Graph::EdgeMap<T>,
-    typename Graph_EdgeMap_T_2=typename Graph::EdgeMap<T> > 
-PreflowAug(Graph G, G_NodeIt s, G_NodeIt t, G_EdgeMap_T_1 capacity, 
-   G_EdgeMap_T_2 flow, bool flow_type)
-
-'capacity' must be non-negative, if flow_type=0 then 
-'flow' must be a flow, otherwise it must be a preflow.
-
-
-Members:
-
-T maxFlow() : returns the value of a maximum flow
-
-T flow(G_EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-G_EdgeMap_T_2 flow() : returns the fixed maximum flow x
-
-void minMinCut(G_NodeMap_bool& M) :
-     sets M to the characteristic vector of the 
-     minimum min cut. M must be initialized to false.
-
-void maxMinCut(G_NodeMap_bool& M) : 
-     sets M to the characteristic vector of the 
-     maximum min cut. M must be initialized to false.
-
-void minCut(G_NodeMap_bool& M) :
-     sets M to the characteristic vector of a  
-     min cut. M must be initialized to false.
-*/
-
-#ifndef PREFLOW_H
-#define PREFLOW_H
-
-#define H0 20
-#define H1 1
-
-#include <vector>
-#include <queue>
-
-#include <iostream> //for error handling
-
-#include <time_measure.h>
-
-namespace hugo {
-
-  template <typename Graph, typename T, 
-    typename CapMap=typename Graph::EdgeMap<T>,
-    typename FlowMap=typename Graph::EdgeMap<T> >
-  class PreflowAug {
-    
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-
-    Graph& G;
-    NodeIt s;
-    NodeIt t;
-    CapMap& capacity;  
-    FlowMap& _flow;
-    bool flow_type;
-    T value;
-
-  public:
-    double time;
-    PreflowAug(Graph& _G, NodeIt _s, NodeIt _t, 
-	       CapMap& _capacity, FlowMap& __flow, bool _flow_type ) :
-      G(_G), s(_s), t(_t), capacity(_capacity), _flow(__flow), 
-      flow_type(_flow_type)
-    {
-
-
-      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) {
-	  if ( capacity.get(e) == _flow.get(e) ) continue;
-	  NodeIt w=G.tail(e);
-	  if ( level.get(w) == n && w != s ) {
-	    bfs_queue.push(w);
-	    NodeIt first=level_list[l];
-	    if ( first.valid() ) left.set(first,w);
-	    right.set(w,first);
-	    level_list[l]=w;
-	    level.set(w, l);
-	  }
-	}
-	    
-	for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
-	  if ( 0 == _flow.get(e) ) continue;
-	  NodeIt w=G.head(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);
-
-
-
-      /*The starting excess.*/
-      if ( flow_type ) {
-	for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
-	  if ( _flow.get(e) > 0 ) {
-	    T flo=_flow.get(e);
-	    NodeIt u=G.tail(e);
-	    NodeIt v=G.head(e);
-	    excess.set(u, excess.get(u)-flo);
-	    excess.set(v, excess.get(v)+flo);
-	  }
-	}
-
-	for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
-	  if ( excess.get(v) < 0 ) {
-	    std::cerr<<"It is not a pre_flow."<<std::endl;
-	    exit(1);
-	  } else {
-	    next.set(v,active[level.get(v)]);
-	    active[level.get(v)]=v;}
-	}
-      }
-
-
-      /* 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)-_flow.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, capacity.get(e)); 
-	    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;
-	    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;
-		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 flow(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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl0.cc
--- a/src/work/jacint/preflow_hl0.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,71 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl0.h
--- a/src/work/jacint/preflow_hl0.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,508 +0,0 @@
-// -*- 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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl1.cc
--- a/src/work/jacint/preflow_hl1.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,73 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl2.cc
--- a/src/work/jacint/preflow_hl2.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,65 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl2.h
--- a/src/work/jacint/preflow_hl2.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,394 +0,0 @@
-// -*- C++ -*-
-/*
-preflow_hl2.h
-by jacint. 
-Runs the highest label variant of the preflow push algorithm with 
-running time O(n^2\sqrt(m)). 
-
-Heuristics:
-
-  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.
-
-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 minCut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-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.
-
-*/
-
-#ifndef PREFLOW_HL2_H
-#define PREFLOW_HL2_H
-
-#define A .9
-
-#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> >
-  class preflow_hl2 {
-    
-    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_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 
-
-      int n=G.nodeNum(); 
-      int b=n-2; 
-      /*
-	b is a bound on the highest level of an active node. 
-      */
-
-      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
-	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();   
-	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; 
-	    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.*/
-	      
-	      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 != s && v !=t) 
-		stack[level.get(v)].push(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
-	  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 Flow() {
-      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 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 marci
-#endif 
-
-
-
-
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl3.cc
--- a/src/work/jacint/preflow_hl3.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,72 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl3.h
--- a/src/work/jacint/preflow_hl3.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,469 +0,0 @@
-// -*- C++ -*-
-/*
-preflow_hl3.h
-by jacint. 
-
-Heuristics: 
-
- suck gap : if there is a gap, then we put all 
-   nodes reachable from the relabelled node to level n
- 2 phase
- highest label
-
-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 minCut(CutMap& M) : sets M to the characteristic vector of a 
-     minimum cut. M should be a map of bools initialized to false.
-
-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.
-
-*/
-
-#ifndef PREFLOW_HL3_H
-#define PREFLOW_HL3_H
-
-#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> >
-  class preflow_hl3 {
-    
-    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; //for test
-
-    preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) {
-      
-      bool phase=0;
-      int n=G.nodeNum(); 
-      int b=n-2; 
-      /*
-	b is a bound on the highest level of the stack. 
-	In the beginning it is at most n-2.
-      */
-
-      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
-	initialized to n+1, because of the reverse_bfs-part.
-	Needed only in phase 0.
-      */
-
-      std::vector<std::stack<NodeIt> > stack(n);    
-      //Stack of the active nodes in level i < n.
-      //We use it in both phases.
-
-
-      /*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 ( level.get(w) < n ) {	  
-	    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 ( true ) {
-
-	if ( b == 0 ) {
-	  if ( phase ) break; 
-	  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 ) stack[l].push(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 ) stack[l].push(u);
-	      }
-	    }
-	  }
-
-	  b=n-2;
-	}
-
-	if ( stack[b].empty() ) --b;
-	else {
-	  
-	  NodeIt w=stack[b].top(); 
-	  stack[b].pop();           
-	  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 ) 
-		stack[level.get(v)].push(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 ) 
-		stack[level.get(v)].push(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);
-	    stack[newlevel].push(w);
-	    b=newlevel;
-	  } else {
-
-	    if ( newlevel >= n-2 || --numb[lev] == 0 ) {
-	      
-	      level.set(w,n);
-	      
-	      if ( newlevel < n ) {
-		
-		std::queue<NodeIt> bfs_queue;
-		bfs_queue.push(w);
-
-		while (!bfs_queue.empty()) {
-
-		  NodeIt v=bfs_queue.front();	
-		  bfs_queue.pop();
-
-		  for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
-		    if ( capacity.get(e) == flow.get(e) ) continue;
-		    NodeIt u=G.head(e);
-		    if ( level.get(u) < n ) { 
-		      bfs_queue.push(u);
-		      --numb[level.get(u)];
-		      level.set(u, n);
-		    }
-		  }
-
-		  for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-		    if ( 0 == flow.get(e) ) continue;
-		    NodeIt u=G.tail(e);
-		    if ( level.get(u) < n ) { 
-		      bfs_queue.push(u);
-		      --numb[level.get(u)];
-		      level.set(u, n);
-		    }
-		  }
-		}
-	      }
-	      b=n-1;
-
-	    } else {
-	      level.set(w,++newlevel);
-	      stack[newlevel].push(w);
-	      ++numb[newlevel];
-	      b=newlevel;
-	    }
-	  }
-	}
-
- 
-	
-	} // 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);
-    }
-
-
-
-    /*
-      Returns the maximum flow x found by the algorithm.
-    */
-
-    FlowMap Flow() {
-      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 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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl4.cc
--- a/src/work/jacint/preflow_hl4.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,76 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_hl4.h
--- a/src/work/jacint/preflow_hl4.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,602 +0,0 @@
-// -*- C++ -*-
-/*
-preflow_h5.h
-by jacint. 
-Heuristics: 
- 2 phase
- gap
- list 'level_list' on the nodes on level i implemented by hand
- highest label
- relevel: in phase 0, after BFS*n relabels, it runs a reverse 
-   bfs from t in the res graph to relevel the nodes reachable from t.
-   BFS is initialized to 20
-
-Due to the last heuristic, this algorithm is quite fast on very 
-sparse graphs, but relatively bad on even the dense graphs.
-
-'NodeMap<bool> cut' is a member, in this way we can count it fast, after
-the algorithm was run.
-
-The constructor runs the algorithm.
-
-Members:
-
-T maxFlow() : returns the value of a maximum flow
-
-T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
-
-FlowMap Flow() : returns the fixed maximum flow x
-
-void Flow(FlowMap& _flow ) : returns the fixed maximum flow x
-
-void minMinCut(CutMap& M) : sets M to the characteristic vector of the 
-     minimum min cut. M should be a map of bools initialized to false.
-
-void maxMinCut(CutMap& M) : sets M to the characteristic vector of the 
-     maximum min cut. M should be a map of bools initialized to false.
-
-void minCut(CutMap& M) : fast function, sets M to the characteristic 
-     vector of a minimum cut. 
-
-Different member from the other preflow_hl-s (here we have a member 
-'NodeMap<bool> cut').
-
-CutMap minCut() : fast function, giving the characteristic 
-     vector of a minimum cut.
-
-
-*/
-
-#ifndef PREFLOW_HL4_H
-#define PREFLOW_HL4_H
-
-#define BFS 20
-
-#include <vector>
-#include <queue>
-
-#include <time_measure.h>  //for test
-
-namespace hugo {
-
-  template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>, 
-    typename CutMap=typename Graph::NodeMap<bool>,
-    typename CapMap=typename Graph::EdgeMap<T> >
-  class preflow_hl4 {
-    
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EdgeIt EdgeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    typedef typename Graph::OutEdgeIt OutEdgeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-    
-    Graph& G;
-    NodeIt s;
-    NodeIt t;
-    FlowMap flow;
-    CapMap& capacity;  
-    CutMap cut;
-    T value;
-    
-  public:
-
-    double time;
-
-    preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
-      cut(G, false) {
-
-      bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd
-      int n=G.nodeNum(); 
-      int relabel=0;
-      int heur=(int)BFS*n;
-      int k=n-2;
-      int b=k;
-      /*
-	b is a bound on the highest level of the stack. 
-	k is a bound on the highest nonempty level i < n.
-      */
-
-      typename Graph::NodeMap<int> level(G,n);      
-      typename Graph::NodeMap<T> excess(G); 
-      
-      std::vector<NodeIt> active(n);
-      typename Graph::NodeMap<NodeIt> next(G);
-      //Stack of the active nodes in level i < n.
-      //We use it in both phases.
-
-      typename Graph::NodeMap<NodeIt> left(G);
-      typename Graph::NodeMap<NodeIt> right(G);
-      std::vector<NodeIt> level_list(n);
-      /*
-	Needed for the list of the nodes in level i.
-      */
-
-      /*Reverse_bfs from t, to find the starting level.*/
-      level.set(t,0);
-      std::queue<NodeIt> bfs_queue;
-      bfs_queue.push(t);
-
-      while (!bfs_queue.empty()) {
-
-	NodeIt v=bfs_queue.front();	
-	bfs_queue.pop();
-	int l=level.get(v)+1;
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-	  NodeIt w=G.tail(e);
-	  if ( level.get(w) == n && w !=s ) {
-	    bfs_queue.push(w);
-	    NodeIt first=level_list[l];
-	    if ( first != 0 ) left.set(first,w);
-	    right.set(w,first);
-	    level_list[l]=w;
-	    level.set(w, l);
-	  }
-	}
-      }
-      
-      level.set(s,n);
-
-
-      /* Starting flow. It is everywhere 0 at the moment. */     
-      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
-	{
-	  T c=capacity.get(e);
-	  if ( c == 0 ) continue;
-	  NodeIt w=G.head(e);
-	  if ( level.get(w) < n ) {	  
-	    if ( excess.get(w) == 0 && w!=t ) {
-	      next.set(w,active[level.get(w)]);
-	      active[level.get(w)]=w;
-	    }
-	    flow.set(e, c); 
-	    excess.set(w, excess.get(w)+c);
-	  }
-	}
-      /* 
-	 End of preprocessing 
-      */
-
-
-      /*
-	Push/relabel on the highest level active nodes.
-      */	
-      while ( true ) {
-
-	if ( b == 0 ) {
-	  if ( phase ) break;
-	  
-	  /*
-	    In the end of phase 0 we apply a bfs from s in
-	    the residual graph.
-	  */
-	  phase=1;
-	  
-	  //Now have a min cut.
-	  for( EachNodeIt v=G.template first<EachNodeIt>(); 
-	       v.valid(); ++v) 
-	    if (level.get(v) >= n ) cut.set(v,true);
-	  
-	  time=currTime();
-	  level.set(s,0);
-	  std::queue<NodeIt> bfs_queue;
-	  bfs_queue.push(s);
-	  
-	  while (!bfs_queue.empty()) {
-	    
-	    NodeIt v=bfs_queue.front();	
-	    bfs_queue.pop();
-	    int l=level.get(v)+1;
-
-	    for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-	      if ( capacity.get(e) == flow.get(e) ) continue;
-	      NodeIt u=G.tail(e);
-	      if ( level.get(u) >= n ) { 
-		bfs_queue.push(u);
-		level.set(u, l);
-		if ( excess.get(u) > 0 ) {
-		    next.set(u,active[l]);
-		    active[l]=u;
-		}
-	      }
-	    }
-
-	    for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
-	      if ( 0 == flow.get(e) ) continue;
-	      NodeIt u=G.head(e);
-	      if ( level.get(u) >= n ) { 
-		bfs_queue.push(u);
-		level.set(u, l);
-		if ( excess.get(u) > 0 ) {
-		    next.set(u,active[l]);
-		    active[l]=u;
-		}
-	      }
-	    }
-	  }
-	  b=n-2;
-	}
-
-
-	if ( active[b] == 0 ) --b;
-	else {
-	  
-	  NodeIt w=active[b];
-	  active[b]=next.get(w);
-	  int lev=level.get(w);
-	  T exc=excess.get(w);
-	  int newlevel=n;          //bound on the next level of w.
-	  
-	  for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
-	    
-	    if ( flow.get(e) == capacity.get(e) ) continue; 
-	    NodeIt v=G.head(e);            
-	    //e=wv	    
-	    
-	    if( lev > level.get(v) ) {      
-	      /*Push is allowed now*/
-	      
-	      if ( excess.get(v)==0 && v!=t && v!=s )  {
-		int lev_v=level.get(v);
-		next.set(v,active[lev_v]);
-		active[lev_v]=v;
-	      }
-	      
-	      T cap=capacity.get(e);
-	      T flo=flow.get(e);
-	      T remcap=cap-flo;
-	      
-	      if ( remcap >= exc ) {       
-		/*A nonsaturating push.*/
-		
-		flow.set(e, flo+exc);
-		excess.set(v, excess.get(v)+exc);
-		exc=0;
-		break; 
-		
-	      } else { 
-		/*A saturating push.*/
-		
-		flow.set(e, cap);
-		excess.set(v, excess.get(v)+remcap);
-		exc-=remcap;
-	      }
-	    } else if ( newlevel > level.get(v) ){
-	      newlevel = level.get(v);
-	    }	    
-	    
-	  } //for out edges wv 
-	
-	
-	if ( exc > 0 ) {	
-	  for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
-	    
-	    if( flow.get(e) == 0 ) continue; 
-	    NodeIt v=G.tail(e);  
-	    //e=vw
-	    
-	    if( lev > level.get(v) ) {  
-	      /*Push is allowed now*/
-	      
-	      if ( excess.get(v)==0 && v!=t && v!=s ) {
-		int lev_v=level.get(v);
-		next.set(v,active[lev_v]);
-		active[lev_v]=v;
-	      }
-	      
-	      T flo=flow.get(e);
-	      
-	      if ( flo >= exc ) { 
-		/*A nonsaturating push.*/
-		
-		flow.set(e, flo-exc);
-		excess.set(v, excess.get(v)+exc);
-		exc=0;
-		break; 
-	      } else {                                               
-		/*A saturating push.*/
-		
-		excess.set(v, excess.get(v)+flo);
-		exc-=flo;
-		flow.set(e,0);
-	      }  
-	    } else if ( newlevel > level.get(v) ) {
-	      newlevel = level.get(v);
-	    }	    
-	  } //for in edges vw
-	  
-	} // if w still has excess after the out edge for cycle
-	
-	excess.set(w, exc);
-	 
-	/*
-	  Relabel
-	*/
-	
-	if ( exc > 0 ) {
-	  //now 'lev' is the old level of w
-	
-	  if ( phase ) {
-	    level.set(w,++newlevel);
-	    next.set(w,active[newlevel]);
-	    active[newlevel]=w;
-	    b=newlevel;
-	  } else {
-	    //unlacing
-	    NodeIt right_n=right.get(w);
-	    NodeIt left_n=left.get(w);
-
-	    if ( right_n != 0 ) {
-	      if ( left_n != 0 ) {
-		right.set(left_n, right_n);
-		left.set(right_n, left_n);
-	      } else {
-		level_list[lev]=right_n;
-		left.set(right_n, 0);
-	      } 
-	    } else {
-	      if ( left_n != 0 ) {
-		right.set(left_n, 0);
-	      } else { 
-		level_list[lev]=0;
-	      } 
-	    }
-	    //unlacing ends
-		
-
-	    if ( level_list[lev]==0 ) {
-
-	      for (int i=lev; i!=k ; ) {
-		NodeIt v=level_list[++i];
-		while ( v != 0 ) {
-		  level.set(v,n);
-		  v=right.get(v);
-		}
-		level_list[i]=0;
-	      }	     
-
-	      level.set(w,n);
-
-	      b=--lev;
-	      k=b;
-
-	    } else {
-
-	      if ( newlevel == n ) {
-		level.set(w,n);
-	      } else {
-		
-		level.set(w,++newlevel);
-		next.set(w,active[newlevel]);
-		active[newlevel]=w;
-		b=newlevel;
-		if ( k < newlevel ) ++k;
-		NodeIt first=level_list[newlevel];
-		if ( first != 0 ) left.set(first,w);
-		right.set(w,first);
-		left.set(w,0);
-		level_list[newlevel]=w;
-	      }
-	    }
-
-	    ++relabel;
-	    if ( relabel >= heur ) {
-	      relabel=0;
-	      b=n-2;
-	      k=b;
-		
-	      for ( int i=1; i!=n; ++i ) { 
-		active[i]=0;
-		level_list[i]=0;
-	      }
-
-	      //bfs from t in the res graph to relevel the nodes
-	      for( EachNodeIt v=G.template first<EachNodeIt>(); 
-		   v.valid(); ++v) level.set(v,n);
-
-	      level.set(t,0);
-	      std::queue<NodeIt> bfs_queue;
-	      bfs_queue.push(t);
-	      
-	      while (!bfs_queue.empty()) {
-		
-		NodeIt v=bfs_queue.front();	
-		bfs_queue.pop();
-		int l=level.get(v)+1;
-		
-		for(InEdgeIt e=G.template first<InEdgeIt>(v); 
-		    e.valid(); ++e) {
-		  if ( capacity.get(e) == flow.get(e) ) continue;
-		  NodeIt u=G.tail(e);
-		  if ( level.get(u) == n ) { 
-		    bfs_queue.push(u);
-		    level.set(u, l);
-		    if ( excess.get(u) > 0 ) {
-		      next.set(u,active[l]);
-		      active[l]=u;
-		    }
-		    NodeIt first=level_list[l];
-		    if ( first != 0 ) left.set(first,w);
-		    right.set(w,first);
-		    left.set(w,0);
-		    level_list[l]=w;
-		  }
-		}
-		
-		
-		for(OutEdgeIt e=G.template first<OutEdgeIt>(v); 
-		    e.valid(); ++e) {
-		  if ( 0 == flow.get(e) ) continue;
-		  NodeIt u=G.head(e);
-		  if ( level.get(u) == n ) { 
-		    bfs_queue.push(u);
-		    level.set(u, l);
-		    if ( excess.get(u) > 0 ) {
-		      next.set(u,active[l]);
-		      active[l]=u;
-		    }
-		    NodeIt first=level_list[l];
-		    if ( first != 0 ) left.set(first,w);
-		    right.set(w,first);
-		    left.set(w,0);
-		    level_list[l]=w;
-		  }
-		}
-	      }
-	      
-	      level.set(s,n);
-	    }
-	  
-	  } //phase 0
-	} // if ( exc > 0 )
-	
-	
-	} // if stack[b] is nonempty
-	
-      } // while(true)
-
-
-      value = excess.get(t);
-      /*Max flow value.*/
-
-
-    } //void run()
-
-
-
-
-
-    /*
-      Returns the maximum value of a flow.
-     */
-
-    T maxFlow() {
-      return value;
-    }
-
-
-
-    /*
-      For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). 
-    */
-
-    T flowOnEdge(EdgeIt e) {
-      return flow.get(e);
-    }
-
-
-
-    FlowMap Flow() {
-      return flow;
-    }
-
-
-    
-    void Flow(FlowMap& _flow ) {
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
-	_flow.set(v,flow.get(v));
-    }
-
-
-
-    /*
-      Returns the minimum min cut, by a bfs from s in the residual graph.
-    */
-    
-    template<typename _CutMap>
-    void minMinCut(_CutMap& M) {
-    
-      std::queue<NodeIt> queue;
-      
-      M.set(s,true);      
-      queue.push(s);
-
-      while (!queue.empty()) {
-        NodeIt w=queue.front();
-	queue.pop();
-
-	for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.head(e);
-	  if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	} 
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.tail(e);
-	  if (!M.get(v) && flow.get(e) > 0 ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	} 
-
-      }
-
-    }
-
-
-
-    /*
-      Returns the maximum min cut, by a reverse bfs 
-      from t in the residual graph.
-    */
-    
-    template<typename _CutMap>
-    void maxMinCut(_CutMap& M) {
-    
-      std::queue<NodeIt> queue;
-      
-      M.set(t,true);        
-      queue.push(t);
-
-      while (!queue.empty()) {
-        NodeIt w=queue.front();
-	queue.pop();
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.tail(e);
-	  if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	}
-
-	for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
-	  NodeIt v=G.head(e);
-	  if (!M.get(v) && flow.get(e) > 0 ) {
-	    queue.push(v);
-	    M.set(v, true);
-	  }
-	}
-      }
-
-      for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
-	M.set(v, !M.get(v));
-      }
-
-    }
-
-
-    template<typename _CutMap>
-    void minCut(_CutMap& M) {
-      for( EachNodeIt v=G.template first<EachNodeIt>(); 
-	   v.valid(); ++v) 
-	M.set(v, cut.get(v));
-    }
-
-   
-    CutMap minCut() {
-      return cut;
-    }
-
-
-  };
-}//namespace marci
-#endif 
-
-
-
-
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_jgraph.cc
--- a/src/work/jacint/preflow_jgraph.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,72 +0,0 @@
-#include <iostream>
-#include <fstream>
-
-#include <j_graph.h>
-#include <dimacs_jgraph.hh>
-#include <preflow_jgraph.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 JGraph::TrivNodeIt TrivNodeIt;
-  typedef JGraph::EdgeIt EdgeIt;
-
-  JGraph G;
-  TrivNodeIt s, t;
-  JGraph::EdgeMap<int> cap(G);
-  readDimacsMaxFlow(std::cin, G, s, t, cap);
-
-  std::cout << "preflow demo jacint ..." << std::endl;
-  
-  double mintime=1000000;
-
-  for ( int i=1; i!=11; ++i ) {
-    double pre_time=currTime();
-    preflow<JGraph, 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<JGraph, int> max_flow_test(G, s, t, cap);
-  double post_time=currTime();
-    
-  JGraph::NodeMap<bool> cut(G);
-  max_flow_test.minCut(cut); 
-  int min_cut_value=0;
-  for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
-    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
-  }
-
-  JGraph::NodeMap<bool> cut1(G);
-  max_flow_test.minMinCut(cut1); 
-  int min_min_cut_value=0;
-  for(EdgeIt e=G.firstEdge(); e; G.next(e)) {
-    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) 
-      min_min_cut_value+=cap.get(e);
-  }
-
-  JGraph::NodeMap<bool> cut2(G);
-  max_flow_test.maxMinCut(cut2); 
-  int max_min_cut_value=0;
-  for(EdgeIt e=G.firstEdge(); e; G.next(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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_jgraph.h
--- a/src/work/jacint/preflow_jgraph.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,536 +0,0 @@
-// -*- C++ -*-
-/*
-preflow.h with 'j_graph interface'
-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 'bound 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>
-
-#include<iostream>
-
-#include <time_measure.h>
-
-namespace hugo {
-
-  template <typename Graph, typename T, 
-    typename FlowMap=typename Graph::EdgeMap<T>,
-    typename CapMap=typename Graph::EdgeMap<T> >
-  class preflow {
-    
-    typedef typename Graph::TrivNodeIt NodeIt;
-    typedef typename Graph::TrivEdgeIt EdgeIt;
-    typedef typename Graph::NodeIt 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(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.numNodes(); 
-      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.firstIn(v); e; G.next(e)) {
-	  NodeIt w=G.tail(e);
-	  if ( level.get(w) == n && w != s ) {
-	    bfs_queue.push(w);
-	    NodeIt first=level_list[l];
-	    if ( first ) 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.firstOut(s); e; G.next(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;
-	    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.firstIn(v); e; G.next(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.firstOut(v); e; G.next(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]  ) --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.firstOut(w); e; G.next(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.firstIn(w); e; G.next(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 ) {
-	      if ( left_n ) {
-		right.set(left_n, right_n);
-		left.set(right_n, left_n);
-	      } else {
-		level_list[lev]=right_n;   
-		left.set(right_n, NodeIt());
-	      } 
-	    } else {
-	      if ( left_n ) {
-		right.set(left_n, NodeIt());
-	      } else { 
-		level_list[lev]=NodeIt();   
-
-	      } 
-	    } 
-	    //unlacing ends
-		
-	    //gapping starts
-	    if ( !level_list[lev] ) {
-	      
-	      for (int i=lev; i!=k ; ) {
-		NodeIt v=level_list[++i];
-		while ( v ) {
-		  level.set(v,n);
-		  v=right.get(v);
-		}
-		level_list[i]=NodeIt(); 
-		if ( !what_heur ) active[i]=NodeIt();
-	      }	     
-
-	      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 ) left.set(first,w);
-		right.set(w,first);
-		left.set(w,NodeIt());
-		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.firstNode() ; v; G.next(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.firstOut(w) ; e; G.next(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.firstIn(w) ; e; G.next(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.firstIn(w) ; e; G.next(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.firstOut(w) ; e; G.next(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.firstNode() ; v; G.next(v)) {
-	M.set(v, !M.get(v));
-      }
-
-    }
-
-
-
-    template<typename CutMap>
-    void minCut(CutMap& M) {
-      minMinCut(M);
-    }
-
-
-  };
-}//namespace marci
-#endif 
-
-
-
-
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_max_flow.cc
--- a/src/work/jacint/preflow_max_flow.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,40 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_max_flow.h
--- a/src/work/jacint/preflow_max_flow.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,358 +0,0 @@
-// -*- 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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_param.cc
--- a/src/work/jacint/preflow_param.cc	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,47 +0,0 @@
-#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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/preflow_param.h
--- a/src/work/jacint/preflow_param.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,541 +0,0 @@
-// -*- 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 01d47457aff3 -r c1ec00df3b3a src/work/jacint/reverse_bfs.h
--- a/src/work/jacint/reverse_bfs.h	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,89 +0,0 @@
-/*
-reverse_bfs
-by jacint
-Performs a bfs on the out Edges. It does not count predecessors, 
-only the distances, but one can easily modify it to know the pred as well.
-
-Constructor: 
-
-reverse_bfs(Graph& G, NodeIt t)
-
-
-
-Member functions:
-
-void run(): runs a reverse bfs from t
-
-  The following function should be used after run() was already run.
-
-int dist(NodeIt v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
-
-*/
-#ifndef REVERSE_BFS_H
-#define REVERSE_BFS_H
-
-#include <queue>
-#include <list_graph.hh>
-
-
-namespace  marci {
-
-  template <typename Graph>
-  class reverse_bfs {
-    typedef typename Graph::NodeIt NodeIt;
-    typedef typename Graph::EachNodeIt EachNodeIt;
-    typedef typename Graph::InEdgeIt InEdgeIt;
-
-
-    Graph& G;
-    NodeIt t;
-    typename Graph::NodeMap<int> distance;
-    
-
-  public :
-
-    /*
-      The distance of the Nodes is n, except t for which it is 0.
-    */
-    reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) {
-      distance.set(t,0);
-    }
-    
-    void run() {
-
-      typename Graph::NodeMap<bool> reached(G, false); 
-      reached.set(t, true);
-
-      std::queue<NodeIt> bfs_queue;
-      bfs_queue.push(t);
-
-      while (!bfs_queue.empty()) {
-
-        NodeIt v=bfs_queue.front();	
-	bfs_queue.pop();
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-	  NodeIt w=G.tail(e);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(w);
-	    distance.set(w, distance.get(v)+1);
-	    reached.set(w, true);
-	  }
-	}
-      }
-    }
-
-
-
-    int dist(NodeIt v) {
-      return distance.get(v);
-    }
-
-
-  };
-
-} // namespace hugo
-
-#endif //REVERSE_BFS_HH
-
-
diff -r 01d47457aff3 -r c1ec00df3b3a src/work/jacint/reverse_bfs.hh
--- a/src/work/jacint/reverse_bfs.hh	Mon Mar 01 17:24:34 2004 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,94 +0,0 @@
-/*
-reverse_bfs
-by jacint
-Performs a bfs on the out Edges. It does not count predecessors, 
-only the distances, but one can easily modify it to know the pred as well.
-
-Constructor: 
-
-reverse_bfs(graph_type& G, NodeIt t)
-
-
-
-Member functions:
-
-void run(): runs a reverse bfs from t
-
-  The following function should be used after run() was already run.
-
-int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
-
-*/
-#ifndef REVERSE_BFS_HH
-#define REVERSE_BFS_HH
-
-#include <queue>
-
-#include <marci_graph_traits.hh>
-#include <marciMap.hh>
-
-
-
-namespace  marci {
-
-  template <typename graph_type>
-  class reverse_bfs {
-    typedef typename graph_traits<graph_type>::NodeIt NodeIt;
-    //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
-    typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
-    typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
-
-
-    graph_type& G;
-    NodeIt t;
-//    NodeMap<graph_type, EdgeIt> pred;
-    NodeMap<graph_type, int> distance;
-    
-
-  public :
-
-    /*
-      The distance of the Nodes is n, except t for which it is 0.
-    */
-    reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
-      distance.put(t,0);
-    }
-    
-    void run() {
-
-      NodeMap<graph_type, bool> reached(G, false); 
-      reached.put(t, true);
-
-      std::queue<NodeIt> bfs_queue;
-      bfs_queue.push(t);
-
-      while (!bfs_queue.empty()) {
-
-        NodeIt v=bfs_queue.front();	
-	bfs_queue.pop();
-
-	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
-	  NodeIt w=G.tail(e);
-	  if (!reached.get(w)) {
-	    bfs_queue.push(w);
-	    distance.put(w, distance.get(v)+1);
-	    reached.put(w, true);
-	  }
-	}
-      }
-    }
-
-
-
-    int dist(NodeIt v) {
-      return distance.get(v);
-    }
-
-
-  };
-
-} // namespace hugo
-
-#endif //REVERSE_BFS_HH
-
-