1.1 --- a/src/work/jacint/preflow.h Thu Apr 29 11:09:12 2004 +0000
1.2 +++ b/src/work/jacint/preflow.h Thu Apr 29 15:01:52 2004 +0000
1.3 @@ -43,6 +43,8 @@
1.4 #include <queue>
1.5 #include <stack>
1.6
1.7 +#include <graph_wrapper.h>
1.8 +
1.9 namespace hugo {
1.10
1.11 template <typename Graph, typename Num,
1.12 @@ -65,10 +67,18 @@
1.13 const CapMap* capacity;
1.14 FlowMap* flow;
1.15 int n; //the number of nodes of G
1.16 - typename Graph::template NodeMap<int> level;
1.17 + typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
1.18 + typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
1.19 + typedef typename ResGW::Edge ResGWEdge;
1.20 + //typedef typename ResGW::template NodeMap<bool> ReachedMap;
1.21 + typedef typename Graph::template NodeMap<int> ReachedMap;
1.22 + ReachedMap level;
1.23 + //level works as a bool map in augmenting path algorithms
1.24 + //and is used by bfs for storing reached information.
1.25 + //In preflow, it shows levels of nodes.
1.26 + //typename Graph::template NodeMap<int> level;
1.27 typename Graph::template NodeMap<Num> excess;
1.28
1.29 -
1.30 public:
1.31
1.32 enum flowEnum{
1.33 @@ -91,172 +101,15 @@
1.34 preflowPhase1();
1.35 }
1.36
1.37 - void preflowPhase0( flowEnum fe ) {
1.38 -
1.39 - int heur0=(int)(H0*n); //time while running 'bound decrease'
1.40 - int heur1=(int)(H1*n); //time while running 'highest label'
1.41 - int heur=heur1; //starting time interval (#of relabels)
1.42 - int numrelabel=0;
1.43 -
1.44 - bool what_heur=1;
1.45 - //It is 0 in case 'bound decrease' and 1 in case 'highest label'
1.46 + void preflowPhase0( flowEnum fe );
1.47
1.48 - bool end=false;
1.49 - //Needed for 'bound decrease', true means no active nodes are above bound b.
1.50 + void preflowPhase1();
1.51
1.52 - int k=n-2; //bound on the highest level under n containing a node
1.53 - int b=k; //bound on the highest level under n of an active node
1.54 -
1.55 - VecStack active(n);
1.56 -
1.57 - NNMap left(*g, INVALID);
1.58 - NNMap right(*g, INVALID);
1.59 - VecNode level_list(n,INVALID);
1.60 - //List of the nodes in level i<n, set to n.
1.61 + bool augmentOnShortestPath();
1.62
1.63 - NodeIt v;
1.64 - for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.65 - //setting each node to level n
1.66 -
1.67 - switch ( fe ) {
1.68 - case PREFLOW:
1.69 - {
1.70 - //counting the excess
1.71 - NodeIt v;
1.72 - for(g->first(v); g->valid(v); g->next(v)) {
1.73 - Num exc=0;
1.74 -
1.75 - InEdgeIt e;
1.76 - for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.77 - OutEdgeIt f;
1.78 - for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.79 -
1.80 - excess.set(v,exc);
1.81 -
1.82 - //putting the active nodes into the stack
1.83 - int lev=level[v];
1.84 - if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
1.85 - }
1.86 - break;
1.87 - }
1.88 - case GEN_FLOW:
1.89 - {
1.90 - //Counting the excess of t
1.91 - Num exc=0;
1.92 -
1.93 - InEdgeIt e;
1.94 - for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.95 - OutEdgeIt f;
1.96 - for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.97 -
1.98 - excess.set(t,exc);
1.99 -
1.100 - break;
1.101 - }
1.102 - default:
1.103 - break;
1.104 - }
1.105 -
1.106 - preflowPreproc( fe, active, level_list, left, right );
1.107 - //End of preprocessing
1.108 -
1.109 -
1.110 - //Push/relabel on the highest level active nodes.
1.111 - while ( true ) {
1.112 - if ( b == 0 ) {
1.113 - if ( !what_heur && !end && k > 0 ) {
1.114 - b=k;
1.115 - end=true;
1.116 - } else break;
1.117 - }
1.118 -
1.119 - if ( active[b].empty() ) --b;
1.120 - else {
1.121 - end=false;
1.122 - Node w=active[b].top();
1.123 - active[b].pop();
1.124 - int newlevel=push(w,active);
1.125 - if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
1.126 - left, right, b, k, what_heur);
1.127 -
1.128 - ++numrelabel;
1.129 - if ( numrelabel >= heur ) {
1.130 - numrelabel=0;
1.131 - if ( what_heur ) {
1.132 - what_heur=0;
1.133 - heur=heur0;
1.134 - end=false;
1.135 - } else {
1.136 - what_heur=1;
1.137 - heur=heur1;
1.138 - b=k;
1.139 - }
1.140 - }
1.141 - }
1.142 - }
1.143 - }
1.144 + template<typename MutableGraph> bool augmentOnBlockingFlow();
1.145
1.146 -
1.147 - void preflowPhase1() {
1.148 -
1.149 - int k=n-2; //bound on the highest level under n containing a node
1.150 - int b=k; //bound on the highest level under n of an active node
1.151 -
1.152 - VecStack active(n);
1.153 - level.set(s,0);
1.154 - std::queue<Node> bfs_queue;
1.155 - bfs_queue.push(s);
1.156 -
1.157 - while (!bfs_queue.empty()) {
1.158 -
1.159 - Node v=bfs_queue.front();
1.160 - bfs_queue.pop();
1.161 - int l=level[v]+1;
1.162 -
1.163 - InEdgeIt e;
1.164 - for(g->first(e,v); g->valid(e); g->next(e)) {
1.165 - if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.166 - Node u=g->tail(e);
1.167 - if ( level[u] >= n ) {
1.168 - bfs_queue.push(u);
1.169 - level.set(u, l);
1.170 - if ( excess[u] > 0 ) active[l].push(u);
1.171 - }
1.172 - }
1.173 -
1.174 - OutEdgeIt f;
1.175 - for(g->first(f,v); g->valid(f); g->next(f)) {
1.176 - if ( 0 >= (*flow)[f] ) continue;
1.177 - Node u=g->head(f);
1.178 - if ( level[u] >= n ) {
1.179 - bfs_queue.push(u);
1.180 - level.set(u, l);
1.181 - if ( excess[u] > 0 ) active[l].push(u);
1.182 - }
1.183 - }
1.184 - }
1.185 - b=n-2;
1.186 -
1.187 - while ( true ) {
1.188 -
1.189 - if ( b == 0 ) break;
1.190 -
1.191 - if ( active[b].empty() ) --b;
1.192 - else {
1.193 - Node w=active[b].top();
1.194 - active[b].pop();
1.195 - int newlevel=push(w,active);
1.196 -
1.197 - //relabel
1.198 - if ( excess[w] > 0 ) {
1.199 - level.set(w,++newlevel);
1.200 - active[newlevel].push(w);
1.201 - b=newlevel;
1.202 - }
1.203 - } // if stack[b] is nonempty
1.204 - } // while(true)
1.205 - }
1.206 -
1.207 + bool augmentOnBlockingFlow2();
1.208
1.209 //Returns the maximum value of a flow.
1.210 Num flowValue() {
1.211 @@ -645,8 +498,190 @@
1.212
1.213 } //relabel
1.214
1.215 + };
1.216
1.217 - };
1.218 +
1.219 + template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.220 + void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase0( flowEnum fe )
1.221 + {
1.222 +
1.223 + int heur0=(int)(H0*n); //time while running 'bound decrease'
1.224 + int heur1=(int)(H1*n); //time while running 'highest label'
1.225 + int heur=heur1; //starting time interval (#of relabels)
1.226 + int numrelabel=0;
1.227 +
1.228 + bool what_heur=1;
1.229 + //It is 0 in case 'bound decrease' and 1 in case 'highest label'
1.230 +
1.231 + bool end=false;
1.232 + //Needed for 'bound decrease', true means no active nodes are above bound b.
1.233 +
1.234 + int k=n-2; //bound on the highest level under n containing a node
1.235 + int b=k; //bound on the highest level under n of an active node
1.236 +
1.237 + VecStack active(n);
1.238 +
1.239 + NNMap left(*g, INVALID);
1.240 + NNMap right(*g, INVALID);
1.241 + VecNode level_list(n,INVALID);
1.242 + //List of the nodes in level i<n, set to n.
1.243 +
1.244 + NodeIt v;
1.245 + for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.246 + //setting each node to level n
1.247 +
1.248 + switch ( fe ) {
1.249 + case PREFLOW:
1.250 + {
1.251 + //counting the excess
1.252 + NodeIt v;
1.253 + for(g->first(v); g->valid(v); g->next(v)) {
1.254 + Num exc=0;
1.255 +
1.256 + InEdgeIt e;
1.257 + for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.258 + OutEdgeIt f;
1.259 + for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.260 +
1.261 + excess.set(v,exc);
1.262 +
1.263 + //putting the active nodes into the stack
1.264 + int lev=level[v];
1.265 + if ( exc > 0 && lev < n && v != t ) active[lev].push(v);
1.266 + }
1.267 + break;
1.268 + }
1.269 + case GEN_FLOW:
1.270 + {
1.271 + //Counting the excess of t
1.272 + Num exc=0;
1.273 +
1.274 + InEdgeIt e;
1.275 + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.276 + OutEdgeIt f;
1.277 + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.278 +
1.279 + excess.set(t,exc);
1.280 +
1.281 + break;
1.282 + }
1.283 + default:
1.284 + break;
1.285 + }
1.286 +
1.287 + preflowPreproc( fe, active, level_list, left, right );
1.288 + //End of preprocessing
1.289 +
1.290 +
1.291 + //Push/relabel on the highest level active nodes.
1.292 + while ( true ) {
1.293 + if ( b == 0 ) {
1.294 + if ( !what_heur && !end && k > 0 ) {
1.295 + b=k;
1.296 + end=true;
1.297 + } else break;
1.298 + }
1.299 +
1.300 + if ( active[b].empty() ) --b;
1.301 + else {
1.302 + end=false;
1.303 + Node w=active[b].top();
1.304 + active[b].pop();
1.305 + int newlevel=push(w,active);
1.306 + if ( excess[w] > 0 ) relabel(w, newlevel, active, level_list,
1.307 + left, right, b, k, what_heur);
1.308 +
1.309 + ++numrelabel;
1.310 + if ( numrelabel >= heur ) {
1.311 + numrelabel=0;
1.312 + if ( what_heur ) {
1.313 + what_heur=0;
1.314 + heur=heur0;
1.315 + end=false;
1.316 + } else {
1.317 + what_heur=1;
1.318 + heur=heur1;
1.319 + b=k;
1.320 + }
1.321 + }
1.322 + }
1.323 + }
1.324 + }
1.325 +
1.326 +
1.327 +
1.328 + template <typename Graph, typename Num, typename CapMap, typename FlowMap>
1.329 + void Preflow<Graph, Num, CapMap, FlowMap>::preflowPhase1()
1.330 + {
1.331 +
1.332 + int k=n-2; //bound on the highest level under n containing a node
1.333 + int b=k; //bound on the highest level under n of an active node
1.334 +
1.335 + VecStack active(n);
1.336 + level.set(s,0);
1.337 + std::queue<Node> bfs_queue;
1.338 + bfs_queue.push(s);
1.339 +
1.340 + while (!bfs_queue.empty()) {
1.341 +
1.342 + Node v=bfs_queue.front();
1.343 + bfs_queue.pop();
1.344 + int l=level[v]+1;
1.345 +
1.346 + InEdgeIt e;
1.347 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.348 + if ( (*capacity)[e] <= (*flow)[e] ) continue;
1.349 + Node u=g->tail(e);
1.350 + if ( level[u] >= n ) {
1.351 + bfs_queue.push(u);
1.352 + level.set(u, l);
1.353 + if ( excess[u] > 0 ) active[l].push(u);
1.354 + }
1.355 + }
1.356 +
1.357 + OutEdgeIt f;
1.358 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.359 + if ( 0 >= (*flow)[f] ) continue;
1.360 + Node u=g->head(f);
1.361 + if ( level[u] >= n ) {
1.362 + bfs_queue.push(u);
1.363 + level.set(u, l);
1.364 + if ( excess[u] > 0 ) active[l].push(u);
1.365 + }
1.366 + }
1.367 + }
1.368 + b=n-2;
1.369 +
1.370 + while ( true ) {
1.371 +
1.372 + if ( b == 0 ) break;
1.373 +
1.374 + if ( active[b].empty() ) --b;
1.375 + else {
1.376 + Node w=active[b].top();
1.377 + active[b].pop();
1.378 + int newlevel=push(w,active);
1.379 +
1.380 + //relabel
1.381 + if ( excess[w] > 0 ) {
1.382 + level.set(w,++newlevel);
1.383 + active[newlevel].push(w);
1.384 + b=newlevel;
1.385 + }
1.386 + } // if stack[b] is nonempty
1.387 + } // while(true)
1.388 + }
1.389 +
1.390 +
1.391 +
1.392 +
1.393 +
1.394 +
1.395 +
1.396 +
1.397 +
1.398 +
1.399 +
1.400
1.401 } //namespace hugo
1.402