lemon/circulation.h
changeset 594 d657c71db7db
parent 559 c5fd2d996909
child 611 85cb3aa71cce
equal deleted inserted replaced
6:dfc6436fbb5a 7:27531e6b14ad
   451     void init()
   451     void init()
   452     {
   452     {
   453       createStructures();
   453       createStructures();
   454 
   454 
   455       for(NodeIt n(_g);n!=INVALID;++n) {
   455       for(NodeIt n(_g);n!=INVALID;++n) {
   456         _excess->set(n, (*_delta)[n]);
   456         (*_excess)[n] = (*_delta)[n];
   457       }
   457       }
   458 
   458 
   459       for (ArcIt e(_g);e!=INVALID;++e) {
   459       for (ArcIt e(_g);e!=INVALID;++e) {
   460         _flow->set(e, (*_lo)[e]);
   460         _flow->set(e, (*_lo)[e]);
   461         _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]);
   461         (*_excess)[_g.target(e)] += (*_flow)[e];
   462         _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]);
   462         (*_excess)[_g.source(e)] -= (*_flow)[e];
   463       }
   463       }
   464 
   464 
   465       // global relabeling tested, but in general case it provides
   465       // global relabeling tested, but in general case it provides
   466       // worse performance for random digraphs
   466       // worse performance for random digraphs
   467       _level->initStart();
   467       _level->initStart();
   480     void greedyInit()
   480     void greedyInit()
   481     {
   481     {
   482       createStructures();
   482       createStructures();
   483 
   483 
   484       for(NodeIt n(_g);n!=INVALID;++n) {
   484       for(NodeIt n(_g);n!=INVALID;++n) {
   485         _excess->set(n, (*_delta)[n]);
   485         (*_excess)[n] = (*_delta)[n];
   486       }
   486       }
   487 
   487 
   488       for (ArcIt e(_g);e!=INVALID;++e) {
   488       for (ArcIt e(_g);e!=INVALID;++e) {
   489         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
   489         if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
   490           _flow->set(e, (*_up)[e]);
   490           _flow->set(e, (*_up)[e]);
   491           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]);
   491           (*_excess)[_g.target(e)] += (*_up)[e];
   492           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]);
   492           (*_excess)[_g.source(e)] -= (*_up)[e];
   493         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
   493         } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
   494           _flow->set(e, (*_lo)[e]);
   494           _flow->set(e, (*_lo)[e]);
   495           _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]);
   495           (*_excess)[_g.target(e)] += (*_lo)[e];
   496           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]);
   496           (*_excess)[_g.source(e)] -= (*_lo)[e];
   497         } else {
   497         } else {
   498           Value fc = -(*_excess)[_g.target(e)];
   498           Value fc = -(*_excess)[_g.target(e)];
   499           _flow->set(e, fc);
   499           _flow->set(e, fc);
   500           _excess->set(_g.target(e), 0);
   500           (*_excess)[_g.target(e)] = 0;
   501           _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc);
   501           (*_excess)[_g.source(e)] -= fc;
   502         }
   502         }
   503       }
   503       }
   504 
   504 
   505       _level->initStart();
   505       _level->initStart();
   506       for(NodeIt n(_g);n!=INVALID;++n)
   506       for(NodeIt n(_g);n!=INVALID;++n)
   535           Value fc=(*_up)[e]-(*_flow)[e];
   535           Value fc=(*_up)[e]-(*_flow)[e];
   536           if(!_tol.positive(fc)) continue;
   536           if(!_tol.positive(fc)) continue;
   537           if((*_level)[v]<actlevel) {
   537           if((*_level)[v]<actlevel) {
   538             if(!_tol.less(fc, exc)) {
   538             if(!_tol.less(fc, exc)) {
   539               _flow->set(e, (*_flow)[e] + exc);
   539               _flow->set(e, (*_flow)[e] + exc);
   540               _excess->set(v, (*_excess)[v] + exc);
   540               (*_excess)[v] += exc;
   541               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   541               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   542                 _level->activate(v);
   542                 _level->activate(v);
   543               _excess->set(act,0);
   543               (*_excess)[act] = 0;
   544               _level->deactivate(act);
   544               _level->deactivate(act);
   545               goto next_l;
   545               goto next_l;
   546             }
   546             }
   547             else {
   547             else {
   548               _flow->set(e, (*_up)[e]);
   548               _flow->set(e, (*_up)[e]);
   549               _excess->set(v, (*_excess)[v] + fc);
   549               (*_excess)[v] += fc;
   550               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   550               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   551                 _level->activate(v);
   551                 _level->activate(v);
   552               exc-=fc;
   552               exc-=fc;
   553             }
   553             }
   554           }
   554           }
   559           Value fc=(*_flow)[e]-(*_lo)[e];
   559           Value fc=(*_flow)[e]-(*_lo)[e];
   560           if(!_tol.positive(fc)) continue;
   560           if(!_tol.positive(fc)) continue;
   561           if((*_level)[v]<actlevel) {
   561           if((*_level)[v]<actlevel) {
   562             if(!_tol.less(fc, exc)) {
   562             if(!_tol.less(fc, exc)) {
   563               _flow->set(e, (*_flow)[e] - exc);
   563               _flow->set(e, (*_flow)[e] - exc);
   564               _excess->set(v, (*_excess)[v] + exc);
   564               (*_excess)[v] += exc;
   565               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   565               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   566                 _level->activate(v);
   566                 _level->activate(v);
   567               _excess->set(act,0);
   567               (*_excess)[act] = 0;
   568               _level->deactivate(act);
   568               _level->deactivate(act);
   569               goto next_l;
   569               goto next_l;
   570             }
   570             }
   571             else {
   571             else {
   572               _flow->set(e, (*_lo)[e]);
   572               _flow->set(e, (*_lo)[e]);
   573               _excess->set(v, (*_excess)[v] + fc);
   573               (*_excess)[v] += fc;
   574               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   574               if(!_level->active(v) && _tol.positive((*_excess)[v]))
   575                 _level->activate(v);
   575                 _level->activate(v);
   576               exc-=fc;
   576               exc-=fc;
   577             }
   577             }
   578           }
   578           }
   579           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   579           else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
   580         }
   580         }
   581 
   581 
   582         _excess->set(act, exc);
   582         (*_excess)[act] = exc;
   583         if(!_tol.positive(exc)) _level->deactivate(act);
   583         if(!_tol.positive(exc)) _level->deactivate(act);
   584         else if(mlevel==_node_num) {
   584         else if(mlevel==_node_num) {
   585           _level->liftHighestActiveToTop();
   585           _level->liftHighestActiveToTop();
   586           _el = _node_num;
   586           _el = _node_num;
   587           return false;
   587           return false;