.
authormarci
Wed, 17 Mar 2004 13:33:13 +0000
changeset 191efea403c9595
parent 190 6f8e34f638c0
child 192 100770da4336
.
src/work/edmonds_karp.h
     1.1 --- a/src/work/edmonds_karp.h	Tue Mar 16 15:28:04 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.h	Wed Mar 17 13:33:13 2004 +0000
     1.3 @@ -266,15 +266,9 @@
     1.4      typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     1.5      typedef typename AugGraph::Edge AugEdge;
     1.6  
     1.7 -    //AugGraph res_graph;    
     1.8 -    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
     1.9 -    //typename AugGraph::NodeMap<AugEdge> pred; 
    1.10 -    //typename AugGraph::NodeMap<Number> free;
    1.11    public:
    1.12      MaxFlow(const Graph& _G, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) : 
    1.13 -      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,  
    1.14 -      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph) 
    1.15 -      { }
    1.16 +      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
    1.17      bool augmentOnShortestPath() {
    1.18        AugGraph res_graph(*G, *flow, *capacity);
    1.19        bool _augment=false;
    1.20 @@ -290,7 +284,7 @@
    1.21  	
    1.22        //searching for augmenting path
    1.23        while ( !res_bfs.finished() ) { 
    1.24 -	AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    1.25 +	AugOutEdgeIt e=res_bfs;
    1.26  	if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    1.27  	  Node v=res_graph.tail(e);
    1.28  	  Node w=res_graph.head(e);
    1.29 @@ -312,7 +306,6 @@
    1.30  	while (res_graph.valid(pred.get(n))) { 
    1.31  	  AugEdge e=pred.get(n);
    1.32  	  res_graph.augment(e, augment_value); 
    1.33 -	  //e.augment(augment_value); 
    1.34  	  n=res_graph.tail(e);
    1.35  	}
    1.36        }
    1.37 @@ -320,21 +313,7 @@
    1.38        return _augment;
    1.39      }
    1.40  
    1.41 -    template<typename MutableGraph> bool augmentOnBlockingFlow() {
    1.42 -      
    1.43 -//       std::cout << "number of nodes: " << G->nodeNum() << std::endl;
    1.44 -//       typename Graph::NodeIt n; 
    1.45 -//       G->first(n);
    1.46 -//       for( ; G->valid(n); G->next(n)) {
    1.47 -// 	std::cout << G->id(n) << std::endl;
    1.48 -//       }
    1.49 -//       std::cout << "meg elek 1";
    1.50 -
    1.51 -//       for(typename Graph::NodeIt n=G->template first<typename Graph::NodeIt>(); G->valid(n); G->next(n)) {
    1.52 -// 	std::cout << G->id(n) << std::endl;
    1.53 -//       }
    1.54 -//       std::cout << "meg elek 2";
    1.55 -      
    1.56 +    template<typename MutableGraph> bool augmentOnBlockingFlow() {      
    1.57        bool _augment=false;
    1.58  
    1.59        AugGraph res_graph(*G, *flow, *capacity);
    1.60 @@ -345,7 +324,7 @@
    1.61        bfs.pushAndSetReached(s);
    1.62        typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    1.63        while ( !bfs.finished() ) { 
    1.64 -	AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    1.65 +	AugOutEdgeIt e=bfs;
    1.66  	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    1.67  	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    1.68  	}
    1.69 @@ -353,11 +332,6 @@
    1.70  	++bfs;
    1.71        } //computing distances from s in the residual graph
    1.72  
    1.73 -//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    1.74 -// 	std::cout << res_graph.id(n) << std::endl;
    1.75 -//       }
    1.76 -//       std::cout << "meg elek";
    1.77 -
    1.78        MutableGraph F;
    1.79        typename AugGraph::NodeMap<typename MutableGraph::Node> 
    1.80  	res_graph_to_F(res_graph);
    1.81 @@ -383,10 +357,6 @@
    1.82  	} 
    1.83        }
    1.84  
    1.85 -//       for(typename MutableGraph::NodeIt n=F.template first<typename MutableGraph::NodeIt>(); F.valid(n); F.next(n)) {
    1.86 -// 	std::cout << F.id(n) << std::endl;
    1.87 -//       }
    1.88 -
    1.89        bool __augment=true;
    1.90  
    1.91        while (__augment) {
    1.92 @@ -405,10 +375,6 @@
    1.93  	  ++dfs;
    1.94  	  if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    1.95  	    if (dfs.isBNodeNewlyReached()) {
    1.96 -// 	      std::cout << "OutEdgeIt: " << dfs; 
    1.97 -// 	      std::cout << " aNode: " << F.aNode(dfs); 
    1.98 -// 	      std::cout << " bNode: " << F.bNode(dfs) << " ";
    1.99 -	  
   1.100  	      typename MutableGraph::Node v=F.aNode(dfs);
   1.101  	      typename MutableGraph::Node w=F.bNode(dfs);
   1.102  	      pred.set(w, dfs);
   1.103 @@ -418,7 +384,6 @@
   1.104  		free.set(w, residual_capacity.get(dfs)); 
   1.105  	      }
   1.106  	      if (w==tF) { 
   1.107 -		//std::cout << "AUGMENTATION"<<std::endl;
   1.108  		__augment=true; 
   1.109  		_augment=true;
   1.110  		break; 
   1.111 @@ -436,7 +401,6 @@
   1.112  	  while (F.valid(pred.get(n))) { 
   1.113  	    typename MutableGraph::Edge e=pred.get(n);
   1.114  	    res_graph.augment(original_edge.get(e), augment_value); 
   1.115 -	    //original_edge.get(e).augment(augment_value); 
   1.116  	    n=F.tail(e);
   1.117  	    if (residual_capacity.get(e)==augment_value) 
   1.118  	      F.erase(e); 
   1.119 @@ -459,49 +423,28 @@
   1.120  
   1.121        EAugGraph res_graph(*G, *flow, *capacity);
   1.122  
   1.123 -      //std::cout << "meg jo1" << std::endl;
   1.124 -
   1.125        //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
   1.126        BfsIterator4< 
   1.127  	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>, 
   1.128  	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt, 
   1.129  	ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
   1.130        
   1.131 -      //std::cout << "meg jo2" << std::endl;
   1.132 +      bfs.pushAndSetReached(s);
   1.133  
   1.134 -      bfs.pushAndSetReached(s);
   1.135 -      //std::cout << "meg jo2.5" << std::endl;
   1.136 -
   1.137 -      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
   1.138        typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
   1.139  	NodeMap<int>& dist=res_graph.dist;
   1.140 -      //std::cout << "meg jo2.6" << std::endl;
   1.141  
   1.142        while ( !bfs.finished() ) {
   1.143  	typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
   1.144 -//	EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
   1.145 - 	//if (res_graph.valid(e)) {
   1.146 - 	//    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
   1.147 - 	//}
   1.148  	if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
   1.149  	  dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
   1.150  	}
   1.151 -	
   1.152  	++bfs;	
   1.153        } //computing distances from s in the residual graph
   1.154  
   1.155 -
   1.156 -      //std::cout << "meg jo3" << std::endl;
   1.157 -
   1.158 -//       typedef typename EAugGraph::NodeIt EAugNodeIt;
   1.159 -//       for(EAugNodeIt n=res_graph.template first<EAugNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
   1.160 -// 	std::cout << "dist: " << dist.get(n) << std::endl;
   1.161 -//       }
   1.162 -
   1.163        bool __augment=true;
   1.164  
   1.165        while (__augment) {
   1.166 -//	std::cout << "new iteration"<< std::endl;
   1.167  
   1.168  	__augment=false;
   1.169  	//computing blocking flow with dfs
   1.170 @@ -519,36 +462,23 @@
   1.171  	  ++dfs;
   1.172  	  if (res_graph.valid(EAugOutEdgeIt(dfs))) { 
   1.173  	    if (dfs.isBNodeNewlyReached()) {
   1.174 -// 	      std::cout << "OutEdgeIt: " << dfs; 
   1.175 -// 	      std::cout << " aNode: " << res_graph.aNode(dfs); 
   1.176 -// 	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
   1.177 -// 	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
   1.178  	  
   1.179  	      typename EAugGraph::Node v=res_graph.aNode(dfs);
   1.180  	      typename EAugGraph::Node w=res_graph.bNode(dfs);
   1.181  
   1.182  	      pred.set(w, EAugOutEdgeIt(dfs));
   1.183 -
   1.184 -	      //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
   1.185  	      if (res_graph.valid(pred.get(v))) {
   1.186 -		free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
   1.187 +		free.set(w, std::min(free.get(v), res_graph.free(dfs)));
   1.188  	      } else {
   1.189 -		free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs))); 
   1.190 +		free.set(w, res_graph.free(dfs)); 
   1.191  	      }
   1.192  	      
   1.193  	      if (w==t) { 
   1.194 -//		std::cout << "t is reached, AUGMENTATION"<<std::endl;
   1.195  		__augment=true; 
   1.196  		_augment=true;
   1.197  		break; 
   1.198  	      }
   1.199  	    } else {
   1.200 -//	      std::cout << "<<DELETE ";
   1.201 -//	      std::cout << " aNode: " << res_graph.aNode(dfs); 
   1.202 -//	      std::cout << " res cap: " << EAugOutEdgeIt(dfs).free(); 
   1.203 -//	      std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
   1.204 -//	      std::cout << "DELETE>> ";
   1.205 -
   1.206  	      res_graph.erase(dfs);
   1.207  	    }
   1.208  	  } 
   1.209 @@ -558,11 +488,9 @@
   1.210  	if (__augment) {
   1.211  	  typename EAugGraph::Node n=t;
   1.212  	  Number augment_value=free.get(t);
   1.213 -//	  std::cout << "av:" << augment_value << std::endl;
   1.214  	  while (res_graph.valid(pred.get(n))) { 
   1.215  	    EAugEdge e=pred.get(n);
   1.216  	    res_graph.augment(e, augment_value);
   1.217 -	    //e.augment(augment_value); 
   1.218  	    n=res_graph.tail(e);
   1.219  	    if (res_graph.free(e)==0)
   1.220  	      res_graph.erase(e);