# HG changeset patch
# User deba
# Date 1166436727 0
# Node ID 9dccb1abc721b4d364ebc472ad20ccc9cfe991d3
# Parent  3f4a04a9b7bf69e7902b23658645c3747359d934
Better handling of inexact computation.
We do not use tolerance for excess, just for edges

diff -r 3f4a04a9b7bf -r 9dccb1abc721 lemon/preflow.h
--- a/lemon/preflow.h	Tue Dec 12 13:35:52 2006 +0000
+++ b/lemon/preflow.h	Mon Dec 18 10:12:07 2006 +0000
@@ -274,8 +274,10 @@
 	  Node w=first[b];
 	  first[b]=next[w];
 	  int newlevel=push(w, next, first);
-	  if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, 
-				       left, right, b, k, what_heur);
+	  if ( excess[w] != 0 ) {
+            relabel(w, newlevel, first, next, level_list, 
+                    left, right, b, k, what_heur);
+          }
 
 	  ++numrelabel;
 	  if ( numrelabel >= heur ) {
@@ -316,6 +318,10 @@
     ///minimum cut, while the methods \ref minMinCut and \ref
     ///maxMinCut return the inclusionwise minimum and maximum cuts of
     ///minimum value, resp.  \pre \ref phase1 must be called before.
+    ///
+    /// \todo The inexact computation can cause positive excess on a set of 
+    /// unpushable nodes. We may have to watch the empty level in this case 
+    /// due to avoid the terrible long running time.
     void phase2()
     {
 
@@ -336,12 +342,12 @@
 	int l=level[v]+1;
 
 	for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
-	  if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
+	  if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
 	  Node u=_g->source(e);
 	  if ( level[u] >= _node_num ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
-	    if ( _surely.positive(excess[u]) ) {
+	    if ( excess[u] != 0 ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
 	    }
@@ -354,7 +360,7 @@
 	  if ( level[u] >= _node_num ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
-	    if ( _surely.positive(excess[u]) ) {
+	    if ( excess[u] != 0 ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
 	    }
@@ -372,8 +378,12 @@
 	  first[b]=next[w];
 	  int newlevel=push(w,next, first);
 	  
+          if ( newlevel == _node_num) {
+            excess.set(w, 0);
+	    level.set(w,_node_num);
+          }
 	  //relabel
-	  if ( _surely.positive(excess[w]) ) {
+	  if ( excess[w] != 0 ) {
 	    level.set(w,++newlevel);
 	    next.set(w,first[newlevel]);
 	    first[newlevel]=w;
@@ -443,7 +453,7 @@
 	
 	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->target(e);
-	  if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
+	  if (!M[v] && _surely.positive((*_capacity)[e] -(*_flow)[e]) ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
@@ -481,7 +491,7 @@
 
 	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->source(e);
-	  if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
+	  if (M[v] && _surely.positive((*_capacity)[e] - (*_flow)[e]) ) {
 	    queue.push(v);
 	    M.set(v, false);
 	  }
@@ -576,12 +586,12 @@
       int newlevel=_node_num;       //bound on the next level of w
 
       for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
-	if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
+	if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
 	Node v=_g->target(e);
 	
 	if( lev > level[v] ) { //Push is allowed now
 	  
-	  if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
+	  if ( excess[v] == 0 && v!=_target && v!=_source ) {
 	    next.set(v,first[level[v]]);
 	    first[level[v]]=v;
 	  }
@@ -605,7 +615,7 @@
 	} else if ( newlevel > level[v] ) newlevel = level[v];
       } //for out edges wv
 
-      if ( _surely.positive(exc) ) {
+      if ( exc != 0 ) {
 	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  
 	  if ( !_surely.positive((*_flow)[e]) ) continue;
@@ -613,7 +623,7 @@
 	  
 	  if( lev > level[v] ) { //Push is allowed now
 
-	    if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
+	    if ( excess[v] == 0 && v!=_target && v!=_source ) {
 	      next.set(v,first[level[v]]);
 	      first[level[v]]=v;
 	    }
@@ -663,7 +673,7 @@
 	  int l=level[v]+1;
 	  
 	  for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
-	    if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
+	    if ( !_surely.positive((*_capacity)[e] - (*_flow)[e] )) continue;
 	    Node w=_g->source(e);
 	    if ( level[w] == _node_num && w != _source ) {
 	      bfs_queue.push(w);
@@ -726,7 +736,7 @@
 	  if ( !_surely.positive(c) ) continue;
 	  Node w=_g->target(e);
 	  if ( level[w] < _node_num ) {
-	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
+	    if ( excess[w] == 0 && w!=_target ) { //putting into the stack
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }
@@ -742,7 +752,10 @@
 	  Num exc=0;
 	  for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e];
 	  for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e];
-	  excess.set(_target,exc);
+          if (!_surely.positive(exc)) {
+            exc = 0;
+          }
+          excess.set(_target,exc);
 	}
 
 	//the starting flow
@@ -751,7 +764,7 @@
 	  if ( !_surely.positive(rem) ) continue;
 	  Node w=_g->target(e);
 	  if ( level[w] < _node_num ) {
-	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
+	    if ( excess[w] == 0 && w!=_target ) { //putting into the stack
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }   
@@ -764,7 +777,7 @@
 	  if ( !_surely.positive((*_flow)[e]) ) continue;
 	  Node w=_g->source(e);
 	  if ( level[w] < _node_num ) {
-	    if ( !_surely.positive(excess[w]) && w!=_target ) {
+	    if ( excess[w] == 0 && w!=_target ) {
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }  
@@ -794,11 +807,14 @@
 	  Num exc=0;
 	  for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e];
 	  for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e];
+          if (!_surely.positive(exc)) {
+            exc = 0;
+          }
 	  excess.set(w,exc);
 	  
 	  //putting the active nodes into the stack
 	  int lev=level[w];
-	    if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
+	    if ( exc != 0 && lev < _node_num && Node(w) != _target ) {
 	      next.set(w,first[lev]);
 	      first[lev]=w;
 	    }