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