COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
03/30/06 17:34:56 (14 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2663
Message:

tolerance class incorporated

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/preflow.h

    r2019 r2024  
    4040  ///This class provides an implementation of the \e preflow \e
    4141  ///algorithm producing a flow of maximum value in a directed
    42   ///graph. The preflow algorithms are the fastest known max flow algorithms
    43   ///up to now. The \e source node, the \e target node, the \e
     42  ///graph. The preflow algorithms are the fastest known max flow algorithms.
     43  ///The \e source node, the \e target node, the \e
    4444  ///capacity of the edges and the \e starting \e flow value of the
    4545  ///edges should be passed to the algorithm through the
     
    6060  ///\param CapacityMap The capacity map type.
    6161  ///\param FlowMap The flow map type.
     62  ///\param Tolerance The tolerance type.
    6263  ///
    6364  ///\author Jacint Szabo
    6465  ///\todo Second template parameter is superfluous
    65   ///\todo Using tolerance
    6666  template <typename Graph, typename Num,
    6767            typename CapacityMap=typename Graph::template EdgeMap<Num>,
     
    248248
    249249      int k=_node_num-2;  //bound on the highest level under n containing a node
    250       int b=k;    //bound on the highest level under n of an active node
     250      int b=k;    //bound on the highest level under n containing an active node
    251251
    252252      VecNode first(_node_num, INVALID);
     
    275275          first[b]=next[w];
    276276          int newlevel=push(w, next, first);
    277           if ( excess[w] > 0 ) relabel(w, newlevel, first, next, level_list,
     277          if ( _surely.positive(excess[w]) ) relabel(w, newlevel, first, next, level_list,
    278278                                       left, right, b, k, what_heur);
    279279
     
    337337
    338338        for(InEdgeIt e(*_g,v); e!=INVALID; ++e) {
    339           if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
     339          if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
    340340          Node u=_g->source(e);
    341341          if ( level[u] >= _node_num ) {
    342342            bfs_queue.push(u);
    343343            level.set(u, l);
    344             if ( excess[u] > 0 ) {
     344            if ( _surely.positive(excess[u]) ) {
    345345              next.set(u,first[l]);
    346346              first[l]=u;
     
    350350
    351351        for(OutEdgeIt e(*_g,v); e!=INVALID; ++e) {
    352           if ( 0 >= (*_flow)[e] ) continue;
     352          if ( !_surely.positive((*_flow)[e]) ) continue;
    353353          Node u=_g->target(e);
    354354          if ( level[u] >= _node_num ) {
    355355            bfs_queue.push(u);
    356356            level.set(u, l);
    357             if ( excess[u] > 0 ) {
     357            if ( _surely.positive(excess[u]) ) {
    358358              next.set(u,first[l]);
    359359              first[l]=u;
     
    374374         
    375375          //relabel
    376           if ( excess[w] > 0 ) {
     376          if ( _surely.positive(excess[w]) ) {
    377377            level.set(w,++newlevel);
    378378            next.set(w,first[newlevel]);
     
    444444        for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    445445          Node v=_g->target(e);
    446           if (!M[v] && (*_flow)[e] < (*_capacity)[e] ) {
     446          if (!M[v] && _surely.less((*_flow)[e] , (*_capacity)[e]) ) {
    447447            queue.push(v);
    448448            M.set(v, true);
     
    452452        for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    453453          Node v=_g->source(e);
    454           if (!M[v] && (*_flow)[e] > 0 ) {
     454          if (!M[v] && _surely.positive((*_flow)[e]) ) {
    455455            queue.push(v);
    456456            M.set(v, true);
     
    482482        for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    483483          Node v=_g->source(e);
    484           if (M[v] && (*_flow)[e] < (*_capacity)[e] ) {
     484          if (M[v] && _surely.less((*_flow)[e], (*_capacity)[e]) ) {
    485485            queue.push(v);
    486486            M.set(v, false);
     
    490490        for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    491491          Node v=_g->target(e);
    492           if (M[v] && (*_flow)[e] > 0 ) {
     492          if (M[v] && _surely.positive((*_flow)[e]) ) {
    493493            queue.push(v);
    494494            M.set(v, false);
     
    577577
    578578      for(OutEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    579         if ( (*_flow)[e] >= (*_capacity)[e] ) continue;
     579        if ( !_surely.less((*_flow)[e], (*_capacity)[e]) ) continue;
    580580        Node v=_g->target(e);
    581 
     581       
    582582        if( lev > level[v] ) { //Push is allowed now
    583583         
    584           if ( excess[v]<=0 && v!=_target && v!=_source ) {
     584          if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
    585585            next.set(v,first[level[v]]);
    586586            first[level[v]]=v;
     
    591591          Num remcap=cap-flo;
    592592         
    593           if ( remcap >= exc ) { //A nonsaturating push.
     593          if ( ! _surely.less(remcap, exc) ) { //A nonsaturating push.
    594594           
    595595            _flow->set(e, flo+exc);
     
    606606      } //for out edges wv
    607607
    608       if ( exc > 0 ) {
     608      if ( _surely.positive(exc) ) {
    609609        for(InEdgeIt e(*_g,w) ; e!=INVALID; ++e) {
    610610         
    611           if( (*_flow)[e] <= 0 ) continue;
     611          if ( !_surely.positive((*_flow)[e]) ) continue;
    612612          Node v=_g->source(e);
    613 
     613         
    614614          if( lev > level[v] ) { //Push is allowed now
    615615
    616             if ( excess[v]<=0 && v!=_target && v!=_source ) {
     616            if ( !_surely.positive(excess[v]) && v!=_target && v!=_source ) {
    617617              next.set(v,first[level[v]]);
    618618              first[level[v]]=v;
     
    621621            Num flo=(*_flow)[e];
    622622
    623             if ( flo >= exc ) { //A nonsaturating push.
     623            if ( !_surely.less(flo, exc) ) { //A nonsaturating push.
    624624
    625625              _flow->set(e, flo-exc);
     
    664664         
    665665          for(InEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
    666             if ( (*_capacity)[e] <= (*_flow)[e] ) continue;
     666            if ( !_surely.less((*_flow)[e],(*_capacity)[e]) ) continue;
    667667            Node w=_g->source(e);
    668668            if ( level[w] == _node_num && w != _source ) {
     
    677677         
    678678          for(OutEdgeIt e(*_g,v) ; e!=INVALID; ++e) {
    679             if ( 0 >= (*_flow)[e] ) continue;
     679            if ( !_surely.positive((*_flow)[e]) ) continue;
    680680            Node w=_g->target(e);
    681681            if ( level[w] == _node_num && w != _source ) {
     
    724724        for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
    725725          Num c=(*_capacity)[e];
    726           if ( c <= 0 ) continue;
     726          if ( !_surely.positive(c) ) continue;
    727727          Node w=_g->target(e);
    728728          if ( level[w] < _node_num ) {
    729             if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
     729            if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
    730730              next.set(w,first[level[w]]);
    731731              first[level[w]]=w;
     
    749749        for(OutEdgeIt e(*_g,_source); e!=INVALID; ++e)  {
    750750          Num rem=(*_capacity)[e]-(*_flow)[e];
    751           if ( rem <= 0 ) continue;
     751          if ( !_surely.positive(rem) ) continue;
    752752          Node w=_g->target(e);
    753753          if ( level[w] < _node_num ) {
    754             if ( excess[w] <= 0 && w!=_target ) { //putting into the stack
     754            if ( !_surely.positive(excess[w]) && w!=_target ) { //putting into the stack
    755755              next.set(w,first[level[w]]);
    756756              first[level[w]]=w;
     
    762762       
    763763        for(InEdgeIt e(*_g,_source); e!=INVALID; ++e) {
    764           if ( (*_flow)[e] <= 0 ) continue;
     764          if ( !_surely.positive((*_flow)[e]) ) continue;
    765765          Node w=_g->source(e);
    766766          if ( level[w] < _node_num ) {
    767             if ( excess[w] <= 0 && w!=_target ) {
     767            if ( !_surely.positive(excess[w]) && w!=_target ) {
    768768              next.set(w,first[level[w]]);
    769769              first[level[w]]=w;
     
    779779        for(OutEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
    780780          Num rem=(*_capacity)[e]-(*_flow)[e];
    781           if ( rem <= 0 ) continue;
     781          if ( !_surely.positive(rem) ) continue;
    782782          Node w=_g->target(e);
    783783          if ( level[w] < _node_num ) _flow->set(e, (*_capacity)[e]);
     
    785785       
    786786        for(InEdgeIt e(*_g,_source) ; e!=INVALID; ++e) {
    787           if ( (*_flow)[e] <= 0 ) continue;
     787          if ( !_surely.positive((*_flow)[e]) ) continue;
    788788          Node w=_g->source(e);
    789789          if ( level[w] < _node_num ) _flow->set(e, 0);
     
    799799          //putting the active nodes into the stack
    800800          int lev=level[w];
    801             if ( exc > 0 && lev < _node_num && Node(w) != _target ) {
     801            if ( _surely.positive(exc) && lev < _node_num && Node(w) != _target ) {
    802802              next.set(w,first[lev]);
    803803              first[lev]=w;
Note: See TracChangeset for help on using the changeset viewer.