1.1 --- a/src/hugo/max_flow.h Thu Jul 29 17:23:55 2004 +0000
1.2 +++ b/src/hugo/max_flow.h Fri Jul 30 10:24:05 2004 +0000
1.3 @@ -1,17 +1,15 @@
1.4 // -*- C++ -*-
1.5 -#ifndef HUGO_MAX_FLOW_NO_STACK_H
1.6 -#define HUGO_MAX_FLOW_NO_STACK_H
1.7 +#ifndef HUGO_MAX_FLOW_H
1.8 +#define HUGO_MAX_FLOW_H
1.9
1.10 #include <vector>
1.11 #include <queue>
1.12 -//#include <stack>
1.13
1.14 #include <hugo/graph_wrapper.h>
1.15 #include <hugo/invalid.h>
1.16 #include <hugo/maps.h>
1.17
1.18 /// \file
1.19 -/// \brief The same as max_flow.h, but without using stl stack for the active nodes. Only for test.
1.20 /// \ingroup galgs
1.21
1.22 namespace hugo {
1.23 @@ -51,7 +49,6 @@
1.24 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.25 typedef typename Graph::InEdgeIt InEdgeIt;
1.26
1.27 - // typedef typename std::vector<std::stack<Node> > VecStack;
1.28 typedef typename std::vector<Node> VecFirst;
1.29 typedef typename Graph::template NodeMap<Node> NNMap;
1.30 typedef typename std::vector<Node> VecNode;
1.31 @@ -66,7 +63,6 @@
1.32 //typedef ExpResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
1.33 typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.34 typedef typename ResGW::Edge ResGWEdge;
1.35 - //typedef typename ResGW::template NodeMap<bool> ReachedMap;
1.36 typedef typename Graph::template NodeMap<int> ReachedMap;
1.37
1.38
1.39 @@ -110,7 +106,7 @@
1.40 AFTER_PRE_FLOW_PHASE_2
1.41 };
1.42
1.43 - /// Don not needle this flag only if necessary.
1.44 + /// Do not needle this flag only if necessary.
1.45 StatusEnum status;
1.46
1.47 // int number_of_augmentations;
1.48 @@ -188,7 +184,7 @@
1.49 ///The preflow algorithm consists of two phases, this method runs the
1.50 ///first phase. After the first phase the maximum flow value and a
1.51 ///minimum value cut can already be computed, though a maximum flow
1.52 - ///is net yet obtained. So after calling this method \ref flowValue
1.53 + ///is not yet obtained. So after calling this method \ref flowValue
1.54 ///and \ref actMinCut gives proper results.
1.55 ///\warning: \ref minCut, \ref minMinCut and \ref maxMinCut do not
1.56 ///give minimum value cuts unless calling \ref preflowPhase2.
1.57 @@ -223,65 +219,9 @@
1.58 VecNode level_list(n,INVALID);
1.59 //List of the nodes in level i<n, set to n.
1.60
1.61 - NodeIt v;
1.62 - for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.63 - //setting each node to level n
1.64 -
1.65 - if ( fe == NO_FLOW ) {
1.66 - EdgeIt e;
1.67 - for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
1.68 - }
1.69 -
1.70 - switch (fe) { //computing the excess
1.71 - case PRE_FLOW:
1.72 - {
1.73 - NodeIt v;
1.74 - for(g->first(v); g->valid(v); g->next(v)) {
1.75 - Num exc=0;
1.76 -
1.77 - InEdgeIt e;
1.78 - for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.79 - OutEdgeIt f;
1.80 - for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.81 -
1.82 - excess.set(v,exc);
1.83 -
1.84 - //putting the active nodes into the stack
1.85 - int lev=level[v];
1.86 - if ( exc > 0 && lev < n && v != t )
1.87 - {
1.88 - next.set(v,first[lev]);
1.89 - first[lev]=v;
1.90 - }
1.91 - }
1.92 - break;
1.93 - }
1.94 - case GEN_FLOW:
1.95 - {
1.96 - NodeIt v;
1.97 - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.98 -
1.99 - Num exc=0;
1.100 - InEdgeIt e;
1.101 - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.102 - OutEdgeIt f;
1.103 - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.104 - excess.set(t,exc);
1.105 - break;
1.106 - }
1.107 - case ZERO_FLOW:
1.108 - case NO_FLOW:
1.109 - {
1.110 - NodeIt v;
1.111 - for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.112 - break;
1.113 - }
1.114 - }
1.115 -
1.116 preflowPreproc(fe, next, first, level_list, left, right);
1.117 //End of preprocessing
1.118
1.119 -
1.120 //Push/relabel on the highest level active nodes.
1.121 while ( true ) {
1.122 if ( b == 0 ) {
1.123 @@ -394,7 +334,7 @@
1.124 first[newlevel]=w;
1.125 b=newlevel;
1.126 }
1.127 - } // if stack[b] is nonempty
1.128 + }
1.129 } // while(true)
1.130
1.131 status=AFTER_PRE_FLOW_PHASE_2;
1.132 @@ -413,15 +353,7 @@
1.133 return a;
1.134 //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
1.135 }
1.136 - Num flowValue2() const {
1.137 - return excess[t];
1.138 -// Num a=0;
1.139 -// for(InEdgeIt e(*g,t);g->valid(e);g->next(e)) a+=(*flow)[e];
1.140 -// for(OutEdgeIt e(*g,t);g->valid(e);g->next(e)) a-=(*flow)[e];
1.141 -// return a;
1.142 -// //marci figyu: excess[t] epp ezt adja preflow 1. fazisa utan
1.143 -
1.144 - }
1.145 +
1.146
1.147 ///Returns a minimum value cut after calling \ref preflowPhase1.
1.148
1.149 @@ -652,13 +584,51 @@
1.150 }
1.151
1.152
1.153 +
1.154 void preflowPreproc(FlowEnum fe, NNMap& next, VecFirst& first,
1.155 VecNode& level_list, NNMap& left, NNMap& right)
1.156 {
1.157 + switch (fe) { //setting excess
1.158 + case NO_FLOW:
1.159 + {
1.160 + EdgeIt e;
1.161 + for(g->first(e); g->valid(e); g->next(e)) flow->set(e,0);
1.162 +
1.163 + NodeIt v;
1.164 + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.165 + break;
1.166 + }
1.167 + case ZERO_FLOW:
1.168 + {
1.169 + NodeIt v;
1.170 + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.171 + break;
1.172 + }
1.173 + case GEN_FLOW:
1.174 + {
1.175 + NodeIt v;
1.176 + for(g->first(v); g->valid(v); g->next(v)) excess.set(v,0);
1.177 +
1.178 + Num exc=0;
1.179 + InEdgeIt e;
1.180 + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.181 + OutEdgeIt f;
1.182 + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.183 + excess.set(t,exc);
1.184 + break;
1.185 + }
1.186 + default: break;
1.187 + }
1.188 +
1.189 + NodeIt v;
1.190 + for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.191 + //setting each node to level n
1.192 +
1.193 std::queue<Node> bfs_queue;
1.194
1.195 +
1.196 switch (fe) {
1.197 - case NO_FLOW: //flow is already set to const zero in this case
1.198 + case NO_FLOW: //flow is already set to const zero
1.199 case ZERO_FLOW:
1.200 {
1.201 //Reverse_bfs from t, to find the starting level.
1.202 @@ -693,8 +663,8 @@
1.203 if ( c <= 0 ) continue;
1.204 Node w=g->head(e);
1.205 if ( level[w] < n ) {
1.206 - if ( excess[w] <= 0 && w!=t )
1.207 - {
1.208 + if ( excess[w] <= 0 && w!=t ) //putting into the stack
1.209 + {
1.210 next.set(w,first[level[w]]);
1.211 first[level[w]]=w;
1.212 }
1.213 @@ -706,6 +676,83 @@
1.214 }
1.215
1.216 case GEN_FLOW:
1.217 + {
1.218 + //Reverse_bfs from t in the residual graph,
1.219 + //to find the starting level.
1.220 + level.set(t,0);
1.221 + bfs_queue.push(t);
1.222 +
1.223 + while (!bfs_queue.empty()) {
1.224 +
1.225 + Node v=bfs_queue.front();
1.226 + bfs_queue.pop();
1.227 + int l=level[v]+1;
1.228 +
1.229 + InEdgeIt e;
1.230 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.231 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.232 + Node w=g->tail(e);
1.233 + if ( level[w] == n && w != s ) {
1.234 + bfs_queue.push(w);
1.235 + Node z=level_list[l];
1.236 + if ( g->valid(z) ) left.set(z,w);
1.237 + right.set(w,z);
1.238 + level_list[l]=w;
1.239 + level.set(w, l);
1.240 + }
1.241 + }
1.242 +
1.243 + OutEdgeIt f;
1.244 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.245 + if ( 0 >= (*flow)[f] ) continue;
1.246 + Node w=g->head(f);
1.247 + if ( level[w] == n && w != s ) {
1.248 + bfs_queue.push(w);
1.249 + Node z=level_list[l];
1.250 + if ( g->valid(z) ) left.set(z,w);
1.251 + right.set(w,z);
1.252 + level_list[l]=w;
1.253 + level.set(w, l);
1.254 + }
1.255 + }
1.256 + }
1.257 +
1.258 + //the starting flow
1.259 + OutEdgeIt e;
1.260 + for(g->first(e,s); g->valid(e); g->next(e))
1.261 + {
1.262 + Num rem=(*capacity)[e]-(*flow)[e];
1.263 + if ( rem <= 0 ) continue;
1.264 + Node w=g->head(e);
1.265 + if ( level[w] < n ) {
1.266 + if ( excess[w] <= 0 && w!=t ) //putting into the stack
1.267 + {
1.268 + next.set(w,first[level[w]]);
1.269 + first[level[w]]=w;
1.270 + }
1.271 + flow->set(e, (*capacity)[e]);
1.272 + excess.set(w, excess[w]+rem);
1.273 + }
1.274 + }
1.275 +
1.276 + InEdgeIt f;
1.277 + for(g->first(f,s); g->valid(f); g->next(f))
1.278 + {
1.279 + if ( (*flow)[f] <= 0 ) continue;
1.280 + Node w=g->tail(f);
1.281 + if ( level[w] < n ) {
1.282 + if ( excess[w] <= 0 && w!=t )
1.283 + {
1.284 + next.set(w,first[level[w]]);
1.285 + first[level[w]]=w;
1.286 + }
1.287 + excess.set(w, excess[w]+(*flow)[f]);
1.288 + flow->set(f, 0);
1.289 + }
1.290 + }
1.291 + break;
1.292 + } //case GEN_FLOW
1.293 +
1.294 case PRE_FLOW:
1.295 {
1.296 //Reverse_bfs from t in the residual graph,
1.297 @@ -757,11 +804,6 @@
1.298 if ( rem <= 0 ) continue;
1.299 Node w=g->head(e);
1.300 if ( level[w] < n ) {
1.301 - if ( excess[w] <= 0 && w!=t )
1.302 - {
1.303 - next.set(w,first[level[w]]);
1.304 - first[level[w]]=w;
1.305 - }
1.306 flow->set(e, (*capacity)[e]);
1.307 excess.set(w, excess[w]+rem);
1.308 }
1.309 @@ -773,22 +815,36 @@
1.310 if ( (*flow)[f] <= 0 ) continue;
1.311 Node w=g->tail(f);
1.312 if ( level[w] < n ) {
1.313 - if ( excess[w] <= 0 && w!=t )
1.314 - {
1.315 - next.set(w,first[level[w]]);
1.316 - first[level[w]]=w;
1.317 - }
1.318 excess.set(w, excess[w]+(*flow)[f]);
1.319 flow->set(f, 0);
1.320 }
1.321 }
1.322 +
1.323 + NodeIt w; //computing the excess
1.324 + for(g->first(w); g->valid(w); g->next(w)) {
1.325 + Num exc=0;
1.326 +
1.327 + InEdgeIt e;
1.328 + for(g->first(e,w); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.329 + OutEdgeIt f;
1.330 + for(g->first(f,w); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.331 +
1.332 + excess.set(w,exc);
1.333 +
1.334 + //putting the active nodes into the stack
1.335 + int lev=level[w];
1.336 + if ( exc > 0 && lev < n && w != t )
1.337 + {
1.338 + next.set(w,first[lev]);
1.339 + first[lev]=w;
1.340 + }
1.341 + }
1.342 break;
1.343 } //case PRE_FLOW
1.344 }
1.345 } //preflowPreproc
1.346
1.347
1.348 -
1.349 void relabel(Node w, int newlevel, NNMap& next, VecFirst& first,
1.350 VecNode& level_list, NNMap& left,
1.351 NNMap& right, int& b, int& k, bool what_heur )
1.352 @@ -852,6 +908,35 @@
1.353 }
1.354 }
1.355 } //relabel
1.356 +
1.357 + void printexcess() {////
1.358 + std::cout << "Excesses:" <<std::endl;
1.359 +
1.360 + NodeIt v;
1.361 + for(g->first(v); g->valid(v); g->next(v)) {
1.362 + std::cout << 1+(g->id(v)) << ":" << excess[v]<<std::endl;
1.363 + }
1.364 + }
1.365 +
1.366 + void printlevel() {////
1.367 + std::cout << "Levels:" <<std::endl;
1.368 +
1.369 + NodeIt v;
1.370 + for(g->first(v); g->valid(v); g->next(v)) {
1.371 + std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
1.372 + }
1.373 + }
1.374 +
1.375 +void printactive() {////
1.376 + std::cout << "Levels:" <<std::endl;
1.377 +
1.378 + NodeIt v;
1.379 + for(g->first(v); g->valid(v); g->next(v)) {
1.380 + std::cout << 1+(g->id(v)) << ":" << level[v]<<std::endl;
1.381 + }
1.382 + }
1.383 +
1.384 +
1.385 }; //class MaxFlow
1.386 } //namespace hugo
1.387