1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/edmonds_karp.h Mon Apr 05 15:02:39 2004 +0000
1.3 @@ -0,0 +1,1238 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef HUGO_EDMONDS_KARP_H
1.6 +#define HUGO_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 hugo {
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.tail(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.tail(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 tail(Edge e) const { return G.aNode(e.sym); }
1.103 + Node head(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 tail(Edge e) const {
1.230 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.231 + Node head(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.tail(e);
1.294 + Node w=res_graph.head(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.head(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.tail(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.tail(e))<dist.get(gw.head(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.head(e), dist.get(res_graph.tail(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.head(e))==dist.get(res_graph.tail(e))+1) {
1.376 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(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.tail(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.head(e), dist.get(res_graph.tail(e))+1);
1.475 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(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.head(e))==(dist.get(res_graph.tail(e))+1)) {
1.482 + typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(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.tail(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.head(e), dist.get(res_graph.tail(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.tail(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.head(e), dist.get(res_graph.tail(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.tail(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.tail(e);
1.824 +// Node w=res_graph.head(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.head(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.tail(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.head(e), dist.get(res_graph.tail(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.head(e))==dist.get(res_graph.tail(e))+1) {
1.917 +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(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.tail(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.head(e), dist.get(res_graph.tail(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.tail(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.tail(e);
1.1191 +// // Node w=res_graph.head(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.head(e))) {
1.1199 +// // _augment=true;
1.1200 +// // reached_t_node=res_graph.head(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.tail(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 hugo
1.1240 +
1.1241 +#endif //HUGO_EDMONDS_KARP_H