1.1 --- a/src/work/jacint/preflow_push_hl.h Tue Feb 17 08:59:49 2004 +0000
1.2 +++ b/src/work/jacint/preflow_push_hl.h Tue Feb 17 09:34:55 2004 +0000
1.3 @@ -65,12 +65,11 @@
1.4 */
1.5 void run() {
1.6
1.7 - int i=0;//DELME
1.8 -
1.9 typename Graph::NodeMap<int> level(G);
1.10 - typename Graph::NodeMap<T> excess(G);
1.11 + typename Graph::NodeMap<T> excess(G);
1.12 + std::cout <<"excess s:"<<excess.get(s); //delme
1.13
1.14 - int n=G.nodeNum();
1.15 + int n=G.nodeNum();
1.16 int b=n-2;
1.17 /*
1.18 b is a bound on the highest level of an active node.
1.19 @@ -89,8 +88,6 @@
1.20 level.set(v, bfs.dist(v));
1.21 }
1.22
1.23 - std::cout << "the level of t is " << bfs.dist(t);//delme
1.24 -
1.25 level.set(s,n);
1.26
1.27
1.28 @@ -99,13 +96,12 @@
1.29 {
1.30 if ( capacity.get(e) > 0 ) {
1.31 NodeIt w=G.head(e);
1.32 + if ( excess.get(w) == 0 && w!=t && w!=s ) stack[level.get(w)].push(w);
1.33 flow.set(e, capacity.get(e));
1.34 - stack[level.get(w)].push(w);
1.35 excess.set(w, excess.get(w)+capacity.get(e));
1.36 }
1.37 }
1.38
1.39 -
1.40 /*
1.41 End of preprocessing
1.42 */
1.43 @@ -113,10 +109,10 @@
1.44
1.45
1.46 /*
1.47 - Push/relabel on the highest level active Nodes.
1.48 + Push/relabel on the highest level active nodes.
1.49 */
1.50
1.51 - /*While there exists active Node.*/
1.52 + /*While there exists active node.*/
1.53 while (b) {
1.54
1.55 /*We decrease the bound if there is no active Node of level b.*/
1.56 @@ -124,29 +120,29 @@
1.57 --b;
1.58 } else {
1.59
1.60 - NodeIt w=stack[b].top(); //w is the highest label active Node.
1.61 - stack[b].pop(); //We delete w from the stack.
1.62 + NodeIt w=stack[b].top(); //w is a highest label active node.
1.63 + stack[b].pop();
1.64
1.65 - int newlevel=2*n-2; //In newlevel we maintain the next level of w.
1.66 + int newlevel=2*n-2; //In newlevel we bound the next level of w.
1.67
1.68 for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
1.69 - NodeIt v=G.head(e);
1.70 - /*e is the Edge wv.*/
1.71 +
1.72 + if ( flow.get(e) < capacity.get(e) ) {
1.73 + /*e is an edge of the residual graph */
1.74
1.75 - if (flow.get(e)<capacity.get(e)) {
1.76 - /*e is an Edge of the residual graph */
1.77 + NodeIt v=G.head(e); /*e is the edge wv.*/
1.78
1.79 - if(level.get(w)==level.get(v)+1) {
1.80 + if( level.get(w) > level.get(v)+1 ) { std::cout<<"HIBA1!";} //delme
1.81 +
1.82 + if( level.get(w) == level.get(v)+1 ) {
1.83 /*Push is allowed now*/
1.84
1.85 if (capacity.get(e)-flow.get(e) > excess.get(w)) {
1.86 /*A nonsaturating push.*/
1.87
1.88 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
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 - //std::cout<<++i;
1.93 -
1.94 flow.set(e, flow.get(e)+excess.get(w));
1.95 excess.set(v, excess.get(v)+excess.get(w));
1.96 excess.set(w,0);
1.97 @@ -155,7 +151,7 @@
1.98 } else {
1.99 /*A saturating push.*/
1.100
1.101 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.102 + if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.103 /*v becomes active.*/
1.104
1.105 excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
1.106 @@ -193,7 +189,7 @@
1.107 if (flow.get(e) > excess.get(w)) {
1.108 /*A nonsaturating push.*/
1.109
1.110 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.111 + if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.112 /*v becomes active.*/
1.113
1.114 flow.set(e, flow.get(e)-excess.get(w));
1.115 @@ -204,7 +200,7 @@
1.116 } else {
1.117 /*A saturating push.*/
1.118
1.119 - if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
1.120 + if (excess.get(v)==0 && v != s&& v !=t) stack[level.get(v)].push(v);
1.121 /*v becomes active.*/
1.122
1.123 excess.set(v, excess.get(v)+flow.get(e));