# HG changeset patch
# User jacint
# Date 1077008389 0
# Node ID efafe79a88d371b03c2922c2c5f68353864f3d4b
# Parent  4d6a48fc0a2d7725ccfdaacf166357197664924c
debuggolt valtozatok

diff -r 4d6a48fc0a2d -r efafe79a88d3 src/work/jacint/preflow_push_hl.h
--- a/src/work/jacint/preflow_push_hl.h	Mon Feb 16 18:15:31 2004 +0000
+++ b/src/work/jacint/preflow_push_hl.h	Tue Feb 17 08:59:49 2004 +0000
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 /*
-preflow_push_hl.hh
+preflow_push_hl.h
 by jacint. 
 Runs the highest label variant of the preflow push algorithm with 
 running time O(n^2\sqrt(m)). 
@@ -13,11 +13,11 @@
 
 T maxflow() : returns the value of a maximum flow
 
-T flowonEdge(Edge_iterator e) : for a fixed maximum flow x it returns x(e) 
+T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 
 
-EdgeMap<graph_type, T> allflow() : returns the fixed maximum flow x
+Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x
 
-NodeMap<graph_type, bool> mincut() : returns a 
+Graph::NodeMap<bool> mincut() : returns a 
      characteristic vector of a minimum cut. (An empty level 
      in the algorithm gives a minimum cut.)
 */
@@ -29,6 +29,7 @@
 #include <vector>
 #include <stack>
 
+#include <list_graph.hh>
 #include <reverse_bfs.h>
 
 namespace marci {
@@ -41,9 +42,7 @@
     typedef typename Graph::EachNodeIt EachNodeIt;
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     typedef typename Graph::InEdgeIt InEdgeIt;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
     
-
     Graph& G;
     NodeIt s;
     NodeIt t;
@@ -52,14 +51,12 @@
     T value;
     typename Graph::NodeMap<bool> mincutvector;
 
-   
   public:
 
     preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 
 		    typename Graph::EdgeMap<T>& _capacity) :
-      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
-
-
+      G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 
+      mincutvector(_G, true) { }
 
 
     /*
@@ -68,42 +65,44 @@
     */
     void run() {
  
-      typename Graph::NodeMap<int> level(G);         //level of Node
-      typename Graph::NodeMap<T> excess(G);          //excess of Node
+      int i=0;//DELME
+
+      typename Graph::NodeMap<int> level(G);      
+      typename Graph::NodeMap<T> excess(G);      
             
-      int n=G.nodeNum();                        //number of Nodes 
-      int b=n; 
-      /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
+      int n=G.nodeNum();    
+      int b=n-2; 
+      /*
+	b is a bound on the highest level of an active node. 
+	In the beginning it is at most n-2.
+      */
 
-      std::vector<std::stack<NodeIt> > stack(2*n-1);    //Stack of the active Nodes in level i.
-
-
+      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.*/
-
       reverse_bfs<Graph> bfs(G, t);
       bfs.run();
-      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
-	level.set(v, bfs.dist(v)); 
-	//std::cout << "the level of " << v << " is " << bfs.dist(v);
-      }
+      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 
+	{
+	  level.set(v, bfs.dist(v)); 
+	}
 
-      /*The level of s is fixed to n*/ 
+      std::cout << "the level of t is " << bfs.dist(t);//delme
+
       level.set(s,n);
 
 
-
-
-
-      /* Starting flow. It is everywhere 0 at the moment. */
-     
-      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 
+      /* Starting flow. It is everywhere 0 at the moment. */     
+      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
 	{
-	  NodeIt w=G.head(i);
-	  flow.set(i, capacity.get(i)); 
-	  stack[bfs.dist(w)].push(w); 
-	  excess.set(w, capacity.get(i));
+	  if ( capacity.get(e) > 0 ) {
+	    NodeIt w=G.head(e);
+	    flow.set(e, capacity.get(e)); 
+	    stack[level.get(w)].push(w); 
+	    excess.set(w, excess.get(w)+capacity.get(e));
+	  }
 	}
 
 
@@ -145,6 +144,8 @@
 		  
 		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
 		  /*v becomes active.*/
+
+		  //std::cout<<++i;
 		  
 		  flow.set(e, flow.get(e)+excess.get(w));
 		  excess.set(v, excess.get(v)+excess.get(w));
