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);