1.1 --- a/src/work/edmonds_karp.hh Mon Feb 16 10:57:01 2004 +0000
1.2 +++ b/src/work/edmonds_karp.hh Mon Feb 16 11:29:48 2004 +0000
1.3 @@ -2,12 +2,14 @@
1.4 #define EDMONDS_KARP_HH
1.5
1.6 #include <algorithm>
1.7 +#include <list>
1.8 +#include <iterator>
1.9
1.10 #include <bfs_iterator.hh>
1.11
1.12 namespace marci {
1.13
1.14 - template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
1.15 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.16 class ResGraph {
1.17 typedef typename Graph::NodeIt NodeIt;
1.18 typedef typename Graph::EachNodeIt EachNodeIt;
1.19 @@ -26,14 +28,14 @@
1.20 friend class OutEdgeIt;
1.21
1.22 class EdgeIt {
1.23 - friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
1.24 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.25 protected:
1.26 - const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
1.27 + const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
1.28 OldSymEdgeIt sym;
1.29 public:
1.30 EdgeIt() { }
1.31 //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
1.32 - T free() const {
1.33 + Number free() const {
1.34 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.35 return (resG->capacity.get(sym)-resG->flow.get(sym));
1.36 } else {
1.37 @@ -41,22 +43,24 @@
1.38 }
1.39 }
1.40 bool valid() const { return sym.valid(); }
1.41 - void augment(T a) const {
1.42 + void augment(Number a) const {
1.43 if (resG->G.aNode(sym)==resG->G.tail(sym)) {
1.44 resG->flow.set(sym, resG->flow.get(sym)+a);
1.45 + //resG->flow[sym]+=a;
1.46 } else {
1.47 resG->flow.set(sym, resG->flow.get(sym)-a);
1.48 + //resG->flow[sym]-=a;
1.49 }
1.50 }
1.51 };
1.52
1.53 class OutEdgeIt : public EdgeIt {
1.54 - friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
1.55 + friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
1.56 public:
1.57 OutEdgeIt() { }
1.58 //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
1.59 private:
1.60 - OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
1.61 + OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
1.62 resG=&_resG;
1.63 sym=resG->G.template first<OldSymEdgeIt>(v);
1.64 while( sym.valid() && !(free()>0) ) { ++sym; }
1.65 @@ -76,6 +80,131 @@
1.66
1.67 template< typename It >
1.68 It first() const {
1.69 + It e;
1.70 + getFirst(e);
1.71 + return e;
1.72 + }
1.73 +
1.74 + template< typename It >
1.75 + It first(NodeIt v) const {
1.76 + It e;
1.77 + getFirst(e, v);
1.78 + return e;
1.79 + }
1.80 +
1.81 + NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
1.82 + NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
1.83 +
1.84 + NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.85 + NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.86 +
1.87 + int id(NodeIt v) const { return G.id(v); }
1.88 +
1.89 + template <typename S>
1.90 + class NodeMap {
1.91 + typename Graph::NodeMap<S> node_map;
1.92 + public:
1.93 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.94 + NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.95 + void set(NodeIt nit, S a) { node_map.set(nit, a); }
1.96 + S get(NodeIt nit) const { return node_map.get(nit); }
1.97 + S& operator[](NodeIt nit) { return node_map[nit]; }
1.98 + const S& operator[](NodeIt nit) const { return node_map[nit]; }
1.99 + };
1.100 +
1.101 + };
1.102 +
1.103 +
1.104 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.105 + class ResGraph2 {
1.106 + typedef typename Graph::NodeIt NodeIt;
1.107 + typedef typename Graph::EachNodeIt EachNodeIt;
1.108 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.109 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.110 + typedef typename Graph::InEdgeIt OldInEdgeIt;
1.111 +
1.112 + const Graph& G;
1.113 + FlowMap& flow;
1.114 + const CapacityMap& capacity;
1.115 + public:
1.116 + ResGraph2(const Graph& _G, FlowMap& _flow,
1.117 + const CapacityMap& _capacity) :
1.118 + G(_G), flow(_flow), capacity(_capacity) { }
1.119 +
1.120 + class EdgeIt;
1.121 + class OutEdgeIt;
1.122 + friend class EdgeIt;
1.123 + friend class OutEdgeIt;
1.124 +
1.125 + class EdgeIt {
1.126 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.127 + protected:
1.128 + const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
1.129 + //OldSymEdgeIt sym;
1.130 + OldOutEdgeIt out;
1.131 + OldInEdgeIt in;
1.132 + bool out_or_in; //1, iff out
1.133 + public:
1.134 + EdgeIt() : out_or_in(1) { }
1.135 + Number free() const {
1.136 + if (out_or_in) {
1.137 + return (resG->capacity.get(out)-resG->flow.get(out));
1.138 + } else {
1.139 + return (resG->flow.get(in));
1.140 + }
1.141 + }
1.142 + bool valid() const {
1.143 + return out_or_in && out.valid() || in.valid(); }
1.144 + void augment(Number a) const {
1.145 + if (out_or_in) {
1.146 + resG->flow.set(out, resG->flow.get(out)+a);
1.147 + } else {
1.148 + resG->flow.set(in, resG->flow.get(in)-a);
1.149 + }
1.150 + }
1.151 + };
1.152 +
1.153 + class OutEdgeIt : public EdgeIt {
1.154 + friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
1.155 + public:
1.156 + OutEdgeIt() { }
1.157 + private:
1.158 + OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
1.159 + resG=&_resG;
1.160 + out=resG->G.template first<OldOutEdgeIt>(v);
1.161 + while( out.valid() && !(free()>0) ) { ++out; }
1.162 + if (!out.valid()) {
1.163 + out_or_in=0;
1.164 + in=resG->G.template first<OldInEdgeIt>(v);
1.165 + while( in.valid() && !(free()>0) ) { ++in; }
1.166 + }
1.167 + }
1.168 + public:
1.169 + OutEdgeIt& operator++() {
1.170 + if (out_or_in) {
1.171 + NodeIt v=resG->G.aNode(out);
1.172 + ++out;
1.173 + while( out.valid() && !(free()>0) ) { ++out; }
1.174 + if (!out.valid()) {
1.175 + out_or_in=0;
1.176 + in=resG->G.template first<OldInEdgeIt>(v);
1.177 + while( in.valid() && !(free()>0) ) { ++in; }
1.178 + }
1.179 + } else {
1.180 + ++in;
1.181 + while( in.valid() && !(free()>0) ) { ++in; }
1.182 + }
1.183 + return *this;
1.184 + }
1.185 + };
1.186 +
1.187 + void getFirst(OutEdgeIt& e, NodeIt v) const {
1.188 + e=OutEdgeIt(*this, v);
1.189 + }
1.190 + void getFirst(EachNodeIt& v) const { G.getFirst(v); }
1.191 +
1.192 + template< typename It >
1.193 + It first() const {
1.194 It e;
1.195 getFirst(e);
1.196 return e;
1.197 @@ -88,11 +217,15 @@
1.198 return e;
1.199 }
1.200
1.201 - NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
1.202 - NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
1.203 + NodeIt tail(EdgeIt e) const {
1.204 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.205 + NodeIt head(EdgeIt e) const {
1.206 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.207
1.208 - NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
1.209 - NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
1.210 + NodeIt aNode(OutEdgeIt e) const {
1.211 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.212 + NodeIt bNode(OutEdgeIt e) const {
1.213 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.214
1.215 int id(NodeIt v) const { return G.id(v); }
1.216
1.217 @@ -100,15 +233,146 @@
1.218 class NodeMap {
1.219 typename Graph::NodeMap<S> node_map;
1.220 public:
1.221 - NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.222 - NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.223 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.224 + NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.225 + void set(NodeIt nit, S a) { node_map.set(nit, a); }
1.226 + S get(NodeIt nit) const { return node_map.get(nit); }
1.227 + };
1.228 + };
1.229 +
1.230 + template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.231 + class ResGraph3 {
1.232 + typedef typename Graph::NodeIt NodeIt;
1.233 + typedef typename Graph::EachNodeIt EachNodeIt;
1.234 + //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
1.235 + typedef typename Graph::OutEdgeIt OldOutEdgeIt;
1.236 + typedef typename Graph::InEdgeIt OldInEdgeIt;
1.237 +
1.238 + const Graph& G;
1.239 + FlowMap& flow;
1.240 + const CapacityMap& capacity;
1.241 + public:
1.242 + ResGraph3(const Graph& _G, FlowMap& _flow,
1.243 + const CapacityMap& _capacity) :
1.244 + G(_G), flow(_flow), capacity(_capacity) { }
1.245 +
1.246 + class EdgeIt;
1.247 + class OutEdgeIt;
1.248 + friend class EdgeIt;
1.249 + friend class OutEdgeIt;
1.250 +
1.251 + class EdgeIt {
1.252 + friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
1.253 + protected:
1.254 + //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
1.255 + const Graph* G;
1.256 + FlowMap* flow;
1.257 + const CapacityMap* capacity;
1.258 + //OldSymEdgeIt sym;
1.259 + OldOutEdgeIt out;
1.260 + OldInEdgeIt in;
1.261 + bool out_or_in; //1, iff out
1.262 + public:
1.263 + EdgeIt() : out_or_in(1) { }
1.264 + Number free() const {
1.265 + if (out_or_in) {
1.266 + return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
1.267 + } else {
1.268 + return (/*resG->*/flow->get(in));
1.269 + }
1.270 + }
1.271 + bool valid() const {
1.272 + return out_or_in && out.valid() || in.valid(); }
1.273 + void augment(Number a) const {
1.274 + if (out_or_in) {
1.275 + /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
1.276 + } else {
1.277 + /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
1.278 + }
1.279 + }
1.280 + };
1.281 +
1.282 + class OutEdgeIt : public EdgeIt {
1.283 + friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
1.284 + public:
1.285 + OutEdgeIt() { }
1.286 + private:
1.287 + OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
1.288 + G=&_G;
1.289 + flow=&_flow;
1.290 + capacity=&_capacity;
1.291 + out=/*resG->*/G->template first<OldOutEdgeIt>(v);
1.292 + while( out.valid() && !(free()>0) ) { ++out; }
1.293 + if (!out.valid()) {
1.294 + out_or_in=0;
1.295 + in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.296 + while( in.valid() && !(free()>0) ) { ++in; }
1.297 + }
1.298 + }
1.299 + public:
1.300 + OutEdgeIt& operator++() {
1.301 + if (out_or_in) {
1.302 + NodeIt v=/*resG->*/G->aNode(out);
1.303 + ++out;
1.304 + while( out.valid() && !(free()>0) ) { ++out; }
1.305 + if (!out.valid()) {
1.306 + out_or_in=0;
1.307 + in=/*resG->*/G->template first<OldInEdgeIt>(v);
1.308 + while( in.valid() && !(free()>0) ) { ++in; }
1.309 + }
1.310 + } else {
1.311 + ++in;
1.312 + while( in.valid() && !(free()>0) ) { ++in; }
1.313 + }
1.314 + return *this;
1.315 + }
1.316 + };
1.317 +
1.318 + void getFirst(OutEdgeIt& e, NodeIt v) const {
1.319 + e=OutEdgeIt(G, v, flow, capacity);
1.320 + }
1.321 + void getFirst(EachNodeIt& v) const { G.getFirst(v); }
1.322 +
1.323 + template< typename It >
1.324 + It first() const {
1.325 + It e;
1.326 + getFirst(e);
1.327 + return e;
1.328 + }
1.329 +
1.330 + template< typename It >
1.331 + It first(NodeIt v) const {
1.332 + It e;
1.333 + getFirst(e, v);
1.334 + return e;
1.335 + }
1.336 +
1.337 + NodeIt tail(EdgeIt e) const {
1.338 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.339 + NodeIt head(EdgeIt e) const {
1.340 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.341 +
1.342 + NodeIt aNode(OutEdgeIt e) const {
1.343 + return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
1.344 + NodeIt bNode(OutEdgeIt e) const {
1.345 + return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
1.346 +
1.347 + int id(NodeIt v) const { return G.id(v); }
1.348 +
1.349 + template <typename S>
1.350 + class NodeMap {
1.351 + typename Graph::NodeMap<S> node_map;
1.352 + public:
1.353 + NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
1.354 + NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
1.355 void set(NodeIt nit, S a) { node_map.set(nit, a); }
1.356 S get(NodeIt nit) const { return node_map.get(nit); }
1.357 };
1.358
1.359 };
1.360
1.361 - template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
1.362 +
1.363 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.364 class MaxFlow {
1.365 typedef typename Graph::NodeIt NodeIt;
1.366 typedef typename Graph::EdgeIt EdgeIt;
1.367 @@ -120,21 +384,30 @@
1.368 NodeIt t;
1.369 FlowMap& flow;
1.370 const CapacityMap& capacity;
1.371 - typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
1.372 + typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.373 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.374 typedef typename AugGraph::EdgeIt AugEdgeIt;
1.375 +
1.376 + //AugGraph res_graph;
1.377 + //typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.378 + //typename AugGraph::NodeMap<AugEdgeIt> pred;
1.379 + //typename AugGraph::NodeMap<int> free;
1.380 public:
1.381 - MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
1.382 + MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
1.383 + G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //,
1.384 + //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
1.385 + { }
1.386 bool augment() {
1.387 AugGraph res_graph(G, flow, capacity);
1.388 bool _augment=false;
1.389
1.390 typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.391 - BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.392 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.393 res_bfs.pushAndSetReached(s);
1.394
1.395 typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.396 - //filled with invalid iterators
1.397 + //filled up with invalid iterators
1.398 + //pred.set(s, AugEdgeIt());
1.399
1.400 typename AugGraph::NodeMap<int> free(res_graph);
1.401
1.402 @@ -158,7 +431,7 @@
1.403
1.404 if (_augment) {
1.405 NodeIt n=t;
1.406 - T augment_value=free.get(t);
1.407 + Number augment_value=free.get(t);
1.408 while (pred.get(n).valid()) {
1.409 AugEdgeIt e=pred.get(n);
1.410 e.augment(augment_value);
1.411 @@ -171,8 +444,8 @@
1.412 void run() {
1.413 while (augment()) { }
1.414 }
1.415 - T flowValue() {
1.416 - T a=0;
1.417 + Number flowValue() {
1.418 + Number a=0;
1.419 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
1.420 a+=flow.get(i);
1.421 }
1.422 @@ -180,6 +453,153 @@
1.423 }
1.424 };
1.425
1.426 +
1.427 +/*
1.428 + template <typename Graph>
1.429 + class IteratorBoolNodeMap {
1.430 + typedef typename Graph::NodeIt NodeIt;
1.431 + typedef typename Graph::EachNodeIt EachNodeIt;
1.432 + class BoolItem {
1.433 + public:
1.434 + bool value;
1.435 + NodeIt prev;
1.436 + NodeIt next;
1.437 + BoolItem() : value(false), prev(), next() {}
1.438 + };
1.439 + NodeIt first_true;
1.440 + //NodeIt last_true;
1.441 + NodeIt first_false;
1.442 + //NodeIt last_false;
1.443 + const Graph& G;
1.444 + typename Graph::NodeMap<BoolItem> container;
1.445 + public:
1.446 + typedef bool ValueType;
1.447 + typedef NodeIt KeyType;
1.448 + IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
1.449 + //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
1.450 + //BoolItem b=container.get(e);
1.451 + //b.me=e;
1.452 + //container.set(b);
1.453 + //}
1.454 + G.getFirst(first_false);
1.455 + NodeIt e_prev;
1.456 + for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
1.457 + container[e].prev=e_prev;
1.458 + if (e_prev.valid()) container[e_prev].next=e;
1.459 + e_prev=e;
1.460 + }
1.461 + }
1.462 + //NodeMap(const Graph& _G, T a) :
1.463 + // G(_G), container(G.node_id, a) { }
1.464 + //FIXME
1.465 + void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
1.466 + T get(NodeIt nit) const { return container[G.id(nit)]; }
1.467 + //void resize() { container.resize(G.node_id); }
1.468 + //void resize(T a) { container.resize(G.node_id, a); }
1.469 + };
1.470 +*/
1.471 +
1.472 +
1.473 + template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
1.474 + class MaxFlow2 {
1.475 + typedef typename Graph::NodeIt NodeIt;
1.476 + typedef typename Graph::EdgeIt EdgeIt;
1.477 + typedef typename Graph::EachEdgeIt EachEdgeIt;
1.478 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.479 + typedef typename Graph::InEdgeIt InEdgeIt;
1.480 + const Graph& G;
1.481 + std::list<NodeIt>& S;
1.482 + std::list<NodeIt>& T;
1.483 + FlowMap& flow;
1.484 + const CapacityMap& capacity;
1.485 + typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
1.486 + typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
1.487 + typedef typename AugGraph::EdgeIt AugEdgeIt;
1.488 + typename Graph::NodeMap<bool> SMap;
1.489 + typename Graph::NodeMap<bool> TMap;
1.490 + public:
1.491 + MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
1.492 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.493 + i!=S.end(); ++i) {
1.494 + SMap.set(*i, true);
1.495 + }
1.496 + for (typename std::list<NodeIt>::const_iterator i=T.begin();
1.497 + i!=T.end(); ++i) {
1.498 + TMap.set(*i, true);
1.499 + }
1.500 + }
1.501 + bool augment() {
1.502 + AugGraph res_graph(G, flow, capacity);
1.503 + bool _augment=false;
1.504 + NodeIt reached_t_node;
1.505 +
1.506 + typedef typename AugGraph::NodeMap<bool> ReachedMap;
1.507 + BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
1.508 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.509 + i!=S.end(); ++i) {
1.510 + res_bfs.pushAndSetReached(*i);
1.511 + }
1.512 + //res_bfs.pushAndSetReached(s);
1.513 +
1.514 + typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
1.515 + //filled up with invalid iterators
1.516 +
1.517 + typename AugGraph::NodeMap<int> free(res_graph);
1.518 +
1.519 + //searching for augmenting path
1.520 + while ( !res_bfs.finished() ) {
1.521 + AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
1.522 + if (e.valid() && res_bfs.isBNodeNewlyReached()) {
1.523 + NodeIt v=res_graph.tail(e);
1.524 + NodeIt w=res_graph.head(e);
1.525 + pred.set(w, e);
1.526 + if (pred.get(v).valid()) {
1.527 + free.set(w, std::min(free.get(v), e.free()));
1.528 + } else {
1.529 + free.set(w, e.free());
1.530 + }
1.531 + if (TMap.get(res_graph.head(e))) {
1.532 + _augment=true;
1.533 + reached_t_node=res_graph.head(e);
1.534 + break;
1.535 + }
1.536 + }
1.537 +
1.538 + ++res_bfs;
1.539 + } //end of searching augmenting path
1.540 +
1.541 + if (_augment) {
1.542 + NodeIt n=reached_t_node;
1.543 + Number augment_value=free.get(reached_t_node);
1.544 + while (pred.get(n).valid()) {
1.545 + AugEdgeIt e=pred.get(n);
1.546 + e.augment(augment_value);
1.547 + n=res_graph.tail(e);
1.548 + }
1.549 + }
1.550 +
1.551 + return _augment;
1.552 + }
1.553 + void run() {
1.554 + while (augment()) { }
1.555 + }
1.556 + Number flowValue() {
1.557 + Number a=0;
1.558 + for(typename std::list<NodeIt>::const_iterator i=S.begin();
1.559 + i!=S.end(); ++i) {
1.560 + for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
1.561 + a+=flow.get(e);
1.562 + }
1.563 + for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
1.564 + a-=flow.get(e);
1.565 + }
1.566 + }
1.567 + return a;
1.568 + }
1.569 + };
1.570 +
1.571 +
1.572 +
1.573 } // namespace marci
1.574
1.575 #endif //EDMONDS_KARP_HH