@@ -164,6 +165,8 @@
 		  if (excess.get(w)==0) break;
 		  /*If w is not active any more, then we go on to the next Node.*/
 		  
+		  //std::cout<<++i;
+		  
 		} // if (capacity.get(e)-flow.get(e) > excess.get(w))
 	      } // if(level.get(w)==level.get(v)+1)
 	    
diff -r 4d6a48fc0a2d -r efafe79a88d3 src/work/jacint/preflow_push_max_flow.h
--- a/src/work/jacint/preflow_push_max_flow.h	Mon Feb 16 18:15:31 2004 +0000
+++ b/src/work/jacint/preflow_push_max_flow.h	Tue Feb 17 08:59:49 2004 +0000
@@ -2,8 +2,8 @@
 preflow_push_max_flow_h
 by jacint. 
 Runs a preflow push algorithm with the modification, 
-that we do not push on Nodes with level at least n. 
-Moreover, if a level gets empty, we.set all Nodes above that
+that we do not push on nodes with level at least n. 
+Moreover, if a level gets empty, we set all nodes above that
 level to level n. Hence, in the end, we arrive at a maximum preflow 
 with value of a max flow value. An empty level gives a minimum cut.
 
@@ -15,7 +15,7 @@
 
 T maxflow() : returns the value of a maximum flow
 
-NodeMap<Graph, bool> mincut(): returns a 
+NodeMap<bool> mincut(): returns a 
      characteristic vector of a minimum cut.
 */
 
@@ -51,31 +51,34 @@
      
   public:
         
-    preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
+    preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t, 
+			    typename Graph::EdgeMap<T>& _capacity) : 
+      G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
 
 
     /*
-      The run() function runs a modified version of the highest label preflow-push, which only 
+      The run() function runs a modified version of the 
+      highest label preflow-push, which only 
       finds a maximum preflow, hence giving the value of a maximum flow.
     */
     void run() {
  
-      typename Graph::EdgeMap<T> flow(G, 0);         //the flow value, 0 everywhere  
-      typename Graph::NodeMap<int> level(G);         //level of Node
-      typename Graph::NodeMap<T> excess(G);          //excess of Node
+      typename Graph::EdgeMap<T> flow(G, 0); 
+      typename Graph::NodeMap<int> level(G);   
+      typename Graph::NodeMap<T> excess(G);    
             
-      int n=G.nodeNum();                        //number of Nodes 
+      int n=G.nodeNum();                       
       int b=n-2; 
-      /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
+      /*
+	b is a bound on the highest level of an active Node. 
+	In the beginning it is at most n-2.
+      */
       
-      std::vector<int> numb(n);                                //The number of Nodes on level i < n.
-
-      std::vector<std::stack<NodeIt> > stack(2*n-1);    //Stack of the active Nodes in level i.
-
-
+      std::vector<int> numb(n);     //The number of Nodes on level i < n.
+      std::vector<std::stack<NodeIt> > stack(2*n-1);    
+      //Stack of the active Nodes in level i.
 
       /*Reverse_bfs from t, to find the starting level.*/
-
       reverse_bfs<Graph> bfs(G, t);
       bfs.run();
       for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 
@@ -85,28 +88,25 @@
 	  ++numb[dist];
 	}
 
-      /*The level of s is fixed to n*/ 
       level.set(s,n);
 
-
       /* Starting flow. It is everywhere 0 at the moment. */
-     
-      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 
+      for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 
 	{
-	  NodeIt w=G.head(i);
-	  flow.set(i, capacity.get(i)); 
-	  stack[bfs.dist(w)].push(w); 
-	  excess.set(w, capacity.get(i));
+	  if ( capacity.get(e) > 0 ) {
+	    NodeIt w=G.head(e);
+	    flow.set(e, capacity.get(e)); 
+	    stack[level.get(w)].push(w); 
+	    excess.set(w, excess.get(w)+capacity.get(e));
+	  }
 	}
 
-
       /* 
 	 End of preprocessing 
       */
 
 
 
-
       /*
 	Push/relabel on the highest level active Nodes.
       */
@@ -114,7 +114,7 @@
       /*While there exists an active Node.*/
       while (b) { 
 
-	/*We decrease the bound if there is no active Node of level b.*/
+	/*We decrease the bound if there is no active node of level b.*/
 	if (stack[b].empty()) {
 	  --b;
 	} else {