# HG changeset patch
# User jacint
# Date 1143732896 0
# Node ID 4ab8a25def3cbaeb14a8a509e8fd0c67e0ed4b73
# Parent  f34f044a043c67c0004c4e101931fbe394c5b125
tolerance class incorporated

diff -r f34f044a043c -r 4ab8a25def3c lemon/preflow.h
--- a/lemon/preflow.h	Thu Mar 30 15:02:11 2006 +0000
+++ b/lemon/preflow.h	Thu Mar 30 15:34:56 2006 +0000
@@ -39,8 +39,8 @@
   ///
   ///This class provides an implementation of the \e preflow \e
   ///algorithm producing a flow of maximum value in a directed
-  ///graph. The preflow algorithms are the fastest known max flow algorithms
-  ///up to now. The \e source node, the \e target node, the \e
+  ///graph. The preflow algorithms are the fastest known max flow algorithms. 
+  ///The \e source node, the \e target node, the \e
   ///capacity of the edges and the \e starting \e flow value of the
   ///edges should be passed to the algorithm through the
   ///constructor. It is possible to change these quantities using the
@@ -59,10 +59,10 @@
   ///\param Num The number type of the capacities and the flow values.
   ///\param CapacityMap The capacity map type.
   ///\param FlowMap The flow map type.
+  ///\param Tolerance The tolerance type. 
   ///
   ///\author Jacint Szabo 
   ///\todo Second template parameter is superfluous
-  ///\todo Using tolerance
   template <typename Graph, typename Num,
 	    typename CapacityMap=typename Graph::template EdgeMap<Num>,
             typename FlowMap=typename Graph::template EdgeMap<Num>,
@@ -247,7 +247,7 @@
       //nodes are above bound b.
 
       int k=_node_num-2;  //bound on the highest level under n containing a node
-      int b=k;    //bound on the highest level under n of an active node
+      int b=k;    //bound on the highest level under n containing an active node
 
       VecNode first(_node_num, INVALID);
       NNMap next(*_g, INVALID);
@@ -274,7 +274,7 @@
 	  Node w=first[b];
 	  first[b]=next[w];
 	  int newlevel=push(w, next, first);
-	  if ( excess[w] > 0 ) relabel(w, newlevel, first, next, level_list, 
+	  if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list, 
 				       left, right, b, k, what_heur);
 
 	  ++numrelabel;
@@ -336,12 +336,12 @@
 	int l=level[v]+1;
 
 	for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
