1.1 --- a/src/work/marci/edmonds_karp.h Thu Apr 29 16:04:27 2004 +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 HUGO_EDMONDS_KARP_H
1.6 -#define HUGO_EDMONDS_KARP_H
1.7 -
1.8 -#include <algorithm>
1.9 -#include <list>
1.10 -#include <iterator>
1.11 -
1.12 -#include <bfs_iterator.h>
1.13 -#include <invalid.h>
1.14 -#include <graph_wrapper.h>
1.15 -#include <maps.h>
1.16 -#include <for_each_macros.h>
1.17 -
1.18 -namespace hugo {
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.tail(e);
1.66 - Node w=res_graph.head(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.head(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.tail(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->tail(e))<dist.get(g->head(e))); }
1.108 - bool operator[](const typename MapGraphWrapper::Edge& e) const {
1.109 - return (dist[g->tail(e)]<dist[g->head(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.head(e), dist[res_graph.tail(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.head(e))==dist.get(res_graph.tail(e))+1) {
1.159 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(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.tail(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.head(e), dist[res_graph.tail(e)]+1);
1.261 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(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.head(e)]==(dist[res_graph.tail(e)]+1)) {
1.268 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(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.tail(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.head(e), dist[res_graph.tail(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.tail(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.tail(e);
1.542 -// Node w=res_graph.head(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.head(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.tail(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.head(e), dist.get(res_graph.tail(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.head(e))==dist.get(res_graph.tail(e))+1) {
1.635 -// // 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.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.tail(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.head(e), dist.get(res_graph.tail(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.tail(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.tail(e);
1.909 -// // Node w=res_graph.head(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.head(e))) {
1.917 -// // _augment=true;
1.918 -// // reached_t_node=res_graph.head(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.tail(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 hugo
1.958 -
1.959 -#endif //HUGO_EDMONDS_KARP_H
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/oldies/edmonds_karp.h Thu Apr 29 16:07:10 2004 +0000
2.3 @@ -0,0 +1,956 @@
2.4 +// -*- c++ -*-
2.5 +#ifndef HUGO_EDMONDS_KARP_H
2.6 +#define HUGO_EDMONDS_KARP_H
2.7 +
2.8 +#include <algorithm>
2.9 +#include <list>
2.10 +#include <iterator>
2.11 +
2.12 +#include <bfs_iterator.h>
2.13 +#include <invalid.h>
2.14 +#include <graph_wrapper.h>
2.15 +#include <maps.h>
2.16 +#include <for_each_macros.h>
2.17 +
2.18 +namespace hugo {
2.19 +
2.20 + template <typename Graph, typename Num,
2.21 + typename CapMap, typename FlowMap>
2.22 + class MaxFlow {
2.23 + protected:
2.24 + typedef typename Graph::Node Node;
2.25 + typedef typename Graph::Edge Edge;
2.26 + typedef typename Graph::EdgeIt EdgeIt;
2.27 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.28 + typedef typename Graph::InEdgeIt InEdgeIt;
2.29 + const Graph* g;
2.30 + Node s;
2.31 + Node t;
2.32 + const CapMap* capacity;
2.33 + FlowMap* flow;
2.34 + typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
2.35 + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
2.36 + typedef typename ResGW::Edge ResGWEdge;
2.37 + //typedef typename ResGW::template NodeMap<bool> ReachedMap;
2.38 + typedef typename Graph::template NodeMap<bool> ReachedMap;
2.39 + ReachedMap level;
2.40 + //reached is called level because of compatibility with preflow
2.41 + public:
2.42 +
2.43 + MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity,
2.44 + FlowMap& _flow) :
2.45 + g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
2.46 +
2.47 + bool augmentOnShortestPath() {
2.48 + ResGW res_graph(*g, *capacity, *flow);
2.49 + bool _augment=false;
2.50 +
2.51 + //ReachedMap level(res_graph);
2.52 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.53 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.54 + bfs.pushAndSetReached(s);
2.55 +
2.56 + typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
2.57 + pred.set(s, INVALID);
2.58 +
2.59 + typename ResGW::template NodeMap<Num> free(res_graph);
2.60 +
2.61 + //searching for augmenting path
2.62 + while ( !bfs.finished() ) {
2.63 + ResGWOutEdgeIt e=bfs;
2.64 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.65 + Node v=res_graph.tail(e);
2.66 + Node w=res_graph.head(e);
2.67 + pred.set(w, e);
2.68 + if (res_graph.valid(pred[v])) {
2.69 + free.set(w, std::min(free[v], res_graph.resCap(e)));
2.70 + } else {
2.71 + free.set(w, res_graph.resCap(e));
2.72 + }
2.73 + if (res_graph.head(e)==t) { _augment=true; break; }
2.74 + }
2.75 +
2.76 + ++bfs;
2.77 + } //end of searching augmenting path
2.78 +
2.79 + if (_augment) {
2.80 + Node n=t;
2.81 + Num augment_value=free[t];
2.82 + while (res_graph.valid(pred[n])) {
2.83 + ResGWEdge e=pred[n];
2.84 + res_graph.augment(e, augment_value);
2.85 + n=res_graph.tail(e);
2.86 + }
2.87 + }
2.88 +
2.89 + return _augment;
2.90 + }
2.91 +
2.92 + template<typename MapGraphWrapper>
2.93 + class DistanceMap {
2.94 + protected:
2.95 + const MapGraphWrapper* g;
2.96 + typename MapGraphWrapper::template NodeMap<int> dist;
2.97 + public:
2.98 + DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
2.99 + void set(const typename MapGraphWrapper::Node& n, int a) {
2.100 + dist.set(n, a);
2.101 + }
2.102 + int operator[](const typename MapGraphWrapper::Node& n)
2.103 + { return dist[n]; }
2.104 +// int get(const typename MapGraphWrapper::Node& n) const {
2.105 +// return dist[n]; }
2.106 +// bool get(const typename MapGraphWrapper::Edge& e) const {
2.107 +// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
2.108 + bool operator[](const typename MapGraphWrapper::Edge& e) const {
2.109 + return (dist[g->tail(e)]<dist[g->head(e)]);
2.110 + }
2.111 + };
2.112 +
2.113 + template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.114 + typedef MutableGraph MG;
2.115 + bool _augment=false;
2.116 +
2.117 + ResGW res_graph(*g, *capacity, *flow);
2.118 +
2.119 + //ReachedMap level(res_graph);
2.120 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.121 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.122 +
2.123 + bfs.pushAndSetReached(s);
2.124 + //typename ResGW::NodeMap<int> dist(res_graph); //filled up with 0's
2.125 + DistanceMap<ResGW> dist(res_graph);
2.126 + while ( !bfs.finished() ) {
2.127 + ResGWOutEdgeIt e=bfs;
2.128 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.129 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.130 + }
2.131 + ++bfs;
2.132 + } //computing distances from s in the residual graph
2.133 +
2.134 + MG F;
2.135 + ConstMap<typename ResGW::Node, bool> true_map(true);
2.136 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.137 + DistanceMap<ResGW> > FilterResGW;
2.138 + FilterResGW filter_res_graph(res_graph, true_map, dist);
2.139 + typename ResGW::template NodeMap<typename MG::Node>
2.140 + res_graph_to_F(res_graph);
2.141 + {
2.142 + typename ResGW::NodeIt n;
2.143 + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
2.144 + res_graph_to_F.set(n, F.addNode());
2.145 + }
2.146 + }
2.147 +
2.148 + typename MG::Node sF=res_graph_to_F[s];
2.149 + typename MG::Node tF=res_graph_to_F[t];
2.150 + typename MG::template EdgeMap<ResGWEdge> original_edge(F);
2.151 + typename MG::template EdgeMap<Num> residual_capacity(F);
2.152 +
2.153 + //Making F to the graph containing the edges of the residual graph
2.154 + //which are in some shortest paths
2.155 + {
2.156 + typename FilterResGW::EdgeIt e;
2.157 + for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
2.158 + //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.159 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.160 + original_edge.update();
2.161 + original_edge.set(f, e);
2.162 + residual_capacity.update();
2.163 + residual_capacity.set(f, res_graph.resCap(e));
2.164 + //}
2.165 + }
2.166 + }
2.167 +
2.168 + bool __augment=true;
2.169 +
2.170 + while (__augment) {
2.171 + __augment=false;
2.172 + //computing blocking flow with dfs
2.173 +
2.174 + DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
2.175 + typename MG::template NodeMap<typename MG::Edge> pred(F);
2.176 + pred.set(sF, INVALID);
2.177 + //invalid iterators for sources
2.178 +
2.179 + typename MG::template NodeMap<Num> free(F);
2.180 +
2.181 + dfs.pushAndSetReached(sF);
2.182 + while (!dfs.finished()) {
2.183 + ++dfs;
2.184 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.185 + if (dfs.isBNodeNewlyReached()) {
2.186 + typename MG::Node v=F.aNode(dfs);
2.187 + typename MG::Node w=F.bNode(dfs);
2.188 + pred.set(w, dfs);
2.189 + if (F.valid(pred[v])) {
2.190 + free.set(w, std::min(free[v], residual_capacity[dfs]));
2.191 + } else {
2.192 + free.set(w, residual_capacity[dfs]);
2.193 + }
2.194 + if (w==tF) {
2.195 + __augment=true;
2.196 + _augment=true;
2.197 + break;
2.198 + }
2.199 +
2.200 + } else {
2.201 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
2.202 + }
2.203 + }
2.204 + }
2.205 +
2.206 + if (__augment) {
2.207 + typename MG::Node n=tF;
2.208 + Num augment_value=free[tF];
2.209 + while (F.valid(pred[n])) {
2.210 + typename MG::Edge e=pred[n];
2.211 + res_graph.augment(original_edge[e], augment_value);
2.212 + n=F.tail(e);
2.213 + if (residual_capacity[e]==augment_value)
2.214 + F.erase(e);
2.215 + else
2.216 + residual_capacity.set(e, residual_capacity[e]-augment_value);
2.217 + }
2.218 + }
2.219 +
2.220 + }
2.221 +
2.222 + return _augment;
2.223 + }
2.224 +
2.225 + template<typename MutableGraph> bool augmentOnBlockingFlow1() {
2.226 + typedef MutableGraph MG;
2.227 + bool _augment=false;
2.228 +
2.229 + ResGW res_graph(*g, *capacity, *flow);
2.230 +
2.231 + //bfs for distances on the residual graph
2.232 + //ReachedMap level(res_graph);
2.233 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.234 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.235 + bfs.pushAndSetReached(s);
2.236 + typename ResGW::template NodeMap<int>
2.237 + dist(res_graph); //filled up with 0's
2.238 +
2.239 + //F will contain the physical copy of the residual graph
2.240 + //with the set of edges which are on shortest paths
2.241 + MG F;
2.242 + typename ResGW::template NodeMap<typename MG::Node>
2.243 + res_graph_to_F(res_graph);
2.244 + {
2.245 + typename ResGW::NodeIt n;
2.246 + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
2.247 + res_graph_to_F.set(n, F.addNode());
2.248 + }
2.249 + }
2.250 +
2.251 + typename MG::Node sF=res_graph_to_F[s];
2.252 + typename MG::Node tF=res_graph_to_F[t];
2.253 + typename MG::template EdgeMap<ResGWEdge> original_edge(F);
2.254 + typename MG::template EdgeMap<Num> residual_capacity(F);
2.255 +
2.256 + while ( !bfs.finished() ) {
2.257 + ResGWOutEdgeIt e=bfs;
2.258 + if (res_graph.valid(e)) {
2.259 + if (bfs.isBNodeNewlyReached()) {
2.260 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.261 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.262 + original_edge.update();
2.263 + original_edge.set(f, e);
2.264 + residual_capacity.update();
2.265 + residual_capacity.set(f, res_graph.resCap(e));
2.266 + } else {
2.267 + if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
2.268 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
2.269 + original_edge.update();
2.270 + original_edge.set(f, e);
2.271 + residual_capacity.update();
2.272 + residual_capacity.set(f, res_graph.resCap(e));
2.273 + }
2.274 + }
2.275 + }
2.276 + ++bfs;
2.277 + } //computing distances from s in the residual graph
2.278 +
2.279 + bool __augment=true;
2.280 +
2.281 + while (__augment) {
2.282 + __augment=false;
2.283 + //computing blocking flow with dfs
2.284 + DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
2.285 + typename MG::template NodeMap<typename MG::Edge> pred(F);
2.286 + pred.set(sF, INVALID);
2.287 + //invalid iterators for sources
2.288 +
2.289 + typename MG::template NodeMap<Num> free(F);
2.290 +
2.291 + dfs.pushAndSetReached(sF);
2.292 + while (!dfs.finished()) {
2.293 + ++dfs;
2.294 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
2.295 + if (dfs.isBNodeNewlyReached()) {
2.296 + typename MG::Node v=F.aNode(dfs);
2.297 + typename MG::Node w=F.bNode(dfs);
2.298 + pred.set(w, dfs);
2.299 + if (F.valid(pred[v])) {
2.300 + free.set(w, std::min(free[v], residual_capacity[dfs]));
2.301 + } else {
2.302 + free.set(w, residual_capacity[dfs]);
2.303 + }
2.304 + if (w==tF) {
2.305 + __augment=true;
2.306 + _augment=true;
2.307 + break;
2.308 + }
2.309 +
2.310 + } else {
2.311 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
2.312 + }
2.313 + }
2.314 + }
2.315 +
2.316 + if (__augment) {
2.317 + typename MG::Node n=tF;
2.318 + Num augment_value=free[tF];
2.319 + while (F.valid(pred[n])) {
2.320 + typename MG::Edge e=pred[n];
2.321 + res_graph.augment(original_edge[e], augment_value);
2.322 + n=F.tail(e);
2.323 + if (residual_capacity[e]==augment_value)
2.324 + F.erase(e);
2.325 + else
2.326 + residual_capacity.set(e, residual_capacity[e]-augment_value);
2.327 + }
2.328 + }
2.329 +
2.330 + }
2.331 +
2.332 + return _augment;
2.333 + }
2.334 +
2.335 + bool augmentOnBlockingFlow2() {
2.336 + bool _augment=false;
2.337 +
2.338 + ResGW res_graph(*g, *capacity, *flow);
2.339 +
2.340 + //ReachedMap level(res_graph);
2.341 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
2.342 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
2.343 +
2.344 + bfs.pushAndSetReached(s);
2.345 + DistanceMap<ResGW> dist(res_graph);
2.346 + while ( !bfs.finished() ) {
2.347 + ResGWOutEdgeIt e=bfs;
2.348 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.349 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
2.350 + }
2.351 + ++bfs;
2.352 + } //computing distances from s in the residual graph
2.353 +
2.354 + //Subgraph containing the edges on some shortest paths
2.355 + ConstMap<typename ResGW::Node, bool> true_map(true);
2.356 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
2.357 + DistanceMap<ResGW> > FilterResGW;
2.358 + FilterResGW filter_res_graph(res_graph, true_map, dist);
2.359 +
2.360 + //Subgraph, which is able to delete edges which are already
2.361 + //met by the dfs
2.362 + typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
2.363 + first_out_edges(filter_res_graph);
2.364 + typename FilterResGW::NodeIt v;
2.365 + for(filter_res_graph.first(v); filter_res_graph.valid(v);
2.366 + filter_res_graph.next(v))
2.367 + {
2.368 + typename FilterResGW::OutEdgeIt e;
2.369 + filter_res_graph.first(e, v);
2.370 + first_out_edges.set(v, e);
2.371 + }
2.372 + typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
2.373 + template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
2.374 + ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
2.375 +
2.376 + bool __augment=true;
2.377 +
2.378 + while (__augment) {
2.379 +
2.380 + __augment=false;
2.381 + //computing blocking flow with dfs
2.382 + DfsIterator< ErasingResGW,
2.383 + typename ErasingResGW::template NodeMap<bool> >
2.384 + dfs(erasing_res_graph);
2.385 + typename ErasingResGW::
2.386 + template NodeMap<typename ErasingResGW::OutEdgeIt>
2.387 + pred(erasing_res_graph);
2.388 + pred.set(s, INVALID);
2.389 + //invalid iterators for sources
2.390 +
2.391 + typename ErasingResGW::template NodeMap<Num>
2.392 + free1(erasing_res_graph);
2.393 +
2.394 + dfs.pushAndSetReached(
2.395 + typename ErasingResGW::Node(
2.396 + typename FilterResGW::Node(
2.397 + typename ResGW::Node(s)
2.398 + )
2.399 + )
2.400 + );
2.401 + while (!dfs.finished()) {
2.402 + ++dfs;
2.403 + if (erasing_res_graph.valid(
2.404 + typename ErasingResGW::OutEdgeIt(dfs)))
2.405 + {
2.406 + if (dfs.isBNodeNewlyReached()) {
2.407 +
2.408 + typename ErasingResGW::Node v=erasing_res_graph.aNode(dfs);
2.409 + typename ErasingResGW::Node w=erasing_res_graph.bNode(dfs);
2.410 +
2.411 + pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
2.412 + if (erasing_res_graph.valid(pred[v])) {
2.413 + free1.set(w, std::min(free1[v], res_graph.resCap(
2.414 + typename ErasingResGW::OutEdgeIt(dfs))));
2.415 + } else {
2.416 + free1.set(w, res_graph.resCap(
2.417 + typename ErasingResGW::OutEdgeIt(dfs)));
2.418 + }
2.419 +
2.420 + if (w==t) {
2.421 + __augment=true;
2.422 + _augment=true;
2.423 + break;
2.424 + }
2.425 + } else {
2.426 + erasing_res_graph.erase(dfs);
2.427 + }
2.428 + }
2.429 + }
2.430 +
2.431 + if (__augment) {
2.432 + typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
2.433 +// typename ResGW::NodeMap<Num> a(res_graph);
2.434 +// typename ResGW::Node b;
2.435 +// Num j=a[b];
2.436 +// typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
2.437 +// typename FilterResGW::Node b1;
2.438 +// Num j1=a1[b1];
2.439 +// typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
2.440 +// typename ErasingResGW::Node b2;
2.441 +// Num j2=a2[b2];
2.442 + Num augment_value=free1[n];
2.443 + while (erasing_res_graph.valid(pred[n])) {
2.444 + typename ErasingResGW::OutEdgeIt e=pred[n];
2.445 + res_graph.augment(e, augment_value);
2.446 + n=erasing_res_graph.tail(e);
2.447 + if (res_graph.resCap(e)==0)
2.448 + erasing_res_graph.erase(e);
2.449 + }
2.450 + }
2.451 +
2.452 + } //while (__augment)
2.453 +
2.454 + return _augment;
2.455 + }
2.456 +
2.457 + void run() {
2.458 + //int num_of_augmentations=0;
2.459 + while (augmentOnShortestPath()) {
2.460 + //while (augmentOnBlockingFlow<MutableGraph>()) {
2.461 + //std::cout << ++num_of_augmentations << " ";
2.462 + //std::cout<<std::endl;
2.463 + }
2.464 + }
2.465 +
2.466 + template<typename MutableGraph> void run() {
2.467 + //int num_of_augmentations=0;
2.468 + //while (augmentOnShortestPath()) {
2.469 + while (augmentOnBlockingFlow<MutableGraph>()) {
2.470 + //std::cout << ++num_of_augmentations << " ";
2.471 + //std::cout<<std::endl;
2.472 + }
2.473 + }
2.474 +
2.475 + Num flowValue() {
2.476 + Num a=0;
2.477 + OutEdgeIt e;
2.478 + for(g->first(e, s); g->valid(e); g->next(e)) {
2.479 + a+=(*flow)[e];
2.480 + }
2.481 + return a;
2.482 + }
2.483 +
2.484 + };
2.485 +
2.486 +
2.487 +// template <typename Graph, typename Num, typename FlowMap, typename CapMap>
2.488 +// class MaxMatching {
2.489 +// public:
2.490 +// typedef typename Graph::Node Node;
2.491 +// typedef typename Graph::NodeIt NodeIt;
2.492 +// typedef typename Graph::Edge Edge;
2.493 +// typedef typename Graph::EdgeIt EdgeIt;
2.494 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
2.495 +// typedef typename Graph::InEdgeIt InEdgeIt;
2.496 +
2.497 +// typedef typename Graph::NodeMap<bool> SMap;
2.498 +// typedef typename Graph::NodeMap<bool> TMap;
2.499 +// private:
2.500 +// const Graph* G;
2.501 +// SMap* S;
2.502 +// TMap* T;
2.503 +// //Node s;
2.504 +// //Node t;
2.505 +// FlowMap* flow;
2.506 +// const CapMap* capacity;
2.507 +// typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
2.508 +// typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.509 +// typedef typename AugGraph::Edge AugEdge;
2.510 +// typename Graph::NodeMap<int> used; //0
2.511 +
2.512 +// public:
2.513 +// MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) :
2.514 +// G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
2.515 +// bool augmentOnShortestPath() {
2.516 +// AugGraph res_graph(*G, *flow, *capacity);
2.517 +// bool _augment=false;
2.518 +
2.519 +// typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.520 +// BfsIterator< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > bfs(res_graph);
2.521 +// typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.522 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.523 +// if ((S->get(s)) && (used.get(s)<1) ) {
2.524 +// //Num u=0;
2.525 +// //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.526 +// //u+=flow->get(e);
2.527 +// //if (u<1) {
2.528 +// bfs.pushAndSetReached(s);
2.529 +// pred.set(s, AugEdge(INVALID));
2.530 +// //}
2.531 +// }
2.532 +// }
2.533 +
2.534 +// typename AugGraph::NodeMap<Num> free(res_graph);
2.535 +
2.536 +// Node n;
2.537 +// //searching for augmenting path
2.538 +// while ( !bfs.finished() ) {
2.539 +// AugOutEdgeIt e=bfs;
2.540 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.541 +// Node v=res_graph.tail(e);
2.542 +// Node w=res_graph.head(e);
2.543 +// pred.set(w, e);
2.544 +// if (res_graph.valid(pred.get(v))) {
2.545 +// free.set(w, std::min(free.get(v), res_graph.free(e)));
2.546 +// } else {
2.547 +// free.set(w, res_graph.free(e));
2.548 +// }
2.549 +// n=res_graph.head(e);
2.550 +// if (T->get(n) && (used.get(n)<1) ) {
2.551 +// //Num u=0;
2.552 +// //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
2.553 +// //u+=flow->get(f);
2.554 +// //if (u<1) {
2.555 +// _augment=true;
2.556 +// break;
2.557 +// //}
2.558 +// }
2.559 +// }
2.560 +
2.561 +// ++bfs;
2.562 +// } //end of searching augmenting path
2.563 +
2.564 +// if (_augment) {
2.565 +// //Node n=t;
2.566 +// used.set(n, 1); //mind2 vegen jav
2.567 +// Num augment_value=free.get(n);
2.568 +// while (res_graph.valid(pred.get(n))) {
2.569 +// AugEdge e=pred.get(n);
2.570 +// res_graph.augment(e, augment_value);
2.571 +// n=res_graph.tail(e);
2.572 +// }
2.573 +// used.set(n, 1); //mind2 vegen jav
2.574 +// }
2.575 +
2.576 +// return _augment;
2.577 +// }
2.578 +
2.579 +// // template<typename MutableGraph> bool augmentOnBlockingFlow() {
2.580 +// // bool _augment=false;
2.581 +
2.582 +// // AugGraph res_graph(*G, *flow, *capacity);
2.583 +
2.584 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.585 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.586 +
2.587 +
2.588 +
2.589 +
2.590 +
2.591 +// // //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.592 +// // for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.593 +// // if (S->get(s)) {
2.594 +// // Num u=0;
2.595 +// // for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.596 +// // u+=flow->get(e);
2.597 +// // if (u<1) {
2.598 +// // bfs.pushAndSetReached(s);
2.599 +// // //pred.set(s, AugEdge(INVALID));
2.600 +// // }
2.601 +// // }
2.602 +// // }
2.603 +
2.604 +
2.605 +
2.606 +
2.607 +// // //bfs.pushAndSetReached(s);
2.608 +// // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
2.609 +// // while ( !bfs.finished() ) {
2.610 +// // AugOutEdgeIt e=bfs;
2.611 +// // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.612 +// // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.613 +// // }
2.614 +
2.615 +// // ++bfs;
2.616 +// // } //computing distances from s in the residual graph
2.617 +
2.618 +// // MutableGraph F;
2.619 +// // typename AugGraph::NodeMap<typename MutableGraph::Node>
2.620 +// // res_graph_to_F(res_graph);
2.621 +// // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
2.622 +// // res_graph_to_F.set(n, F.addNode());
2.623 +// // }
2.624 +
2.625 +// // typename MutableGraph::Node sF=res_graph_to_F.get(s);
2.626 +// // typename MutableGraph::Node tF=res_graph_to_F.get(t);
2.627 +
2.628 +// // typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
2.629 +// // typename MutableGraph::EdgeMap<Num> residual_capacity(F);
2.630 +
2.631 +// // //Making F to the graph containing the edges of the residual graph
2.632 +// // //which are in some shortest paths
2.633 +// // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
2.634 +// // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
2.635 +// // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
2.636 +// // original_edge.update();
2.637 +// // original_edge.set(f, e);
2.638 +// // residual_capacity.update();
2.639 +// // residual_capacity.set(f, res_graph.free(e));
2.640 +// // }
2.641 +// // }
2.642 +
2.643 +// // bool __augment=true;
2.644 +
2.645 +// // while (__augment) {
2.646 +// // __augment=false;
2.647 +// // //computing blocking flow with dfs
2.648 +// // typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
2.649 +// // DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
2.650 +// // typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
2.651 +// // pred.set(sF, typename MutableGraph::Edge(INVALID));
2.652 +// // //invalid iterators for sources
2.653 +
2.654 +// // typename MutableGraph::NodeMap<Num> free(F);
2.655 +
2.656 +// // dfs.pushAndSetReached(sF);
2.657 +// // while (!dfs.finished()) {
2.658 +// // ++dfs;
2.659 +// // if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
2.660 +// // if (dfs.isBNodeNewlyReached()) {
2.661 +// // typename MutableGraph::Node v=F.aNode(dfs);
2.662 +// // typename MutableGraph::Node w=F.bNode(dfs);
2.663 +// // pred.set(w, dfs);
2.664 +// // if (F.valid(pred.get(v))) {
2.665 +// // free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
2.666 +// // } else {
2.667 +// // free.set(w, residual_capacity.get(dfs));
2.668 +// // }
2.669 +// // if (w==tF) {
2.670 +// // __augment=true;
2.671 +// // _augment=true;
2.672 +// // break;
2.673 +// // }
2.674 +
2.675 +// // } else {
2.676 +// // F.erase(typename MutableGraph::OutEdgeIt(dfs));
2.677 +// // }
2.678 +// // }
2.679 +// // }
2.680 +
2.681 +// // if (__augment) {
2.682 +// // typename MutableGraph::Node n=tF;
2.683 +// // Num augment_value=free.get(tF);
2.684 +// // while (F.valid(pred.get(n))) {
2.685 +// // typename MutableGraph::Edge e=pred.get(n);
2.686 +// // res_graph.augment(original_edge.get(e), augment_value);
2.687 +// // n=F.tail(e);
2.688 +// // if (residual_capacity.get(e)==augment_value)
2.689 +// // F.erase(e);
2.690 +// // else
2.691 +// // residual_capacity.set(e, residual_capacity.get(e)-augment_value);
2.692 +// // }
2.693 +// // }
2.694 +
2.695 +// // }
2.696 +
2.697 +// // return _augment;
2.698 +// // }
2.699 +// bool augmentOnBlockingFlow2() {
2.700 +// bool _augment=false;
2.701 +
2.702 +// //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph;
2.703 +// typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph;
2.704 +// typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
2.705 +// typedef typename EAugGraph::Edge EAugEdge;
2.706 +
2.707 +// EAugGraph res_graph(*G, *flow, *capacity);
2.708 +
2.709 +// //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
2.710 +// BfsIterator<
2.711 +// ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>,
2.712 +// /*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/
2.713 +// ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph);
2.714 +
2.715 +
2.716 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.717 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.718 +// if (S->get(s)) {
2.719 +// Num u=0;
2.720 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.721 +// u+=flow->get(e);
2.722 +// if (u<1) {
2.723 +// bfs.pushAndSetReached(s);
2.724 +// //pred.set(s, AugEdge(INVALID));
2.725 +// }
2.726 +// }
2.727 +// }
2.728 +
2.729 +
2.730 +// //bfs.pushAndSetReached(s);
2.731 +
2.732 +// typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::
2.733 +// NodeMap<int>& dist=res_graph.dist;
2.734 +
2.735 +// while ( !bfs.finished() ) {
2.736 +// typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
2.737 +// if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
2.738 +// dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
2.739 +// }
2.740 +// ++bfs;
2.741 +// } //computing distances from s in the residual graph
2.742 +
2.743 +// bool __augment=true;
2.744 +
2.745 +// while (__augment) {
2.746 +
2.747 +// __augment=false;
2.748 +// //computing blocking flow with dfs
2.749 +// typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
2.750 +// DfsIterator< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
2.751 +// dfs(res_graph);
2.752 +// typename EAugGraph::NodeMap<EAugEdge> pred(res_graph, INVALID);
2.753 +// //pred.set(s, EAugEdge(INVALID));
2.754 +// //invalid iterators for sources
2.755 +
2.756 +// typename EAugGraph::NodeMap<Num> free(res_graph);
2.757 +
2.758 +
2.759 +// //typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.760 +// for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
2.761 +// if (S->get(s)) {
2.762 +// Num u=0;
2.763 +// for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
2.764 +// u+=flow->get(e);
2.765 +// if (u<1) {
2.766 +// dfs.pushAndSetReached(s);
2.767 +// //pred.set(s, AugEdge(INVALID));
2.768 +// }
2.769 +// }
2.770 +// }
2.771 +
2.772 +
2.773 +
2.774 +// //dfs.pushAndSetReached(s);
2.775 +// typename EAugGraph::Node n;
2.776 +// while (!dfs.finished()) {
2.777 +// ++dfs;
2.778 +// if (res_graph.valid(EAugOutEdgeIt(dfs))) {
2.779 +// if (dfs.isBNodeNewlyReached()) {
2.780 +
2.781 +// typename EAugGraph::Node v=res_graph.aNode(dfs);
2.782 +// typename EAugGraph::Node w=res_graph.bNode(dfs);
2.783 +
2.784 +// pred.set(w, EAugOutEdgeIt(dfs));
2.785 +// if (res_graph.valid(pred.get(v))) {
2.786 +// free.set(w, std::min(free.get(v), res_graph.free(dfs)));
2.787 +// } else {
2.788 +// free.set(w, res_graph.free(dfs));
2.789 +// }
2.790 +
2.791 +// n=w;
2.792 +// if (T->get(w)) {
2.793 +// Num u=0;
2.794 +// for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
2.795 +// u+=flow->get(f);
2.796 +// if (u<1) {
2.797 +// __augment=true;
2.798 +// _augment=true;
2.799 +// break;
2.800 +// }
2.801 +// }
2.802 +// } else {
2.803 +// res_graph.erase(dfs);
2.804 +// }
2.805 +// }
2.806 +
2.807 +// }
2.808 +
2.809 +// if (__augment) {
2.810 +// // typename EAugGraph::Node n=t;
2.811 +// Num augment_value=free.get(n);
2.812 +// while (res_graph.valid(pred.get(n))) {
2.813 +// EAugEdge e=pred.get(n);
2.814 +// res_graph.augment(e, augment_value);
2.815 +// n=res_graph.tail(e);
2.816 +// if (res_graph.free(e)==0)
2.817 +// res_graph.erase(e);
2.818 +// }
2.819 +// }
2.820 +
2.821 +// }
2.822 +
2.823 +// return _augment;
2.824 +// }
2.825 +// void run() {
2.826 +// //int num_of_augmentations=0;
2.827 +// while (augmentOnShortestPath()) {
2.828 +// //while (augmentOnBlockingFlow<MutableGraph>()) {
2.829 +// //std::cout << ++num_of_augmentations << " ";
2.830 +// //std::cout<<std::endl;
2.831 +// }
2.832 +// }
2.833 +// // template<typename MutableGraph> void run() {
2.834 +// // //int num_of_augmentations=0;
2.835 +// // //while (augmentOnShortestPath()) {
2.836 +// // while (augmentOnBlockingFlow<MutableGraph>()) {
2.837 +// // //std::cout << ++num_of_augmentations << " ";
2.838 +// // //std::cout<<std::endl;
2.839 +// // }
2.840 +// // }
2.841 +// Num flowValue() {
2.842 +// Num a=0;
2.843 +// EdgeIt e;
2.844 +// for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
2.845 +// a+=flow->get(e);
2.846 +// }
2.847 +// return a;
2.848 +// }
2.849 +// };
2.850 +
2.851 +
2.852 +
2.853 +
2.854 +
2.855 +
2.856 +// // template <typename Graph, typename Num, typename FlowMap, typename CapMap>
2.857 +// // class MaxFlow2 {
2.858 +// // public:
2.859 +// // typedef typename Graph::Node Node;
2.860 +// // typedef typename Graph::Edge Edge;
2.861 +// // typedef typename Graph::EdgeIt EdgeIt;
2.862 +// // typedef typename Graph::OutEdgeIt OutEdgeIt;
2.863 +// // typedef typename Graph::InEdgeIt InEdgeIt;
2.864 +// // private:
2.865 +// // const Graph& G;
2.866 +// // std::list<Node>& S;
2.867 +// // std::list<Node>& T;
2.868 +// // FlowMap& flow;
2.869 +// // const CapMap& capacity;
2.870 +// // typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
2.871 +// // typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
2.872 +// // typedef typename AugGraph::Edge AugEdge;
2.873 +// // typename Graph::NodeMap<bool> SMap;
2.874 +// // typename Graph::NodeMap<bool> TMap;
2.875 +// // public:
2.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) {
2.877 +// // for(typename std::list<Node>::const_iterator i=S.begin();
2.878 +// // i!=S.end(); ++i) {
2.879 +// // SMap.set(*i, true);
2.880 +// // }
2.881 +// // for (typename std::list<Node>::const_iterator i=T.begin();
2.882 +// // i!=T.end(); ++i) {
2.883 +// // TMap.set(*i, true);
2.884 +// // }
2.885 +// // }
2.886 +// // bool augment() {
2.887 +// // AugGraph res_graph(G, flow, capacity);
2.888 +// // bool _augment=false;
2.889 +// // Node reached_t_node;
2.890 +
2.891 +// // typedef typename AugGraph::NodeMap<bool> ReachedMap;
2.892 +// // BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
2.893 +// // for(typename std::list<Node>::const_iterator i=S.begin();
2.894 +// // i!=S.end(); ++i) {
2.895 +// // bfs.pushAndSetReached(*i);
2.896 +// // }
2.897 +// // //bfs.pushAndSetReached(s);
2.898 +
2.899 +// // typename AugGraph::NodeMap<AugEdge> pred(res_graph);
2.900 +// // //filled up with invalid iterators
2.901 +
2.902 +// // typename AugGraph::NodeMap<Num> free(res_graph);
2.903 +
2.904 +// // //searching for augmenting path
2.905 +// // while ( !bfs.finished() ) {
2.906 +// // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
2.907 +// // if (e.valid() && bfs.isBNodeNewlyReached()) {
2.908 +// // Node v=res_graph.tail(e);
2.909 +// // Node w=res_graph.head(e);
2.910 +// // pred.set(w, e);
2.911 +// // if (pred.get(v).valid()) {
2.912 +// // free.set(w, std::min(free.get(v), e.free()));
2.913 +// // } else {
2.914 +// // free.set(w, e.free());
2.915 +// // }
2.916 +// // if (TMap.get(res_graph.head(e))) {
2.917 +// // _augment=true;
2.918 +// // reached_t_node=res_graph.head(e);
2.919 +// // break;
2.920 +// // }
2.921 +// // }
2.922 +
2.923 +// // ++bfs;
2.924 +// // } //end of searching augmenting path
2.925 +
2.926 +// // if (_augment) {
2.927 +// // Node n=reached_t_node;
2.928 +// // Num augment_value=free.get(reached_t_node);
2.929 +// // while (pred.get(n).valid()) {
2.930 +// // AugEdge e=pred.get(n);
2.931 +// // e.augment(augment_value);
2.932 +// // n=res_graph.tail(e);
2.933 +// // }
2.934 +// // }
2.935 +
2.936 +// // return _augment;
2.937 +// // }
2.938 +// // void run() {
2.939 +// // while (augment()) { }
2.940 +// // }
2.941 +// // Num flowValue() {
2.942 +// // Num a=0;
2.943 +// // for(typename std::list<Node>::const_iterator i=S.begin();
2.944 +// // i!=S.end(); ++i) {
2.945 +// // for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
2.946 +// // a+=flow.get(e);
2.947 +// // }
2.948 +// // for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
2.949 +// // a-=flow.get(e);
2.950 +// // }
2.951 +// // }
2.952 +// // return a;
2.953 +// // }
2.954 +// // };
2.955 +
2.956 +
2.957 +} // namespace hugo
2.958 +
2.959 +#endif //HUGO_EDMONDS_KARP_H