1.1 --- a/src/work/jacint/preflow_push_hl.h Tue Feb 17 09:34:55 2004 +0000
1.2 +++ b/src/work/jacint/preflow_push_hl.h Tue Feb 17 11:16:39 2004 +0000
1.3 @@ -25,11 +25,10 @@
1.4 #ifndef PREFLOW_PUSH_HL_H
1.5 #define PREFLOW_PUSH_HL_H
1.6
1.7 -#include <algorithm>
1.8 +//#include <algorithm>
1.9 #include <vector>
1.10 #include <stack>
1.11
1.12 -#include <list_graph.hh>
1.13 #include <reverse_bfs.h>
1.14
1.15 namespace marci {
1.16 @@ -67,8 +66,7 @@
1.17
1.18 typename Graph::NodeMap<int> level(G);
1.19 typename Graph::NodeMap<T> excess(G);
1.20 - std::cout <<"excess s:"<<excess.get(s); //delme
1.21 -
1.22 +
1.23 int n=G.nodeNum();
1.24 int b=n-2;
1.25 /*
1.26 @@ -76,6 +74,7 @@
1.27 In the beginning it is at most n-2.
1.28 */
1.29
1.30 + std::vector<int> numb(n); //The number of nodes on level i < n.
1.31 std::vector<std::stack<NodeIt> > stack(2*n-1);
1.32 //Stack of the active nodes in level i.
1.33
1.34 @@ -85,7 +84,9 @@
1.35 bfs.run();
1.36 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
1.37 {
1.38 - level.set(v, bfs.dist(v));
1.39 + int dist=bfs.dist(v);
1.40 + level.set(v, dist);
1.41 + ++numb[dist];
1.42 }
1.43
1.44 level.set(s,n);
1.45 @@ -96,9 +97,11 @@
1.46 {
1.47 if ( capacity.get(e) > 0 ) {
1.48 NodeIt w=G.head(e);
1.49 - if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w);
1.50 - flow.set(e, capacity.get(e));
1.51 - excess.set(w, excess.get(w)+capacity.get(e));
1.52 + if ( w!=s ) {
1.53 + if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w);
1.54 + flow.set(e, capacity.get(e));
1.55 + excess.set(w, excess.get(w)+capacity.get(e));
1.56 + }
1.57 }
1.58 }
1.59
1.60 @@ -112,10 +115,10 @@
1.61 Push/relabel on the highest level active nodes.
1.62 */
1.63
1.64 - /*While there exists active node.*/
1.65 + /*While there exists an active node.*/
1.66 while (b) {
1.67
1.68 - /*We decrease the bound if there is no active Node of level b.*/
1.69 + /*We decrease the bound if there is no active node of level b.*/
1.70 if (stack[b].empty()) {
1.71 --b;
1.72 } else {
1.73 @@ -132,111 +135,119 @@
1.74
1.75 NodeIt v=G.head(e); /*e is the edge wv.*/
1.76
1.77 - if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme
1.78 -
1.79 if( level.get(w) == level.get(v)+1 ) {
1.80 /*Push is allowed now*/
1.81
1.82 - if (capacity.get(e)-flow.get(e) > excess.get(w)) {
1.83 + if ( excess.get(v)==0 && v != s && v !=t ) stack[level.get(v)].push(v);
1.84 + /*v becomes active.*/
1.85 +
1.86 + if ( capacity.get(e)-flow.get(e) > excess.get(w) ) {
1.87 /*A nonsaturating push.*/
1.88
1.89 - if (excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
1.90 - /*v becomes active.*/
1.91 -
1.92 flow.set(e, flow.get(e)+excess.get(w));
1.93 excess.set(v, excess.get(v)+excess.get(w));
1.94 excess.set(w,0);
1.95 - //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
1.96 break;
1.97 +
1.98 } else {
1.99 /*A saturating push.*/
1.100
1.101 - if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.102 - /*v becomes active.*/
1.103 -
1.104 excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
1.105 excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
1.106 flow.set(e, capacity.get(e));
1.107 - //std::cout << w<<" " <<v<<" elore elen sat pump " << std::endl;
1.108 - if (excess.get(w)==0) break;
1.109 - /*If w is not active any more, then we go on to the next Node.*/
1.110 + if ( excess.get(w)==0 ) break;
1.111 + /*If w is not active any more, then we go on to the next node.*/
1.112
1.113 - //std::cout<<++i;
1.114 -
1.115 - } // if (capacity.get(e)-flow.get(e) > excess.get(w))
1.116 - } // if(level.get(w)==level.get(v)+1)
1.117 + }
1.118 + } else {
1.119 + newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
1.120 + }
1.121
1.122 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
1.123 -
1.124 - } //if (flow.get(e)<capacity.get(e))
1.125 + } //if the out edge wv is in the res graph
1.126
1.127 - } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
1.128 + } //for out edges wv
1.129
1.130
1.131 + if ( excess.get(w) > 0 ) {
1.132 +
1.133 + for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
1.134 + NodeIt v=G.tail(e); /*e is the edge vw.*/
1.135
1.136 - for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
1.137 - NodeIt v=G.tail(e);
1.138 - /*e is the Edge vw.*/
1.139 + if( flow.get(e) > 0 ) {
1.140 + /*e is an edge of the residual graph */
1.141
1.142 - if (excess.get(w)==0) break;
1.143 - /*It may happen, that w became inactive in the first for cycle.*/
1.144 - if(flow.get(e)>0) {
1.145 - /*e is an Edge of the residual graph */
1.146 -
1.147 - if(level.get(w)==level.get(v)+1) {
1.148 - /*Push is allowed now*/
1.149 + if( level.get(w)==level.get(v)+1 ) {
1.150 + /*Push is allowed now*/
1.151
1.152 - if (flow.get(e) > excess.get(w)) {
1.153 - /*A nonsaturating push.*/
1.154 -
1.155 - if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.156 + if ( excess.get(v)==0 && v != s && v !=t) stack[level.get(v)].push(v);
1.157 /*v becomes active.*/
1.158
1.159 - flow.set(e, flow.get(e)-excess.get(w));
1.160 - excess.set(v, excess.get(v)+excess.get(w));
1.161 - excess.set(w,0);
1.162 - //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
1.163 - break;
1.164 - } else {
1.165 - /*A saturating push.*/
1.166 + if ( flow.get(e) > excess.get(w) ) {
1.167 + /*A nonsaturating push.*/
1.168
1.169 - if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.170 - /*v becomes active.*/
1.171 -
1.172 - excess.set(v, excess.get(v)+flow.get(e));
1.173 - excess.set(w, excess.get(w)-flow.get(e));
1.174 - flow.set(e,0);
1.175 - //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
1.176 - if (excess.get(w)==0) { break;}
1.177 - } //if (flow.get(e) > excess.get(v))
1.178 - } //if(level.get(w)==level.get(v)+1)
1.179 -
1.180 - else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
1.181 -
1.182 + flow.set(e, flow.get(e)-excess.get(w));
1.183 + excess.set(v, excess.get(v)+excess.get(w));
1.184 + excess.set(w,0);
1.185 + break;
1.186 + } else {
1.187 + /*A saturating push.*/
1.188 +
1.189 + excess.set(v, excess.get(v)+flow.get(e));
1.190 + excess.set(w, excess.get(w)-flow.get(e));
1.191 + flow.set(e,0);
1.192 + if ( excess.get(w)==0 ) break;
1.193 + }
1.194 + } else {
1.195 + newlevel = newlevel < level.get(v) ? newlevel : level.get(v);
1.196 + }
1.197 +
1.198 + } //if in edge vw is in the res graph
1.199
1.200 - } //if (flow.get(e)>0)
1.201 + } //for in edges vw
1.202
1.203 - } //for
1.204 + } // if w still has excess after the out edge for cycle
1.205
1.206
1.207 - if (excess.get(w)>0) {
1.208 + /*
1.209 + Relabel
1.210 + */
1.211 +
1.212 + if ( excess.get(w) > 0 ) {
1.213 +
1.214 + int oldlevel=level.get(w);
1.215 level.set(w,++newlevel);
1.216 +
1.217 + if ( oldlevel < n ) {
1.218 + --numb[oldlevel];
1.219 +
1.220 + if ( !numb[oldlevel] ) { //If the level of w gets empty.
1.221 +
1.222 + for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
1.223 + if (level.get(v) > oldlevel && level.get(v) < n ) level.set(v,n);
1.224 + }
1.225 + for (int i=oldlevel+1 ; i!=n ; ++i) numb[i]=0;
1.226 + if ( newlevel < n ) newlevel=n;
1.227 + } else {
1.228 + if ( newlevel < n ) ++numb[newlevel];
1.229 + }
1.230 + } else {
1.231 + if ( newlevel < n ) ++numb[newlevel];
1.232 + }
1.233 +
1.234 stack[newlevel].push(w);
1.235 b=newlevel;
1.236 - //std::cout << "The new level of " << w << " is "<< newlevel <<std::endl;
1.237 +
1.238 }
1.239
1.240 + } // if stack[b] is nonempty
1.241
1.242 - } //else
1.243 -
1.244 - } //while(b)
1.245 + } // while(b)
1.246 +
1.247
1.248 value = excess.get(t);
1.249 /*Max flow value.*/
1.250
1.251
1.252 -
1.253 -
1.254 } //void run()
1.255
1.256
2.1 --- a/src/work/jacint/preflow_push_max_flow.h Tue Feb 17 09:34:55 2004 +0000
2.2 +++ b/src/work/jacint/preflow_push_max_flow.h Tue Feb 17 11:16:39 2004 +0000
2.3 @@ -26,7 +26,6 @@
2.4 #include <vector>
2.5 #include <stack>
2.6
2.7 -#include <list_graph.hh>
2.8 #include <reverse_bfs.h>
2.9
2.10