1.1 --- a/src/work/jacint/preflow.h Thu Apr 29 09:08:14 2004 +0000
1.2 +++ b/src/work/jacint/preflow.h Thu Apr 29 10:16:46 2004 +0000
1.3 @@ -59,7 +59,7 @@
1.4 typedef typename Graph::template NodeMap<Node> NNMap;
1.5 typedef typename std::vector<Node> VecNode;
1.6
1.7 - const Graph& G;
1.8 + const Graph* g;
1.9 Node s;
1.10 Node t;
1.11 const CapMap* capacity;
1.12 @@ -79,7 +79,7 @@
1.13
1.14 Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
1.15 FlowMap& _flow) :
1.16 - G(_G), s(_s), t(_t), capacity(&_capacity),
1.17 + g(&_G), s(_s), t(_t), capacity(&_capacity),
1.18 flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0) {}
1.19
1.20 void run() {
1.21 @@ -109,13 +109,13 @@
1.22
1.23 VecStack active(n);
1.24
1.25 - NNMap left(G,INVALID);
1.26 - NNMap right(G,INVALID);
1.27 + NNMap left(*g, INVALID);
1.28 + NNMap right(*g, INVALID);
1.29 VecNode level_list(n,INVALID);
1.30 //List of the nodes in level i<n, set to n.
1.31
1.32 NodeIt v;
1.33 - for(G.first(v); G.valid(v); G.next(v)) level.set(v,n);
1.34 + for(g->first(v); g->valid(v); g->next(v)) level.set(v,n);
1.35 //setting each node to level n
1.36
1.37 switch ( fe ) {
1.38 @@ -123,13 +123,13 @@
1.39 {
1.40 //counting the excess
1.41 NodeIt v;
1.42 - for(G.first(v); G.valid(v); G.next(v)) {
1.43 + for(g->first(v); g->valid(v); g->next(v)) {
1.44 T exc=0;
1.45
1.46 InEdgeIt e;
1.47 - for(G.first(e,v); G.valid(e); G.next(e)) exc+=(*flow)[e];
1.48 + for(g->first(e,v); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.49 OutEdgeIt f;
1.50 - for(G.first(f,v); G.valid(f); G.next(f)) exc-=(*flow)[f];
1.51 + for(g->first(f,v); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.52
1.53 excess.set(v,exc);
1.54
1.55 @@ -145,9 +145,9 @@
1.56 T exc=0;
1.57
1.58 InEdgeIt e;
1.59 - for(G.first(e,t); G.valid(e); G.next(e)) exc+=(*flow)[e];
1.60 + for(g->first(e,t); g->valid(e); g->next(e)) exc+=(*flow)[e];
1.61 OutEdgeIt f;
1.62 - for(G.first(f,t); G.valid(f); G.next(f)) exc-=(*flow)[f];
1.63 + for(g->first(f,t); g->valid(f); g->next(f)) exc-=(*flow)[f];
1.64
1.65 excess.set(t,exc);
1.66
1.67 @@ -216,9 +216,9 @@
1.68 int l=level[v]+1;
1.69
1.70 InEdgeIt e;
1.71 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.72 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.73 if ( (*capacity)[e] == (*flow)[e] ) continue;
1.74 - Node u=G.tail(e);
1.75 + Node u=g->tail(e);
1.76 if ( level[u] >= n ) {
1.77 bfs_queue.push(u);
1.78 level.set(u, l);
1.79 @@ -227,9 +227,9 @@
1.80 }
1.81
1.82 OutEdgeIt f;
1.83 - for(G.first(f,v); G.valid(f); G.next(f)) {
1.84 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.85 if ( 0 == (*flow)[f] ) continue;
1.86 - Node u=G.head(f);
1.87 + Node u=g->head(f);
1.88 if ( level[u] >= n ) {
1.89 bfs_queue.push(u);
1.90 level.set(u, l);
1.91 @@ -269,9 +269,12 @@
1.92 template<typename _CutMap>
1.93 void actMinCut(_CutMap& M) {
1.94 NodeIt v;
1.95 - for(G.first(v); G.valid(v); G.next(v))
1.96 - if ( level[v] < n ) M.set(v,false);
1.97 - else M.set(v,true);
1.98 + for(g->first(v); g->valid(v); g->next(v))
1.99 + if ( level[v] < n ) {
1.100 + M.set(v,false);
1.101 + } else {
1.102 + M.set(v,true);
1.103 + }
1.104 }
1.105
1.106
1.107 @@ -292,8 +295,8 @@
1.108 queue.pop();
1.109
1.110 OutEdgeIt e;
1.111 - for(G.first(e,w) ; G.valid(e); G.next(e)) {
1.112 - Node v=G.head(e);
1.113 + for(g->first(e,w) ; g->valid(e); g->next(e)) {
1.114 + Node v=g->head(e);
1.115 if (!M[v] && (*flow)[e] < (*capacity)[e] ) {
1.116 queue.push(v);
1.117 M.set(v, true);
1.118 @@ -301,8 +304,8 @@
1.119 }
1.120
1.121 InEdgeIt f;
1.122 - for(G.first(f,w) ; G.valid(f); G.next(f)) {
1.123 - Node v=G.tail(f);
1.124 + for(g->first(f,w) ; g->valid(f); g->next(f)) {
1.125 + Node v=g->tail(f);
1.126 if (!M[v] && (*flow)[f] > 0 ) {
1.127 queue.push(v);
1.128 M.set(v, true);
1.129 @@ -322,7 +325,7 @@
1.130 void maxMinCut(_CutMap& M) {
1.131
1.132 NodeIt v;
1.133 - for(G.first(v) ; G.valid(v); G.next(v)) {
1.134 + for(g->first(v) ; g->valid(v); g->next(v)) {
1.135 M.set(v, true);
1.136 }
1.137
1.138 @@ -337,8 +340,8 @@
1.139
1.140
1.141 InEdgeIt e;
1.142 - for(G.first(e,w) ; G.valid(e); G.next(e)) {
1.143 - Node v=G.tail(e);
1.144 + for(g->first(e,w) ; g->valid(e); g->next(e)) {
1.145 + Node v=g->tail(e);
1.146 if (M[v] && (*flow)[e] < (*capacity)[e] ) {
1.147 queue.push(v);
1.148 M.set(v, false);
1.149 @@ -346,8 +349,8 @@
1.150 }
1.151
1.152 OutEdgeIt f;
1.153 - for(G.first(f,w) ; G.valid(f); G.next(f)) {
1.154 - Node v=G.head(f);
1.155 + for(g->first(f,w) ; g->valid(f); g->next(f)) {
1.156 + Node v=g->head(f);
1.157 if (M[v] && (*flow)[f] > 0 ) {
1.158 queue.push(v);
1.159 M.set(v, false);
1.160 @@ -385,10 +388,10 @@
1.161 int newlevel=n; //bound on the next level of w
1.162
1.163 OutEdgeIt e;
1.164 - for(G.first(e,w); G.valid(e); G.next(e)) {
1.165 + for(g->first(e,w); g->valid(e); g->next(e)) {
1.166
1.167 if ( (*flow)[e] == (*capacity)[e] ) continue;
1.168 - Node v=G.head(e);
1.169 + Node v=g->head(e);
1.170
1.171 if( lev > level[v] ) { //Push is allowed now
1.172
1.173 @@ -418,10 +421,10 @@
1.174
1.175 if ( exc > 0 ) {
1.176 InEdgeIt e;
1.177 - for(G.first(e,w); G.valid(e); G.next(e)) {
1.178 + for(g->first(e,w); g->valid(e); g->next(e)) {
1.179
1.180 if( (*flow)[e] == 0 ) continue;
1.181 - Node v=G.tail(e);
1.182 + Node v=g->tail(e);
1.183
1.184 if( lev > level[v] ) { //Push is allowed now
1.185
1.186 @@ -474,12 +477,12 @@
1.187 int l=level[v]+1;
1.188
1.189 InEdgeIt e;
1.190 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.191 - Node w=G.tail(e);
1.192 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.193 + Node w=g->tail(e);
1.194 if ( level[w] == n && w != s ) {
1.195 bfs_queue.push(w);
1.196 Node first=level_list[l];
1.197 - if ( G.valid(first) ) left.set(first,w);
1.198 + if ( g->valid(first) ) left.set(first,w);
1.199 right.set(w,first);
1.200 level_list[l]=w;
1.201 level.set(w, l);
1.202 @@ -489,11 +492,11 @@
1.203
1.204 //the starting flow
1.205 OutEdgeIt e;
1.206 - for(G.first(e,s); G.valid(e); G.next(e))
1.207 + for(g->first(e,s); g->valid(e); g->next(e))
1.208 {
1.209 T c=(*capacity)[e];
1.210 if ( c == 0 ) continue;
1.211 - Node w=G.head(e);
1.212 + Node w=g->head(e);
1.213 if ( level[w] < n ) {
1.214 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.215 flow->set(e, c);
1.216 @@ -518,13 +521,13 @@
1.217 int l=level[v]+1;
1.218
1.219 InEdgeIt e;
1.220 - for(G.first(e,v); G.valid(e); G.next(e)) {
1.221 + for(g->first(e,v); g->valid(e); g->next(e)) {
1.222 if ( (*capacity)[e] == (*flow)[e] ) continue;
1.223 - Node w=G.tail(e);
1.224 + Node w=g->tail(e);
1.225 if ( level[w] == n && w != s ) {
1.226 bfs_queue.push(w);
1.227 Node first=level_list[l];
1.228 - if ( G.valid(first) ) left.set(first,w);
1.229 + if ( g->valid(first) ) left.set(first,w);
1.230 right.set(w,first);
1.231 level_list[l]=w;
1.232 level.set(w, l);
1.233 @@ -532,13 +535,13 @@
1.234 }
1.235
1.236 OutEdgeIt f;
1.237 - for(G.first(f,v); G.valid(f); G.next(f)) {
1.238 + for(g->first(f,v); g->valid(f); g->next(f)) {
1.239 if ( 0 == (*flow)[f] ) continue;
1.240 - Node w=G.head(f);
1.241 + Node w=g->head(f);
1.242 if ( level[w] == n && w != s ) {
1.243 bfs_queue.push(w);
1.244 Node first=level_list[l];
1.245 - if ( G.valid(first) ) left.set(first,w);
1.246 + if ( g->valid(first) ) left.set(first,w);
1.247 right.set(w,first);
1.248 level_list[l]=w;
1.249 level.set(w, l);
1.250 @@ -549,11 +552,11 @@
1.251
1.252 //the starting flow
1.253 OutEdgeIt e;
1.254 - for(G.first(e,s); G.valid(e); G.next(e))
1.255 + for(g->first(e,s); g->valid(e); g->next(e))
1.256 {
1.257 T rem=(*capacity)[e]-(*flow)[e];
1.258 if ( rem == 0 ) continue;
1.259 - Node w=G.head(e);
1.260 + Node w=g->head(e);
1.261 if ( level[w] < n ) {
1.262 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.263 flow->set(e, (*capacity)[e]);
1.264 @@ -562,10 +565,10 @@
1.265 }
1.266
1.267 InEdgeIt f;
1.268 - for(G.first(f,s); G.valid(f); G.next(f))
1.269 + for(g->first(f,s); g->valid(f); g->next(f))
1.270 {
1.271 if ( (*flow)[f] == 0 ) continue;
1.272 - Node w=G.tail(f);
1.273 + Node w=g->tail(f);
1.274 if ( level[w] < n ) {
1.275 if ( excess[w] == 0 && w!=t ) active[level[w]].push(w);
1.276 excess.set(w, excess[w]+(*flow)[f]);
1.277 @@ -589,8 +592,8 @@
1.278 Node left_n=left[w];
1.279
1.280 //unlacing starts
1.281 - if ( G.valid(right_n) ) {
1.282 - if ( G.valid(left_n) ) {
1.283 + if ( g->valid(right_n) ) {
1.284 + if ( g->valid(left_n) ) {
1.285 right.set(left_n, right_n);
1.286 left.set(right_n, left_n);
1.287 } else {
1.288 @@ -598,7 +601,7 @@
1.289 left.set(right_n, INVALID);
1.290 }
1.291 } else {
1.292 - if ( G.valid(left_n) ) {
1.293 + if ( g->valid(left_n) ) {
1.294 right.set(left_n, INVALID);
1.295 } else {
1.296 level_list[lev]=INVALID;
1.297 @@ -606,12 +609,12 @@
1.298 }
1.299 //unlacing ends
1.300
1.301 - if ( !G.valid(level_list[lev]) ) {
1.302 + if ( !g->valid(level_list[lev]) ) {
1.303
1.304 //gapping starts
1.305 for (int i=lev; i!=k ; ) {
1.306 Node v=level_list[++i];
1.307 - while ( G.valid(v) ) {
1.308 + while ( g->valid(v) ) {
1.309 level.set(v,n);
1.310 v=right[v];
1.311 }
1.312 @@ -637,7 +640,7 @@
1.313 if ( what_heur ) b=newlevel;
1.314 if ( k < newlevel ) ++k; //now k=newlevel
1.315 Node first=level_list[newlevel];
1.316 - if ( G.valid(first) ) left.set(first,w);
1.317 + if ( g->valid(first) ) left.set(first,w);
1.318 right.set(w,first);
1.319 left.set(w,INVALID);
1.320 level_list[newlevel]=w;