.
authormarci
Wed, 17 Mar 2004 15:01:04 +0000
changeset 19384c19824322a
parent 192 100770da4336
child 194 a1680b3c516c
.
src/work/edmonds_karp.h
     1.1 --- a/src/work/edmonds_karp.h	Wed Mar 17 14:50:01 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.h	Wed Mar 17 15:01:04 2004 +0000
     1.3 @@ -527,6 +527,306 @@
     1.4      }
     1.5    };
     1.6  
     1.7 +
     1.8 +  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     1.9 +  class MaxMatching {
    1.10 +  public:
    1.11 +    typedef typename Graph::Node Node;
    1.12 +    typedef typename Graph::Edge Edge;
    1.13 +    typedef typename Graph::EdgeIt EdgeIt;
    1.14 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.15 +    typedef typename Graph::InEdgeIt InEdgeIt;
    1.16 +
    1.17 +    typedef typename Graph::NodeMap<bool> SMap;
    1.18 +    typedef typename Graph::NodeMap<bool> TMap;
    1.19 +  private:
    1.20 +    const Graph* G;
    1.21 +    SMap* S;
    1.22 +    TMap* T;
    1.23 +    //Node s;
    1.24 +    //Node t;
    1.25 +    FlowMap* flow;
    1.26 +    const CapacityMap* capacity;
    1.27 +    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
    1.28 +    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    1.29 +    typedef typename AugGraph::Edge AugEdge;
    1.30 +
    1.31 +  public:
    1.32 +    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
    1.33 +      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
    1.34 +    bool augmentOnShortestPath() {
    1.35 +      AugGraph res_graph(*G, *flow, *capacity);
    1.36 +      bool _augment=false;
    1.37 +      
    1.38 +      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1.39 +      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    1.40 +      typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
    1.41 +      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    1.42 +	Number f=0;
    1.43 +	for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
    1.44 +	  f+=flow->get(e);
    1.45 +	if (f<1) {
    1.46 +	  res_bfs.pushAndSetReached(s);
    1.47 +	  pred.set(s, AugEdge(INVALID));
    1.48 +	}
    1.49 +      }
    1.50 +      
    1.51 +      typename AugGraph::NodeMap<Number> free(res_graph);
    1.52 +	
    1.53 +      Node n;
    1.54 +      //searching for augmenting path
    1.55 +      while ( !res_bfs.finished() ) { 
    1.56 +	AugOutEdgeIt e=res_bfs;
    1.57 +	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    1.58 +	  Node v=res_graph.tail(e);
    1.59 +	  Node w=res_graph.head(e);
    1.60 +	  pred.set(w, e);
    1.61 +	  if (res_graph.valid(pred.get(v))) {
    1.62 +	    free.set(w, std::min(free.get(v), res_graph.free(e)));
    1.63 +	  } else {
    1.64 +	    free.set(w, res_graph.free(e)); 
    1.65 +	  }
    1.66 +	  if (TMap(res_graph.head(e))) { 
    1.67 +	    n=res_graph.head(e);
    1.68 +	    _augment=true; 
    1.69 +	    break; 
    1.70 +	  }
    1.71 +	}
    1.72 +	
    1.73 +	++res_bfs;
    1.74 +      } //end of searching augmenting path
    1.75 +
    1.76 +      if (_augment) {
    1.77 +	//Node n=t;
    1.78 +	Number augment_value=free.get(t);
    1.79 +	while (res_graph.valid(pred.get(n))) { 
    1.80 +	  AugEdge e=pred.get(n);
    1.81 +	  res_graph.augment(e, augment_value); 
    1.82 +	  n=res_graph.tail(e);
    1.83 +	}
    1.84 +      }
    1.85 +
    1.86 +      return _augment;
    1.87 +    }
    1.88 +
    1.89 +//     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
    1.90 +//       bool _augment=false;
    1.91 +
    1.92 +//       AugGraph res_graph(*G, *flow, *capacity);
    1.93 +
    1.94 +//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    1.95 +//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
    1.96 +
    1.97 +//       bfs.pushAndSetReached(s);
    1.98 +//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    1.99 +//       while ( !bfs.finished() ) { 
   1.100 +// 	AugOutEdgeIt e=bfs;
   1.101 +// 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   1.102 +// 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   1.103 +// 	}
   1.104 +	
   1.105 +// 	++bfs;
   1.106 +//       } //computing distances from s in the residual graph
   1.107 +
   1.108 +//       MutableGraph F;
   1.109 +//       typename AugGraph::NodeMap<typename MutableGraph::Node> 
   1.110 +// 	res_graph_to_F(res_graph);
   1.111 +//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   1.112 +// 	res_graph_to_F.set(n, F.addNode());
   1.113 +//       }
   1.114 +      
   1.115 +//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
   1.116 +//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
   1.117 +
   1.118 +//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
   1.119 +//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
   1.120 +
   1.121 +//       //Making F to the graph containing the edges of the residual graph 
   1.122 +//       //which are in some shortest paths
   1.123 +//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
   1.124 +// 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
   1.125 +// 	  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.126 +// 	  original_edge.update();
   1.127 +// 	  original_edge.set(f, e);
   1.128 +// 	  residual_capacity.update();
   1.129 +// 	  residual_capacity.set(f, res_graph.free(e));
   1.130 +// 	} 
   1.131 +//       }
   1.132 +
   1.133 +//       bool __augment=true;
   1.134 +
   1.135 +//       while (__augment) {
   1.136 +// 	__augment=false;
   1.137 +// 	//computing blocking flow with dfs
   1.138 +// 	typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
   1.139 +// 	DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
   1.140 +// 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
   1.141 +// 	pred.set(sF, typename MutableGraph::Edge(INVALID));
   1.142 +// 	//invalid iterators for sources
   1.143 +
   1.144 +// 	typename MutableGraph::NodeMap<Number> free(F);
   1.145 +
   1.146 +// 	dfs.pushAndSetReached(sF);      
   1.147 +// 	while (!dfs.finished()) {
   1.148 +// 	  ++dfs;
   1.149 +// 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   1.150 +// 	    if (dfs.isBNodeNewlyReached()) {
   1.151 +// 	      typename MutableGraph::Node v=F.aNode(dfs);
   1.152 +// 	      typename MutableGraph::Node w=F.bNode(dfs);
   1.153 +// 	      pred.set(w, dfs);
   1.154 +// 	      if (F.valid(pred.get(v))) {
   1.155 +// 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
   1.156 +// 	      } else {
   1.157 +// 		free.set(w, residual_capacity.get(dfs)); 
   1.158 +// 	      }
   1.159 +// 	      if (w==tF) { 
   1.160 +// 		__augment=true; 
   1.161 +// 		_augment=true;
   1.162 +// 		break; 
   1.163 +// 	      }
   1.164 +	      
   1.165 +// 	    } else {
   1.166 +// 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   1.167 +// 	    }
   1.168 +// 	  } 
   1.169 +// 	}
   1.170 +
   1.171 +// 	if (__augment) {
   1.172 +// 	  typename MutableGraph::Node n=tF;
   1.173 +// 	  Number augment_value=free.get(tF);
   1.174 +// 	  while (F.valid(pred.get(n))) { 
   1.175 +// 	    typename MutableGraph::Edge e=pred.get(n);
   1.176 +// 	    res_graph.augment(original_edge.get(e), augment_value); 
   1.177 +// 	    n=F.tail(e);
   1.178 +// 	    if (residual_capacity.get(e)==augment_value) 
   1.179 +// 	      F.erase(e); 
   1.180 +// 	    else 
   1.181 +// 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   1.182 +// 	  }
   1.183 +// 	}
   1.184 +	
   1.185 +//       }
   1.186 +            
   1.187 +//       return _augment;
   1.188 +//     }
   1.189 +//     bool augmentOnBlockingFlow2() {
   1.190 +//       bool _augment=false;
   1.191 +
   1.192 +//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
   1.193 +//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
   1.194 +//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
   1.195 +//       typedef typename EAugGraph::Edge EAugEdge;
   1.196 +
   1.197 +//       EAugGraph res_graph(*G, *flow, *capacity);
   1.198 +
   1.199 +//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
   1.200 +//       BfsIterator4< 
   1.201 +// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
   1.202 +// 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
   1.203 +// 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
   1.204 +      
   1.205 +//       bfs.pushAndSetReached(s);
   1.206 +
   1.207 +//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
   1.208 +// 	NodeMap<int>& dist=res_graph.dist;
   1.209 +
   1.210 +//       while ( !bfs.finished() ) {
   1.211 +// 	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
   1.212 +// 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   1.213 +// 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   1.214 +// 	}
   1.215 +// 	++bfs;	
   1.216 +//       } //computing distances from s in the residual graph
   1.217 +
   1.218 +//       bool __augment=true;
   1.219 +
   1.220 +//       while (__augment) {
   1.221 +
   1.222 +// 	__augment=false;
   1.223 +// 	//computing blocking flow with dfs
   1.224 +// 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
   1.225 +// 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
   1.226 +// 	  dfs(res_graph);
   1.227 +// 	typename EAugGraph::NodeMap<EAugEdge> pred(res_graph); 
   1.228 +// 	pred.set(s, EAugEdge(INVALID));
   1.229 +// 	//invalid iterators for sources
   1.230 +
   1.231 +// 	typename EAugGraph::NodeMap<Number> free(res_graph);
   1.232 +
   1.233 +// 	dfs.pushAndSetReached(s);
   1.234 +// 	while (!dfs.finished()) {
   1.235 +// 	  ++dfs;
   1.236 +// 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
   1.237 +// 	    if (dfs.isBNodeNewlyReached()) {
   1.238 +	  
   1.239 +// 	      typename EAugGraph::Node v=res_graph.aNode(dfs);
   1.240 +// 	      typename EAugGraph::Node w=res_graph.bNode(dfs);
   1.241 +
   1.242 +// 	      pred.set(w, EAugOutEdgeIt(dfs));
   1.243 +// 	      if (res_graph.valid(pred.get(v))) {
   1.244 +// 		free.set(w, std::min(free.get(v), res_graph.free(dfs)));
   1.245 +// 	      } else {
   1.246 +// 		free.set(w, res_graph.free(dfs)); 
   1.247 +// 	      }
   1.248 +	      
   1.249 +// 	      if (w==t) { 
   1.250 +// 		__augment=true; 
   1.251 +// 		_augment=true;
   1.252 +// 		break; 
   1.253 +// 	      }
   1.254 +// 	    } else {
   1.255 +// 	      res_graph.erase(dfs);
   1.256 +// 	    }
   1.257 +// 	  } 
   1.258 +
   1.259 +// 	}
   1.260 +
   1.261 +// 	if (__augment) {
   1.262 +// 	  typename EAugGraph::Node n=t;
   1.263 +// 	  Number augment_value=free.get(t);
   1.264 +// 	  while (res_graph.valid(pred.get(n))) { 
   1.265 +// 	    EAugEdge e=pred.get(n);
   1.266 +// 	    res_graph.augment(e, augment_value);
   1.267 +// 	    n=res_graph.tail(e);
   1.268 +// 	    if (res_graph.free(e)==0)
   1.269 +// 	      res_graph.erase(e);
   1.270 +// 	  }
   1.271 +// 	}
   1.272 +      
   1.273 +//       }
   1.274 +            
   1.275 +//       return _augment;
   1.276 +//     }
   1.277 +    void run() {
   1.278 +      //int num_of_augmentations=0;
   1.279 +      while (augmentOnShortestPath()) { 
   1.280 +	//while (augmentOnBlockingFlow<MutableGraph>()) { 
   1.281 +	//std::cout << ++num_of_augmentations << " ";
   1.282 +	//std::cout<<std::endl;
   1.283 +      } 
   1.284 +    }
   1.285 +    template<typename MutableGraph> void run() {
   1.286 +      //int num_of_augmentations=0;
   1.287 +      //while (augmentOnShortestPath()) { 
   1.288 +	while (augmentOnBlockingFlow<MutableGraph>()) { 
   1.289 +	//std::cout << ++num_of_augmentations << " ";
   1.290 +	//std::cout<<std::endl;
   1.291 +      } 
   1.292 +    }
   1.293 +    Number flowValue() { 
   1.294 +      Number a=0;
   1.295 +      OutEdgeIt e;
   1.296 +      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
   1.297 +	a+=flow->get(e);
   1.298 +      }
   1.299 +      return a;
   1.300 +    }
   1.301 +  };
   1.302 +
   1.303 +
   1.304 +
   1.305 +
   1.306 +
   1.307    
   1.308  //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
   1.309  //   class MaxFlow2 {