1.1 --- a/src/work/edmonds_karp.hh Sat Apr 03 14:22:33 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,677 +0,0 @@
1.4 -#ifndef EDMONDS_KARP_HH
1.5 -#define EDMONDS_KARP_HH
1.6 -
1.7 -#include <algorithm>
1.8 -#include <list>
1.9 -#include <iterator>
1.10 -
1.11 -#include <bfs_iterator.hh>
1.12 -//#include <time_measure.h>
1.13 -
1.14 -namespace hugo {
1.15 -
1.16 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.17 - class ResGraph {
1.18 - public:
1.19 - typedef typename Graph::NodeIt NodeIt;
1.20 - typedef typename Graph::EachNodeIt EachNodeIt;
1.21 - private:
1.22 - typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.23 - const Graph& G;
1.24 - FlowMap& flow;
1.25 - const CapacityMap& capacity;
1.26 - public:
1.27 - ResGraph(const Graph& _G, FlowMap& _flow,
1.28 - const CapacityMap& _capacity) :
1.29 - G(_G), flow(_flow), capacity(_capacity) { }
1.30 -
1.31 - class EdgeIt;
1.32 - class OutEdgeIt;
1.33 - friend class EdgeIt;
1.34 - friend class OutEdgeIt;
1.35 -
1.36 - class EdgeIt {
1.37 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.38 - protected:
1.39 - const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.40 - OldSymEdgeIt sym;
1.41 - public:
1.42 - EdgeIt() { }
1.43 - //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
1.44 - Number free() const {
1.45 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.46 - return (resG->capacity.get(sym)-resG->flow.get(sym));
1.47 - } else {
1.48 - return (resG->flow.get(sym));
1.49 - }
1.50 - }
1.51 - bool valid() const { return sym.valid(); }
1.52 - void augment(Number a) const {
1.53 - if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.54 - resG->flow.set(sym, resG->flow.get(sym)+a);
1.55 - //resG->flow[sym]+=a;
1.56 - } else {
1.57 - resG->flow.set(sym, resG->flow.get(sym)-a);
1.58 - //resG->flow[sym]-=a;
1.59 - }
1.60 - }
1.61 - };
1.62 -
1.63 - class OutEdgeIt : public EdgeIt {
1.64 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.65 - public:
1.66 - OutEdgeIt() { }
1.67 - //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.68 - private:
1.69 - OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
1.70 - resG=&_resG;
1.71 - sym=resG->G.template first<OldSymEdgeIt>(v);
1.72 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.73 - }
1.74 - public:
1.75 - OutEdgeIt& operator++() {
1.76 - ++sym;
1.77 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.78 - return *this;
1.79 - }
1.80 - };
1.81 -
1.82 - void getFirst(OutEdgeIt& e, NodeIt v) const {
1.83 - e=OutEdgeIt(*this, v);
1.84 - }
1.85 - void getFirst(EachNodeIt& v) const { G.getFirst(v); }
1.86 -
1.87 - template< typename It >
1.88 - It first() const {
1.89 - It e;
1.90 - getFirst(e);
1.91 - return e;
1.92 - }
1.93 -
1.94 - template< typename It >
1.95 - It first(NodeIt v) const {
1.96 - It e;
1.97 - getFirst(e, v);
1.98 - return e;
1.99 - }
1.100 -
1.101 - NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
1.102 - NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
1.103 -
1.104 - NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.105 - NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.106 -
1.107 - int id(NodeIt v) const { return G.id(v); }
1.108 -
1.109 - template <typename S>
1.110 - class NodeMap {
1.111 - typename Graph::NodeMap<S> node_map;
1.112 - public:
1.113 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.114 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.115 - void set(NodeIt nit, S a) { node_map.set(nit, a); }
1.116 - S get(NodeIt nit) const { return node_map.get(nit); }
1.117 - S& operator[](NodeIt nit) { return node_map[nit]; }
1.118 - const S& operator[](NodeIt nit) const { return node_map[nit]; }
1.119 - };
1.120 -
1.121 - };
1.122 -
1.123 -
1.124 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.125 - class ResGraph2 {
1.126 - public:
1.127 - typedef typename Graph::NodeIt NodeIt;
1.128 - typedef typename Graph::EachNodeIt EachNodeIt;
1.129 - private:
1.130 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.131 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.132 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.133 -
1.134 - const Graph& G;
1.135 - FlowMap& flow;
1.136 - const CapacityMap& capacity;
1.137 - public:
1.138 - ResGraph2(const Graph& _G, FlowMap& _flow,
1.139 - const CapacityMap& _capacity) :
1.140 - G(_G), flow(_flow), capacity(_capacity) { }
1.141 -
1.142 - class EdgeIt;
1.143 - class OutEdgeIt;
1.144 - friend class EdgeIt;
1.145 - friend class OutEdgeIt;
1.146 -
1.147 - class EdgeIt {
1.148 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.149 - protected:
1.150 - const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.151 - //OldSymEdgeIt sym;
1.152 - OldOutEdgeIt out;
1.153 - OldInEdgeIt in;
1.154 - bool out_or_in; //true, iff out
1.155 - public:
1.156 - EdgeIt() : out_or_in(true) { }
1.157 - Number free() const {
1.158 - if (out_or_in) {
1.159 - return (resG->capacity.get(out)-resG->flow.get(out));
1.160 - } else {
1.161 - return (resG->flow.get(in));
1.162 - }
1.163 - }
1.164 - bool valid() const {
1.165 - return out_or_in && out.valid() || in.valid(); }
1.166 - void augment(Number a) const {
1.167 - if (out_or_in) {
1.168 - resG->flow.set(out, resG->flow.get(out)+a);
1.169 - } else {
1.170 - resG->flow.set(in, resG->flow.get(in)-a);
1.171 - }
1.172 - }
1.173 - };
1.174 -
1.175 - class OutEdgeIt : public EdgeIt {
1.176 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.177 - public:
1.178 - OutEdgeIt() { }
1.179 - private:
1.180 - OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
1.181 - resG=&_resG;
1.182 - out=resG->G.template first<OldOutEdgeIt>(v);
1.183 - while( out.valid() && !(free()>0) ) { ++out; }
1.184 - if (!out.valid()) {
1.185 - out_or_in=0;
1.186 - in=resG->G.template first<OldInEdgeIt>(v);
1.187 - while( in.valid() && !(free()>0) ) { ++in; }
1.188 - }
1.189 - }
1.190 - public:
1.191 - OutEdgeIt& operator++() {
1.192 - if (out_or_in) {
1.193 - NodeIt v=resG->G.aNode(out);
1.194 - ++out;
1.195 - while( out.valid() && !(free()>0) ) { ++out; }
1.196 - if (!out.valid()) {
1.197 - out_or_in=0;
1.198 - in=resG->G.template first<OldInEdgeIt>(v);
1.199 - while( in.valid() && !(free()>0) ) { ++in; }
1.200 - }
1.201 - } else {
1.202 - ++in;
1.203 - while( in.valid() && !(free()>0) ) { ++in; }
1.204 - }
1.205 - return *this;
1.206 - }
1.207 - };
1.208 -
1.209 - void getFirst(OutEdgeIt& e, NodeIt v) const {
1.210 - e=OutEdgeIt(*this, v);
1.211 - }
1.212 - void getFirst(EachNodeIt& v) const { G.getFirst(v); }
1.213 -
1.214 - template< typename It >
1.215 - It first() const {
1.216 - It e;
1.217 - getFirst(e);
1.218 - return e;
1.219 - }
1.220 -
1.221 - template< typename It >
1.222 - It first(NodeIt v) const {
1.223 - It e;
1.224 - getFirst(e, v);
1.225 - return e;
1.226 - }
1.227 -
1.228 - NodeIt tail(EdgeIt e) const {
1.229 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.230 - NodeIt head(EdgeIt e) const {
1.231 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.232 -
1.233 - NodeIt aNode(OutEdgeIt e) const {
1.234 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.235 - NodeIt bNode(OutEdgeIt e) const {
1.236 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.237 -
1.238 - int id(NodeIt v) const { return G.id(v); }
1.239 -
1.240 - template <typename S>
1.241 - class NodeMap {
1.242 - typename Graph::NodeMap<S> node_map;
1.243 - public:
1.244 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.245 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.246 - void set(NodeIt nit, S a) { node_map.set(nit, a); }
1.247 - S get(NodeIt nit) const { return node_map.get(nit); }
1.248 - };
1.249 - };
1.250 -
1.251 -
1.252 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.253 - class MaxFlow {
1.254 - public:
1.255 - typedef typename Graph::NodeIt NodeIt;
1.256 - typedef typename Graph::EdgeIt EdgeIt;
1.257 - typedef typename Graph::EachEdgeIt EachEdgeIt;
1.258 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.259 - typedef typename Graph::InEdgeIt InEdgeIt;
1.260 -
1.261 - private:
1.262 - const Graph* G;
1.263 - NodeIt s;
1.264 - NodeIt t;
1.265 - FlowMap* flow;
1.266 - const CapacityMap* capacity;
1.267 - typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.268 - typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.269 - typedef typename AugGraph::EdgeIt AugEdgeIt;
1.270 -
1.271 - //AugGraph res_graph;
1.272 - //typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.273 - //typename AugGraph::NodeMap<AugEdgeIt> pred;
1.274 - //typename AugGraph::NodeMap<Number> free;
1.275 - public:
1.276 - MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.277 - G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //,
1.278 - //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
1.279 - { }
1.280 - bool augmentOnShortestPath() {
1.281 - AugGraph res_graph(*G, *flow, *capacity);
1.282 - bool _augment=false;
1.283 -
1.284 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.285 - BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
1.286 - res_bfs.pushAndSetReached(s);
1.287 -
1.288 - typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.289 - //filled up with invalid iterators
1.290 - //pred.set(s, AugEdgeIt());
1.291 -
1.292 - typename AugGraph::NodeMap<Number> free(res_graph);
1.293 -
1.294 - //searching for augmenting path
1.295 - while ( !res_bfs.finished() ) {
1.296 - AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.297 - if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
1.298 - NodeIt v=res_graph.tail(e);
1.299 - NodeIt w=res_graph.head(e);
1.300 - pred.set(w, e);
1.301 - if (res_graph.valid(pred.get(v))) {
1.302 - free.set(w, std::min(free.get(v), res_graph.free(e)));
1.303 - } else {
1.304 - free.set(w, res_graph.free(e));
1.305 - }
1.306 - if (res_graph.head(e)==t) { _augment=true; break; }
1.307 - }
1.308 -
1.309 - ++res_bfs;
1.310 - } //end of searching augmenting path
1.311 -
1.312 - if (_augment) {
1.313 - NodeIt n=t;
1.314 - Number augment_value=free.get(t);
1.315 - while (res_graph.valid(pred.get(n))) {
1.316 - AugEdgeIt e=pred.get(n);
1.317 - res_graph.augment(e, augment_value);
1.318 - //e.augment(augment_value);
1.319 - n=res_graph.tail(e);
1.320 - }
1.321 - }
1.322 -
1.323 - return _augment;
1.324 - }
1.325 -
1.326 - template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.327 - bool _augment=false;
1.328 -
1.329 - AugGraph res_graph(*G, *flow, *capacity);
1.330 -
1.331 - typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.332 - BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.333 -
1.334 - bfs.pushAndSetReached(s);
1.335 - typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.336 - while ( !bfs.finished() ) {
1.337 - AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.338 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.339 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.340 - }
1.341 -
1.342 - ++bfs;
1.343 - } //computing distances from s in the residual graph
1.344 -
1.345 - MutableGraph F;
1.346 - typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
1.347 - for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.348 - res_graph_to_F.set(n, F.addNode());
1.349 - }
1.350 -
1.351 - typename MutableGraph::NodeIt sF=res_graph_to_F.get(s);
1.352 - typename MutableGraph::NodeIt tF=res_graph_to_F.get(t);
1.353 -
1.354 - typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
1.355 - typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.356 -
1.357 - //Making F to the graph containing the edges of the residual graph
1.358 - //which are in some shortest paths
1.359 - for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.360 - if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
1.361 - typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
1.362 - original_edge.update();
1.363 - original_edge.set(f, e);
1.364 - residual_capacity.update();
1.365 - residual_capacity.set(f, res_graph.free(e));
1.366 - }
1.367 - }
1.368 -
1.369 - bool __augment=true;
1.370 -
1.371 - while (__augment) {
1.372 - __augment=false;
1.373 - //computing blocking flow with dfs
1.374 - typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
1.375 - DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
1.376 - typename MutableGraph::NodeMap<EdgeIt> pred(F); //invalid iterators
1.377 - typename MutableGraph::NodeMap<Number> free(F);
1.378 -
1.379 - dfs.pushAndSetReached(sF);
1.380 - while (!dfs.finished()) {
1.381 - ++dfs;
1.382 - if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.383 - if (dfs.isBNodeNewlyReached()) {
1.384 -// std::cout << "OutEdgeIt: " << dfs;
1.385 -// std::cout << " aNode: " << F.aNode(dfs);
1.386 -// std::cout << " bNode: " << F.bNode(dfs) << " ";
1.387 -
1.388 - typename MutableGraph::NodeIt v=F.aNode(dfs);
1.389 - typename MutableGraph::NodeIt w=F.bNode(dfs);
1.390 - pred.set(w, dfs);
1.391 - if (F.valid(pred.get(v))) {
1.392 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.393 - } else {
1.394 - free.set(w, residual_capacity.get(dfs));
1.395 - }
1.396 - if (w==tF) {
1.397 - //std::cout << "AUGMENTATION"<<std::endl;
1.398 - __augment=true;
1.399 - _augment=true;
1.400 - break;
1.401 - }
1.402 -
1.403 - } else {
1.404 - F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.405 - }
1.406 - }
1.407 - }
1.408 -
1.409 - if (__augment) {
1.410 - typename MutableGraph::NodeIt n=tF;
1.411 - Number augment_value=free.get(tF);
1.412 - while (F.valid(pred.get(n))) {
1.413 - typename MutableGraph::EdgeIt e=pred.get(n);
1.414 - res_graph.augment(original_edge.get(e), augment_value);
1.415 - //original_edge.get(e).augment(augment_value);
1.416 - n=F.tail(e);
1.417 - if (residual_capacity.get(e)==augment_value)
1.418 - F.erase(e);
1.419 - else
1.420 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.421 - }
1.422 - }
1.423 -
1.424 - }
1.425 -
1.426 - return _augment;
1.427 - }
1.428 - bool augmentOnBlockingFlow2() {
1.429 - bool _augment=false;
1.430 -
1.431 - //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.432 - typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.433 - typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.434 - typedef typename EAugGraph::EdgeIt EAugEdgeIt;
1.435 -
1.436 - EAugGraph res_graph(*G, *flow, *capacity);
1.437 -
1.438 - //std::cout << "meg jo1" << std::endl;
1.439 -
1.440 - //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.441 - BfsIterator4<
1.442 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.443 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
1.444 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.445 -
1.446 - //std::cout << "meg jo2" << std::endl;
1.447 -
1.448 - bfs.pushAndSetReached(s);
1.449 - //std::cout << "meg jo2.5" << std::endl;
1.450 -
1.451 - //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.452 - typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.453 - NodeMap<int>& dist=res_graph.dist;
1.454 - //std::cout << "meg jo2.6" << std::endl;
1.455 -
1.456 - while ( !bfs.finished() ) {
1.457 - ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.458 -// EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.459 - //if (res_graph.valid(e)) {
1.460 - // std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
1.461 - //}
1.462 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.463 - dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
1.464 - }
1.465 -
1.466 - ++bfs;
1.467 - } //computing distances from s in the residual graph
1.468 -
1.469 -
1.470 - //std::cout << "meg jo3" << std::endl;
1.471 -
1.472 -// typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
1.473 -// for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.474 -// std::cout << "dist: " << dist.get(n) << std::endl;
1.475 -// }
1.476 -
1.477 - bool __augment=true;
1.478 -
1.479 - while (__augment) {
1.480 -// std::cout << "new iteration"<< std::endl;
1.481 -
1.482 - __augment=false;
1.483 - //computing blocking flow with dfs
1.484 - typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.485 - DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
1.486 - dfs(res_graph);
1.487 - typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
1.488 - typename EAugGraph::NodeMap<Number> free(res_graph);
1.489 -
1.490 - dfs.pushAndSetReached(s);
1.491 - while (!dfs.finished()) {
1.492 - ++dfs;
1.493 - if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.494 - if (dfs.isBNodeNewlyReached()) {
1.495 -// std::cout << "OutEdgeIt: " << dfs;
1.496 -// std::cout << " aNode: " << res_graph.aNode(dfs);
1.497 -// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
1.498 -// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
1.499 -
1.500 - typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
1.501 - typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
1.502 -
1.503 - pred.set(w, EAugOutEdgeIt(dfs));
1.504 -
1.505 - //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
1.506 - if (res_graph.valid(pred.get(v))) {
1.507 - free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
1.508 - } else {
1.509 - free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
1.510 - }
1.511 -
1.512 - if (w==t) {
1.513 -// std::cout << "t is reached, AUGMENTATION"<<std::endl;
1.514 - __augment=true;
1.515 - _augment=true;
1.516 - break;
1.517 - }
1.518 - } else {
1.519 -// std::cout << "<<DELETE ";
1.520 -// std::cout << " aNode: " << res_graph.aNode(dfs);
1.521 -// std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
1.522 -// std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
1.523 -// std::cout << "DELETE>> ";
1.524 -
1.525 - res_graph.erase(dfs);
1.526 - }
1.527 - }
1.528 -
1.529 - }
1.530 -
1.531 - if (__augment) {
1.532 - typename EAugGraph::NodeIt n=t;
1.533 - Number augment_value=free.get(t);
1.534 -// std::cout << "av:" << augment_value << std::endl;
1.535 - while (res_graph.valid(pred.get(n))) {
1.536 - EAugEdgeIt e=pred.get(n);
1.537 - res_graph.augment(e, augment_value);
1.538 - //e.augment(augment_value);
1.539 - n=res_graph.tail(e);
1.540 - if (res_graph.free(e)==0)
1.541 - res_graph.erase(e);
1.542 - }
1.543 - }
1.544 -
1.545 - }
1.546 -
1.547 - return _augment;
1.548 - }
1.549 - void run() {
1.550 - //int num_of_augmentations=0;
1.551 - while (augmentOnShortestPath()) {
1.552 - //while (augmentOnBlockingFlow<MutableGraph>()) {
1.553 - //std::cout << ++num_of_augmentations << " ";
1.554 - //std::cout<<std::endl;
1.555 - }
1.556 - }
1.557 - template<typename MutableGraph> void run() {
1.558 - //int num_of_augmentations=0;
1.559 - //while (augmentOnShortestPath()) {
1.560 - while (augmentOnBlockingFlow<MutableGraph>()) {
1.561 - //std::cout << ++num_of_augmentations << " ";
1.562 - //std::cout<<std::endl;
1.563 - }
1.564 - }
1.565 - Number flowValue() {
1.566 - Number a=0;
1.567 - OutEdgeIt e;
1.568 - for(G->getFirst(e, s); G->valid(e); G->next(e)) {
1.569 - a+=flow->get(e);
1.570 - }
1.571 - return a;
1.572 - }
1.573 - };
1.574 -
1.575 -
1.576 -// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.577 -// class MaxFlow2 {
1.578 -// public:
1.579 -// typedef typename Graph::NodeIt NodeIt;
1.580 -// typedef typename Graph::EdgeIt EdgeIt;
1.581 -// typedef typename Graph::EachEdgeIt EachEdgeIt;
1.582 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.583 -// typedef typename Graph::InEdgeIt InEdgeIt;
1.584 -// private:
1.585 -// const Graph& G;
1.586 -// std::list<NodeIt>& S;
1.587 -// std::list<NodeIt>& T;
1.588 -// FlowMap& flow;
1.589 -// const CapacityMap& capacity;
1.590 -// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.591 -// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.592 -// typedef typename AugGraph::EdgeIt AugEdgeIt;
1.593 -// typename Graph::NodeMap<bool> SMap;
1.594 -// typename Graph::NodeMap<bool> TMap;
1.595 -// public:
1.596 -// MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.597 -// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.598 -// i!=S.end(); ++i) {
1.599 -// SMap.set(*i, true);
1.600 -// }
1.601 -// for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.602 -// i!=T.end(); ++i) {
1.603 -// TMap.set(*i, true);
1.604 -// }
1.605 -// }
1.606 -// bool augment() {
1.607 -// AugGraph res_graph(G, flow, capacity);
1.608 -// bool _augment=false;
1.609 -// NodeIt reached_t_node;
1.610 -
1.611 -// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.612 -// BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.613 -// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.614 -// i!=S.end(); ++i) {
1.615 -// res_bfs.pushAndSetReached(*i);
1.616 -// }
1.617 -// //res_bfs.pushAndSetReached(s);
1.618 -
1.619 -// typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.620 -// //filled up with invalid iterators
1.621 -
1.622 -// typename AugGraph::NodeMap<Number> free(res_graph);
1.623 -
1.624 -// //searching for augmenting path
1.625 -// while ( !res_bfs.finished() ) {
1.626 -// AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
1.627 -// if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.628 -// NodeIt v=res_graph.tail(e);
1.629 -// NodeIt w=res_graph.head(e);
1.630 -// pred.set(w, e);
1.631 -// if (pred.get(v).valid()) {
1.632 -// free.set(w, std::min(free.get(v), e.free()));
1.633 -// } else {
1.634 -// free.set(w, e.free());
1.635 -// }
1.636 -// if (TMap.get(res_graph.head(e))) {
1.637 -// _augment=true;
1.638 -// reached_t_node=res_graph.head(e);
1.639 -// break;
1.640 -// }
1.641 -// }
1.642 -
1.643 -// ++res_bfs;
1.644 -// } //end of searching augmenting path
1.645 -
1.646 -// if (_augment) {
1.647 -// NodeIt n=reached_t_node;
1.648 -// Number augment_value=free.get(reached_t_node);
1.649 -// while (pred.get(n).valid()) {
1.650 -// AugEdgeIt e=pred.get(n);
1.651 -// e.augment(augment_value);
1.652 -// n=res_graph.tail(e);
1.653 -// }
1.654 -// }
1.655 -
1.656 -// return _augment;
1.657 -// }
1.658 -// void run() {
1.659 -// while (augment()) { }
1.660 -// }
1.661 -// Number flowValue() {
1.662 -// Number a=0;
1.663 -// for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.664 -// i!=S.end(); ++i) {
1.665 -// for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.666 -// a+=flow.get(e);
1.667 -// }
1.668 -// for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.669 -// a-=flow.get(e);
1.670 -// }
1.671 -// }
1.672 -// return a;
1.673 -// }
1.674 -// };
1.675 -
1.676 -
1.677 -
1.678 -} // namespace hugo
1.679 -
1.680 -#endif //EDMONDS_KARP_HH