src/work/edmonds_karp.h
changeset 264 fe81c4b117f4
parent 259 509ba9f136d2
child 265 bf7aea53635a
equal deleted inserted replaced
10:4d92c597bc99 11:573bbddac962
   311       }
   311       }
   312 
   312 
   313       return _augment;
   313       return _augment;
   314     }
   314     }
   315 
   315 
       
   316 //     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
       
   317 //       bool _augment=false;
       
   318 
       
   319 //       AugGraph res_graph(*G, *flow, *capacity);
       
   320 
       
   321 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
       
   322 //       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
       
   323 
       
   324 //       bfs.pushAndSetReached(s);
       
   325 //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
       
   326 //       while ( !bfs.finished() ) { 
       
   327 // 	AugOutEdgeIt e=bfs;
       
   328 // 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
       
   329 // 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
       
   330 // 	}
       
   331 	
       
   332 // 	++bfs;
       
   333 //       } //computing distances from s in the residual graph
       
   334 
       
   335 //       MutableGraph F;
       
   336 //       typename AugGraph::NodeMap<typename MutableGraph::Node> 
       
   337 // 	res_graph_to_F(res_graph);
       
   338 //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
       
   339 // 	res_graph_to_F.set(n, F.addNode());
       
   340 //       }
       
   341       
       
   342 //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
       
   343 //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
       
   344 
       
   345 //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
       
   346 //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
       
   347 
       
   348 //       //Making F to the graph containing the edges of the residual graph 
       
   349 //       //which are in some shortest paths
       
   350 //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
       
   351 // 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
       
   352 // 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
       
   353 // 	  original_edge.update();
       
   354 // 	  original_edge.set(f, e);
       
   355 // 	  residual_capacity.update();
       
   356 // 	  residual_capacity.set(f, res_graph.free(e));
       
   357 // 	} 
       
   358 //       }
       
   359 
       
   360 //       bool __augment=true;
       
   361 
       
   362 //       while (__augment) {
       
   363 // 	__augment=false;
       
   364 // 	//computing blocking flow with dfs
       
   365 // 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
       
   366 // 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
       
   367 // 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
       
   368 // 	pred.set(sF, typename MutableGraph::Edge(INVALID));
       
   369 // 	//invalid iterators for sources
       
   370 
       
   371 // 	typename MutableGraph::NodeMap<Number> free(F);
       
   372 
       
   373 // 	dfs.pushAndSetReached(sF);      
       
   374 // 	while (!dfs.finished()) {
       
   375 // 	  ++dfs;
       
   376 // 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
       
   377 // 	    if (dfs.isBNodeNewlyReached()) {
       
   378 // 	      typename MutableGraph::Node v=F.aNode(dfs);
       
   379 // 	      typename MutableGraph::Node w=F.bNode(dfs);
       
   380 // 	      pred.set(w, dfs);
       
   381 // 	      if (F.valid(pred.get(v))) {
       
   382 // 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
       
   383 // 	      } else {
       
   384 // 		free.set(w, residual_capacity.get(dfs)); 
       
   385 // 	      }
       
   386 // 	      if (w==tF) { 
       
   387 // 		__augment=true; 
       
   388 // 		_augment=true;
       
   389 // 		break; 
       
   390 // 	      }
       
   391 	      
       
   392 // 	    } else {
       
   393 // 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
       
   394 // 	    }
       
   395 // 	  } 
       
   396 // 	}
       
   397 
       
   398 // 	if (__augment) {
       
   399 // 	  typename MutableGraph::Node n=tF;
       
   400 // 	  Number augment_value=free.get(tF);
       
   401 // 	  while (F.valid(pred.get(n))) { 
       
   402 // 	    typename MutableGraph::Edge e=pred.get(n);
       
   403 // 	    res_graph.augment(original_edge.get(e), augment_value); 
       
   404 // 	    n=F.tail(e);
       
   405 // 	    if (residual_capacity.get(e)==augment_value) 
       
   406 // 	      F.erase(e); 
       
   407 // 	    else 
       
   408 // 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
       
   409 // 	  }
       
   410 // 	}
       
   411 	
       
   412 //       }
       
   413             
       
   414 //       return _augment;
       
   415 //     }
       
   416 
       
   417     template<typename GraphWrapper> 
       
   418     class DistanceMap {
       
   419     protected:
       
   420       GraphWrapper gw;
       
   421       typename GraphWrapper::NodeMap<int> dist; 
       
   422     public:
       
   423       DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
       
   424       //NodeMap(const ListGraph& _G, T a) : 
       
   425       //G(_G), container(G.node_id, a) { }
       
   426       void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; }
       
   427       int get(const typename GraphWrapper::Node& n) const { return dist[n]; }
       
   428       bool get(const typename GraphWrapper::Edge& e) const { 
       
   429 	return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 
       
   430       }
       
   431       //typename std::vector<T>::reference operator[](Node n) { 
       
   432       //return container[/*G.id(n)*/n.node->id]; }
       
   433       //typename std::vector<T>::const_reference operator[](Node n) const { 
       
   434       //return container[/*G.id(n)*/n.node->id]; 
       
   435     };
       
   436 
   316     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
   437     template<typename MutableGraph> bool augmentOnBlockingFlow() {      
   317       bool _augment=false;
   438       bool _augment=false;
   318 
   439 
   319       AugGraph res_graph(*G, *flow, *capacity);
   440       AugGraph res_graph(*G, *flow, *capacity);
   320 
   441 
   321       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   442       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   322       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
   443       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
   323 
   444 
   324       bfs.pushAndSetReached(s);
   445       bfs.pushAndSetReached(s);
   325       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   446       //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
       
   447       DistanceMap<AugGraph> dist(res_graph);
   326       while ( !bfs.finished() ) { 
   448       while ( !bfs.finished() ) { 
   327 	AugOutEdgeIt e=bfs;
   449 	AugOutEdgeIt e=bfs;
   328 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   450 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   329 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   451 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   330 	}
   452 	}
   331 	
       
   332 	++bfs;
   453 	++bfs;
   333       } //computing distances from s in the residual graph
   454       } //computing distances from s in the residual graph
   334 
   455 
       
   456 //       MutableGraph F;
       
   457 //       typename AugGraph::NodeMap<typename MutableGraph::Node> 
       
   458 // 	res_graph_to_F(res_graph);
       
   459 //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
       
   460 // 	res_graph_to_F.set(n, F.addNode());
       
   461 //       }
       
   462       
       
   463 //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
       
   464 //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
       
   465 
       
   466 //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
       
   467 //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
       
   468 
       
   469 //       //Making F to the graph containing the edges of the residual graph 
       
   470 //       //which are in some shortest paths
       
   471 //       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
       
   472 // 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
       
   473 // 	  typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
       
   474 // 	  original_edge.update();
       
   475 // 	  original_edge.set(f, e);
       
   476 // 	  residual_capacity.update();
       
   477 // 	  residual_capacity.set(f, res_graph.free(e));
       
   478 // 	} 
       
   479 //       }
       
   480 
   335       MutableGraph F;
   481       MutableGraph F;
       
   482       typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph;
       
   483       FilterResGraph filter_res_graph(res_graph, dist);
   336       typename AugGraph::NodeMap<typename MutableGraph::Node> 
   484       typename AugGraph::NodeMap<typename MutableGraph::Node> 
   337 	res_graph_to_F(res_graph);
   485 	res_graph_to_F(res_graph);
   338       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   486       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   339 	res_graph_to_F.set(n, F.addNode());
   487 	res_graph_to_F.set(n, F.addNode());
   340       }
   488       }
   361 
   509 
   362       while (__augment) {
   510       while (__augment) {
   363 	__augment=false;
   511 	__augment=false;
   364 	//computing blocking flow with dfs
   512 	//computing blocking flow with dfs
   365 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
   513 	typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
   366 	DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
   514 	DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F);
   367 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
   515 	typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
   368 	pred.set(sF, typename MutableGraph::Edge(INVALID));
   516 	pred.set(sF, typename MutableGraph::Edge(INVALID));
   369 	//invalid iterators for sources
   517 	//invalid iterators for sources
   370 
   518 
   371 	typename MutableGraph::NodeMap<Number> free(F);
   519 	typename MutableGraph::NodeMap<Number> free(F);
   411 	
   559 	
   412       }
   560       }
   413             
   561             
   414       return _augment;
   562       return _augment;
   415     }
   563     }
       
   564 
   416     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
   565     template<typename MutableGraph> bool augmentOnBlockingFlow1() {      
   417       bool _augment=false;
   566       bool _augment=false;
   418 
   567 
   419       AugGraph res_graph(*G, *flow, *capacity);
   568       AugGraph res_graph(*G, *flow, *capacity);
   420 
   569 
   421       //bfs for distances on the residual graph
   570       //bfs for distances on the residual graph
   422       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   571       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   423       BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);
   572       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
   424       bfs.pushAndSetReached(s);
   573       bfs.pushAndSetReached(s);
   425       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   574       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   426 
   575 
   427       //F will contain the physical copy of the residual graph
   576       //F will contain the physical copy of the residual graph
   428       //with the set of edges which areon shortest paths
   577       //with the set of edges which areon shortest paths