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