COIN-OR::LEMON - Graph Library

Changeset 2330:9dccb1abc721 in lemon-0.x for lemon


Ignore:
Timestamp:
12/18/06 11:12:07 (17 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3116
Message:

Better handling of inexact computation.
We do not use tolerance for excess, just for edges

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r2151 r2330  
    275275          first[b]=next[w];
    276276          int newlevel=push(w, next, first);
    277           if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list,
    278                                        left, right, b, k, what_heur);
     277          if ( excess[w] != 0 ) {
     278            relabel(w, newlevel, first, next, level_list,
     279                    left, right, b, k, what_heur);
     280          }
    279281
    280282          ++numrelabel;
     
    317319    ///maxMinCut return the inclusionwise minimum and maximum cuts of
    318320    ///minimum value, resp.  \pre \ref phase1 must be called before.
     321    ///
     322    /// \todo The inexact computation can cause positive excess on a set of
     323    /// unpushable nodes. We may have to watch the empty level in this case
     324    /// due to avoid the terrible long running time.
    319325    void phase2()
    320326    {
     
    337343
    338344        for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
    339           if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
     345          if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
    340346          Node u=_g->source(e);
    341347          if ( level[u] >= _node_num ) {
    342348            bfs_queue.push(u);
    343349            level.set(u, l);
    344             if ( _surely.positive(excess[u]) ) {
     350            if ( excess[u] != 0 ) {
    345351              next.set(u,first[l]);
    346352              first[l]=u;
     
    355361            bfs_queue.push(u);
    356362            level.set(u, l);
    357             if ( _surely.positive(excess[u]) ) {
     363            if ( excess[u] != 0 ) {
    358364              next.set(u,first[l]);
    359365              first[l]=u;
     
    373379          int newlevel=push(w,next, first);
    374380         
     381          if ( newlevel == _node_num) {
     382            excess.set(w, 0);
     383            level.set(w,_node_num);
     384          }
    375385          //relabel
    376           if ( _surely.positive(excess[w]) ) {
     386          if ( excess[w] != 0 ) {
    377387            level.set(w,++newlevel);
    378388            next.set(w,first[newlevel]);
     
    444454        for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    445455          Node v=_g->target(e);
    446           if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
     456          if (!M[v] && _surely.positive((*_capacity)[e] -(*_flow)[e]) ) {
    447457            queue.push(v);
    448458            M.set(v, true);
     
    482492        for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    483493          Node v=_g->source(e);
    484           if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
     494          if (M[v] && _surely.positive((*_capacity)[e] - (*_flow)[e]) ) {
    485495            queue.push(v);
    486496            M.set(v, false);
     
    577587
    578588      for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    579         if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
     589        if ( !_surely.positive((*_capacity)[e] - (*_flow)[e])) continue;
    580590        Node v=_g->target(e);
    581591       
    582592        if( lev > level[v] ) { //Push is allowed now
    583593         
    584           if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
     594          if ( excess[v] == 0 && v!=_target && v!=_source ) {
    585595            next.set(v,first[level[v]]);
    586596            first[level[v]]=v;
     
    606616      } //for out edges wv
    607617
    608       if ( _surely.positive(exc) ) {
     618      if ( exc != 0 ) {
    609619        for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    610620         
     
    614624          if( lev > level[v] ) { //Push is allowed now
    615625
    616             if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
     626            if ( excess[v] == 0 && v!=_target && v!=_source ) {
    617627              next.set(v,first[level[v]]);
    618628              first[level[v]]=v;
     
    664674         
    665675          for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
    666             if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
     676            if ( !_surely.positive((*_capacity)[e] - (*_flow)[e] )) continue;
    667677            Node w=_g->source(e);
    668678            if ( level[w] == _node_num && w != _source ) {
     
    727737          Node w=_g->target(e);
    728738          if ( level[w] < _node_num ) {
    729             if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
     739            if ( excess[w] == 0 && w!=_target ) { //putting into the stack
    730740              next.set(w,first[level[w]]);
    731741              first[level[w]]=w;
     
    743753          for(InEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc+=(*_flow)[e];
    744754          for(OutEdgeIt e(*_g,_target) ; e!=INVALID; ++e) exc-=(*_flow)[e];
    745           excess.set(_target,exc);
     755          if (!_surely.positive(exc)) {
     756            exc = 0;
     757          }
     758          excess.set(_target,exc);
    746759        }
    747760
     
    752765          Node w=_g->target(e);
    753766          if ( level[w] < _node_num ) {
    754             if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
     767            if ( excess[w] == 0 && w!=_target ) { //putting into the stack
    755768              next.set(w,first[level[w]]);
    756769              first[level[w]]=w;
     
    765778          Node w=_g->source(e);
    766779          if ( level[w] < _node_num ) {
    767             if ( !_surely.positive(excess[w]) && w!=_target ) {
     780            if ( excess[w] == 0 && w!=_target ) {
    768781              next.set(w,first[level[w]]);
    769782              first[level[w]]=w;
     
    795808          for(InEdgeIt e(*_g,w); e!=INVALID; ++e) exc+=(*_flow)[e];
    796809          for(OutEdgeIt e(*_g,w); e!=INVALID; ++e) exc-=(*_flow)[e];
     810          if (!_surely.positive(exc)) {
     811            exc = 0;
     812          }
    797813          excess.set(w,exc);
    798814         
    799815          //putting the active nodes into the stack
    800816          int lev=level[w];
    801             if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
     817            if ( exc != 0 && lev < _node_num && Node(w) != _target ) {
    802818              next.set(w,first[lev]);
    803819              first[lev]=w;
Note: See TracChangeset for help on using the changeset viewer.