-	  if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
+	  if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
 	  Node u=_g->source(e);
 	  if ( level[u] >= _node_num ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
-	    if ( excess[u] > 0 ) {
+	    if ( _surely.positive(excess[u]) ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
 	    }
@@ -349,12 +349,12 @@
 	}
 
 	for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) {
-	  if ( 0 >= (*_flow)[e] ) continue;
+	  if ( !_surely.positive((*_flow)[e]) ) continue;
 	  Node u=_g->target(e);
 	  if ( level[u] >= _node_num ) {
 	    bfs_queue.push(u);
 	    level.set(u, l);
-	    if ( excess[u] > 0 ) {
+	    if ( _surely.positive(excess[u]) ) {
 	      next.set(u,first[l]);
 	      first[l]=u;
 	    }
@@ -373,7 +373,7 @@
 	  int newlevel=push(w,next, first);
 	  
 	  //relabel
-	  if ( excess[w] > 0 ) {
+	  if ( _surely.positive(excess[w]) ) {
 	    level.set(w,++newlevel);
 	    next.set(w,first[newlevel]);
 	    first[newlevel]=w;
@@ -443,7 +443,7 @@
 	
 	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->target(e);
-	  if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) {
+	  if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
@@ -451,7 +451,7 @@
 	
 	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->source(e);
-	  if (!M[v] && (*_flow)[e] > 0 ) {
+	  if (!M[v] && _surely.positive((*_flow)[e]) ) {
 	    queue.push(v);
 	    M.set(v, true);
 	  }
@@ -481,7 +481,7 @@
 
 	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->source(e);
-	  if (M[v] && (*_flow)[e] < (*_capacity)[e] ) {
+	  if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
 	    queue.push(v);
 	    M.set(v, false);
 	  }
@@ -489,7 +489,7 @@
 
 	for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  Node v=_g->target(e);
-	  if (M[v] && (*_flow)[e] > 0 ) {
+	  if (M[v] && _surely.positive((*_flow)[e]) ) {
 	    queue.push(v);
 	    M.set(v, false);
 	  }
@@ -576,12 +576,12 @@
       int newlevel=_node_num;       //bound on the next level of w
 
       for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
-	if ( (*_flow)[e] >= (*_capacity)[e] ) continue;
+	if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
 	Node v=_g->target(e);
-
+	
 	if( lev > level[v] ) { //Push is allowed now
 	  
-	  if ( excess[v]<=0 && v!=_target && v!=_source ) {
+	  if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
 	    next.set(v,first[level[v]]);
 	    first[level[v]]=v;
 	  }
@@ -590,7 +590,7 @@
 	  Num flo=(*_flow)[e];
 	  Num remcap=cap-flo;
 	  
-	  if ( remcap >= exc ) { //A nonsaturating push.
+	  if ( ! _surely.less(remcap, exc) ) { //A nonsaturating push.
 	    
 	    _flow->set(e, flo+exc);
 	    excess.set(v, excess[v]+exc);
@@ -605,22 +605,22 @@
 	} else if ( newlevel > level[v] ) newlevel = level[v];
       } //for out edges wv
 
-      if ( exc > 0 ) {
+      if ( _surely.positive(exc) ) {
 	for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
 	  
-	  if( (*_flow)[e] <= 0 ) continue;
+	  if ( !_surely.positive((*_flow)[e]) ) continue;
 	  Node v=_g->source(e);
-
+	  
 	  if( lev > level[v] ) { //Push is allowed now
 
-	    if ( excess[v]<=0 && v!=_target && v!=_source ) {
+	    if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
 	      next.set(v,first[level[v]]);
 	      first[level[v]]=v;
 	    }
 
 	    Num flo=(*_flow)[e];
 
-	    if ( flo >= exc ) { //A nonsaturating push.
+	    if ( !_surely.less(flo, exc) ) { //A nonsaturating push.
 
 	      _flow->set(e, flo-exc);
 	      excess.set(v, excess[v]+exc);
@@ -663,7 +663,7 @@
 	  int l=level[v]+1;
 	  
 	  for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
-	    if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
+	    if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
 	    Node w=_g->source(e);
 	    if ( level[w] == _node_num && w != _source ) {
 	      bfs_queue.push(w);
@@ -676,7 +676,7 @@
 	  }
 	  
 	  for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
-	    if ( 0 >= (*_flow)[e] ) continue;
+	    if ( !_surely.positive((*_flow)[e]) ) continue;
 	    Node w=_g->target(e);
 	    if ( level[w] == _node_num && w != _source ) {
 	      bfs_queue.push(w);
@@ -723,10 +723,10 @@
 	//the starting flow
 	for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
 	  Num c=(*_capacity)[e];
-	  if ( c <= 0 ) continue;
+	  if ( !_surely.positive(c) ) continue;
 	  Node w=_g->target(e);
 	  if ( level[w] < _node_num ) {
-	    if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
+	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }
@@ -748,10 +748,10 @@
 	//the starting flow
 	for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e)	{
 	  Num rem=(*_capacity)[e]-(*_flow)[e];
-	  if ( rem <= 0 ) continue;
+	  if ( !_surely.positive(rem) ) continue;
 	  Node w=_g->target(e);
 	  if ( level[w] < _node_num ) {
-	    if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
+	    if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }   
@@ -761,10 +761,10 @@
 	}
 	
 	for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) {
-	  if ( (*_flow)[e] <= 0 ) continue;
+	  if ( !_surely.positive((*_flow)[e]) ) continue;
 	  Node w=_g->source(e);
 	  if ( level[w] < _node_num ) {
-	    if ( excess[w] <= 0 && w!=_target ) {
+	    if ( !_surely.positive(excess[w]) && w!=_target ) {
 	      next.set(w,first[level[w]]);
 	      first[level[w]]=w;
 	    }  
@@ -778,13 +778,13 @@
 	//the starting flow
 	for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
 	  Num rem=(*_capacity)[e]-(*_flow)[e];
-	  if ( rem <= 0 ) continue;
+	  if ( !_surely.positive(rem) ) continue;
 	  Node w=_g->target(e);
 	  if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]);
 	}
 	
 	for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
-	  if ( (*_flow)[e] <= 0 ) continue;
+	  if ( !_surely.positive((*_flow)[e]) ) continue;
 	  Node w=_g->source(e);
 	  if ( level[w] < _node_num ) _flow->set(e, 0);
 	}
@@ -798,7 +798,7 @@
 	  
 	  //putting the active nodes into the stack
 	  int lev=level[w];
-	    if ( exc > 0 && lev < _node_num && Node(w) != _target ) {
+	    if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
 	      next.set(w,first[lev]);
 	      first[lev]=w;
 	    }