1.1 --- a/src/work/jacint/max_flow.h Thu Apr 29 17:23:56 2004 +0000
1.2 +++ b/src/work/jacint/max_flow.h Thu Apr 29 17:34:42 2004 +0000
1.3 @@ -1,35 +1,35 @@
1.4 // -*- C++ -*-
1.5
1.6 /*
1.7 -Heuristics:
1.8 - 2 phase
1.9 - gap
1.10 - list 'level_list' on the nodes on level i implemented by hand
1.11 - stack 'active' on the active nodes on level i
1.12 - runs heuristic 'highest label' for H1*n relabels
1.13 - runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
1.14 + Heuristics:
1.15 + 2 phase
1.16 + gap
1.17 + list 'level_list' on the nodes on level i implemented by hand
1.18 + stack 'active' on the active nodes on level i
1.19 + runs heuristic 'highest label' for H1*n relabels
1.20 + runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
1.21
1.22 -Parameters H0 and H1 are initialized to 20 and 1.
1.23 + Parameters H0 and H1 are initialized to 20 and 1.
1.24
1.25 -Constructors:
1.26 + Constructors:
1.27
1.28 -Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
1.29 - FlowMap is not constant zero, and should be true if it is
1.30 + Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
1.31 + FlowMap is not constant zero, and should be true if it is
1.32
1.33 -Members:
1.34 + Members:
1.35
1.36 -void run()
1.37 + void run()
1.38
1.39 -Num flowValue() : returns the value of a maximum flow
1.40 + Num flowValue() : returns the value of a maximum flow
1.41
1.42 -void minMinCut(CutMap& M) : sets M to the characteristic vector of the
1.43 - minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
1.44 + void minMinCut(CutMap& M) : sets M to the characteristic vector of the
1.45 + minimum min cut. M should be a map of bools initialized to false. ??Is it OK?
1.46
1.47 -void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
1.48 - maximum min cut. M should be a map of bools initialized to false.
1.49 + void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
1.50 + maximum min cut. M should be a map of bools initialized to false.
1.51
1.52 -void minCut(CutMap& M) : sets M to the characteristic vector of
1.53 - a min cut. M should be a map of bools initialized to false.
1.54 + void minCut(CutMap& M) : sets M to the characteristic vector of
1.55 + a min cut. M should be a map of bools initialized to false.
1.56
1.57 */
1.58
1.59 @@ -52,6 +52,7 @@
1.60
1.61 namespace hugo {
1.62
1.63 + ///\author Marton Makai, Jacint Szabo
1.64 template <typename Graph, typename Num,
1.65 typename CapMap=typename Graph::template EdgeMap<Num>,
1.66 typename FlowMap=typename Graph::template EdgeMap<Num> >
1.67 @@ -97,23 +98,39 @@
1.68 g(&_G), s(_s), t(_t), capacity(&_capacity),
1.69 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
1.70
1.71 + /// A max flow algorithm is run.
1.72 + ///\pre the flow have to be 0 at the beginning.
1.73 void run() {
1.74 preflow( ZERO_FLOW );
1.75 }
1.76
1.77 + /// A preflow algorithm is run. The initial edge-set have to be a flow,
1.78 + /// or from a preflow, according to \c fe.
1.79 void preflow( flowEnum fe ) {
1.80 preflowPhase0(fe);
1.81 preflowPhase1();
1.82 }
1.83
1.84 + /// Run the first phase of preflow, starting from a 0 flow, from a flow,
1.85 + /// or from a preflow, according to \c fe.
1.86 void preflowPhase0( flowEnum fe );
1.87
1.88 + /// Second phase of preflow.
1.89 void preflowPhase1();
1.90
1.91 + /// Starting from a flow, this method searches for an augmenting path
1.92 + /// according to the Edmonds-Karp algorithm
1.93 + /// and augments the flow on if any.
1.94 bool augmentOnShortestPath();
1.95
1.96 + /// Starting from a flow, this method searches for an augmenting blockin
1.97 + /// flow according to Dinits' algorithm and augments the flow on if any.
1.98 + /// The blocking flow is computed in a physically constructed
1.99 + /// residual graph of type \c Mutablegraph.
1.100 template<typename MutableGraph> bool augmentOnBlockingFlow();
1.101
1.102 + /// The same as \c augmentOnBlockingFlow<MutableGraph> but the
1.103 + /// residual graph is not constructed physically.
1.104 bool augmentOnBlockingFlow2();
1.105
1.106 /// Returns the actual flow value.
1.107 @@ -126,23 +143,26 @@
1.108 return a;
1.109 }
1.110
1.111 - //should be used only between preflowPhase0 and preflowPhase1
1.112 + /// Should be used between preflowPhase0 and preflowPhase1.
1.113 + ///\todo We have to make some status variable which shows the actual state
1.114 + /// of the class. This enables us to determine which methods are valid
1.115 + /// for MinCut computation
1.116 template<typename _CutMap>
1.117 void actMinCut(_CutMap& M) {
1.118 NodeIt v;
1.119 - for(g->first(v); g->valid(v); g->next(v))
1.120 - if ( level[v] < n ) {
1.121 - M.set(v,false);
1.122 - } else {
1.123 - M.set(v,true);
1.124 + for(g->first(v); g->valid(v); g->next(v)) {
1.125 + if ( level[v] < n ) {
1.126 + M.set(v,false);
1.127 + } else {
1.128 + M.set(v,true);
1.129 + }
1.130 }
1.131 }
1.132
1.133
1.134 -
1.135 - /*
1.136 - Returns the minimum min cut, by a bfs from s in the residual graph.
1.137 - */
1.138 + /// The unique inclusionwise minimum cut is computed by
1.139 + /// processing a bfs from s in the residual graph.
1.140 + ///\pre flow have to be a max flow otherwise it will the whole node-set.
1.141 template<typename _CutMap>
1.142 void minMinCut(_CutMap& M) {
1.143
1.144 @@ -176,12 +196,9 @@
1.145 }
1.146
1.147
1.148 -
1.149 - /*
1.150 - Returns the maximum min cut, by a reverse bfs
1.151 - from t in the residual graph.
1.152 - */
1.153 -
1.154 + /// The unique inclusionwise maximum cut is computed by
1.155 + /// processing a reverse bfs from t in the residual graph.
1.156 + ///\pre flow have to be a max flow otherwise it will be empty.
1.157 template<typename _CutMap>
1.158 void maxMinCut(_CutMap& M) {
1.159
1.160 @@ -221,21 +238,20 @@
1.161 }
1.162
1.163
1.164 + /// A minimum cut is computed.
1.165 template<typename CutMap>
1.166 - void minCut(CutMap& M) {
1.167 - minMinCut(M);
1.168 - }
1.169 + void minCut(CutMap& M) { minMinCut(M); }
1.170
1.171 + ///
1.172 + void resetSource(Node _s) {s=_s;}
1.173 + ///
1.174 void resetTarget(Node _t) {t=_t;}
1.175 - void resetSource(Node _s) {s=_s;}
1.176
1.177 - void resetCap(const CapMap& _cap) {
1.178 - capacity=&_cap;
1.179 - }
1.180 + /// capacity-map is changed.
1.181 + void resetCap(const CapMap& _cap) { capacity=&_cap; }
1.182
1.183 - void resetFlow(FlowMap& _flow) {
1.184 - flow=&_flow;
1.185 - }
1.186 + /// flow-map is changed.
1.187 + void resetFlow(FlowMap& _flow) { flow=&_flow; }
1.188
1.189
1.190 private:
1.191 @@ -314,130 +330,130 @@
1.192 excess.set(w, exc);
1.193
1.194 return newlevel;
1.195 - }
1.196 + }
1.197
1.198
1.199 void preflowPreproc ( flowEnum fe, VecStack& active,
1.200 VecNode& level_list, NNMap& left, NNMap& right ) {
1.201
1.202 - std::queue<Node> bfs_queue;
1.203 + std::queue<Node> bfs_queue;
1.204
1.205 - switch ( fe ) {
1.206 - case ZERO_FLOW:
1.207 - {
1.208 - //Reverse_bfs from t, to find the starting level.
1.209 - level.set(t,0);
1.210 - bfs_queue.push(t);
1.211 + switch ( fe ) {
1.212 + case ZERO_FLOW:
1.213 + {
1.214 + //Reverse_bfs from t, to find the starting level.
1.215 + level.set(t,0);
1.216 + bfs_queue.push(t);
1.217
1.218 - while (!bfs_queue.empty()) {
1.219 + while (!bfs_queue.empty()) {
1.220
1.221 - Node v=bfs_queue.front();
1.222 - bfs_queue.pop();
1.223 - int l=level[v]+1;
1.224 + Node v=bfs_queue.front();
1.225 + bfs_queue.pop();
1.226 + int l=level[v]+1;
1.227
1.228 - InEdgeIt e;
1.229 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.230 - Node w=g->tail(e);
1.231 - if ( level[w] == n && w != s ) {
1.232 - bfs_queue.push(w);
1.233 - Node first=level_list[l];
1.234 - if ( g->valid(first) ) left.set(first,w);
1.235 - right.set(w,first);
1.236 - level_list[l]=w;
1.237 - level.set(w, l);
1.238 - }
1.239 - }
1.240 - }
1.241 + InEdgeIt e;
1.242 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.243 + Node w=g->tail(e);
1.244 + if ( level[w] == n && w != s ) {
1.245 + bfs_queue.push(w);
1.246 + Node first=level_list[l];
1.247 + if ( g->valid(first) ) left.set(first,w);
1.248 + right.set(w,first);
1.249 + level_list[l]=w;
1.250 + level.set(w, l);
1.251 + }
1.252 + }
1.253 + }
1.254
1.255 - //the starting flow
1.256 - OutEdgeIt e;
1.257 - for(g->first(e,s); g->valid(e); g->next(e))
1.258 - {
1.259 - Num c=(*capacity)[e];
1.260 - if ( c <= 0 ) continue;
1.261 - Node w=g->head(e);
1.262 - if ( level[w] < n ) {
1.263 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.264 - flow->set(e, c);
1.265 - excess.set(w, excess[w]+c);
1.266 - }
1.267 - }
1.268 - break;
1.269 - }
1.270 + //the starting flow
1.271 + OutEdgeIt e;
1.272 + for(g->first(e,s); g->valid(e); g->next(e))
1.273 + {
1.274 + Num c=(*capacity)[e];
1.275 + if ( c <= 0 ) continue;
1.276 + Node w=g->head(e);
1.277 + if ( level[w] < n ) {
1.278 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.279 + flow->set(e, c);
1.280 + excess.set(w, excess[w]+c);
1.281 + }
1.282 + }
1.283 + break;
1.284 + }
1.285
1.286 - case GEN_FLOW:
1.287 - case PREFLOW:
1.288 - {
1.289 - //Reverse_bfs from t in the residual graph,
1.290 - //to find the starting level.
1.291 - level.set(t,0);
1.292 - bfs_queue.push(t);
1.293 + case GEN_FLOW:
1.294 + case PREFLOW:
1.295 + {
1.296 + //Reverse_bfs from t in the residual graph,
1.297 + //to find the starting level.
1.298 + level.set(t,0);
1.299 + bfs_queue.push(t);
1.300
1.301 - while (!bfs_queue.empty()) {
1.302 + while (!bfs_queue.empty()) {
1.303
1.304 - Node v=bfs_queue.front();
1.305 - bfs_queue.pop();
1.306 - int l=level[v]+1;
1.307 + Node v=bfs_queue.front();
1.308 + bfs_queue.pop();
1.309 + int l=level[v]+1;
1.310
1.311 - InEdgeIt e;
1.312 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.313 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.314 - Node w=g->tail(e);
1.315 - if ( level[w] == n && w != s ) {
1.316 - bfs_queue.push(w);
1.317 - Node first=level_list[l];
1.318 - if ( g->valid(first) ) left.set(first,w);
1.319 - right.set(w,first);
1.320 - level_list[l]=w;
1.321 - level.set(w, l);
1.322 - }
1.323 - }
1.324 + InEdgeIt e;
1.325 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.326 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.327 + Node w=g->tail(e);
1.328 + if ( level[w] == n && w != s ) {
1.329 + bfs_queue.push(w);
1.330 + Node first=level_list[l];
1.331 + if ( g->valid(first) ) left.set(first,w);
1.332 + right.set(w,first);
1.333 + level_list[l]=w;
1.334 + level.set(w, l);
1.335 + }
1.336 + }
1.337
1.338 - OutEdgeIt f;
1.339 - for(g->first(f,v); g->valid(f); g->next(f)) {
1.340 - if ( 0 >= (*flow)[f] ) continue;
1.341 - Node w=g->head(f);
1.342 - if ( level[w] == n && w != s ) {
1.343 - bfs_queue.push(w);
1.344 - Node first=level_list[l];
1.345 - if ( g->valid(first) ) left.set(first,w);
1.346 - right.set(w,first);
1.347 - level_list[l]=w;
1.348 - level.set(w, l);
1.349 - }
1.350 - }
1.351 - }
1.352 + OutEdgeIt f;
1.353 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.354 + if ( 0 >= (*flow)[f] ) continue;
1.355 + Node w=g->head(f);
1.356 + if ( level[w] == n && w != s ) {
1.357 + bfs_queue.push(w);
1.358 + Node first=level_list[l];
1.359 + if ( g->valid(first) ) left.set(first,w);
1.360 + right.set(w,first);
1.361 + level_list[l]=w;
1.362 + level.set(w, l);
1.363 + }
1.364 + }
1.365 + }
1.366
1.367
1.368 - //the starting flow
1.369 - OutEdgeIt e;
1.370 - for(g->first(e,s); g->valid(e); g->next(e))
1.371 - {
1.372 - Num rem=(*capacity)[e]-(*flow)[e];
1.373 - if ( rem <= 0 ) continue;
1.374 - Node w=g->head(e);
1.375 - if ( level[w] < n ) {
1.376 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.377 - flow->set(e, (*capacity)[e]);
1.378 - excess.set(w, excess[w]+rem);
1.379 - }
1.380 - }
1.381 + //the starting flow
1.382 + OutEdgeIt e;
1.383 + for(g->first(e,s); g->valid(e); g->next(e))
1.384 + {
1.385 + Num rem=(*capacity)[e]-(*flow)[e];
1.386 + if ( rem <= 0 ) continue;
1.387 + Node w=g->head(e);
1.388 + if ( level[w] < n ) {
1.389 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.390 + flow->set(e, (*capacity)[e]);
1.391 + excess.set(w, excess[w]+rem);
1.392 + }
1.393 + }
1.394
1.395 - InEdgeIt f;
1.396 - for(g->first(f,s); g->valid(f); g->next(f))
1.397 - {
1.398 - if ( (*flow)[f] <= 0 ) continue;
1.399 - Node w=g->tail(f);
1.400 - if ( level[w] < n ) {
1.401 - if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.402 - excess.set(w, excess[w]+(*flow)[f]);
1.403 - flow->set(f, 0);
1.404 - }
1.405 - }
1.406 - break;
1.407 - } //case PREFLOW
1.408 - }
1.409 - } //preflowPreproc
1.410 + InEdgeIt f;
1.411 + for(g->first(f,s); g->valid(f); g->next(f))
1.412 + {
1.413 + if ( (*flow)[f] <= 0 ) continue;
1.414 + Node w=g->tail(f);
1.415 + if ( level[w] < n ) {
1.416 + if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w);
1.417 + excess.set(w, excess[w]+(*flow)[f]);
1.418 + flow->set(f, 0);
1.419 + }
1.420 + }
1.421 + break;
1.422 + } //case PREFLOW
1.423 + }
1.424 + } //preflowPreproc
1.425
1.426
1.427
1.428 @@ -521,11 +537,11 @@
1.429 dist.set(n, a);
1.430 }
1.431 int operator[](const typename MapGraphWrapper::Node& n)
1.432 - { return dist[n]; }
1.433 -// int get(const typename MapGraphWrapper::Node& n) const {
1.434 -// return dist[n]; }
1.435 -// bool get(const typename MapGraphWrapper::Edge& e) const {
1.436 -// return (dist.get(g->tail(e))<dist.get(g->head(e))); }
1.437 + { return dist[n]; }
1.438 + // int get(const typename MapGraphWrapper::Node& n) const {
1.439 + // return dist[n]; }
1.440 + // bool get(const typename MapGraphWrapper::Edge& e) const {
1.441 + // return (dist.get(g->tail(e))<dist.get(g->head(e))); }
1.442 bool operator[](const typename MapGraphWrapper::Edge& e) const {
1.443 return (dist[g->tail(e)]<dist[g->head(e)]);
1.444 }
1.445 @@ -538,108 +554,108 @@
1.446 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
1.447 {
1.448
1.449 - int heur0=(int)(H0*n); //time while running 'bound decrease'
1.450 - int heur1=(int)(H1*n); //time while running 'highest label'
1.451 - int heur=heur1; //starting time interval (#of relabels)
1.452 - int numrelabel=0;
1.453 + int heur0=(int)(H0*n); //time while running 'bound decrease'
1.454 + int heur1=(int)(H1*n); //time while running 'highest label'
1.455 + int heur=heur1; //starting time interval (#of relabels)
1.456 + int numrelabel=0;
1.457
1.458 - bool what_heur=1;
1.459 - //It is 0 in case 'bound decrease' and 1 in case 'highest label'
1.460 + bool what_heur=1;
1.461 + //It is 0 in case 'bound decrease' and 1 in case 'highest label'
1.462
1.463 - bool end=false;
1.464 - //Needed for 'bound decrease', true means no active nodes are above bound b.
1.465 + bool end=false;
1.466 + //Needed for 'bound decrease', true means no active nodes are above bound b.
1.467
1.468 - int k=n-2; //bound on the highest level under n containing a node
1.469 - int b=k; //bound on the highest level under n of an active node
1.470 + int k=n-2; //bound on the highest level under n containing a node
1.471 + int b=k; //bound on the highest level under n of an active node
1.472
1.473 - VecStack active(n);
1.474 + VecStack active(n);
1.475
1.476 - NNMap left(*g, INVALID);
1.477 - NNMap right(*g, INVALID);
1.478 - VecNode level_list(n,INVALID);
1.479 - //List of the nodes in level i<n, set to n.
1.480 + NNMap left(*g, INVALID);
1.481 + NNMap right(*g, INVALID);
1.482 + VecNode level_list(n,INVALID);
1.483 + //List of the nodes in level i<n, set to n.
1.484
1.485 - NodeIt v;
1.486 - for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.487 - //setting each node to level n
1.488 + NodeIt v;
1.489 + for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.490 + //setting each node to level n
1.491
1.492 - switch ( fe ) {
1.493 - case PREFLOW:
1.494 - {
1.495 - //counting the excess
1.496 - NodeIt v;
1.497 - for(g->first(v); g->valid(v); g->next(v)) {
1.498 - Num exc=0;
1.499 -
1.500 - InEdgeIt e;
1.501 - for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.502 - OutEdgeIt f;
1.503 - for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.504 -
1.505 - excess.set(v,exc);
1.506 -
1.507 - //putting the active nodes into the stack
1.508 - int lev=level[v];
1.509 - if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
1.510 - }
1.511 - break;
1.512 - }
1.513 - case GEN_FLOW:
1.514 - {
1.515 - //Counting the excess of t
1.516 + switch ( fe ) {
1.517 + case PREFLOW:
1.518 + {
1.519 + //counting the excess
1.520 + NodeIt v;
1.521 + for(g->first(v); g->valid(v); g->next(v)) {
1.522 Num exc=0;
1.523
1.524 InEdgeIt e;
1.525 - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.526 + for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.527 OutEdgeIt f;
1.528 - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.529 -
1.530 - excess.set(t,exc);
1.531 -
1.532 - break;
1.533 + for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.534 +
1.535 + excess.set(v,exc);
1.536 +
1.537 + //putting the active nodes into the stack
1.538 + int lev=level[v];
1.539 + if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
1.540 }
1.541 - default:
1.542 break;
1.543 }
1.544 + case GEN_FLOW:
1.545 + {
1.546 + //Counting the excess of t
1.547 + Num exc=0;
1.548 +
1.549 + InEdgeIt e;
1.550 + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.551 + OutEdgeIt f;
1.552 + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.553 +
1.554 + excess.set(t,exc);
1.555 +
1.556 + break;
1.557 + }
1.558 + default:
1.559 + break;
1.560 + }
1.561
1.562 - preflowPreproc( fe, active, level_list, left, right );
1.563 - //End of preprocessing
1.564 + preflowPreproc( fe, active, level_list, left, right );
1.565 + //End of preprocessing
1.566
1.567
1.568 - //Push/relabel on the highest level active nodes.
1.569 - while ( true ) {
1.570 - if ( b == 0 ) {
1.571 - if ( !what_heur && !end && k > 0 ) {
1.572 - b=k;
1.573 - end=true;
1.574 - } else break;
1.575 + //Push/relabel on the highest level active nodes.
1.576 + while ( true ) {
1.577 + if ( b == 0 ) {
1.578 + if ( !what_heur && !end && k > 0 ) {
1.579 + b=k;
1.580 + end=true;
1.581 + } else break;
1.582 + }
1.583 +
1.584 + if ( active[b].empty() ) --b;
1.585 + else {
1.586 + end=false;
1.587 + Node w=active[b].top();
1.588 + active[b].pop();
1.589 + int newlevel=push(w,active);
1.590 + if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
1.591 + left, right, b, k, what_heur);
1.592 +
1.593 + ++numrelabel;
1.594 + if ( numrelabel >= heur ) {
1.595 + numrelabel=0;
1.596 + if ( what_heur ) {
1.597 + what_heur=0;
1.598 + heur=heur0;
1.599 + end=false;
1.600 + } else {
1.601 + what_heur=1;
1.602 + heur=heur1;
1.603 + b=k;
1.604 + }
1.605 }
1.606 -
1.607 - if ( active[b].empty() ) --b;
1.608 - else {
1.609 - end=false;
1.610 - Node w=active[b].top();
1.611 - active[b].pop();
1.612 - int newlevel=push(w,active);
1.613 - if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
1.614 - left, right, b, k, what_heur);
1.615 -
1.616 - ++numrelabel;
1.617 - if ( numrelabel >= heur ) {
1.618 - numrelabel=0;
1.619 - if ( what_heur ) {
1.620 - what_heur=0;
1.621 - heur=heur0;
1.622 - end=false;
1.623 - } else {
1.624 - what_heur=1;
1.625 - heur=heur1;
1.626 - b=k;
1.627 - }
1.628 - }
1.629 - }
1.630 }
1.631 - }
1.632 + }
1.633 + }
1.634
1.635
1.636
1.637 @@ -647,112 +663,112 @@
1.638 void MaxFlow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
1.639 {
1.640
1.641 - int k=n-2; //bound on the highest level under n containing a node
1.642 - int b=k; //bound on the highest level under n of an active node
1.643 + int k=n-2; //bound on the highest level under n containing a node
1.644 + int b=k; //bound on the highest level under n of an active node
1.645
1.646 - VecStack active(n);
1.647 - level.set(s,0);
1.648 - std::queue<Node> bfs_queue;
1.649 - bfs_queue.push(s);
1.650 + VecStack active(n);
1.651 + level.set(s,0);
1.652 + std::queue<Node> bfs_queue;
1.653 + bfs_queue.push(s);
1.654
1.655 - while (!bfs_queue.empty()) {
1.656 + while (!bfs_queue.empty()) {
1.657
1.658 - Node v=bfs_queue.front();
1.659 - bfs_queue.pop();
1.660 - int l=level[v]+1;
1.661 + Node v=bfs_queue.front();
1.662 + bfs_queue.pop();
1.663 + int l=level[v]+1;
1.664
1.665 - InEdgeIt e;
1.666 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.667 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.668 - Node u=g->tail(e);
1.669 - if ( level[u] >= n ) {
1.670 - bfs_queue.push(u);
1.671 - level.set(u, l);
1.672 - if ( excess[u] > 0 ) active[l].push(u);
1.673 - }
1.674 - }
1.675 -
1.676 - OutEdgeIt f;
1.677 - for(g->first(f,v); g->valid(f); g->next(f)) {
1.678 - if ( 0 >= (*flow)[f] ) continue;
1.679 - Node u=g->head(f);
1.680 - if ( level[u] >= n ) {
1.681 - bfs_queue.push(u);
1.682 - level.set(u, l);
1.683 - if ( excess[u] > 0 ) active[l].push(u);
1.684 - }
1.685 + InEdgeIt e;
1.686 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.687 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.688 + Node u=g->tail(e);
1.689 + if ( level[u] >= n ) {
1.690 + bfs_queue.push(u);
1.691 + level.set(u, l);
1.692 + if ( excess[u] > 0 ) active[l].push(u);
1.693 }
1.694 }
1.695 - b=n-2;
1.696 +
1.697 + OutEdgeIt f;
1.698 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.699 + if ( 0 >= (*flow)[f] ) continue;
1.700 + Node u=g->head(f);
1.701 + if ( level[u] >= n ) {
1.702 + bfs_queue.push(u);
1.703 + level.set(u, l);
1.704 + if ( excess[u] > 0 ) active[l].push(u);
1.705 + }
1.706 + }
1.707 + }
1.708 + b=n-2;
1.709
1.710 - while ( true ) {
1.711 + while ( true ) {
1.712
1.713 - if ( b == 0 ) break;
1.714 + if ( b == 0 ) break;
1.715
1.716 - if ( active[b].empty() ) --b;
1.717 - else {
1.718 - Node w=active[b].top();
1.719 - active[b].pop();
1.720 - int newlevel=push(w,active);
1.721 + if ( active[b].empty() ) --b;
1.722 + else {
1.723 + Node w=active[b].top();
1.724 + active[b].pop();
1.725 + int newlevel=push(w,active);
1.726
1.727 - //relabel
1.728 - if ( excess[w] > 0 ) {
1.729 - level.set(w,++newlevel);
1.730 - active[newlevel].push(w);
1.731 - b=newlevel;
1.732 - }
1.733 - } // if stack[b] is nonempty
1.734 - } // while(true)
1.735 - }
1.736 + //relabel
1.737 + if ( excess[w] > 0 ) {
1.738 + level.set(w,++newlevel);
1.739 + active[newlevel].push(w);
1.740 + b=newlevel;
1.741 + }
1.742 + } // if stack[b] is nonempty
1.743 + } // while(true)
1.744 + }
1.745
1.746
1.747
1.748 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.749 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnShortestPath()
1.750 {
1.751 - ResGW res_graph(*g, *capacity, *flow);
1.752 - bool _augment=false;
1.753 + ResGW res_graph(*g, *capacity, *flow);
1.754 + bool _augment=false;
1.755
1.756 - //ReachedMap level(res_graph);
1.757 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.758 - BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.759 - bfs.pushAndSetReached(s);
1.760 + //ReachedMap level(res_graph);
1.761 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.762 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.763 + bfs.pushAndSetReached(s);
1.764
1.765 - typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
1.766 - pred.set(s, INVALID);
1.767 + typename ResGW::template NodeMap<ResGWEdge> pred(res_graph);
1.768 + pred.set(s, INVALID);
1.769
1.770 - typename ResGW::template NodeMap<Num> free(res_graph);
1.771 + typename ResGW::template NodeMap<Num> free(res_graph);
1.772
1.773 - //searching for augmenting path
1.774 - while ( !bfs.finished() ) {
1.775 - ResGWOutEdgeIt e=bfs;
1.776 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.777 - Node v=res_graph.tail(e);
1.778 - Node w=res_graph.head(e);
1.779 - pred.set(w, e);
1.780 - if (res_graph.valid(pred[v])) {
1.781 - free.set(w, std::min(free[v], res_graph.resCap(e)));
1.782 - } else {
1.783 - free.set(w, res_graph.resCap(e));
1.784 - }
1.785 - if (res_graph.head(e)==t) { _augment=true; break; }
1.786 + //searching for augmenting path
1.787 + while ( !bfs.finished() ) {
1.788 + ResGWOutEdgeIt e=bfs;
1.789 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.790 + Node v=res_graph.tail(e);
1.791 + Node w=res_graph.head(e);
1.792 + pred.set(w, e);
1.793 + if (res_graph.valid(pred[v])) {
1.794 + free.set(w, std::min(free[v], res_graph.resCap(e)));
1.795 + } else {
1.796 + free.set(w, res_graph.resCap(e));
1.797 }
1.798 + if (res_graph.head(e)==t) { _augment=true; break; }
1.799 + }
1.800
1.801 - ++bfs;
1.802 - } //end of searching augmenting path
1.803 + ++bfs;
1.804 + } //end of searching augmenting path
1.805
1.806 - if (_augment) {
1.807 - Node n=t;
1.808 - Num augment_value=free[t];
1.809 - while (res_graph.valid(pred[n])) {
1.810 - ResGWEdge e=pred[n];
1.811 - res_graph.augment(e, augment_value);
1.812 - n=res_graph.tail(e);
1.813 - }
1.814 + if (_augment) {
1.815 + Node n=t;
1.816 + Num augment_value=free[t];
1.817 + while (res_graph.valid(pred[n])) {
1.818 + ResGWEdge e=pred[n];
1.819 + res_graph.augment(e, augment_value);
1.820 + n=res_graph.tail(e);
1.821 }
1.822 + }
1.823
1.824 - return _augment;
1.825 - }
1.826 + return _augment;
1.827 + }
1.828
1.829
1.830
1.831 @@ -766,114 +782,114 @@
1.832 template<typename MutableGraph>
1.833 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow()
1.834 {
1.835 - typedef MutableGraph MG;
1.836 - bool _augment=false;
1.837 + typedef MutableGraph MG;
1.838 + bool _augment=false;
1.839
1.840 - ResGW res_graph(*g, *capacity, *flow);
1.841 + ResGW res_graph(*g, *capacity, *flow);
1.842
1.843 - //bfs for distances on the residual graph
1.844 - //ReachedMap level(res_graph);
1.845 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.846 - BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.847 - bfs.pushAndSetReached(s);
1.848 - typename ResGW::template NodeMap<int>
1.849 - dist(res_graph); //filled up with 0's
1.850 + //bfs for distances on the residual graph
1.851 + //ReachedMap level(res_graph);
1.852 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.853 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.854 + bfs.pushAndSetReached(s);
1.855 + typename ResGW::template NodeMap<int>
1.856 + dist(res_graph); //filled up with 0's
1.857
1.858 - //F will contain the physical copy of the residual graph
1.859 - //with the set of edges which are on shortest paths
1.860 - MG F;
1.861 - typename ResGW::template NodeMap<typename MG::Node>
1.862 - res_graph_to_F(res_graph);
1.863 - {
1.864 - typename ResGW::NodeIt n;
1.865 - for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
1.866 - res_graph_to_F.set(n, F.addNode());
1.867 - }
1.868 + //F will contain the physical copy of the residual graph
1.869 + //with the set of edges which are on shortest paths
1.870 + MG F;
1.871 + typename ResGW::template NodeMap<typename MG::Node>
1.872 + res_graph_to_F(res_graph);
1.873 + {
1.874 + typename ResGW::NodeIt n;
1.875 + for(res_graph.first(n); res_graph.valid(n); res_graph.next(n)) {
1.876 + res_graph_to_F.set(n, F.addNode());
1.877 }
1.878 + }
1.879
1.880 - typename MG::Node sF=res_graph_to_F[s];
1.881 - typename MG::Node tF=res_graph_to_F[t];
1.882 - typename MG::template EdgeMap<ResGWEdge> original_edge(F);
1.883 - typename MG::template EdgeMap<Num> residual_capacity(F);
1.884 + typename MG::Node sF=res_graph_to_F[s];
1.885 + typename MG::Node tF=res_graph_to_F[t];
1.886 + typename MG::template EdgeMap<ResGWEdge> original_edge(F);
1.887 + typename MG::template EdgeMap<Num> residual_capacity(F);
1.888
1.889 - while ( !bfs.finished() ) {
1.890 - ResGWOutEdgeIt e=bfs;
1.891 - if (res_graph.valid(e)) {
1.892 - if (bfs.isBNodeNewlyReached()) {
1.893 - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.894 + while ( !bfs.finished() ) {
1.895 + ResGWOutEdgeIt e=bfs;
1.896 + if (res_graph.valid(e)) {
1.897 + if (bfs.isBNodeNewlyReached()) {
1.898 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.899 + typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.900 + original_edge.update();
1.901 + original_edge.set(f, e);
1.902 + residual_capacity.update();
1.903 + residual_capacity.set(f, res_graph.resCap(e));
1.904 + } else {
1.905 + if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
1.906 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.907 original_edge.update();
1.908 original_edge.set(f, e);
1.909 residual_capacity.update();
1.910 residual_capacity.set(f, res_graph.resCap(e));
1.911 - } else {
1.912 - if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
1.913 - typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
1.914 - original_edge.update();
1.915 - original_edge.set(f, e);
1.916 - residual_capacity.update();
1.917 - residual_capacity.set(f, res_graph.resCap(e));
1.918 - }
1.919 }
1.920 }
1.921 - ++bfs;
1.922 - } //computing distances from s in the residual graph
1.923 + }
1.924 + ++bfs;
1.925 + } //computing distances from s in the residual graph
1.926
1.927 - bool __augment=true;
1.928 + bool __augment=true;
1.929
1.930 - while (__augment) {
1.931 - __augment=false;
1.932 - //computing blocking flow with dfs
1.933 - DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
1.934 - typename MG::template NodeMap<typename MG::Edge> pred(F);
1.935 - pred.set(sF, INVALID);
1.936 - //invalid iterators for sources
1.937 + while (__augment) {
1.938 + __augment=false;
1.939 + //computing blocking flow with dfs
1.940 + DfsIterator< MG, typename MG::template NodeMap<bool> > dfs(F);
1.941 + typename MG::template NodeMap<typename MG::Edge> pred(F);
1.942 + pred.set(sF, INVALID);
1.943 + //invalid iterators for sources
1.944
1.945 - typename MG::template NodeMap<Num> free(F);
1.946 + typename MG::template NodeMap<Num> free(F);
1.947
1.948 - dfs.pushAndSetReached(sF);
1.949 - while (!dfs.finished()) {
1.950 - ++dfs;
1.951 - if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.952 - if (dfs.isBNodeNewlyReached()) {
1.953 - typename MG::Node v=F.aNode(dfs);
1.954 - typename MG::Node w=F.bNode(dfs);
1.955 - pred.set(w, dfs);
1.956 - if (F.valid(pred[v])) {
1.957 - free.set(w, std::min(free[v], residual_capacity[dfs]));
1.958 - } else {
1.959 - free.set(w, residual_capacity[dfs]);
1.960 - }
1.961 - if (w==tF) {
1.962 - __augment=true;
1.963 - _augment=true;
1.964 - break;
1.965 - }
1.966 + dfs.pushAndSetReached(sF);
1.967 + while (!dfs.finished()) {
1.968 + ++dfs;
1.969 + if (F.valid(/*typename MG::OutEdgeIt*/(dfs))) {
1.970 + if (dfs.isBNodeNewlyReached()) {
1.971 + typename MG::Node v=F.aNode(dfs);
1.972 + typename MG::Node w=F.bNode(dfs);
1.973 + pred.set(w, dfs);
1.974 + if (F.valid(pred[v])) {
1.975 + free.set(w, std::min(free[v], residual_capacity[dfs]));
1.976 + } else {
1.977 + free.set(w, residual_capacity[dfs]);
1.978 + }
1.979 + if (w==tF) {
1.980 + __augment=true;
1.981 + _augment=true;
1.982 + break;
1.983 + }
1.984
1.985 - } else {
1.986 - F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.987 - }
1.988 - }
1.989 + } else {
1.990 + F.erase(/*typename MG::OutEdgeIt*/(dfs));
1.991 + }
1.992 + }
1.993 + }
1.994 +
1.995 + if (__augment) {
1.996 + typename MG::Node n=tF;
1.997 + Num augment_value=free[tF];
1.998 + while (F.valid(pred[n])) {
1.999 + typename MG::Edge e=pred[n];
1.1000 + res_graph.augment(original_edge[e], augment_value);
1.1001 + n=F.tail(e);
1.1002 + if (residual_capacity[e]==augment_value)
1.1003 + F.erase(e);
1.1004 + else
1.1005 + residual_capacity.set(e, residual_capacity[e]-augment_value);
1.1006 }
1.1007 -
1.1008 - if (__augment) {
1.1009 - typename MG::Node n=tF;
1.1010 - Num augment_value=free[tF];
1.1011 - while (F.valid(pred[n])) {
1.1012 - typename MG::Edge e=pred[n];
1.1013 - res_graph.augment(original_edge[e], augment_value);
1.1014 - n=F.tail(e);
1.1015 - if (residual_capacity[e]==augment_value)
1.1016 - F.erase(e);
1.1017 - else
1.1018 - residual_capacity.set(e, residual_capacity[e]-augment_value);
1.1019 - }
1.1020 - }
1.1021 + }
1.1022
1.1023 - }
1.1024 + }
1.1025
1.1026 - return _augment;
1.1027 - }
1.1028 + return _augment;
1.1029 + }
1.1030
1.1031
1.1032
1.1033 @@ -883,75 +899,75 @@
1.1034 template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.1035 bool MaxFlow<Graph, Num, CapMap, FlowMap>::augmentOnBlockingFlow2()
1.1036 {
1.1037 - bool _augment=false;
1.1038 + bool _augment=false;
1.1039
1.1040 - ResGW res_graph(*g, *capacity, *flow);
1.1041 + ResGW res_graph(*g, *capacity, *flow);
1.1042
1.1043 - //ReachedMap level(res_graph);
1.1044 - FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.1045 - BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.1046 + //ReachedMap level(res_graph);
1.1047 + FOR_EACH_LOC(typename Graph::NodeIt, e, *g) level.set(e, 0);
1.1048 + BfsIterator<ResGW, ReachedMap> bfs(res_graph, level);
1.1049
1.1050 - bfs.pushAndSetReached(s);
1.1051 - DistanceMap<ResGW> dist(res_graph);
1.1052 - while ( !bfs.finished() ) {
1.1053 - ResGWOutEdgeIt e=bfs;
1.1054 - if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.1055 - dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.1056 - }
1.1057 - ++bfs;
1.1058 - } //computing distances from s in the residual graph
1.1059 + bfs.pushAndSetReached(s);
1.1060 + DistanceMap<ResGW> dist(res_graph);
1.1061 + while ( !bfs.finished() ) {
1.1062 + ResGWOutEdgeIt e=bfs;
1.1063 + if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
1.1064 + dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
1.1065 + }
1.1066 + ++bfs;
1.1067 + } //computing distances from s in the residual graph
1.1068
1.1069 //Subgraph containing the edges on some shortest paths
1.1070 - ConstMap<typename ResGW::Node, bool> true_map(true);
1.1071 - typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
1.1072 - DistanceMap<ResGW> > FilterResGW;
1.1073 - FilterResGW filter_res_graph(res_graph, true_map, dist);
1.1074 + ConstMap<typename ResGW::Node, bool> true_map(true);
1.1075 + typedef SubGraphWrapper<ResGW, ConstMap<typename ResGW::Node, bool>,
1.1076 + DistanceMap<ResGW> > FilterResGW;
1.1077 + FilterResGW filter_res_graph(res_graph, true_map, dist);
1.1078
1.1079 - //Subgraph, which is able to delete edges which are already
1.1080 - //met by the dfs
1.1081 - typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
1.1082 - first_out_edges(filter_res_graph);
1.1083 - typename FilterResGW::NodeIt v;
1.1084 - for(filter_res_graph.first(v); filter_res_graph.valid(v);
1.1085 - filter_res_graph.next(v))
1.1086 + //Subgraph, which is able to delete edges which are already
1.1087 + //met by the dfs
1.1088 + typename FilterResGW::template NodeMap<typename FilterResGW::OutEdgeIt>
1.1089 + first_out_edges(filter_res_graph);
1.1090 + typename FilterResGW::NodeIt v;
1.1091 + for(filter_res_graph.first(v); filter_res_graph.valid(v);
1.1092 + filter_res_graph.next(v))
1.1093 {
1.1094 typename FilterResGW::OutEdgeIt e;
1.1095 filter_res_graph.first(e, v);
1.1096 first_out_edges.set(v, e);
1.1097 }
1.1098 - typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
1.1099 - template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
1.1100 - ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
1.1101 + typedef ErasingFirstGraphWrapper<FilterResGW, typename FilterResGW::
1.1102 + template NodeMap<typename FilterResGW::OutEdgeIt> > ErasingResGW;
1.1103 + ErasingResGW erasing_res_graph(filter_res_graph, first_out_edges);
1.1104
1.1105 - bool __augment=true;
1.1106 + bool __augment=true;
1.1107
1.1108 - while (__augment) {
1.1109 + while (__augment) {
1.1110
1.1111 - __augment=false;
1.1112 - //computing blocking flow with dfs
1.1113 - DfsIterator< ErasingResGW,
1.1114 - typename ErasingResGW::template NodeMap<bool> >
1.1115 - dfs(erasing_res_graph);
1.1116 - typename ErasingResGW::
1.1117 - template NodeMap<typename ErasingResGW::OutEdgeIt>
1.1118 - pred(erasing_res_graph);
1.1119 - pred.set(s, INVALID);
1.1120 - //invalid iterators for sources
1.1121 + __augment=false;
1.1122 + //computing blocking flow with dfs
1.1123 + DfsIterator< ErasingResGW,
1.1124 + typename ErasingResGW::template NodeMap<bool> >
1.1125 + dfs(erasing_res_graph);
1.1126 + typename ErasingResGW::
1.1127 + template NodeMap<typename ErasingResGW::OutEdgeIt>
1.1128 + pred(erasing_res_graph);
1.1129 + pred.set(s, INVALID);
1.1130 + //invalid iterators for sources
1.1131
1.1132 - typename ErasingResGW::template NodeMap<Num>
1.1133 - free1(erasing_res_graph);
1.1134 + typename ErasingResGW::template NodeMap<Num>
1.1135 + free1(erasing_res_graph);
1.1136
1.1137 - dfs.pushAndSetReached(
1.1138 - typename ErasingResGW::Node(
1.1139 - typename FilterResGW::Node(
1.1140 - typename ResGW::Node(s)
1.1141 - )
1.1142 - )
1.1143 - );
1.1144 - while (!dfs.finished()) {
1.1145 - ++dfs;
1.1146 - if (erasing_res_graph.valid(
1.1147 - typename ErasingResGW::OutEdgeIt(dfs)))
1.1148 + dfs.pushAndSetReached(
1.1149 + typename ErasingResGW::Node(
1.1150 + typename FilterResGW::Node(
1.1151 + typename ResGW::Node(s)
1.1152 + )
1.1153 + )
1.1154 + );
1.1155 + while (!dfs.finished()) {
1.1156 + ++dfs;
1.1157 + if (erasing_res_graph.valid(
1.1158 + typename ErasingResGW::OutEdgeIt(dfs)))
1.1159 {
1.1160 if (dfs.isBNodeNewlyReached()) {
1.1161
1.1162 @@ -961,10 +977,10 @@
1.1163 pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
1.1164 if (erasing_res_graph.valid(pred[v])) {
1.1165 free1.set(w, std::min(free1[v], res_graph.resCap(
1.1166 - typename ErasingResGW::OutEdgeIt(dfs))));
1.1167 + typename ErasingResGW::OutEdgeIt(dfs))));
1.1168 } else {
1.1169 free1.set(w, res_graph.resCap(
1.1170 - typename ErasingResGW::OutEdgeIt(dfs)));
1.1171 + typename ErasingResGW::OutEdgeIt(dfs)));
1.1172 }
1.1173
1.1174 if (w==t) {
1.1175 @@ -976,33 +992,33 @@
1.1176 erasing_res_graph.erase(dfs);
1.1177 }
1.1178 }
1.1179 - }
1.1180 + }
1.1181
1.1182 - if (__augment) {
1.1183 - typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
1.1184 -// typename ResGW::NodeMap<Num> a(res_graph);
1.1185 -// typename ResGW::Node b;
1.1186 -// Num j=a[b];
1.1187 -// typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
1.1188 -// typename FilterResGW::Node b1;
1.1189 -// Num j1=a1[b1];
1.1190 -// typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
1.1191 -// typename ErasingResGW::Node b2;
1.1192 -// Num j2=a2[b2];
1.1193 - Num augment_value=free1[n];
1.1194 - while (erasing_res_graph.valid(pred[n])) {
1.1195 - typename ErasingResGW::OutEdgeIt e=pred[n];
1.1196 - res_graph.augment(e, augment_value);
1.1197 - n=erasing_res_graph.tail(e);
1.1198 - if (res_graph.resCap(e)==0)
1.1199 - erasing_res_graph.erase(e);
1.1200 + if (__augment) {
1.1201 + typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
1.1202 + // typename ResGW::NodeMap<Num> a(res_graph);
1.1203 + // typename ResGW::Node b;
1.1204 + // Num j=a[b];
1.1205 + // typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
1.1206 + // typename FilterResGW::Node b1;
1.1207 + // Num j1=a1[b1];
1.1208 + // typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
1.1209 + // typename ErasingResGW::Node b2;
1.1210 + // Num j2=a2[b2];
1.1211 + Num augment_value=free1[n];
1.1212 + while (erasing_res_graph.valid(pred[n])) {
1.1213 + typename ErasingResGW::OutEdgeIt e=pred[n];
1.1214 + res_graph.augment(e, augment_value);
1.1215 + n=erasing_res_graph.tail(e);
1.1216 + if (res_graph.resCap(e)==0)
1.1217 + erasing_res_graph.erase(e);
1.1218 }
1.1219 }
1.1220
1.1221 - } //while (__augment)
1.1222 + } //while (__augment)
1.1223
1.1224 - return _augment;
1.1225 - }
1.1226 + return _augment;
1.1227 + }
1.1228
1.1229
1.1230