1.1 --- a/lemon/preflow.h	Tue Dec 12 13:35:52 2006 +0000
     1.2 +++ b/lemon/preflow.h	Mon Dec 18 10:12:07 2006 +0000
     1.3 @@ -274,8 +274,10 @@
     1.4  	  Node w=first[b];
     1.5  	  first[b]=next[w];
     1.6  	  int newlevel=push(w, next, first);
     1.7 -	  if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, 
     1.8 -				       left, right, b, k, what_heur);
     1.9 +	  if ( excess[w] != 0 ) {
    1.10 +            relabel(w, newlevel, first, next, level_list, 
    1.11 +                    left, right, b, k, what_heur);
    1.12 +          }
    1.13  
    1.14  	  ++numrelabel;
    1.15  	  if ( numrelabel >= heur ) {
    1.16 @@ -316,6 +318,10 @@
    1.17      ///minimum cut, while the methods \ref minMinCut and \ref
    1.18      ///maxMinCut return the inclusionwise minimum and maximum cuts of
    1.19      ///minimum value, resp.  \pre \ref phase1 must be called before.
    1.20 +    ///
    1.21 +    /// \todo The inexact computation can cause positive excess on a set of 
    1.22 +    /// unpushable nodes. We may have to watch the empty level in this case 
    1.23 +    /// due to avoid the terrible long running time.
    1.24      void phase2()
    1.25      {
    1.26  
    1.27 @@ -336,12 +342,12 @@
    1.28  	int l=level[v]+1;
    1.29  
    1.30  	for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
    1.31 -	  if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
    1.32 +	  if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
    1.33  	  Node u=_g->source(e);
    1.34  	  if ( level[u] >= _node_num ) {
    1.35  	    bfs_queue.push(u);
    1.36  	    level.set(u, l);
    1.37 -	    if ( _surely.positive(excess[u]) ) {
    1.38 +	    if ( excess[u] != 0 ) {
    1.39  	      next.set(u,first[l]);
    1.40  	      first[l]=u;
    1.41  	    }
    1.42 @@ -354,7 +360,7 @@
    1.43  	  if ( level[u] >= _node_num ) {
    1.44  	    bfs_queue.push(u);
    1.45  	    level.set(u, l);
    1.46 -	    if ( _surely.positive(excess[u]) ) {
    1.47 +	    if ( excess[u] != 0 ) {
    1.48  	      next.set(u,first[l]);
    1.49  	      first[l]=u;
    1.50  	    }
    1.51 @@ -372,8 +378,12 @@
    1.52  	  first[b]=next[w];
    1.53  	  int newlevel=push(w,next, first);
    1.54  	  
    1.55 +          if ( newlevel == _node_num) {
    1.56 +            excess.set(w, 0);
    1.57 +	    level.set(w,_node_num);
    1.58 +          }
    1.59  	  //relabel
    1.60 -	  if ( _surely.positive(excess[w]) ) {
    1.61 +	  if ( excess[w] != 0 ) {
    1.62  	    level.set(w,++newlevel);
    1.63  	    next.set(w,first[newlevel]);
    1.64  	    first[newlevel]=w;
    1.65 @@ -443,7 +453,7 @@
    1.66  	
    1.67  	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    1.68  	  Node v=_g->target(e);
    1.69 -	  if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
    1.70 +	  if (!M[v] && _surely.positive((*_capacity)[e] -(*_flow)[e]) ) {
    1.71  	    queue.push(v);
    1.72  	    M.set(v, true);
    1.73  	  }
    1.74 @@ -481,7 +491,7 @@
    1.75  
    1.76  	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    1.77  	  Node v=_g->source(e);
    1.78 -	  if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
    1.79 +	  if (M[v] && _surely.positive((*_capacity)[e] - (*_flow)[e]) ) {
    1.80  	    queue.push(v);
    1.81  	    M.set(v, false);
    1.82  	  }
    1.83 @@ -576,12 +586,12 @@
    1.84        int newlevel=_node_num;       //bound on the next level of w
    1.85  
    1.86        for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    1.87 -	if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
    1.88 +	if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
    1.89  	Node v=_g->target(e);
    1.90  	
    1.91  	if( lev > level[v] ) { //Push is allowed now
    1.92  	  
    1.93 -	  if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
    1.94 +	  if ( excess[v] == 0 && v!=_target && v!=_source ) {
    1.95  	    next.set(v,first[level[v]]);
    1.96  	    first[level[v]]=v;
    1.97  	  }
    1.98 @@ -605,7 +615,7 @@
    1.99  	} else if ( newlevel > level[v] ) newlevel = level[v];
   1.100        } //for out edges wv
   1.101  
   1.102 -      if ( _surely.positive(exc) ) {
   1.103 +      if ( exc != 0 ) {
   1.104  	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
   1.105  	  
   1.106  	  if ( !_surely.positive((*_flow)[e]) ) continue;
   1.107 @@ -613,7 +623,7 @@
   1.108  	  
   1.109  	  if( lev > level[v] ) { //Push is allowed now
   1.110  
   1.111 -	    if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
   1.112 +	    if ( excess[v] == 0 && v!=_target && v!=_source ) {
   1.113  	      next.set(v,first[level[v]]);
   1.114  	      first[level[v]]=v;
   1.115  	    }
   1.116 @@ -663,7 +673,7 @@
   1.117  	  int l=level[v]+1;
   1.118  	  
   1.119  	  for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
   1.120 -	    if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
   1.121 +	    if ( !_surely.positive((*_capacity)[e] - (*_flow)[e] )) continue;
   1.122  	    Node w=_g->source(e);
   1.123  	    if ( level[w] == _node_num && w != _source ) {
   1.124  	      bfs_queue.push(w);
   1.125 @@ -726,7 +736,7 @@
   1.126  	  if ( !_surely.positive(c) ) continue;
   1.127  	  Node w=_g->target(e);
   1.128  	  if ( level[w] < _node_num ) {
   1.129 -	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
   1.130 +	    if ( excess[w] == 0 && w!=_target ) { //putting into the stack
   1.131  	      next.set(w,first[level[w]]);
   1.132  	      first[level[w]]=w;
   1.133  	    }
   1.134 @@ -742,7 +752,10 @@
   1.135  	  Num exc=0;
   1.136  	  for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e];
   1.137  	  for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e];
   1.138 -	  excess.set(_target,exc);
   1.139 +          if (!_surely.positive(exc)) {
   1.140 +            exc = 0;
   1.141 +          }
   1.142 +          excess.set(_target,exc);
   1.143  	}
   1.144  
   1.145  	//the starting flow
   1.146 @@ -751,7 +764,7 @@
   1.147  	  if ( !_surely.positive(rem) ) continue;
   1.148  	  Node w=_g->target(e);
   1.149  	  if ( level[w] < _node_num ) {
   1.150 -	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
   1.151 +	    if ( excess[w] == 0 && w!=_target ) { //putting into the stack
   1.152  	      next.set(w,first[level[w]]);
   1.153  	      first[level[w]]=w;
   1.154  	    }   
   1.155 @@ -764,7 +777,7 @@
   1.156  	  if ( !_surely.positive((*_flow)[e]) ) continue;
   1.157  	  Node w=_g->source(e);
   1.158  	  if ( level[w] < _node_num ) {
   1.159 -	    if ( !_surely.positive(excess[w]) && w!=_target ) {
   1.160 +	    if ( excess[w] == 0 && w!=_target ) {
   1.161  	      next.set(w,first[level[w]]);
   1.162  	      first[level[w]]=w;
   1.163  	    }  
   1.164 @@ -794,11 +807,14 @@
   1.165  	  Num exc=0;
   1.166  	  for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e];
   1.167  	  for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e];
   1.168 +          if (!_surely.positive(exc)) {
   1.169 +            exc = 0;
   1.170 +          }
   1.171  	  excess.set(w,exc);
   1.172  	  
   1.173  	  //putting the active nodes into the stack
   1.174  	  int lev=level[w];
   1.175 -	    if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
   1.176 +	    if ( exc != 0 && lev < _node_num && Node(w) != _target ) {
   1.177  	      next.set(w,first[lev]);
   1.178  	      first[lev]=w;
   1.179  	    }