COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 581:aa1804409f29 in lemon-main for lemon/preflow.h


Ignore:
Timestamp:
04/14/09 10:35:38 (15 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Exploit that the standard maps are reference maps (#190)

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/preflow.h

    r559 r581  
    405405      _phase = true;
    406406      for (NodeIt n(_graph); n != INVALID; ++n) {
    407         _excess->set(n, 0);
     407        (*_excess)[n] = 0;
    408408      }
    409409
    … …  
    418418
    419419      std::vector<Node> queue;
    420       reached.set(_source, true);
     420      reached[_source] = true;
    421421
    422422      queue.push_back(_target);
    423       reached.set(_target, true);
     423      reached[_target] = true;
    424424      while (!queue.empty()) {
    425425        _level->initNewLevel();
    … …  
    430430            Node u = _graph.source(e);
    431431            if (!reached[u] && _tolerance.positive((*_capacity)[e])) {
    432               reached.set(u, true);
     432              reached[u] = true;
    433433              _level->initAddItem(u);
    434434              nqueue.push_back(u);
    … …  
    445445          if ((*_level)[u] == _level->maxLevel()) continue;
    446446          _flow->set(e, (*_capacity)[e]);
    447           _excess->set(u, (*_excess)[u] + (*_capacity)[e]);
     447          (*_excess)[u] += (*_capacity)[e];
    448448          if (u != _target && !_level->active(u)) {
    449449            _level->activate(u);
    … …  
    479479        }
    480480        if (excess < 0 && n != _source) return false;
    481         _excess->set(n, excess);
     481        (*_excess)[n] = excess;
    482482      }
    483483
    … …  
    488488
    489489      std::vector<Node> queue;
    490       reached.set(_source, true);
     490      reached[_source] = true;
    491491
    492492      queue.push_back(_target);
    493       reached.set(_target, true);
     493      reached[_target] = true;
    494494      while (!queue.empty()) {
    495495        _level->initNewLevel();
    … …  
    501501            if (!reached[u] &&
    502502                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    503               reached.set(u, true);
     503              reached[u] = true;
    504504              _level->initAddItem(u);
    505505              nqueue.push_back(u);
    … …  
    509509            Node v = _graph.target(e);
    510510            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    511               reached.set(v, true);
     511              reached[v] = true;
    512512              _level->initAddItem(v);
    513513              nqueue.push_back(v);
    … …  
    525525          if ((*_level)[u] == _level->maxLevel()) continue;
    526526          _flow->set(e, (*_capacity)[e]);
    527           _excess->set(u, (*_excess)[u] + rem);
     527          (*_excess)[u] += rem;
    528528          if (u != _target && !_level->active(u)) {
    529529            _level->activate(u);
    … …  
    537537          if ((*_level)[v] == _level->maxLevel()) continue;
    538538          _flow->set(e, 0);
    539           _excess->set(v, (*_excess)[v] + rem);
     539          (*_excess)[v] += rem;
    540540          if (v != _target && !_level->active(v)) {
    541541            _level->activate(v);
    … …  
    578578              if (!_tolerance.less(rem, excess)) {
    579579                _flow->set(e, (*_flow)[e] + excess);
    580                 _excess->set(v, (*_excess)[v] + excess);
     580                (*_excess)[v] += excess;
    581581                excess = 0;
    582582                goto no_more_push_1;
    583583              } else {
    584584                excess -= rem;
    585                 _excess->set(v, (*_excess)[v] + rem);
     585                (*_excess)[v] += rem;
    586586                _flow->set(e, (*_capacity)[e]);
    587587              }
    … …  
    601601              if (!_tolerance.less(rem, excess)) {
    602602                _flow->set(e, (*_flow)[e] - excess);
    603                 _excess->set(v, (*_excess)[v] + excess);
     603                (*_excess)[v] += excess;
    604604                excess = 0;
    605605                goto no_more_push_1;
    606606              } else {
    607607                excess -= rem;
    608                 _excess->set(v, (*_excess)[v] + rem);
     608                (*_excess)[v] += rem;
    609609                _flow->set(e, 0);
    610610              }
    … …  
    616616        no_more_push_1:
    617617
    618           _excess->set(n, excess);
     618          (*_excess)[n] = excess;
    619619
    620620          if (excess != 0) {
    … …  
    651651              if (!_tolerance.less(rem, excess)) {
    652652                _flow->set(e, (*_flow)[e] + excess);
    653                 _excess->set(v, (*_excess)[v] + excess);
     653                (*_excess)[v] += excess;
    654654                excess = 0;
    655655                goto no_more_push_2;
    656656              } else {
    657657                excess -= rem;
    658                 _excess->set(v, (*_excess)[v] + rem);
     658                (*_excess)[v] += rem;
    659659                _flow->set(e, (*_capacity)[e]);
    660660              }
    … …  
    674674              if (!_tolerance.less(rem, excess)) {
    675675                _flow->set(e, (*_flow)[e] - excess);
    676                 _excess->set(v, (*_excess)[v] + excess);
     676                (*_excess)[v] += excess;
    677677                excess = 0;
    678678                goto no_more_push_2;
    679679              } else {
    680680                excess -= rem;
    681                 _excess->set(v, (*_excess)[v] + rem);
     681                (*_excess)[v] += rem;
    682682                _flow->set(e, 0);
    683683              }
    … …  
    689689        no_more_push_2:
    690690
    691           _excess->set(n, excess);
     691          (*_excess)[n] = excess;
    692692
    693693          if (excess != 0) {
    … …  
    732732      typename Digraph::template NodeMap<bool> reached(_graph);
    733733      for (NodeIt n(_graph); n != INVALID; ++n) {
    734         reached.set(n, (*_level)[n] < _level->maxLevel());
     734        reached[n] = (*_level)[n] < _level->maxLevel();
    735735      }
    736736
    … …  
    740740      std::vector<Node> queue;
    741741      queue.push_back(_source);
    742       reached.set(_source, true);
     742      reached[_source] = true;
    743743
    744744      while (!queue.empty()) {
    … …  
    750750            Node v = _graph.target(e);
    751751            if (!reached[v] && _tolerance.positive((*_flow)[e])) {
    752               reached.set(v, true);
     752              reached[v] = true;
    753753              _level->initAddItem(v);
    754754              nqueue.push_back(v);
    … …  
    759759            if (!reached[u] &&
    760760                _tolerance.positive((*_capacity)[e] - (*_flow)[e])) {
    761               reached.set(u, true);
     761              reached[u] = true;
    762762              _level->initAddItem(u);
    763763              nqueue.push_back(u);
    … …  
    793793            if (!_tolerance.less(rem, excess)) {
    794794              _flow->set(e, (*_flow)[e] + excess);
    795               _excess->set(v, (*_excess)[v] + excess);
     795              (*_excess)[v] += excess;
    796796              excess = 0;
    797797              goto no_more_push;
    798798            } else {
    799799              excess -= rem;
    800               _excess->set(v, (*_excess)[v] + rem);
     800              (*_excess)[v] += rem;
    801801              _flow->set(e, (*_capacity)[e]);
    802802            }
    … …  
    816816            if (!_tolerance.less(rem, excess)) {
    817817              _flow->set(e, (*_flow)[e] - excess);
    818               _excess->set(v, (*_excess)[v] + excess);
     818              (*_excess)[v] += excess;
    819819              excess = 0;
    820820              goto no_more_push;
    821821            } else {
    822822              excess -= rem;
    823               _excess->set(v, (*_excess)[v] + rem);
     823              (*_excess)[v] += rem;
    824824              _flow->set(e, 0);
    825825            }
    … …  
    831831      no_more_push:
    832832
    833         _excess->set(n, excess);
     833        (*_excess)[n] = excess;
    834834
    835835        if (excess != 0) {
Note: See TracChangeset for help on using the changeset viewer.