# HG changeset patch
# User marci
# Date 1083233806 0
# Node ID cd40ecf4d2a9ae6f864661bc8eb61e70303a85b7
# Parent  d72e56f1730ddd7b67c564bbca085005a4c8865d
preflow, maxflow comp

diff -r d72e56f1730d -r cd40ecf4d2a9 src/work/jacint/preflow.h
--- a/src/work/jacint/preflow.h	Thu Apr 29 09:08:14 2004 +0000
+++ b/src/work/jacint/preflow.h	Thu Apr 29 10:16:46 2004 +0000
@@ -59,7 +59,7 @@
     typedef typename Graph::template NodeMap<Node> NNMap;
     typedef typename std::vector<Node> VecNode;
 
-    const Graph& G;
+    const Graph* g;
     Node s;
     Node t;
     const CapMap* capacity;  
@@ -79,7 +79,7 @@
 
     Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity, 
 	    FlowMap& _flow) :
-      G(_G), s(_s), t(_t), capacity(&_capacity), 
+      g(&_G), s(_s), t(_t), capacity(&_capacity), 
       flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
 
     void run() {
@@ -109,13 +109,13 @@
       
       VecStack active(n);
       
-      NNMap left(G,INVALID);
-      NNMap right(G,INVALID);
+      NNMap left(*g, INVALID);
+      NNMap right(*g, INVALID);
       VecNode level_list(n,INVALID);
       //List of the nodes in level i<n, set to n.
 
       NodeIt v;
-      for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
+      for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
       //setting each node to level n
       
       switch ( fe ) {
@@ -123,13 +123,13 @@
 	{
 	  //counting the excess
 	  NodeIt v;
-	  for(G.first(v); G.valid(v); G.next(v)) {
+	  for(g->first(v); g->valid(v); g->next(v)) {
 	    T exc=0;
 	  
 	    InEdgeIt e;
-	    for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
+	    for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
 	    OutEdgeIt f;
-	    for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
+	    for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
 	    
 	    excess.set(v,exc);	  
 	    
@@ -145,9 +145,9 @@
 	  T exc=0;
 	  
 	  InEdgeIt e;
-	  for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
+	  for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
 	  OutEdgeIt f;
-	  for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
+	  for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
 	  
 	  excess.set(t,exc);	
 	  
@@ -216,9 +216,9 @@
 	int l=level[v]+1;
 	      
 	InEdgeIt e;
-	for(G.first(e,v); G.valid(e); G.next(e)) {
+	for(g->first(e,v); g->valid(e); g->next(e)) {
 	  if ( (*capacity)[e] == (*flow)[e] ) continue;
-	  Node u=G.tail(e);
+	  Node u=g->tail(e);
 	  if ( level[u] >= n ) { 
 	    bfs_queue.push(u);
 	    level.set(u, l);
@@ -227,9 +227,9 @@
 	}
 	
 	OutEdgeIt f;
-	for(G.first(f,v); G.valid(f); G.next(f)) {
+	for(g->first(f,v); g->valid(f); g->next(f)) {
 	  if ( 0 == (*flow)[f] ) continue;
-	  Node u=G.head(f);
+	  Node u=g->head(f);
 	  if ( level[u] >= n ) { 
 	    bfs_queue.push(u);
 	    level.set(u, l);
@@ -269,9 +269,12 @@
     template<typename _CutMap>
     void actMinCut(_CutMap& M) {
       NodeIt v;
-      for(G.first(v); G.valid(v); G.next(v)) 
-	if ( level[v] < n ) M.set(v,false);
-	else M.set(v,true);
+      for(g->first(v); g->valid(v); g->next(v)) 
+      if ( level[v] < n ) {
+	M.set(v,false);
+      } else {
+	M.set(v,true);
+      }
     }
 
 
@@ -292,8 +295,8 @@
 	queue.pop();
 
 	OutEdgeIt e;
-	for(G.first(e,w) ; G.valid(e); G.next(e)) {
-	  Node v=G.head(e);
+	for(g->first(e,w) ; g->valid(e); g->next(e)) {
+	  Node v=g->head(e);
 	  if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
 	    queue.push(v);
 	    M.set(v, true);
@@ -301,8 +304,8 @@
 	} 
 
 	InEdgeIt f;
-	for(G.first(f,w) ; G.valid(f); G.next(f)) {
-	  Node v=G.tail(f);
+	for(g->first(f,w) ; g->valid(f); g->next(f)) {
+	  Node v=g->tail(f);
 	  if (!M[v] && (*flow)[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, true);
@@ -322,7 +325,7 @@
     void maxMinCut(_CutMap& M) {
 
       NodeIt v;
-      for(G.first(v) ; G.valid(v); G.next(v)) {
+      for(g->first(v) ; g->valid(v); g->next(v)) {
 	M.set(v, true);
       }
 
@@ -337,8 +340,8 @@
 
 
 	InEdgeIt e;
-	for(G.first(e,w) ; G.valid(e); G.next(e)) {
-	  Node v=G.tail(e);
+	for(g->first(e,w) ; g->valid(e); g->next(e)) {
+	  Node v=g->tail(e);
 	  if (M[v] && (*flow)[e] < (*capacity)[e] ) {
 	    queue.push(v);
 	    M.set(v, false);
@@ -346,8 +349,8 @@
 	}
 	
 	OutEdgeIt f;
-	for(G.first(f,w) ; G.valid(f); G.next(f)) {
-	  Node v=G.head(f);
+	for(g->first(f,w) ; g->valid(f); g->next(f)) {
+	  Node v=g->head(f);
 	  if (M[v] && (*flow)[f] > 0 ) {
 	    queue.push(v);
 	    M.set(v, false);
@@ -385,10 +388,10 @@
       int newlevel=n;       //bound on the next level of w
 	  
       OutEdgeIt e;
-      for(G.first(e,w); G.valid(e); G.next(e)) {
+      for(g->first(e,w); g->valid(e); g->next(e)) {
 	    
 	if ( (*flow)[e] == (*capacity)[e] ) continue; 
-	Node v=G.head(e);            
+	Node v=g->head(e);            
 	    
 	if( lev > level[v] ) { //Push is allowed now
 	  
@@ -418,10 +421,10 @@
       
       if ( exc > 0 ) {	
 	InEdgeIt e;
-	for(G.first(e,w); G.valid(e); G.next(e)) {
+	for(g->first(e,w); g->valid(e); g->next(e)) {
 	  
 	  if( (*flow)[e] == 0 ) continue; 
-	  Node v=G.tail(e); 
+	  Node v=g->tail(e); 
 	  
 	  if( lev > level[v] ) { //Push is allowed now
 	    
@@ -474,12 +477,12 @@
 	    int l=level[v]+1;
 	    
 	    InEdgeIt e;
-	    for(G.first(e,v); G.valid(e); G.next(e)) {
-	      Node w=G.tail(e);
+	    for(g->first(e,v); g->valid(e); g->next(e)) {
+	      Node w=g->tail(e);
 	      if ( level[w] == n && w != s ) {
 		bfs_queue.push(w);
 		Node first=level_list[l];
-		if ( G.valid(first) ) left.set(first,w);
+		if ( g->valid(first) ) left.set(first,w);
 		right.set(w,first);
 		level_list[l]=w;
 		level.set(w, l);
@@ -489,11 +492,11 @@
 	  
 	  //the starting flow
 	  OutEdgeIt e;
-	  for(G.first(e,s); G.valid(e); G.next(e)) 
+	  for(g->first(e,s); g->valid(e); g->next(e)) 
 	    {
 	      T c=(*capacity)[e];
 	      if ( c == 0 ) continue;
-	      Node w=G.head(e);
+	      Node w=g->head(e);
 	      if ( level[w] < n ) {	  
 		if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
 		flow->set(e, c); 
@@ -518,13 +521,13 @@
 	    int l=level[v]+1;
 	    
 	    InEdgeIt e;
-	    for(G.first(e,v); G.valid(e); G.next(e)) {
+	    for(g->first(e,v); g->valid(e); g->next(e)) {
 	      if ( (*capacity)[e] == (*flow)[e] ) continue;
-	      Node w=G.tail(e);
+	      Node w=g->tail(e);
 	      if ( level[w] == n && w != s ) {
 		bfs_queue.push(w);
 		Node first=level_list[l];
-		if ( G.valid(first) ) left.set(first,w);
+		if ( g->valid(first) ) left.set(first,w);
 		right.set(w,first);
 		level_list[l]=w;
 		level.set(w, l);
@@ -532,13 +535,13 @@
 	    }
 	    
 	    OutEdgeIt f;
-	    for(G.first(f,v); G.valid(f); G.next(f)) {
+	    for(g->first(f,v); g->valid(f); g->next(f)) {
 	      if ( 0 == (*flow)[f] ) continue;
-	      Node w=G.head(f);
+	      Node w=g->head(f);
 	      if ( level[w] == n && w != s ) {
 		bfs_queue.push(w);
 		Node first=level_list[l];
-		if ( G.valid(first) ) left.set(first,w);
+		if ( g->valid(first) ) left.set(first,w);
 		right.set(w,first);
 		level_list[l]=w;
 		level.set(w, l);
@@ -549,11 +552,11 @@
 	  
 	  //the starting flow
 	  OutEdgeIt e;
-	  for(G.first(e,s); G.valid(e); G.next(e)) 
+	  for(g->first(e,s); g->valid(e); g->next(e)) 
 	    {
 	      T rem=(*capacity)[e]-(*flow)[e];
 	      if ( rem == 0 ) continue;
-	      Node w=G.head(e);
+	      Node w=g->head(e);
 	      if ( level[w] < n ) {	  
 		if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
 		flow->set(e, (*capacity)[e]); 
@@ -562,10 +565,10 @@
 	    }
 	  
 	  InEdgeIt f;
-	  for(G.first(f,s); G.valid(f); G.next(f)) 
+	  for(g->first(f,s); g->valid(f); g->next(f)) 
 	    {
 	      if ( (*flow)[f] == 0 ) continue;
-	      Node w=G.tail(f);
+	      Node w=g->tail(f);
 	      if ( level[w] < n ) {	  
 		if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
 		excess.set(w, excess[w]+(*flow)[f]);
@@ -589,8 +592,8 @@
       Node left_n=left[w];
       
       //unlacing starts
-      if ( G.valid(right_n) ) {
-	if ( G.valid(left_n) ) {
+      if ( g->valid(right_n) ) {
+	if ( g->valid(left_n) ) {
 	  right.set(left_n, right_n);
 	  left.set(right_n, left_n);
 	} else {
@@ -598,7 +601,7 @@
 	  left.set(right_n, INVALID);
 	} 
       } else {
-	if ( G.valid(left_n) ) {
+	if ( g->valid(left_n) ) {
 	  right.set(left_n, INVALID);
 	} else { 
 	  level_list[lev]=INVALID;   
@@ -606,12 +609,12 @@
       } 
       //unlacing ends
 		
-      if ( !G.valid(level_list[lev]) ) {
+      if ( !g->valid(level_list[lev]) ) {
 	      
 	//gapping starts
 	for (int i=lev; i!=k ; ) {
 	  Node v=level_list[++i];
-	  while ( G.valid(v) ) {
+	  while ( g->valid(v) ) {
 	    level.set(v,n);
 	    v=right[v];
 	  }
@@ -637,7 +640,7 @@
 	  if ( what_heur ) b=newlevel;
 	  if ( k < newlevel ) ++k;      //now k=newlevel
 	  Node first=level_list[newlevel];
-	  if ( G.valid(first) ) left.set(first,w);
+	  if ( g->valid(first) ) left.set(first,w);
 	  right.set(w,first);
 	  left.set(w,INVALID);
 	  level_list[newlevel]=w;
diff -r d72e56f1730d -r cd40ecf4d2a9 src/work/marci/edmonds_karp.h
--- a/src/work/marci/edmonds_karp.h	Thu Apr 29 09:08:14 2004 +0000
+++ b/src/work/marci/edmonds_karp.h	Thu Apr 29 10:16:46 2004 +0000
@@ -10,244 +10,10 @@
 #include <invalid.h>
 #include <graph_wrapper.h>
 #include <maps.h>
+#include <for_each_macros.h>
 
 namespace hugo {
 
-//   template<typename Graph, typename Number, typename CapacityMap, typename FlowMap>
-//   class ResGraph {
-//   public:
-//     typedef typename Graph::Node Node;
-//     typedef typename Graph::NodeIt NodeIt;
-//   private:
-//     typedef typename Graph::SymEdgeIt OldSymEdgeIt;
-//     const Graph& G;
-//     const CapacityMap& capacity;
-//     FlowMap& flow;
-//   public:
-//     ResGraph(const Graph& _G, const CapacityMap& _capacity, FlowMap& _flow) : 
-//       G(_G), capacity(_capacity), flow(_flow) { }
-
-//     class Edge; 
-//     class OutEdgeIt; 
-//     friend class Edge; 
-//     friend class OutEdgeIt; 
-
-//     class Edge {
-//       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
-//     protected:
-//       const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
-//       OldSymEdgeIt sym;
-//     public:
-//       Edge() { } 
-//       //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
-//       Number free() const { 
-// 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
-// 	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
-// 	} else { 
-// 	  return (resG->flow.get(sym)); 
-// 	}
-//       }
-//       bool valid() const { return sym.valid(); }
-//       void augment(Number a) const {
-// 	if (resG->G.aNode(sym)==resG->G.tail(sym)) { 
-// 	  resG->flow.set(sym, resG->flow.get(sym)+a);
-// 	  //resG->flow[sym]+=a;
-// 	} else { 
-// 	  resG->flow.set(sym, resG->flow.get(sym)-a);
-// 	  //resG->flow[sym]-=a;
-// 	}
-//       }
-//     };
-
-//     class OutEdgeIt : public Edge {
-//       friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
-//     public:
-//       OutEdgeIt() { }
-//       //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
-//     private:
-//       OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { 
-//       	resG=&_resG;
-// 	sym=resG->G.template first<OldSymEdgeIt>(v);
-// 	while( sym.valid() && !(free()>0) ) { ++sym; }
-//       }
-//     public:
-//       OutEdgeIt& operator++() { 
-// 	++sym; 
-// 	while( sym.valid() && !(free()>0) ) { ++sym; }
-// 	return *this; 
-//       }
-//     };
-
-//     void /*getF*/first(OutEdgeIt& e, Node v) const { 
-//       e=OutEdgeIt(*this, v); 
-//     }
-//     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
-    
-//     template< typename It >
-//     It first() const { 
-//       It e;      
-//       /*getF*/first(e);
-//       return e; 
-//     }
-
-//     template< typename It >
-//     It first(Node v) const { 
-//       It e;
-//       /*getF*/first(e, v);
-//       return e; 
-//     }
-
-//     Node tail(Edge e) const { return G.aNode(e.sym); }
-//     Node head(Edge e) const { return G.bNode(e.sym); }
-
-//     Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
-//     Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
-
-//     int id(Node v) const { return G.id(v); }
-
-//     template <typename S>
-//     class NodeMap {
-//       typename Graph::NodeMap<S> node_map; 
-//     public:
-//       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-//       NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
-//       void set(Node nit, S a) { node_map.set(nit, a); }
-//       S get(Node nit) const { return node_map.get(nit); }
-//       S& operator[](Node nit) { return node_map[nit]; } 
-//       const S& operator[](Node nit) const { return node_map[nit]; } 
-//     };
-
-//   };
-
-
-//   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
-//   class ResGraph2 {
-//   public:
-//     typedef typename Graph::Node Node;
-//     typedef typename Graph::NodeIt NodeIt;
-//   private:
-//     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
-//     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
-//     typedef typename Graph::InEdgeIt OldInEdgeIt;
-    
-//     const Graph& G;
-//     FlowMap& flow;
-//     const CapacityMap& capacity;
-//   public:
-//     ResGraph2(const Graph& _G, FlowMap& _flow, 
-// 	     const CapacityMap& _capacity) : 
-//       G(_G), flow(_flow), capacity(_capacity) { }
-
-//     class Edge; 
-//     class OutEdgeIt; 
-//     friend class Edge; 
-//     friend class OutEdgeIt; 
-
-//     class Edge {
-//       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
-//     protected:
-//       const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
-//       //OldSymEdgeIt sym;
-//       OldOutEdgeIt out;
-//       OldInEdgeIt in;
-//       bool out_or_in; //true, iff out
-//     public:
-//       Edge() : out_or_in(true) { } 
-//       Number free() const { 
-// 	if (out_or_in) { 
-// 	  return (resG->capacity.get(out)-resG->flow.get(out)); 
-// 	} else { 
-// 	  return (resG->flow.get(in)); 
-// 	}
-//       }
-//       bool valid() const { 
-// 	return out_or_in && out.valid() || in.valid(); }
-//       void augment(Number a) const {
-// 	if (out_or_in) { 
-// 	  resG->flow.set(out, resG->flow.get(out)+a);
-// 	} else { 
-// 	  resG->flow.set(in, resG->flow.get(in)-a);
-// 	}
-//       }
-//     };
-
-//     class OutEdgeIt : public Edge {
-//       friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
-//     public:
-//       OutEdgeIt() { }
-//     private:
-//       OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) { 
-//       	resG=&_resG;
-// 	out=resG->G.template first<OldOutEdgeIt>(v);
-// 	while( out.valid() && !(free()>0) ) { ++out; }
-// 	if (!out.valid()) {
-// 	  out_or_in=0;
-// 	  in=resG->G.template first<OldInEdgeIt>(v);
-// 	  while( in.valid() && !(free()>0) ) { ++in; }
-// 	}
-//       }
-//     public:
-//       OutEdgeIt& operator++() { 
-// 	if (out_or_in) {
-// 	  Node v=resG->G.aNode(out);
-// 	  ++out;
-// 	  while( out.valid() && !(free()>0) ) { ++out; }
-// 	  if (!out.valid()) {
-// 	    out_or_in=0;
-// 	    in=resG->G.template first<OldInEdgeIt>(v);
-// 	    while( in.valid() && !(free()>0) ) { ++in; }
-// 	  }
-// 	} else {
-// 	  ++in;
-// 	  while( in.valid() && !(free()>0) ) { ++in; } 
-// 	}
-// 	return *this; 
-//       }
-//     };
-
-//     void /*getF*/first(OutEdgeIt& e, Node v) const { 
-//       e=OutEdgeIt(*this, v); 
-//     }
-//     void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
-    
-//     template< typename It >
-//     It first() const { 
-//       It e;
-//       /*getF*/first(e);
-//       return e; 
-//     }
-
-//     template< typename It >
-//     It first(Node v) const { 
-//       It e;
-//       /*getF*/first(e, v);
-//       return e; 
-//     }
-
-//     Node tail(Edge e) const { 
-//       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
-//     Node head(Edge e) const { 
-//       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
-
-//     Node aNode(OutEdgeIt e) const { 
-//       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
-//     Node bNode(OutEdgeIt e) const { 
-//       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
-
-//     int id(Node v) const { return G.id(v); }
-
-//     template <typename S>
-//     class NodeMap {
-//       typename Graph::NodeMap<S> node_map; 
-//     public:
-//       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
-//       NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
-//       void set(Node nit, S a) { node_map.set(nit, a); }
-//       S get(Node nit) const { return node_map.get(nit); }
-//     };
-//   };
-
-
   template <typename Graph, typename Number, 
 	    typename CapacityMap, typename FlowMap>
   class MaxFlow {
@@ -265,18 +31,23 @@
     typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
     typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
     typedef typename ResGW::Edge ResGWEdge;
+    //typedef typename ResGW::template NodeMap<bool> ReachedMap;
+    typedef typename Graph::template NodeMap<bool> ReachedMap;
+    ReachedMap level;
+    //reached is called level because of compatibility with preflow
   public:
 
     MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity, 
 	    FlowMap& _flow) : 
-      g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow) { }
+      g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
 
     bool augmentOnShortestPath() {
       ResGW res_graph(*g, *capacity, *flow);
       bool _augment=false;
       
-      BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 
-	bfs(res_graph);
+      //ReachedMap level(res_graph);
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
       bfs.pushAndSetReached(s);
 	
       typename ResGW::template NodeMap<ResGWEdge> pred(res_graph); 
@@ -342,8 +113,9 @@
 
       ResGW res_graph(*g, *capacity, *flow);
 
-      BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 
-	bfs(res_graph);
+      //ReachedMap level(res_graph);
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 
       bfs.pushAndSetReached(s);
       //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
@@ -454,8 +226,9 @@
       ResGW res_graph(*g, *capacity, *flow);
 
       //bfs for distances on the residual graph
-      BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 
-	bfs(res_graph);
+      //ReachedMap level(res_graph);
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
       bfs.pushAndSetReached(s);
       typename ResGW::template NodeMap<int> 
 	dist(res_graph); //filled up with 0's
@@ -560,9 +333,10 @@
       bool _augment=false;
 
       ResGW res_graph(*g, *capacity, *flow);
-
-      BfsIterator< ResGW, typename ResGW::template NodeMap<bool> > 
-	bfs(res_graph);
+      
+      //ReachedMap level(res_graph);
+      FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
+      BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
 
       bfs.pushAndSetReached(s);
       DistanceMap<ResGW> dist(res_graph);