1.1 --- a/src/work/edmonds_karp.h	Tue Mar 30 17:37:14 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.h	Tue Mar 30 17:47:51 2004 +0000
     1.3 @@ -432,109 +432,110 @@
     1.4        return _augment;
     1.5      }
     1.6  
     1.7 -//     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
     1.8 -//       bool _augment=false;
     1.9 +    template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
    1.10 +      bool _augment=false;
    1.11  
    1.12 -//       AugGraph res_graph(*G, *flow, *capacity);
    1.13 +      AugGraph res_graph(gw, *flow, *capacity);
    1.14  
    1.15 -//       //bfs for distances on the residual graph
    1.16 -//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1.17 -//       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    1.18 -//       bfs.pushAndSetReached(s);
    1.19 -//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    1.20 +      //bfs for distances on the residual graph
    1.21 +      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1.22 +      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    1.23 +      bfs.pushAndSetReached(s);
    1.24 +      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    1.25  
    1.26 -//       //F will contain the physical copy of the residual graph
    1.27 -//       //with the set of edges which areon shortest paths
    1.28 -//       MutableGraph F;
    1.29 -//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
    1.30 -// 	res_graph_to_F(res_graph);
    1.31 -//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    1.32 -// 	res_graph_to_F.set(n, F.addNode());
    1.33 -//       }
    1.34 -//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    1.35 -//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    1.36 -//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    1.37 -//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    1.38 +      //F will contain the physical copy of the residual graph
    1.39 +      //with the set of edges which areon shortest paths
    1.40 +      MutableGraph F;
    1.41 +      typename AugGraph::NodeMap<typename MutableGraph::Node> 
    1.42 +	res_graph_to_F(res_graph);
    1.43 +      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    1.44 +	res_graph_to_F.set(n, F.addNode());
    1.45 +      }
    1.46 +      typename MutableGraph::Node sF=res_graph_to_F.get(s);
    1.47 +      typename MutableGraph::Node tF=res_graph_to_F.get(t);
    1.48 +      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    1.49 +      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    1.50  
    1.51 -//       while ( !bfs.finished() ) { 
    1.52 -// 	AugOutEdgeIt e=bfs;
    1.53 -// 	if (res_graph.valid(e)) {
    1.54 -// 	  if (bfs.isBNodeNewlyReached()) {
    1.55 -// 	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    1.56 -// 	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.57 -// 	    original_edge.update();
    1.58 -// 	    original_edge.set(f, e);
    1.59 -// 	    residual_capacity.update();
    1.60 -// 	    residual_capacity.set(f, res_graph.free(e));
    1.61 -// 	  } else {
    1.62 -// 	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    1.63 -// 	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.64 -// 	      original_edge.update();
    1.65 -// 	      original_edge.set(f, e);
    1.66 -// 	      residual_capacity.update();
    1.67 -// 	      residual_capacity.set(f, res_graph.free(e));
    1.68 -// 	    }
    1.69 -// 	  }
    1.70 -// 	}
    1.71 -// 	++bfs;
    1.72 -//       } //computing distances from s in the residual graph
    1.73 +      while ( !bfs.finished() ) { 
    1.74 +	AugOutEdgeIt e=bfs;
    1.75 +	if (res_graph.valid(e)) {
    1.76 +	  if (bfs.isBNodeNewlyReached()) {
    1.77 +	    dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    1.78 +	    typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.79 +	    original_edge.update();
    1.80 +	    original_edge.set(f, e);
    1.81 +	    residual_capacity.update();
    1.82 +	    residual_capacity.set(f, res_graph.free(e));
    1.83 +	  } else {
    1.84 +	    if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    1.85 +	      typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    1.86 +	      original_edge.update();
    1.87 +	      original_edge.set(f, e);
    1.88 +	      residual_capacity.update();
    1.89 +	      residual_capacity.set(f, res_graph.free(e));
    1.90 +	    }
    1.91 +	  }
    1.92 +	}
    1.93 +	++bfs;
    1.94 +      } //computing distances from s in the residual graph
    1.95  
    1.96 -//       bool __augment=true;
    1.97 +      bool __augment=true;
    1.98  
    1.99 -//       while (__augment) {
   1.100 -// 	__augment=false;
   1.101 -// 	//computing blocking flow with dfs
   1.102 -// 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
   1.103 -// 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
   1.104 -// 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
   1.105 -// 	pred.set(sF, typename MutableGraph::Edge(INVALID));
   1.106 -// 	//invalid iterators for sources
   1.107 +      while (__augment) {
   1.108 +	__augment=false;
   1.109 +	//computing blocking flow with dfs
   1.110 +	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
   1.111 +	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
   1.112 +	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
   1.113 +	pred.set(sF, typename MutableGraph::Edge(INVALID));
   1.114 +	//invalid iterators for sources
   1.115  
   1.116 -// 	typename MutableGraph::NodeMap<Number> free(F);
   1.117 +	typename MutableGraph::NodeMap<Number> free(F);
   1.118  
   1.119 -// 	dfs.pushAndSetReached(sF);      
   1.120 -// 	while (!dfs.finished()) {
   1.121 -// 	  ++dfs;
   1.122 -// 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   1.123 -// 	    if (dfs.isBNodeNewlyReached()) {
   1.124 -// 	      typename MutableGraph::Node v=F.aNode(dfs);
   1.125 -// 	      typename MutableGraph::Node w=F.bNode(dfs);
   1.126 -// 	      pred.set(w, dfs);
   1.127 -// 	      if (F.valid(pred.get(v))) {
   1.128 -// 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
   1.129 -// 	      } else {
   1.130 -// 		free.set(w, residual_capacity.get(dfs)); 
   1.131 -// 	      }
   1.132 -// 	      if (w==tF) { 
   1.133 -// 		__augment=true; 
   1.134 -// 		_augment=true;
   1.135 -// 		break; 
   1.136 -// 	      }
   1.137 +	dfs.pushAndSetReached(sF);      
   1.138 +	while (!dfs.finished()) {
   1.139 +	  ++dfs;
   1.140 +	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   1.141 +	    if (dfs.isBNodeNewlyReached()) {
   1.142 +	      typename MutableGraph::Node v=F.aNode(dfs);
   1.143 +	      typename MutableGraph::Node w=F.bNode(dfs);
   1.144 +	      pred.set(w, dfs);
   1.145 +	      if (F.valid(pred.get(v))) {
   1.146 +		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
   1.147 +	      } else {
   1.148 +		free.set(w, residual_capacity.get(dfs)); 
   1.149 +	      }
   1.150 +	      if (w==tF) { 
   1.151 +		__augment=true; 
   1.152 +		_augment=true;
   1.153 +		break; 
   1.154 +	      }
   1.155  	      
   1.156 -// 	    } else {
   1.157 -// 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   1.158 -// 	    }
   1.159 -// 	  } 
   1.160 -// 	}
   1.161 +	    } else {
   1.162 +	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   1.163 +	    }
   1.164 +	  } 
   1.165 +	}
   1.166  
   1.167 -// 	if (__augment) {
   1.168 -// 	  typename MutableGraph::Node n=tF;
   1.169 -// 	  Number augment_value=free.get(tF);
   1.170 -// 	  while (F.valid(pred.get(n))) { 
   1.171 -// 	    typename MutableGraph::Edge e=pred.get(n);
   1.172 -// 	    res_graph.augment(original_edge.get(e), augment_value); 
   1.173 -// 	    n=F.tail(e);
   1.174 -// 	    if (residual_capacity.get(e)==augment_value) 
   1.175 -// 	      F.erase(e); 
   1.176 -// 	    else 
   1.177 -// 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   1.178 -// 	  }
   1.179 -// 	}
   1.180 +	if (__augment) {
   1.181 +	  typename MutableGraph::Node n=tF;
   1.182 +	  Number augment_value=free.get(tF);
   1.183 +	  while (F.valid(pred.get(n))) { 
   1.184 +	    typename MutableGraph::Edge e=pred.get(n);
   1.185 +	    res_graph.augment(original_edge.get(e), augment_value); 
   1.186 +	    n=F.tail(e);
   1.187 +	    if (residual_capacity.get(e)==augment_value) 
   1.188 +	      F.erase(e); 
   1.189 +	    else 
   1.190 +	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   1.191 +	  }
   1.192 +	}
   1.193  	
   1.194 -//       }
   1.195 +      }
   1.196              
   1.197 -//       return _augment;
   1.198 -//     }
   1.199 +      return _augment;
   1.200 +    }
   1.201 +
   1.202  //     bool augmentOnBlockingFlow2() {
   1.203  //       bool _augment=false;
   1.204  

     2.1 --- a/src/work/marci/edmonds_karp_demo.cc	Tue Mar 30 17:37:14 2004 +0000
     2.2 +++ b/src/work/marci/edmonds_karp_demo.cc	Tue Mar 30 17:47:51 2004 +0000
     2.3 @@ -121,33 +121,37 @@
     2.4      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     2.5    }
     2.6  
     2.7 -//   {
     2.8 -//     //std::cout << "SmartGraph..." << std::endl;
     2.9 -//     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    2.10 -//     Graph::EdgeMap<int> flow(G); //0 flow
    2.11 +  {
    2.12 +    //std::cout << "SmartGraph..." << std::endl;
    2.13 +    typedef TrivGraphWrapper<const Graph> GW;
    2.14 +    GW gw(G);
    2.15 +    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
    2.16 +    GW::EdgeMap<int> flow(G); //0 flow
    2.17  
    2.18 -//     Timer ts;
    2.19 -//     ts.reset();
    2.20 +    Timer ts;
    2.21 +    ts.reset();
    2.22  
    2.23 -//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    2.24 -//     int i=0;
    2.25 -//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
    2.26 -// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
    2.27 -// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    2.28 -// //     }
    2.29 -// //     std::cout<<std::endl;
    2.30 -//       ++i; 
    2.31 +    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
    2.32 +    EMW cw(cap);
    2.33 +    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
    2.34 +    int i=0;
    2.35 +    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
    2.36 +//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
    2.37 +//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    2.38  //     }
    2.39 +//     std::cout<<std::endl;
    2.40 +      ++i; 
    2.41 +    }
    2.42  
    2.43 -// //   std::cout << "maximum flow: "<< std::endl;
    2.44 -// //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
    2.45 -// //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    2.46 -// //   }
    2.47 -// //   std::cout<<std::endl;
    2.48 -//     std::cout << "elapsed time: " << ts << std::endl;
    2.49 -//     std::cout << "number of augmentation phases: " << i << std::endl; 
    2.50 -//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    2.51 +//   std::cout << "maximum flow: "<< std::endl;
    2.52 +//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
    2.53 +//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    2.54  //   }
    2.55 +//   std::cout<<std::endl;
    2.56 +    std::cout << "elapsed time: " << ts << std::endl;
    2.57 +    std::cout << "number of augmentation phases: " << i << std::endl; 
    2.58 +    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    2.59 +  }
    2.60  
    2.61  //   {
    2.62  //     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;