Changeset 2024:4ab8a25def3c in lemon-0.x for lemon/preflow.h

Timestamp:

03/30/06 17:34:56 (18 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2663

Message:

tolerance class incorporated

File:

• lemon/preflow.h (modified) (23 diffs)

lemon/preflow.h

@@ -40 +40 @@
   ///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
@@ -60 +60 @@
   ///\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>,
@@ -248 +248 @@
 
       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);
@@ -275 +275 @@
           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);
 
@@ -337 +337 @@
 
         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;
@@ -350 +350 @@
 
         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;
@@ -374 +374 @@
           
           //relabel
-          if ( excess[w] > 0 ) {
+          if ( _surely.positive(excess[w]) ) {
             level.set(w,++newlevel);
             next.set(w,first[newlevel]);
@@ -444 +444 @@
         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);
@@ -452 +452 @@
         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);
@@ -482 +482 @@
         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);
@@ -490 +490 @@
         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);
@@ -577 +577 @@
 
       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;
@@ -591 +591 @@
           Num remcap=cap-flo;
           
-          if ( remcap >= exc ) { //A nonsaturating push.
+          if ( ! _surely.less(remcap, exc) ) { //A nonsaturating push.
             
             _flow->set(e, flo+exc);
@@ -606 +606 @@
       } //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;
@@ -621 +621 @@
             Num flo=(*_flow)[e];
 
-            if ( flo >= exc ) { //A nonsaturating push.
+            if ( !_surely.less(flo, exc) ) { //A nonsaturating push.
 
               _flow->set(e, flo-exc);
@@ -664 +664 @@
           
           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 ) {
@@ -677 +677 @@
           
           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 ) {
@@ -724 +724 @@
         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;
@@ -749 +749 @@
         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;
@@ -762 +762 @@
         
         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;
@@ -779 +779 @@
         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]);
@@ -785 +785 @@
         
         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);
@@ -799 +799 @@
           //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;