src/work/edmonds_karp.hh
changeset 227 cea88d0854a9
parent 155 8c6292ec54c6
equal deleted inserted replaced
14:1b5652316598 15:1faac9f4ca3b
   277     bool augmentOnShortestPath() {
   277     bool augmentOnShortestPath() {
   278       AugGraph res_graph(*G, *flow, *capacity);
   278       AugGraph res_graph(*G, *flow, *capacity);
   279       bool _augment=false;
   279       bool _augment=false;
   280       
   280       
   281       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   281       typedef typename AugGraph::NodeMap<bool> ReachedMap;
   282       BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
   282       BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
   283       res_bfs.pushAndSetReached(s);
   283       res_bfs.pushAndSetReached(s);
   284 	
   284 	
   285       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
   285       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph); 
   286       //filled up with invalid iterators
   286       //filled up with invalid iterators
   287       //pred.set(s, AugEdgeIt());
   287       //pred.set(s, AugEdgeIt());
   294 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
   294 	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
   295 	  NodeIt v=res_graph.tail(e);
   295 	  NodeIt v=res_graph.tail(e);
   296 	  NodeIt w=res_graph.head(e);
   296 	  NodeIt w=res_graph.head(e);
   297 	  pred.set(w, e);
   297 	  pred.set(w, e);
   298 	  if (res_graph.valid(pred.get(v))) {
   298 	  if (res_graph.valid(pred.get(v))) {
   299 	    free.set(w, std::min(free.get(v), e.free()));
   299 	    free.set(w, std::min(free.get(v), res_graph.free(e)));
   300 	  } else {
   300 	  } else {
   301 	    free.set(w, e.free()); 
   301 	    free.set(w, res_graph.free(e)); 
   302 	  }
   302 	  }
   303 	  if (res_graph.head(e)==t) { _augment=true; break; }
   303 	  if (res_graph.head(e)==t) { _augment=true; break; }
   304 	}
   304 	}
   305 	
   305 	
   306 	++res_bfs;
   306 	++res_bfs;
   309       if (_augment) {
   309       if (_augment) {
   310 	NodeIt n=t;
   310 	NodeIt n=t;
   311 	Number augment_value=free.get(t);
   311 	Number augment_value=free.get(t);
   312 	while (res_graph.valid(pred.get(n))) { 
   312 	while (res_graph.valid(pred.get(n))) { 
   313 	  AugEdgeIt e=pred.get(n);
   313 	  AugEdgeIt e=pred.get(n);
   314 	  e.augment(augment_value); 
   314 	  res_graph.augment(e, augment_value); 
       
   315 	  //e.augment(augment_value); 
   315 	  n=res_graph.tail(e);
   316 	  n=res_graph.tail(e);
   316 	}
   317 	}
   317       }
   318       }
   318 
   319 
   319       return _augment;
   320       return _augment;
   356 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
   357 	if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
   357 	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
   358 	  typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
   358 	  original_edge.update();
   359 	  original_edge.update();
   359 	  original_edge.set(f, e);
   360 	  original_edge.set(f, e);
   360 	  residual_capacity.update();
   361 	  residual_capacity.update();
   361 	  residual_capacity.set(f, e.free());
   362 	  residual_capacity.set(f, res_graph.free(e));
   362 	} 
   363 	} 
   363       }
   364       }
   364 
   365 
   365       bool __augment=true;
   366       bool __augment=true;
   366 
   367 
   374 
   375 
   375 	dfs.pushAndSetReached(sF);      
   376 	dfs.pushAndSetReached(sF);      
   376 	while (!dfs.finished()) {
   377 	while (!dfs.finished()) {
   377 	  ++dfs;
   378 	  ++dfs;
   378 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   379 	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
   379 	    //std::cout << "OutEdgeIt: " << dfs; 
   380 	    if (dfs.isBNodeNewlyReached()) {
   380 	    //std::cout << " aNode: " << F.aNode(dfs); 
   381 // 	      std::cout << "OutEdgeIt: " << dfs; 
   381 	    //std::cout << " bNode: " << F.bNode(dfs) << " ";
   382 // 	      std::cout << " aNode: " << F.aNode(dfs); 
       
   383 // 	      std::cout << " bNode: " << F.bNode(dfs) << " ";
   382 	  
   384 	  
   383 	    typename MutableGraph::NodeIt v=F.aNode(dfs);
   385 	      typename MutableGraph::NodeIt v=F.aNode(dfs);
   384 	    typename MutableGraph::NodeIt w=F.bNode(dfs);
   386 	      typename MutableGraph::NodeIt w=F.bNode(dfs);
   385 	    pred.set(w, dfs);
   387 	      pred.set(w, dfs);
   386 	    if (F.valid(pred.get(v))) {
   388 	      if (F.valid(pred.get(v))) {
   387 	      free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
   389 		free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
       
   390 	      } else {
       
   391 		free.set(w, residual_capacity.get(dfs)); 
       
   392 	      }
       
   393 	      if (w==tF) { 
       
   394 		//std::cout << "AUGMENTATION"<<std::endl;
       
   395 		__augment=true; 
       
   396 		_augment=true;
       
   397 		break; 
       
   398 	      }
       
   399 	      
   388 	    } else {
   400 	    } else {
   389 	      free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/); 
       
   390 	    }
       
   391 	    if (w==tF) { 
       
   392 	      //std::cout << "AUGMENTATION"<<std::endl;
       
   393 	      __augment=true; 
       
   394 	      _augment=true;
       
   395 	      break; 
       
   396 	    }
       
   397 	  } else { 
       
   398 	    //std::cout << "OutEdgeIt: " << "invalid"; 
       
   399 	    //std::cout << " aNode: " << dfs.aNode(); 
       
   400 	    //std::cout << " bNode: " << "invalid" << " ";
       
   401 	  }
       
   402 	  if (dfs.isBNodeNewlyReached()) { 
       
   403 	    //std::cout << "bNodeIsNewlyReached ";
       
   404 	  } else { 
       
   405 	    //std::cout << "bNodeIsNotNewlyReached ";
       
   406 	    if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
       
   407 	      //std::cout << "DELETE ";
       
   408 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   401 	      F.erase(typename MutableGraph::OutEdgeIt(dfs));
   409 	    }
   402 	    }
   410 	  } 
   403 	  } 
   411 	  //if (dfs.isANodeExamined()) { 
       
   412 	    //std::cout << "aNodeIsExamined ";
       
   413 	    //} else { 
       
   414 	    //std::cout << "aNodeIsNotExamined ";
       
   415 	    //} 
       
   416 	  //std::cout<<std::endl;
       
   417 	}
   404 	}
   418 
   405 
   419 	if (__augment) {
   406 	if (__augment) {
   420 	  typename MutableGraph::NodeIt n=tF;
   407 	  typename MutableGraph::NodeIt n=tF;
   421 	  Number augment_value=free.get(tF);
   408 	  Number augment_value=free.get(tF);
   422 	  while (F.valid(pred.get(n))) { 
   409 	  while (F.valid(pred.get(n))) { 
   423 	    typename MutableGraph::EdgeIt e=pred.get(n);
   410 	    typename MutableGraph::EdgeIt e=pred.get(n);
   424 	    original_edge.get(e).augment(augment_value); 
   411 	    res_graph.augment(original_edge.get(e), augment_value); 
       
   412 	    //original_edge.get(e).augment(augment_value); 
   425 	    n=F.tail(e);
   413 	    n=F.tail(e);
   426 	    if (residual_capacity.get(e)==augment_value) 
   414 	    if (residual_capacity.get(e)==augment_value) 
   427 	      F.erase(e); 
   415 	      F.erase(e); 
   428 	    else 
   416 	    else 
   429 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
   417 	      residual_capacity.set(e, residual_capacity.get(e)-augment_value);
       
   418 	  }
       
   419 	}
       
   420 	
       
   421       }
       
   422             
       
   423       return _augment;
       
   424     }
       
   425     bool augmentOnBlockingFlow2() {
       
   426       bool _augment=false;
       
   427 
       
   428       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
       
   429       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
       
   430       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
       
   431       typedef typename EAugGraph::EdgeIt EAugEdgeIt;
       
   432 
       
   433       EAugGraph res_graph(*G, *flow, *capacity);
       
   434 
       
   435       //std::cout << "meg jo1" << std::endl;
       
   436 
       
   437       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
       
   438       BfsIterator4< 
       
   439 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
       
   440 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
       
   441 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
       
   442       
       
   443       //std::cout << "meg jo2" << std::endl;
       
   444 
       
   445       bfs.pushAndSetReached(s);
       
   446       //std::cout << "meg jo2.5" << std::endl;
       
   447 
       
   448       //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
       
   449       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
       
   450 	NodeMap<int>& dist=res_graph.dist;
       
   451       //std::cout << "meg jo2.6" << std::endl;
       
   452 
       
   453       while ( !bfs.finished() ) {
       
   454 	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
       
   455 //	EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
       
   456  	//if (res_graph.valid(e)) {
       
   457  	//    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
       
   458  	//}
       
   459 	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
       
   460 	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
       
   461 	}
       
   462 	
       
   463 	++bfs;	
       
   464       } //computing distances from s in the residual graph
       
   465 
       
   466 
       
   467       //std::cout << "meg jo3" << std::endl;
       
   468 
       
   469 //       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
       
   470 //       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
       
   471 // 	std::cout << "dist: " << dist.get(n) << std::endl;
       
   472 //       }
       
   473 
       
   474       bool __augment=true;
       
   475 
       
   476       while (__augment) {
       
   477 //	std::cout << "new iteration"<< std::endl;
       
   478 
       
   479 	__augment=false;
       
   480 	//computing blocking flow with dfs
       
   481 	typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
       
   482 	DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap > 
       
   483 	  dfs(res_graph);
       
   484 	typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
       
   485 	typename EAugGraph::NodeMap<Number> free(res_graph);
       
   486 
       
   487 	dfs.pushAndSetReached(s);
       
   488 	while (!dfs.finished()) {
       
   489 	  ++dfs;
       
   490 	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
       
   491 	    if (dfs.isBNodeNewlyReached()) {
       
   492 // 	      std::cout << "OutEdgeIt: " << dfs; 
       
   493 // 	      std::cout << " aNode: " << res_graph.aNode(dfs); 
       
   494 // 	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
       
   495 // 	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
       
   496 	  
       
   497 	      typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
       
   498 	      typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
       
   499 
       
   500 	      pred.set(w, EAugOutEdgeIt(dfs));
       
   501 
       
   502 	      //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
       
   503 	      if (res_graph.valid(pred.get(v))) {
       
   504 		free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
       
   505 	      } else {
       
   506 		free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
       
   507 	      }
       
   508 	      
       
   509 	      if (w==t) { 
       
   510 //		std::cout << "t is reached, AUGMENTATION"<<std::endl;
       
   511 		__augment=true; 
       
   512 		_augment=true;
       
   513 		break; 
       
   514 	      }
       
   515 	    } else {
       
   516 //	      std::cout << "<<DELETE ";
       
   517 //	      std::cout << " aNode: " << res_graph.aNode(dfs); 
       
   518 //	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
       
   519 //	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
       
   520 //	      std::cout << "DELETE>> ";
       
   521 
       
   522 	      res_graph.erase(dfs);
       
   523 	    }
       
   524 	  } 
       
   525 
       
   526 	}
       
   527 
       
   528 	if (__augment) {
       
   529 	  typename EAugGraph::NodeIt n=t;
       
   530 	  Number augment_value=free.get(t);
       
   531 //	  std::cout << "av:" << augment_value << std::endl;
       
   532 	  while (res_graph.valid(pred.get(n))) { 
       
   533 	    EAugEdgeIt e=pred.get(n);
       
   534 	    res_graph.augment(e, augment_value);
       
   535 	    //e.augment(augment_value); 
       
   536 	    n=res_graph.tail(e);
       
   537 	    if (res_graph.free(e)==0)
       
   538 	      res_graph.erase(e);
   430 	  }
   539 	  }
   431 	}
   540 	}
   432       
   541       
   433       }
   542       }
   434             
   543