1.1 --- a/lemon/preflow.h Thu Mar 30 15:02:11 2006 +0000
1.2 +++ b/lemon/preflow.h Thu Mar 30 15:34:56 2006 +0000
1.3 @@ -39,8 +39,8 @@
1.4 ///
1.5 ///This class provides an implementation of the \e preflow \e
1.6 ///algorithm producing a flow of maximum value in a directed
1.7 - ///graph. The preflow algorithms are the fastest known max flow algorithms
1.8 - ///up to now. The \e source node, the \e target node, the \e
1.9 + ///graph. The preflow algorithms are the fastest known max flow algorithms.
1.10 + ///The \e source node, the \e target node, the \e
1.11 ///capacity of the edges and the \e starting \e flow value of the
1.12 ///edges should be passed to the algorithm through the
1.13 ///constructor. It is possible to change these quantities using the
1.14 @@ -59,10 +59,10 @@
1.15 ///\param Num The number type of the capacities and the flow values.
1.16 ///\param CapacityMap The capacity map type.
1.17 ///\param FlowMap The flow map type.
1.18 + ///\param Tolerance The tolerance type.
1.19 ///
1.20 ///\author Jacint Szabo
1.21 ///\todo Second template parameter is superfluous
1.22 - ///\todo Using tolerance
1.23 template <typename Graph, typename Num,
1.24 typename CapacityMap=typename Graph::template EdgeMap<Num>,
1.25 typename FlowMap=typename Graph::template EdgeMap<Num>,
1.26 @@ -247,7 +247,7 @@
1.27 //nodes are above bound b.
1.28
1.29 int k=_node_num-2; //bound on the highest level under n containing a node
1.30 - int b=k; //bound on the highest level under n of an active node
1.31 + int b=k; //bound on the highest level under n containing an active node
1.32
1.33 VecNode first(_node_num, INVALID);
1.34 NNMap next(*_g, INVALID);
1.35 @@ -274,7 +274,7 @@
1.36 Node w=first[b];
1.37 first[b]=next[w];
1.38 int newlevel=push(w, next, first);
1.39 - if ( excess[w] > 0 ) relabel(w, newlevel, first, next, level_list,
1.40 + if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list,
1.41 left, right, b, k, what_heur);
1.42
1.43 ++numrelabel;
1.44 @@ -336,12 +336,12 @@
1.45 int l=level[v]+1;
1.46
1.47 for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
1.48 - if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
1.49 + if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
1.50 Node u=_g->source(e);
1.51 if ( level[u] >= _node_num ) {
1.52 bfs_queue.push(u);
1.53 level.set(u, l);
1.54 - if ( excess[u] > 0 ) {
1.55 + if ( _surely.positive(excess[u]) ) {
1.56 next.set(u,first[l]);
1.57 first[l]=u;
1.58 }
1.59 @@ -349,12 +349,12 @@
1.60 }
1.61
1.62 for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) {
1.63 - if ( 0 >= (*_flow)[e] ) continue;
1.64 + if ( !_surely.positive((*_flow)[e]) ) continue;
1.65 Node u=_g->target(e);
1.66 if ( level[u] >= _node_num ) {
1.67 bfs_queue.push(u);
1.68 level.set(u, l);
1.69 - if ( excess[u] > 0 ) {
1.70 + if ( _surely.positive(excess[u]) ) {
1.71 next.set(u,first[l]);
1.72 first[l]=u;
1.73 }
1.74 @@ -373,7 +373,7 @@
1.75 int newlevel=push(w,next, first);
1.76
1.77 //relabel
1.78 - if ( excess[w] > 0 ) {
1.79 + if ( _surely.positive(excess[w]) ) {
1.80 level.set(w,++newlevel);
1.81 next.set(w,first[newlevel]);
1.82 first[newlevel]=w;
1.83 @@ -443,7 +443,7 @@
1.84
1.85 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.86 Node v=_g->target(e);
1.87 - if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) {
1.88 + if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
1.89 queue.push(v);
1.90 M.set(v, true);
1.91 }
1.92 @@ -451,7 +451,7 @@
1.93
1.94 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.95 Node v=_g->source(e);
1.96 - if (!M[v] && (*_flow)[e] > 0 ) {
1.97 + if (!M[v] && _surely.positive((*_flow)[e]) ) {
1.98 queue.push(v);
1.99 M.set(v, true);
1.100 }
1.101 @@ -481,7 +481,7 @@
1.102
1.103 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.104 Node v=_g->source(e);
1.105 - if (M[v] && (*_flow)[e] < (*_capacity)[e] ) {
1.106 + if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
1.107 queue.push(v);
1.108 M.set(v, false);
1.109 }
1.110 @@ -489,7 +489,7 @@
1.111
1.112 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.113 Node v=_g->target(e);
1.114 - if (M[v] && (*_flow)[e] > 0 ) {
1.115 + if (M[v] && _surely.positive((*_flow)[e]) ) {
1.116 queue.push(v);
1.117 M.set(v, false);
1.118 }
1.119 @@ -576,12 +576,12 @@
1.120 int newlevel=_node_num; //bound on the next level of w
1.121
1.122 for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.123 - if ( (*_flow)[e] >= (*_capacity)[e] ) continue;
1.124 + if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
1.125 Node v=_g->target(e);
1.126 -
1.127 +
1.128 if( lev > level[v] ) { //Push is allowed now
1.129
1.130 - if ( excess[v]<=0 && v!=_target && v!=_source ) {
1.131 + if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
1.132 next.set(v,first[level[v]]);
1.133 first[level[v]]=v;
1.134 }
1.135 @@ -590,7 +590,7 @@
1.136 Num flo=(*_flow)[e];
1.137 Num remcap=cap-flo;
1.138
1.139 - if ( remcap >= exc ) { //A nonsaturating push.
1.140 + if ( ! _surely.less(remcap, exc) ) { //A nonsaturating push.
1.141
1.142 _flow->set(e, flo+exc);
1.143 excess.set(v, excess[v]+exc);
1.144 @@ -605,22 +605,22 @@
1.145 } else if ( newlevel > level[v] ) newlevel = level[v];
1.146 } //for out edges wv
1.147
1.148 - if ( exc > 0 ) {
1.149 + if ( _surely.positive(exc) ) {
1.150 for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
1.151
1.152 - if( (*_flow)[e] <= 0 ) continue;
1.153 + if ( !_surely.positive((*_flow)[e]) ) continue;
1.154 Node v=_g->source(e);
1.155 -
1.156 +
1.157 if( lev > level[v] ) { //Push is allowed now
1.158
1.159 - if ( excess[v]<=0 && v!=_target && v!=_source ) {
1.160 + if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
1.161 next.set(v,first[level[v]]);
1.162 first[level[v]]=v;
1.163 }
1.164
1.165 Num flo=(*_flow)[e];
1.166
1.167 - if ( flo >= exc ) { //A nonsaturating push.
1.168 + if ( !_surely.less(flo, exc) ) { //A nonsaturating push.
1.169
1.170 _flow->set(e, flo-exc);
1.171 excess.set(v, excess[v]+exc);
1.172 @@ -663,7 +663,7 @@
1.173 int l=level[v]+1;
1.174
1.175 for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
1.176 - if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
1.177 + if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
1.178 Node w=_g->source(e);
1.179 if ( level[w] == _node_num && w != _source ) {
1.180 bfs_queue.push(w);
1.181 @@ -676,7 +676,7 @@
1.182 }
1.183
1.184 for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
1.185 - if ( 0 >= (*_flow)[e] ) continue;
1.186 + if ( !_surely.positive((*_flow)[e]) ) continue;
1.187 Node w=_g->target(e);
1.188 if ( level[w] == _node_num && w != _source ) {
1.189 bfs_queue.push(w);
1.190 @@ -723,10 +723,10 @@
1.191 //the starting flow
1.192 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
1.193 Num c=(*_capacity)[e];
1.194 - if ( c <= 0 ) continue;
1.195 + if ( !_surely.positive(c) ) continue;
1.196 Node w=_g->target(e);
1.197 if ( level[w] < _node_num ) {
1.198 - if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
1.199 + if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
1.200 next.set(w,first[level[w]]);
1.201 first[level[w]]=w;
1.202 }
1.203 @@ -748,10 +748,10 @@
1.204 //the starting flow
1.205 for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e) {
1.206 Num rem=(*_capacity)[e]-(*_flow)[e];
1.207 - if ( rem <= 0 ) continue;
1.208 + if ( !_surely.positive(rem) ) continue;
1.209 Node w=_g->target(e);
1.210 if ( level[w] < _node_num ) {
1.211 - if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
1.212 + if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
1.213 next.set(w,first[level[w]]);
1.214 first[level[w]]=w;
1.215 }
1.216 @@ -761,10 +761,10 @@
1.217 }
1.218
1.219 for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) {
1.220 - if ( (*_flow)[e] <= 0 ) continue;
1.221 + if ( !_surely.positive((*_flow)[e]) ) continue;
1.222 Node w=_g->source(e);
1.223 if ( level[w] < _node_num ) {
1.224 - if ( excess[w] <= 0 && w!=_target ) {
1.225 + if ( !_surely.positive(excess[w]) && w!=_target ) {
1.226 next.set(w,first[level[w]]);
1.227 first[level[w]]=w;
1.228 }
1.229 @@ -778,13 +778,13 @@
1.230 //the starting flow
1.231 for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
1.232 Num rem=(*_capacity)[e]-(*_flow)[e];
1.233 - if ( rem <= 0 ) continue;
1.234 + if ( !_surely.positive(rem) ) continue;
1.235 Node w=_g->target(e);
1.236 if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]);
1.237 }
1.238
1.239 for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
1.240 - if ( (*_flow)[e] <= 0 ) continue;
1.241 + if ( !_surely.positive((*_flow)[e]) ) continue;
1.242 Node w=_g->source(e);
1.243 if ( level[w] < _node_num ) _flow->set(e, 0);
1.244 }
1.245 @@ -798,7 +798,7 @@
1.246
1.247 //putting the active nodes into the stack
1.248 int lev=level[w];
1.249 - if ( exc > 0 && lev < _node_num && Node(w) != _target ) {
1.250 + if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
1.251 next.set(w,first[lev]);
1.252 first[lev]=w;
1.253 }