# HG changeset patch
# User marci
# Date 1080668871 0
# Node ID f4eb1ae59b507fddeb6cecc4302063b8e1f7c88b
# Parent  c17f741190f75aa44880b2f3db056ac79b5fa67c
blocking flows

diff -r c17f741190f7 -r f4eb1ae59b50 src/work/edmonds_karp.h
--- a/src/work/edmonds_karp.h	Tue Mar 30 17:37:14 2004 +0000
+++ b/src/work/edmonds_karp.h	Tue Mar 30 17:47:51 2004 +0000
@@ -432,109 +432,110 @@
       return _augment;
     }
 
-//     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
-//       bool _augment=false;
+    template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
+      bool _augment=false;
 
-//       AugGraph res_graph(*G, *flow, *capacity);
+      AugGraph res_graph(gw, *flow, *capacity);
 
-//       //bfs for distances on the residual graph
-//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
-//       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
-//       bfs.pushAndSetReached(s);
-//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
+      //bfs for distances on the residual graph
+      typedef typename AugGraph::NodeMap<bool> ReachedMap;
+      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
+      bfs.pushAndSetReached(s);
+      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
 
-//       //F will contain the physical copy of the residual graph
-//       //with the set of edges which areon shortest paths
-//       MutableGraph F;
-//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
-// 	res_graph_to_F(res_graph);
-//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
-// 	res_graph_to_F.set(n, F.addNode());
-//       }
-//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
-//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
-//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
-//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
+      //F will contain the physical copy of the residual graph
+      //with the set of edges which areon shortest paths
+      MutableGraph F;
+      typename AugGraph::NodeMap<typename MutableGraph::Node> 
+	res_graph_to_F(res_graph);
+      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
+	res_graph_to_F.set(n, F.addNode());
+      }
+      typename MutableGraph::Node sF=res_graph_to_F.get(s);
+      typename MutableGraph::Node tF=res_graph_to_F.get(t);
+      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
+      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
 
-//       while ( !bfs.finished() ) { 
-// 	AugOutEdgeIt e=bfs;
-// 	if (res_graph.valid(e)) {
-// 	  if (bfs.isBNodeNewlyReached()) {
-// 	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
-// 	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
-// 	    original_edge.update();
-// 	    original_edge.set(f, e);
-// 	    residual_capacity.update();
-// 	    residual_capacity.set(f, res_graph.free(e));
-// 	  } else {
-// 	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
-// 	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
-// 	      original_edge.update();
-// 	      original_edge.set(f, e);
-// 	      residual_capacity.update();
-// 	      residual_capacity.set(f, res_graph.free(e));
-// 	    }
-// 	  }
-// 	}
-// 	++bfs;
-//       } //computing distances from s in the residual graph
+      while ( !bfs.finished() ) { 
+	AugOutEdgeIt e=bfs;
+	if (res_graph.valid(e)) {
+	  if (bfs.isBNodeNewlyReached()) {
+	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
+	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+	    original_edge.update();
+	    original_edge.set(f, e);
+	    residual_capacity.update();
+	    residual_capacity.set(f, res_graph.free(e));
+	  } else {
+	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
+	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
+	      original_edge.update();
+	      original_edge.set(f, e);
+	      residual_capacity.update();
+	      residual_capacity.set(f, res_graph.free(e));
+	    }
+	  }
+	}
+	++bfs;
+      } //computing distances from s in the residual graph
 
-//       bool __augment=true;
+      bool __augment=true;
 
