1.1 --- a/src/work/marci/experiment/edmonds_karp_1.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1148 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_EDMONDS_KARP_H
1.6 -#define LEMON_EDMONDS_KARP_H
1.7 -
1.8 -#include <algorithm>
1.9 -#include <list>
1.10 -#include <iterator>
1.11 -
1.12 -#include <bfs_iterator_1.h>
1.13 -#include <invalid.h>
1.14 -#include <graph_wrapper_1.h>
1.15 -
1.16 -namespace lemon {
1.17 -
1.18 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.19 - class ResGraph {
1.20 - public:
1.21 - typedef typename Graph::Node Node;
1.22 - typedef typename Graph::NodeIt NodeIt;
1.23 - private:
1.24 - typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.25 - const Graph& G;
1.26 - FlowMap& flow;
1.27 - const CapacityMap& capacity;
1.28 - public:
1.29 - ResGraph(const Graph& _G, FlowMap& _flow,
1.30 - const CapacityMap& _capacity) :
1.31 - G(_G), flow(_flow), capacity(_capacity) { }
1.32 -
1.33 - class Edge;
1.34 - class OutEdgeIt;
1.35 - friend class Edge;
1.36 - friend class OutEdgeIt;
1.37 -
1.38 - class Edge {
1.39 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.40 - protected:
1.41 - const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.42 - OldSymEdgeIt sym;
1.43 - public:
1.44 - Edge() { }
1.45 - //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { }
1.46 - Number free() const {
1.47 - if (resG->G.aNode(sym)==resG->G.source(sym)) {
1.48 - return (resG->capacity.get(sym)-resG->flow.get(sym));
1.49 - } else {
1.50 - return (resG->flow.get(sym));
1.51 - }
1.52 - }
1.53 - bool valid() const { return sym.valid(); }
1.54 - void augment(Number a) const {
1.55 - if (resG->G.aNode(sym)==resG->G.source(sym)) {
1.56 - resG->flow.set(sym, resG->flow.get(sym)+a);
1.57 - //resG->flow[sym]+=a;
1.58 - } else {
1.59 - resG->flow.set(sym, resG->flow.get(sym)-a);
1.60 - //resG->flow[sym]-=a;
1.61 - }
1.62 - }
1.63 - };
1.64 -
1.65 - class OutEdgeIt : public Edge {
1.66 - friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.67 - public:
1.68 - OutEdgeIt() { }
1.69 - //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.70 - private:
1.71 - OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.72 - resG=&_resG;
1.73 - sym=resG->G.template first<OldSymEdgeIt>(v);
1.74 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.75 - }
1.76 - public:
1.77 - OutEdgeIt& operator++() {
1.78 - ++sym;
1.79 - while( sym.valid() && !(free()>0) ) { ++sym; }
1.80 - return *this;
1.81 - }
1.82 - };
1.83 -
1.84 - void /*getF*/first(OutEdgeIt& e, Node v) const {
1.85 - e=OutEdgeIt(*this, v);
1.86 - }
1.87 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.88 -
1.89 - template< typename It >
1.90 - It first() const {
1.91 - It e;
1.92 - /*getF*/first(e);
1.93 - return e;
1.94 - }
1.95 -
1.96 - template< typename It >
1.97 - It first(Node v) const {
1.98 - It e;
1.99 - /*getF*/first(e, v);
1.100 - return e;
1.101 - }
1.102 -
1.103 - Node source(Edge e) const { return G.aNode(e.sym); }
1.104 - Node target(Edge e) const { return G.bNode(e.sym); }
1.105 -
1.106 - Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.107 - Node bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.108 -
1.109 - int id(Node v) const { return G.id(v); }
1.110 -
1.111 - template <typename S>
1.112 - class NodeMap {
1.113 - typename Graph::NodeMap<S> node_map;
1.114 - public:
1.115 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.116 - NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.117 - void set(Node nit, S a) { node_map.set(nit, a); }
1.118 - S get(Node nit) const { return node_map.get(nit); }
1.119 - S& operator[](Node nit) { return node_map[nit]; }
1.120 - const S& operator[](Node nit) const { return node_map[nit]; }
1.121 - };
1.122 -
1.123 - };
1.124 -
1.125 -
1.126 - template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.127 - class ResGraph2 {
1.128 - public:
1.129 - typedef typename Graph::Node Node;
1.130 - typedef typename Graph::NodeIt NodeIt;
1.131 - private:
1.132 - //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.133 - typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.134 - typedef typename Graph::InEdgeIt OldInEdgeIt;
1.135 -
1.136 - const Graph& G;
1.137 - FlowMap& flow;
1.138 - const CapacityMap& capacity;
1.139 - public:
1.140 - ResGraph2(const Graph& _G, FlowMap& _flow,
1.141 - const CapacityMap& _capacity) :
1.142 - G(_G), flow(_flow), capacity(_capacity) { }
1.143 -
1.144 - class Edge;
1.145 - class OutEdgeIt;
1.146 - friend class Edge;
1.147 - friend class OutEdgeIt;
1.148 -
1.149 - class Edge {
1.150 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.151 - protected:
1.152 - const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.153 - //OldSymEdgeIt sym;
1.154 - OldOutEdgeIt out;
1.155 - OldInEdgeIt in;
1.156 - bool out_or_in; //true, iff out
1.157 - public:
1.158 - Edge() : out_or_in(true) { }
1.159 - Number free() const {
1.160 - if (out_or_in) {
1.161 - return (resG->capacity.get(out)-resG->flow.get(out));
1.162 - } else {
1.163 - return (resG->flow.get(in));
1.164 - }
1.165 - }
1.166 - bool valid() const {
1.167 - return out_or_in && out.valid() || in.valid(); }
1.168 - void augment(Number a) const {
1.169 - if (out_or_in) {
1.170 - resG->flow.set(out, resG->flow.get(out)+a);
1.171 - } else {
1.172 - resG->flow.set(in, resG->flow.get(in)-a);
1.173 - }
1.174 - }
1.175 - };
1.176 -
1.177 - class OutEdgeIt : public Edge {
1.178 - friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.179 - public:
1.180 - OutEdgeIt() { }
1.181 - private:
1.182 - OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, Node v) {
1.183 - resG=&_resG;
1.184 - out=resG->G.template first<OldOutEdgeIt>(v);
1.185 - while( out.valid() && !(free()>0) ) { ++out; }
1.186 - if (!out.valid()) {
1.187 - out_or_in=0;
1.188 - in=resG->G.template first<OldInEdgeIt>(v);
1.189 - while( in.valid() && !(free()>0) ) { ++in; }
1.190 - }
1.191 - }
1.192 - public:
1.193 - OutEdgeIt& operator++() {
1.194 - if (out_or_in) {
1.195 - Node v=resG->G.aNode(out);
1.196 - ++out;
1.197 - while( out.valid() && !(free()>0) ) { ++out; }
1.198 - if (!out.valid()) {
1.199 - out_or_in=0;
1.200 - in=resG->G.template first<OldInEdgeIt>(v);
1.201 - while( in.valid() && !(free()>0) ) { ++in; }
1.202 - }
1.203 - } else {
1.204 - ++in;
1.205 - while( in.valid() && !(free()>0) ) { ++in; }
1.206 - }
1.207 - return *this;
1.208 - }
1.209 - };
1.210 -
1.211 - void /*getF*/first(OutEdgeIt& e, Node v) const {
1.212 - e=OutEdgeIt(*this, v);
1.213 - }
1.214 - void /*getF*/first(NodeIt& v) const { G./*getF*/first(v); }
1.215 -
1.216 - template< typename It >
1.217 - It first() const {
1.218 - It e;
1.219 - /*getF*/first(e);
1.220 - return e;
1.221 - }
1.222 -
1.223 - template< typename It >
1.224 - It first(Node v) const {
1.225 - It e;
1.226 - /*getF*/first(e, v);
1.227 - return e;
1.228 - }
1.229 -
1.230 - Node source(Edge e) const {
1.231 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.232 - Node target(Edge e) const {
1.233 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.234 -
1.235 - Node aNode(OutEdgeIt e) const {
1.236 - return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.237 - Node bNode(OutEdgeIt e) const {
1.238 - return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.239 -
1.240 - int id(Node v) const { return G.id(v); }
1.241 -
1.242 - template <typename S>
1.243 - class NodeMap {
1.244 - typename Graph::NodeMap<S> node_map;
1.245 - public:
1.246 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.247 - NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.248 - void set(Node nit, S a) { node_map.set(nit, a); }
1.249 - S get(Node nit) const { return node_map.get(nit); }
1.250 - };
1.251 - };
1.252 -
1.253 -
1.254 - template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.255 - class MaxFlow {
1.256 - protected:
1.257 - typedef typename Graph::Node Node;
1.258 - typedef typename Graph::Edge Edge;
1.259 - typedef typename Graph::EdgeIt EdgeIt;
1.260 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.261 - typedef typename Graph::InEdgeIt InEdgeIt;
1.262 - const Graph* g;
1.263 - Node s;
1.264 - Node t;
1.265 - FlowMap* flow;
1.266 - const CapacityMap* capacity;
1.267 - typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
1.268 - typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.269 - typedef typename ResGW::Edge ResGWEdge;
1.270 - public:
1.271 -
1.272 - MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.273 - g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
1.274 -
1.275 - bool augmentOnShortestPath() {
1.276 - ResGW res_graph(*g, *flow, *capacity);
1.277 - bool _augment=false;
1.278 -
1.279 - typedef typename ResGW::NodeMap<bool> ReachedMap;
1.280 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.281 - bfs.pushAndSetReached(s);
1.282 -
1.283 - typename ResGW::NodeMap<ResGWEdge> pred(res_graph);
1.284 - pred.set(s, INVALID);
1.285 -
1.286 - typename ResGW::NodeMap<Number> free(res_graph);
1.287 -
1.288 - //searching for augmenting path
1.289 - while ( !bfs.finished() ) {
1.290 - ResGWOutEdgeIt e=bfs;
1.291 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.292 - Node v=res_graph.source(e);
1.293 - Node w=res_graph.target(e);
1.294 - pred.set(w, e);
1.295 - if (res_graph.valid(pred.get(v))) {
1.296 - free.set(w, std::min(free.get(v), res_graph.resCap(e)));
1.297 - } else {
1.298 - free.set(w, res_graph.resCap(e));
1.299 - }
1.300 - if (res_graph.target(e)==t) { _augment=true; break; }
1.301 - }
1.302 -
1.303 - ++bfs;
1.304 - } //end of searching augmenting path
1.305 -
1.306 - if (_augment) {
1.307 - Node n=t;
1.308 - Number augment_value=free.get(t);
1.309 - while (res_graph.valid(pred.get(n))) {
1.310 - ResGWEdge e=pred.get(n);
1.311 - res_graph.augment(e, augment_value);
1.312 - n=res_graph.source(e);
1.313 - }
1.314 - }
1.315 -
1.316 - return _augment;
1.317 - }
1.318 -
1.319 - template<typename MapGraphWrapper>
1.320 - class DistanceMap {
1.321 - protected:
1.322 - const MapGraphWrapper* g;
1.323 - typename MapGraphWrapper::NodeMap<int> dist;
1.324 - public:
1.325 - DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
1.326 - void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
1.327 - int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
1.328 - bool get(const typename MapGraphWrapper::Edge& e) const {
1.329 - return (dist.get(g->source(e))<dist.get(g->target(e)));
1.330 - }
1.331 - };
1.332 -
1.333 - template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.334 - typedef MutableGraph MG;
1.335 - bool _augment=false;
1.336 -
1.337 - ResGW res_graph(*g, *flow, *capacity);
1.338 -
1.339 - typedef typename ResGW::NodeMap<bool> ReachedMap;
1.340 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.341 -
1.342 - bfs.pushAndSetReached(s);
1.343 - //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
1.344 - DistanceMap<ResGW> dist(res_graph);
1.345 - while ( !bfs.finished() ) {
1.346 - ResGWOutEdgeIt e=bfs;
1.347 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.348 - dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.349 - }
1.350 - ++bfs;
1.351 - } //computing distances from s in the residual graph
1.352 -
1.353 - MG F;
1.354 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
1.355 - FilterResGW filter_res_graph(res_graph, dist);
1.356 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
1.357 - {
1.358 - typename ResGW::NodeIt n;
1.359 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
1.360 - res_graph_to_F.set(n, F.addNode());
1.361 - }
1.362 - }
1.363 -
1.364 - typename MG::Node sF=res_graph_to_F.get(s);
1.365 - typename MG::Node tF=res_graph_to_F.get(t);
1.366 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
1.367 - typename MG::EdgeMap<Number> residual_capacity(F);
1.368 -
1.369 - //Making F to the graph containing the edges of the residual graph
1.370 - //which are in some shortest paths
1.371 - {
1.372 - typename FilterResGW::EdgeIt e;
1.373 - for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
1.374 - //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.375 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.376 - original_edge.update();
1.377 - original_edge.set(f, e);
1.378 - residual_capacity.update();
1.379 - residual_capacity.set(f, res_graph.resCap(e));
1.380 - //}
1.381 - }
1.382 - }
1.383 -
1.384 - bool __augment=true;
1.385 -
1.386 - while (__augment) {
1.387 - __augment=false;
1.388 - //computing blocking flow with dfs
1.389 - typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
1.390 - DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
1.391 - typename MG::NodeMap<typename MG::Edge> pred(F);
1.392 - pred.set(sF, INVALID);
1.393 - //invalid iterators for sources
1.394 -
1.395 - typename MG::NodeMap<Number> free(F);
1.396 -
1.397 - dfs.pushAndSetReached(sF);
1.398 - while (!dfs.finished()) {
1.399 - ++dfs;
1.400 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.401 - if (dfs.isBNodeNewlyReached()) {
1.402 - typename MG::Node v=F.aNode(dfs);
1.403 - typename MG::Node w=F.bNode(dfs);
1.404 - pred.set(w, dfs);
1.405 - if (F.valid(pred.get(v))) {
1.406 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.407 - } else {
1.408 - free.set(w, residual_capacity.get(dfs));
1.409 - }
1.410 - if (w==tF) {
1.411 - __augment=true;
1.412 - _augment=true;
1.413 - break;
1.414 - }
1.415 -
1.416 - } else {
1.417 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.418 - }
1.419 - }
1.420 - }
1.421 -
1.422 - if (__augment) {
1.423 - typename MG::Node n=tF;
1.424 - Number augment_value=free.get(tF);
1.425 - while (F.valid(pred.get(n))) {
1.426 - typename MG::Edge e=pred.get(n);
1.427 - res_graph.augment(original_edge.get(e), augment_value);
1.428 - n=F.source(e);
1.429 - if (residual_capacity.get(e)==augment_value)
1.430 - F.erase(e);
1.431 - else
1.432 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.433 - }
1.434 - }
1.435 -
1.436 - }
1.437 -
1.438 - return _augment;
1.439 - }
1.440 -
1.441 - template<typename MutableGraph> bool augmentOnBlockingFlow1() {
1.442 - typedef MutableGraph MG;
1.443 - bool _augment=false;
1.444 -
1.445 - ResGW res_graph(*g, *flow, *capacity);
1.446 -
1.447 - //bfs for distances on the residual graph
1.448 - typedef typename ResGW::NodeMap<bool> ReachedMap;
1.449 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.450 - bfs.pushAndSetReached(s);
1.451 - typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
1.452 -
1.453 - //F will contain the physical copy of the residual graph
1.454 - //with the set of edges which are on shortest paths
1.455 - MG F;
1.456 - typename ResGW::NodeMap<typename MG::Node> res_graph_to_F(res_graph);
1.457 - {
1.458 - typename ResGW::NodeIt n;
1.459 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
1.460 - res_graph_to_F.set(n, F.addNode());
1.461 - }
1.462 - }
1.463 -
1.464 - typename MG::Node sF=res_graph_to_F.get(s);
1.465 - typename MG::Node tF=res_graph_to_F.get(t);
1.466 - typename MG::EdgeMap<ResGWEdge> original_edge(F);
1.467 - typename MG::EdgeMap<Number> residual_capacity(F);
1.468 -
1.469 - while ( !bfs.finished() ) {
1.470 - ResGWOutEdgeIt e=bfs;
1.471 - if (res_graph.valid(e)) {
1.472 - if (bfs.isBNodeNewlyReached()) {
1.473 - dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.474 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.475 - original_edge.update();
1.476 - original_edge.set(f, e);
1.477 - residual_capacity.update();
1.478 - residual_capacity.set(f, res_graph.resCap(e));
1.479 - } else {
1.480 - if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) {
1.481 - typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.482 - original_edge.update();
1.483 - original_edge.set(f, e);
1.484 - residual_capacity.update();
1.485 - residual_capacity.set(f, res_graph.resCap(e));
1.486 - }
1.487 - }
1.488 - }
1.489 - ++bfs;
1.490 - } //computing distances from s in the residual graph
1.491 -
1.492 - bool __augment=true;
1.493 -
1.494 - while (__augment) {
1.495 - __augment=false;
1.496 - //computing blocking flow with dfs
1.497 - typedef typename TrivGraphWrapper<MG>::NodeMap<bool> BlockingReachedMap;
1.498 - DfsIterator5< TrivGraphWrapper<MG>, BlockingReachedMap > dfs(F);
1.499 - typename MG::NodeMap<typename MG::Edge> pred(F);
1.500 - pred.set(sF, INVALID);
1.501 - //invalid iterators for sources
1.502 -
1.503 - typename MG::NodeMap<Number> free(F);
1.504 -
1.505 - dfs.pushAndSetReached(sF);
1.506 - while (!dfs.finished()) {
1.507 - ++dfs;
1.508 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.509 - if (dfs.isBNodeNewlyReached()) {
1.510 - typename MG::Node v=F.aNode(dfs);
1.511 - typename MG::Node w=F.bNode(dfs);
1.512 - pred.set(w, dfs);
1.513 - if (F.valid(pred.get(v))) {
1.514 - free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.515 - } else {
1.516 - free.set(w, residual_capacity.get(dfs));
1.517 - }
1.518 - if (w==tF) {
1.519 - __augment=true;
1.520 - _augment=true;
1.521 - break;
1.522 - }
1.523 -
1.524 - } else {
1.525 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.526 - }
1.527 - }
1.528 - }
1.529 -
1.530 - if (__augment) {
1.531 - typename MG::Node n=tF;
1.532 - Number augment_value=free.get(tF);
1.533 - while (F.valid(pred.get(n))) {
1.534 - typename MG::Edge e=pred.get(n);
1.535 - res_graph.augment(original_edge.get(e), augment_value);
1.536 - n=F.source(e);
1.537 - if (residual_capacity.get(e)==augment_value)
1.538 - F.erase(e);
1.539 - else
1.540 - residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.541 - }
1.542 - }
1.543 -
1.544 - }
1.545 -
1.546 - return _augment;
1.547 - }
1.548 -
1.549 - bool augmentOnBlockingFlow2() {
1.550 - bool _augment=false;
1.551 -
1.552 - ResGW res_graph(*g, *flow, *capacity);
1.553 -
1.554 - typedef typename ResGW::NodeMap<bool> ReachedMap;
1.555 - BfsIterator5< ResGW, ReachedMap > bfs(res_graph);
1.556 -
1.557 - bfs.pushAndSetReached(s);
1.558 - DistanceMap<ResGW> dist(res_graph);
1.559 - while ( !bfs.finished() ) {
1.560 - ResGWOutEdgeIt e=bfs;
1.561 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.562 - dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.563 - }
1.564 - ++bfs;
1.565 - } //computing distances from s in the residual graph
1.566 -
1.567 - //Subgraph containing the edges on some shortest paths
1.568 - typedef SubGraphWrapper<ResGW, DistanceMap<ResGW> > FilterResGW;
1.569 - FilterResGW filter_res_graph(res_graph, dist);
1.570 -
1.571 - //Subgraph, which is able to delete edges which are already
1.572 - //met by the dfs
1.573 - typename FilterResGW::NodeMap<typename FilterResGW::OutEdgeIt>
1.574 - first_out_edges(filter_res_graph);
1.575 - typename FilterResGW::NodeIt v;
1.576 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
1.577 - filter_res_graph.next(v))
1.578 - {
1.579 - typename FilterResGW::OutEdgeIt e;
1.580 - filter_res_graph.first(e, v);
1.581 - first_out_edges.set(v, e);
1.582 - }
1.583 - typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
1.584 - NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
1.585 - ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
1.586 -
1.587 - bool __augment=true;
1.588 -
1.589 - while (__augment) {
1.590 -
1.591 - __augment=false;
1.592 - //computing blocking flow with dfs
1.593 - typedef typename ErasingResGW::NodeMap<bool> BlockingReachedMap;
1.594 - DfsIterator5< ErasingResGW, BlockingReachedMap >
1.595 - dfs(erasing_res_graph);
1.596 - typename ErasingResGW::NodeMap<typename ErasingResGW::OutEdgeIt>
1.597 - pred(erasing_res_graph);
1.598 - pred.set(s, INVALID);
1.599 - //invalid iterators for sources
1.600 -
1.601 - typename ErasingResGW::NodeMap<Number> free(erasing_res_graph);
1.602 -
1.603 - dfs.pushAndSetReached(s);
1.604 - while (!dfs.finished()) {
1.605 - ++dfs;
1.606 - if (erasing_res_graph.valid(
1.607 - /*typename ErasingResGW::OutEdgeIt*/(dfs)))
1.608 - {
1.609 - if (dfs.isBNodeNewlyReached()) {
1.610 -
1.611 - typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
1.612 - typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
1.613 -
1.614 - pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
1.615 - if (erasing_res_graph.valid(pred.get(v))) {
1.616 - free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
1.617 - } else {
1.618 - free.set(w, res_graph.resCap(dfs));
1.619 - }
1.620 -
1.621 - if (w==t) {
1.622 - __augment=true;
1.623 - _augment=true;
1.624 - break;
1.625 - }
1.626 - } else {
1.627 - erasing_res_graph.erase(dfs);
1.628 - }
1.629 - }
1.630 - }
1.631 -
1.632 - if (__augment) {
1.633 - typename ErasingResGW::Node n=t;
1.634 - Number augment_value=free.get(n);
1.635 - while (erasing_res_graph.valid(pred.get(n))) {
1.636 - typename ErasingResGW::OutEdgeIt e=pred.get(n);
1.637 - res_graph.augment(e, augment_value);
1.638 - n=erasing_res_graph.source(e);
1.639 - if (res_graph.resCap(e)==0)
1.640 - erasing_res_graph.erase(e);
1.641 - }
1.642 - }
1.643 -
1.644 - } //while (__augment)
1.645 -
1.646 - return _augment;
1.647 - }
1.648 -
1.649 - void run() {
1.650 - //int num_of_augmentations=0;
1.651 - while (augmentOnShortestPath()) {
1.652 - //while (augmentOnBlockingFlow<MutableGraph>()) {
1.653 - //std::cout << ++num_of_augmentations << " ";
1.654 - //std::cout<<std::endl;
1.655 - }
1.656 - }
1.657 -
1.658 - template<typename MutableGraph> void run() {
1.659 - //int num_of_augmentations=0;
1.660 - //while (augmentOnShortestPath()) {
1.661 - while (augmentOnBlockingFlow<MutableGraph>()) {
1.662 - //std::cout << ++num_of_augmentations << " ";
1.663 - //std::cout<<std::endl;
1.664 - }
1.665 - }
1.666 -
1.667 - Number flowValue() {
1.668 - Number a=0;
1.669 - OutEdgeIt e;
1.670 - for(g->first(e, s); g->valid(e); g->next(e)) {
1.671 - a+=flow->get(e);
1.672 - }
1.673 - return a;
1.674 - }
1.675 -
1.676 - };
1.677 -
1.678 -
1.679 -// template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.680 -// class MaxMatching {
1.681 -// public:
1.682 -// typedef typename Graph::Node Node;
1.683 -// typedef typename Graph::NodeIt NodeIt;
1.684 -// typedef typename Graph::Edge Edge;
1.685 -// typedef typename Graph::EdgeIt EdgeIt;
1.686 -// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.687 -// typedef typename Graph::InEdgeIt InEdgeIt;
1.688 -
1.689 -// typedef typename Graph::NodeMap<bool> SMap;
1.690 -// typedef typename Graph::NodeMap<bool> TMap;
1.691 -// private:
1.692 -// const Graph* G;
1.693 -// SMap* S;
1.694 -// TMap* T;
1.695 -// //Node s;
1.696 -// //Node t;
1.697 -// FlowMap* flow;
1.698 -// const CapacityMap* capacity;
1.699 -// typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.700 -// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.701 -// typedef typename AugGraph::Edge AugEdge;
1.702 -// typename Graph::NodeMap<int> used; //0
1.703 -
1.704 -// public:
1.705 -// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
1.706 -// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
1.707 -// bool augmentOnShortestPath() {
1.708 -// AugGraph res_graph(*G, *flow, *capacity);
1.709 -// bool _augment=false;
1.710 -
1.711 -// typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.712 -// BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
1.713 -// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.714 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.715 -// if ((S->get(s)) && (used.get(s)<1) ) {
1.716 -// //Number u=0;
1.717 -// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.718 -// //u+=flow->get(e);
1.719 -// //if (u<1) {
1.720 -// bfs.pushAndSetReached(s);
1.721 -// pred.set(s, AugEdge(INVALID));
1.722 -// //}
1.723 -// }
1.724 -// }
1.725 -
1.726 -// typename AugGraph::NodeMap<Number> free(res_graph);
1.727 -
1.728 -// Node n;
1.729 -// //searching for augmenting path
1.730 -// while ( !bfs.finished() ) {
1.731 -// AugOutEdgeIt e=bfs;
1.732 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.733 -// Node v=res_graph.source(e);
1.734 -// Node w=res_graph.target(e);
1.735 -// pred.set(w, e);
1.736 -// if (res_graph.valid(pred.get(v))) {
1.737 -// free.set(w, std::min(free.get(v), res_graph.free(e)));
1.738 -// } else {
1.739 -// free.set(w, res_graph.free(e));
1.740 -// }
1.741 -// n=res_graph.target(e);
1.742 -// if (T->get(n) && (used.get(n)<1) ) {
1.743 -// //Number u=0;
1.744 -// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.745 -// //u+=flow->get(f);
1.746 -// //if (u<1) {
1.747 -// _augment=true;
1.748 -// break;
1.749 -// //}
1.750 -// }
1.751 -// }
1.752 -
1.753 -// ++bfs;
1.754 -// } //end of searching augmenting path
1.755 -
1.756 -// if (_augment) {
1.757 -// //Node n=t;
1.758 -// used.set(n, 1); //mind2 vegen jav
1.759 -// Number augment_value=free.get(n);
1.760 -// while (res_graph.valid(pred.get(n))) {
1.761 -// AugEdge e=pred.get(n);
1.762 -// res_graph.augment(e, augment_value);
1.763 -// n=res_graph.source(e);
1.764 -// }
1.765 -// used.set(n, 1); //mind2 vegen jav
1.766 -// }
1.767 -
1.768 -// return _augment;
1.769 -// }
1.770 -
1.771 -// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
1.772 -// // bool _augment=false;
1.773 -
1.774 -// // AugGraph res_graph(*G, *flow, *capacity);
1.775 -
1.776 -// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.777 -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.778 -
1.779 -
1.780 -
1.781 -
1.782 -
1.783 -// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.784 -// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.785 -// // if (S->get(s)) {
1.786 -// // Number u=0;
1.787 -// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.788 -// // u+=flow->get(e);
1.789 -// // if (u<1) {
1.790 -// // bfs.pushAndSetReached(s);
1.791 -// // //pred.set(s, AugEdge(INVALID));
1.792 -// // }
1.793 -// // }
1.794 -// // }
1.795 -
1.796 -
1.797 -
1.798 -
1.799 -// // //bfs.pushAndSetReached(s);
1.800 -// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
1.801 -// // while ( !bfs.finished() ) {
1.802 -// // AugOutEdgeIt e=bfs;
1.803 -// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.804 -// // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.805 -// // }
1.806 -
1.807 -// // ++bfs;
1.808 -// // } //computing distances from s in the residual graph
1.809 -
1.810 -// // MutableGraph F;
1.811 -// // typename AugGraph::NodeMap<typename MutableGraph::Node>
1.812 -// // res_graph_to_F(res_graph);
1.813 -// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
1.814 -// // res_graph_to_F.set(n, F.addNode());
1.815 -// // }
1.816 -
1.817 -// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
1.818 -// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
1.819 -
1.820 -// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
1.821 -// // typename MutableGraph::EdgeMap<Number> residual_capacity(F);
1.822 -
1.823 -// // //Making F to the graph containing the edges of the residual graph
1.824 -// // //which are in some shortest paths
1.825 -// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
1.826 -// // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) {
1.827 -// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e)));
1.828 -// // original_edge.update();
1.829 -// // original_edge.set(f, e);
1.830 -// // residual_capacity.update();
1.831 -// // residual_capacity.set(f, res_graph.free(e));
1.832 -// // }
1.833 -// // }
1.834 -
1.835 -// // bool __augment=true;
1.836 -
1.837 -// // while (__augment) {
1.838 -// // __augment=false;
1.839 -// // //computing blocking flow with dfs
1.840 -// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
1.841 -// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
1.842 -// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
1.843 -// // pred.set(sF, typename MutableGraph::Edge(INVALID));
1.844 -// // //invalid iterators for sources
1.845 -
1.846 -// // typename MutableGraph::NodeMap<Number> free(F);
1.847 -
1.848 -// // dfs.pushAndSetReached(sF);
1.849 -// // while (!dfs.finished()) {
1.850 -// // ++dfs;
1.851 -// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
1.852 -// // if (dfs.isBNodeNewlyReached()) {
1.853 -// // typename MutableGraph::Node v=F.aNode(dfs);
1.854 -// // typename MutableGraph::Node w=F.bNode(dfs);
1.855 -// // pred.set(w, dfs);
1.856 -// // if (F.valid(pred.get(v))) {
1.857 -// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
1.858 -// // } else {
1.859 -// // free.set(w, residual_capacity.get(dfs));
1.860 -// // }
1.861 -// // if (w==tF) {
1.862 -// // __augment=true;
1.863 -// // _augment=true;
1.864 -// // break;
1.865 -// // }
1.866 -
1.867 -// // } else {
1.868 -// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
1.869 -// // }
1.870 -// // }
1.871 -// // }
1.872 -
1.873 -// // if (__augment) {
1.874 -// // typename MutableGraph::Node n=tF;
1.875 -// // Number augment_value=free.get(tF);
1.876 -// // while (F.valid(pred.get(n))) {
1.877 -// // typename MutableGraph::Edge e=pred.get(n);
1.878 -// // res_graph.augment(original_edge.get(e), augment_value);
1.879 -// // n=F.source(e);
1.880 -// // if (residual_capacity.get(e)==augment_value)
1.881 -// // F.erase(e);
1.882 -// // else
1.883 -// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
1.884 -// // }
1.885 -// // }
1.886 -
1.887 -// // }
1.888 -
1.889 -// // return _augment;
1.890 -// // }
1.891 -// bool augmentOnBlockingFlow2() {
1.892 -// bool _augment=false;
1.893 -
1.894 -// //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
1.895 -// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
1.896 -// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
1.897 -// typedef typename EAugGraph::Edge EAugEdge;
1.898 -
1.899 -// EAugGraph res_graph(*G, *flow, *capacity);
1.900 -
1.901 -// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
1.902 -// BfsIterator5<
1.903 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
1.904 -// /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
1.905 -// ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
1.906 -
1.907 -
1.908 -// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.909 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.910 -// if (S->get(s)) {
1.911 -// Number u=0;
1.912 -// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.913 -// u+=flow->get(e);
1.914 -// if (u<1) {
1.915 -// bfs.pushAndSetReached(s);
1.916 -// //pred.set(s, AugEdge(INVALID));
1.917 -// }
1.918 -// }
1.919 -// }
1.920 -
1.921 -
1.922 -// //bfs.pushAndSetReached(s);
1.923 -
1.924 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
1.925 -// NodeMap<int>& dist=res_graph.dist;
1.926 -
1.927 -// while ( !bfs.finished() ) {
1.928 -// typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
1.929 -// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.930 -// dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1);
1.931 -// }
1.932 -// ++bfs;
1.933 -// } //computing distances from s in the residual graph
1.934 -
1.935 -// bool __augment=true;
1.936 -
1.937 -// while (__augment) {
1.938 -
1.939 -// __augment=false;
1.940 -// //computing blocking flow with dfs
1.941 -// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
1.942 -// DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
1.943 -// dfs(res_graph);
1.944 -// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
1.945 -// //pred.set(s, EAugEdge(INVALID));
1.946 -// //invalid iterators for sources
1.947 -
1.948 -// typename EAugGraph::NodeMap<Number> free(res_graph);
1.949 -
1.950 -
1.951 -// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.952 -// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
1.953 -// if (S->get(s)) {
1.954 -// Number u=0;
1.955 -// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
1.956 -// u+=flow->get(e);
1.957 -// if (u<1) {
1.958 -// dfs.pushAndSetReached(s);
1.959 -// //pred.set(s, AugEdge(INVALID));
1.960 -// }
1.961 -// }
1.962 -// }
1.963 -
1.964 -
1.965 -
1.966 -// //dfs.pushAndSetReached(s);
1.967 -// typename EAugGraph::Node n;
1.968 -// while (!dfs.finished()) {
1.969 -// ++dfs;
1.970 -// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
1.971 -// if (dfs.isBNodeNewlyReached()) {
1.972 -
1.973 -// typename EAugGraph::Node v=res_graph.aNode(dfs);
1.974 -// typename EAugGraph::Node w=res_graph.bNode(dfs);
1.975 -
1.976 -// pred.set(w, EAugOutEdgeIt(dfs));
1.977 -// if (res_graph.valid(pred.get(v))) {
1.978 -// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
1.979 -// } else {
1.980 -// free.set(w, res_graph.free(dfs));
1.981 -// }
1.982 -
1.983 -// n=w;
1.984 -// if (T->get(w)) {
1.985 -// Number u=0;
1.986 -// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
1.987 -// u+=flow->get(f);
1.988 -// if (u<1) {
1.989 -// __augment=true;
1.990 -// _augment=true;
1.991 -// break;
1.992 -// }
1.993 -// }
1.994 -// } else {
1.995 -// res_graph.erase(dfs);
1.996 -// }
1.997 -// }
1.998 -
1.999 -// }
1.1000 -
1.1001 -// if (__augment) {
1.1002 -// // typename EAugGraph::Node n=t;
1.1003 -// Number augment_value=free.get(n);
1.1004 -// while (res_graph.valid(pred.get(n))) {
1.1005 -// EAugEdge e=pred.get(n);
1.1006 -// res_graph.augment(e, augment_value);
1.1007 -// n=res_graph.source(e);
1.1008 -// if (res_graph.free(e)==0)
1.1009 -// res_graph.erase(e);
1.1010 -// }
1.1011 -// }
1.1012 -
1.1013 -// }
1.1014 -
1.1015 -// return _augment;
1.1016 -// }
1.1017 -// void run() {
1.1018 -// //int num_of_augmentations=0;
1.1019 -// while (augmentOnShortestPath()) {
1.1020 -// //while (augmentOnBlockingFlow<MutableGraph>()) {
1.1021 -// //std::cout << ++num_of_augmentations << " ";
1.1022 -// //std::cout<<std::endl;
1.1023 -// }
1.1024 -// }
1.1025 -// // template<typename MutableGraph> void run() {
1.1026 -// // //int num_of_augmentations=0;
1.1027 -// // //while (augmentOnShortestPath()) {
1.1028 -// // while (augmentOnBlockingFlow<MutableGraph>()) {
1.1029 -// // //std::cout << ++num_of_augmentations << " ";
1.1030 -// // //std::cout<<std::endl;
1.1031 -// // }
1.1032 -// // }
1.1033 -// Number flowValue() {
1.1034 -// Number a=0;
1.1035 -// EdgeIt e;
1.1036 -// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
1.1037 -// a+=flow->get(e);
1.1038 -// }
1.1039 -// return a;
1.1040 -// }
1.1041 -// };
1.1042 -
1.1043 -
1.1044 -
1.1045 -
1.1046 -
1.1047 -
1.1048 -// // template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.1049 -// // class MaxFlow2 {
1.1050 -// // public:
1.1051 -// // typedef typename Graph::Node Node;
1.1052 -// // typedef typename Graph::Edge Edge;
1.1053 -// // typedef typename Graph::EdgeIt EdgeIt;
1.1054 -// // typedef typename Graph::OutEdgeIt OutEdgeIt;
1.1055 -// // typedef typename Graph::InEdgeIt InEdgeIt;
1.1056 -// // private:
1.1057 -// // const Graph& G;
1.1058 -// // std::list<Node>& S;
1.1059 -// // std::list<Node>& T;
1.1060 -// // FlowMap& flow;
1.1061 -// // const CapacityMap& capacity;
1.1062 -// // typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.1063 -// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.1064 -// // typedef typename AugGraph::Edge AugEdge;
1.1065 -// // typename Graph::NodeMap<bool> SMap;
1.1066 -// // typename Graph::NodeMap<bool> TMap;
1.1067 -// // public:
1.1068 -// // MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.1069 -// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1070 -// // i!=S.end(); ++i) {
1.1071 -// // SMap.set(*i, true);
1.1072 -// // }
1.1073 -// // for (typename std::list<Node>::const_iterator i=T.begin();
1.1074 -// // i!=T.end(); ++i) {
1.1075 -// // TMap.set(*i, true);
1.1076 -// // }
1.1077 -// // }
1.1078 -// // bool augment() {
1.1079 -// // AugGraph res_graph(G, flow, capacity);
1.1080 -// // bool _augment=false;
1.1081 -// // Node reached_t_node;
1.1082 -
1.1083 -// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.1084 -// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
1.1085 -// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1086 -// // i!=S.end(); ++i) {
1.1087 -// // bfs.pushAndSetReached(*i);
1.1088 -// // }
1.1089 -// // //bfs.pushAndSetReached(s);
1.1090 -
1.1091 -// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
1.1092 -// // //filled up with invalid iterators
1.1093 -
1.1094 -// // typename AugGraph::NodeMap<Number> free(res_graph);
1.1095 -
1.1096 -// // //searching for augmenting path
1.1097 -// // while ( !bfs.finished() ) {
1.1098 -// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
1.1099 -// // if (e.valid() && bfs.isBNodeNewlyReached()) {
1.1100 -// // Node v=res_graph.source(e);
1.1101 -// // Node w=res_graph.target(e);
1.1102 -// // pred.set(w, e);
1.1103 -// // if (pred.get(v).valid()) {
1.1104 -// // free.set(w, std::min(free.get(v), e.free()));
1.1105 -// // } else {
1.1106 -// // free.set(w, e.free());
1.1107 -// // }
1.1108 -// // if (TMap.get(res_graph.target(e))) {
1.1109 -// // _augment=true;
1.1110 -// // reached_t_node=res_graph.target(e);
1.1111 -// // break;
1.1112 -// // }
1.1113 -// // }
1.1114 -
1.1115 -// // ++bfs;
1.1116 -// // } //end of searching augmenting path
1.1117 -
1.1118 -// // if (_augment) {
1.1119 -// // Node n=reached_t_node;
1.1120 -// // Number augment_value=free.get(reached_t_node);
1.1121 -// // while (pred.get(n).valid()) {
1.1122 -// // AugEdge e=pred.get(n);
1.1123 -// // e.augment(augment_value);
1.1124 -// // n=res_graph.source(e);
1.1125 -// // }
1.1126 -// // }
1.1127 -
1.1128 -// // return _augment;
1.1129 -// // }
1.1130 -// // void run() {
1.1131 -// // while (augment()) { }
1.1132 -// // }
1.1133 -// // Number flowValue() {
1.1134 -// // Number a=0;
1.1135 -// // for(typename std::list<Node>::const_iterator i=S.begin();
1.1136 -// // i!=S.end(); ++i) {
1.1137 -// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.1138 -// // a+=flow.get(e);
1.1139 -// // }
1.1140 -// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.1141 -// // a-=flow.get(e);
1.1142 -// // }
1.1143 -// // }
1.1144 -// // return a;
1.1145 -// // }
1.1146 -// // };
1.1147 -
1.1148 -
1.1149 -} // namespace lemon
1.1150 -
1.1151 -#endif //LEMON_EDMONDS_KARP_H