1.1 --- a/src/work/edmonds_karp.hh Thu Mar 11 12:55:50 2004 +0000
1.2 +++ b/src/work/edmonds_karp.hh Thu Mar 11 14:15:07 2004 +0000
1.3 @@ -279,7 +279,7 @@
1.4 bool _augment=false;
1.5
1.6 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.7 - BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.8 + BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.9 res_bfs.pushAndSetReached(s);
1.10
1.11 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.12 @@ -296,9 +296,9 @@
1.13 NodeIt w=res_graph.head(e);
1.14 pred.set(w, e);
1.15 if (res_graph.valid(pred.get(v))) {
1.16 - free.set(w, std::min(free.get(v), e.free()));
1.17 + free.set(w, std::min(free.get(v), res_graph.free(e)));
1.18 } else {
1.19 - free.set(w, e.free());
1.20 + free.set(w, res_graph.free(e));
1.21 }
1.22 if (res_graph.head(e)==t) { _augment=true; break; }
1.23 }
1.24 @@ -311,7 +311,8 @@
1.25 Number augment_value=free.get(t);
1.26 while (res_graph.valid(pred.get(n))) {
1.27 AugEdgeIt e=pred.get(n);
1.28 - e.augment(augment_value);
1.29 + res_graph.augment(e, augment_value);
1.30 + //e.augment(augment_value);
1.31 n=res_graph.tail(e);
1.32 }
1.33 }
1.34 @@ -358,7 +359,7 @@
1.35 original_edge.update();
1.36 original_edge.set(f, e);
1.37 residual_capacity.update();
1.38 - residual_capacity.set(f, e.free());
1.39 + residual_capacity.set(f, res_graph.free(e));
1.40 }
1.41 }
1.42
1.43 @@ -376,44 +377,30 @@
1.44 while (!dfs.finished()) {
1.45 ++dfs;
1.46 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.47 - //std::cout << "OutEdgeIt: " << dfs;
1.48 - //std::cout << " aNode: " << F.aNode(dfs);
1.49 - //std::cout << " bNode: " << F.bNode(dfs) << " ";
1.50 + if (dfs.isBNodeNewlyReached()) {
1.51 +// std::cout << "OutEdgeIt: " << dfs;
1.52 +// std::cout << " aNode: " << F.aNode(dfs);
1.53 +// std::cout << " bNode: " << F.bNode(dfs) << " ";
1.54
1.55 - typename MutableGraph::NodeIt v=F.aNode(dfs);
1.56 - typename MutableGraph::NodeIt w=F.bNode(dfs);
1.57 - pred.set(w, dfs);
1.58 - if (F.valid(pred.get(v))) {
1.59 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.60 + typename MutableGraph::NodeIt v=F.aNode(dfs);
1.61 + typename MutableGraph::NodeIt w=F.bNode(dfs);
1.62 + pred.set(w, dfs);
1.63 + if (F.valid(pred.get(v))) {
1.64 + free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.65 + } else {
1.66 + free.set(w, residual_capacity.get(dfs));
1.67 + }
1.68 + if (w==tF) {
1.69 + //std::cout << "AUGMENTATION"<<std::endl;
1.70 + __augment=true;
1.71 + _augment=true;
1.72 + break;
1.73 + }
1.74 +
1.75 } else {
1.76 - free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
1.77 - }
1.78 - if (w==tF) {
1.79 - //std::cout << "AUGMENTATION"<<std::endl;
1.80 - __augment=true;
1.81 - _augment=true;
1.82 - break;
1.83 - }
1.84 - } else {
1.85 - //std::cout << "OutEdgeIt: " << "invalid";
1.86 - //std::cout << " aNode: " << dfs.aNode();
1.87 - //std::cout << " bNode: " << "invalid" << " ";
1.88 - }
1.89 - if (dfs.isBNodeNewlyReached()) {
1.90 - //std::cout << "bNodeIsNewlyReached ";
1.91 - } else {
1.92 - //std::cout << "bNodeIsNotNewlyReached ";
1.93 - if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
1.94 - //std::cout << "DELETE ";
1.95 F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.96 }
1.97 }
1.98 - //if (dfs.isANodeExamined()) {
1.99 - //std::cout << "aNodeIsExamined ";
1.100 - //} else {
1.101 - //std::cout << "aNodeIsNotExamined ";
1.102 - //}
1.103 - //std::cout<<std::endl;
1.104 }
1.105
1.106 if (__augment) {
1.107 @@ -421,7 +408,8 @@
1.108 Number augment_value=free.get(tF);
1.109 while (F.valid(pred.get(n))) {
1.110 typename MutableGraph::EdgeIt e=pred.get(n);
1.111 - original_edge.get(e).augment(augment_value);
1.112 + res_graph.augment(original_edge.get(e), augment_value);
1.113 + //original_edge.get(e).augment(augment_value);
1.114 n=F.tail(e);
1.115 if (residual_capacity.get(e)==augment_value)
1.116 F.erase(e);
1.117 @@ -429,6 +417,127 @@
1.118 residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.119 }
1.120 }
1.121 +
1.122 + }
1.123 +
1.124 + return _augment;
1.125 + }
1.126 + bool augmentOnBlockingFlow2() {
1.127 + bool _augment=false;
1.128 +
1.129 + //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.130 + typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.131 + typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.132 + typedef typename EAugGraph::EdgeIt EAugEdgeIt;
1.133 +
1.134 + EAugGraph res_graph(*G, *flow, *capacity);
1.135 +
1.136 + //std::cout << "meg jo1" << std::endl;
1.137 +
1.138 + //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.139 + BfsIterator4<
1.140 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.141 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.142 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.143 +
1.144 + //std::cout << "meg jo2" << std::endl;
1.145 +
1.146 + bfs.pushAndSetReached(s);
1.147 + //std::cout << "meg jo2.5" << std::endl;
1.148 +
1.149 + //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.150 + typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.151 + NodeMap<int>& dist=res_graph.dist;
1.152 + //std::cout << "meg jo2.6" << std::endl;
1.153 +
1.154 + while ( !bfs.finished() ) {
1.155 + ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.156 +// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.157 + //if (res_graph.valid(e)) {
1.158 + // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
1.159 + //}
1.160 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.161 + dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.162 + }
1.163 +
1.164 + ++bfs;
1.165 + } //computing distances from s in the residual graph
1.166 +
1.167 +
1.168 + //std::cout << "meg jo3" << std::endl;
1.169 +
1.170 +// typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
1.171 +// for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.172 +// std::cout << "dist: " << dist.get(n) << std::endl;
1.173 +// }
1.174 +
1.175 + bool __augment=true;
1.176 +
1.177 + while (__augment) {
1.178 +// std::cout << "new iteration"<< std::endl;
1.179 +
1.180 + __augment=false;
1.181 + //computing blocking flow with dfs
1.182 + typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.183 + DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.184 + dfs(res_graph);
1.185 + typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
1.186 + typename EAugGraph::NodeMap<Number> free(res_graph);
1.187 +
1.188 + dfs.pushAndSetReached(s);
1.189 + while (!dfs.finished()) {
1.190 + ++dfs;
1.191 + if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.192 + if (dfs.isBNodeNewlyReached()) {
1.193 +// std::cout << "OutEdgeIt: " << dfs;
1.194 +// std::cout << " aNode: " << res_graph.aNode(dfs);
1.195 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
1.196 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
1.197 +
1.198 + typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
1.199 + typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
1.200 +
1.201 + pred.set(w, EAugOutEdgeIt(dfs));
1.202 +
1.203 + //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
1.204 + if (res_graph.valid(pred.get(v))) {
1.205 + free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
1.206 + } else {
1.207 + free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
1.208 + }
1.209 +
1.210 + if (w==t) {
1.211 +// std::cout << "t is reached, AUGMENTATION"<<std::endl;
1.212 + __augment=true;
1.213 + _augment=true;
1.214 + break;
1.215 + }
1.216 + } else {
1.217 +// std::cout << "<<DELETE ";
1.218 +// std::cout << " aNode: " << res_graph.aNode(dfs);
1.219 +// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
1.220 +// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
1.221 +// std::cout << "DELETE>> ";
1.222 +
1.223 + res_graph.erase(dfs);
1.224 + }
1.225 + }
1.226 +
1.227 + }
1.228 +
1.229 + if (__augment) {
1.230 + typename EAugGraph::NodeIt n=t;
1.231 + Number augment_value=free.get(t);
1.232 +// std::cout << "av:" << augment_value << std::endl;
1.233 + while (res_graph.valid(pred.get(n))) {
1.234 + EAugEdgeIt e=pred.get(n);
1.235 + res_graph.augment(e, augment_value);
1.236 + //e.augment(augment_value);
1.237 + n=res_graph.tail(e);
1.238 + if (res_graph.free(e)==0)
1.239 + res_graph.erase(e);
1.240 + }
1.241 + }
1.242
1.243 }
1.244