-//       while (__augment) {
-// 	__augment=false;
-// 	//computing blocking flow with dfs
-// 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
-// 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
-// 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
-// 	pred.set(sF, typename MutableGraph::Edge(INVALID));
-// 	//invalid iterators for sources
+      while (__augment) {
+	__augment=false;
+	//computing blocking flow with dfs
+	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
+	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
+	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
+	pred.set(sF, typename MutableGraph::Edge(INVALID));
+	//invalid iterators for sources
 
-// 	typename MutableGraph::NodeMap<Number> free(F);
+	typename MutableGraph::NodeMap<Number> free(F);
 
-// 	dfs.pushAndSetReached(sF);      
-// 	while (!dfs.finished()) {
-// 	  ++dfs;
-// 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
-// 	    if (dfs.isBNodeNewlyReached()) {
-// 	      typename MutableGraph::Node v=F.aNode(dfs);
-// 	      typename MutableGraph::Node w=F.bNode(dfs);
-// 	      pred.set(w, dfs);
-// 	      if (F.valid(pred.get(v))) {
-// 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
-// 	      } else {
-// 		free.set(w, residual_capacity.get(dfs)); 
-// 	      }
-// 	      if (w==tF) { 
-// 		__augment=true; 
-// 		_augment=true;
-// 		break; 
-// 	      }
+	dfs.pushAndSetReached(sF);      
+	while (!dfs.finished()) {
+	  ++dfs;
+	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
+	    if (dfs.isBNodeNewlyReached()) {
+	      typename MutableGraph::Node v=F.aNode(dfs);
+	      typename MutableGraph::Node w=F.bNode(dfs);
+	      pred.set(w, dfs);
+	      if (F.valid(pred.get(v))) {
+		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
+	      } else {
+		free.set(w, residual_capacity.get(dfs)); 
+	      }
+	      if (w==tF) { 
+		__augment=true; 
+		_augment=true;
+		break; 
+	      }
 	      
-// 	    } else {
-// 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
-// 	    }
-// 	  } 
-// 	}
+	    } else {
+	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
+	    }
+	  } 
+	}
 
-// 	if (__augment) {
-// 	  typename MutableGraph::Node n=tF;
-// 	  Number augment_value=free.get(tF);
-// 	  while (F.valid(pred.get(n))) { 
-// 	    typename MutableGraph::Edge e=pred.get(n);
-// 	    res_graph.augment(original_edge.get(e), augment_value); 
-// 	    n=F.tail(e);
-// 	    if (residual_capacity.get(e)==augment_value) 
-// 	      F.erase(e); 
-// 	    else 
-// 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
-// 	  }
-// 	}
+	if (__augment) {
+	  typename MutableGraph::Node n=tF;
+	  Number augment_value=free.get(tF);
+	  while (F.valid(pred.get(n))) { 
+	    typename MutableGraph::Edge e=pred.get(n);
+	    res_graph.augment(original_edge.get(e), augment_value); 
+	    n=F.tail(e);
+	    if (residual_capacity.get(e)==augment_value) 
+	      F.erase(e); 
+	    else 
+	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
+	  }
+	}
 	
-//       }
+      }
             
-//       return _augment;
-//     }
+      return _augment;
+    }
+
 //     bool augmentOnBlockingFlow2() {
 //       bool _augment=false;
 
diff -r c17f741190f7 -r f4eb1ae59b50 src/work/marci/edmonds_karp_demo.cc
--- a/src/work/marci/edmonds_karp_demo.cc	Tue Mar 30 17:37:14 2004 +0000
+++ b/src/work/marci/edmonds_karp_demo.cc	Tue Mar 30 17:47:51 2004 +0000
@@ -121,33 +121,37 @@
     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   }
 
-//   {
-//     //std::cout << "SmartGraph..." << std::endl;
-//     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
-//     Graph::EdgeMap<int> flow(G); //0 flow
+  {
+    //std::cout << "SmartGraph..." << std::endl;
+    typedef TrivGraphWrapper<const Graph> GW;
+    GW gw(G);
+    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
+    GW::EdgeMap<int> flow(G); //0 flow
 
-//     Timer ts;
-//     ts.reset();
+    Timer ts;
+    ts.reset();
 
-//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
-//     int i=0;
-//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
-// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
-// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-// //     }
-// //     std::cout<<std::endl;
-//       ++i; 
+    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
+    EMW cw(cap);
+    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
+    int i=0;
+    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
+//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
+//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 //     }
+//     std::cout<<std::endl;
+      ++i; 
+    }
 
-// //   std::cout << "maximum flow: "<< std::endl;
-// //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
-// //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
-// //   }
-// //   std::cout<<std::endl;
-//     std::cout << "elapsed time: " << ts << std::endl;
-//     std::cout << "number of augmentation phases: " << i << std::endl; 
-//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+//   std::cout << "maximum flow: "<< std::endl;
+//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
+//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 //   }
+//   std::cout<<std::endl;
+    std::cout << "elapsed time: " << ts << std::endl;
+    std::cout << "number of augmentation phases: " << i << std::endl; 
+    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
+  }
 
 //   {
 //     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;