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