COIN-OR::LEMON - Graph Library

Changeset 811:fe80a8145653 in lemon-1.2 for lemon/capacity_scaling.h


Ignore:
Timestamp:
11/12/09 23:45:15 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Rebase:
35386664633435303433383038316635626132313231366463363862653565653936303733646463
Message:

Small implementation improvements in MCF algorithms (#180)

  • Handle max() as infinite value (not only infinity()).
  • Better GEQ handling in CapacityScaling?.
  • Skip the unnecessary saturating operations in the first phase in CapacityScaling?.
  • Use vector<char> instead of vector<bool> and vector<int> if it is possible and it proved to be usually faster.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/capacity_scaling.h

    r810 r811  
    134134
    135135    typedef std::vector<int> IntVector;
    136     typedef std::vector<bool> BoolVector;
     136    typedef std::vector<char> BoolVector;
    137137    typedef std::vector<Value> ValueVector;
    138138    typedef std::vector<Cost> CostVector;
     
    197197
    198198      int _node_num;
     199      bool _geq;
    199200      const IntVector &_first_out;
    200201      const IntVector &_target;
     
    211212
    212213      ResidualDijkstra(CapacityScaling& cs) :
    213         _node_num(cs._node_num), _first_out(cs._first_out),
    214         _target(cs._target), _cost(cs._cost), _res_cap(cs._res_cap),
    215         _excess(cs._excess), _pi(cs._pi), _pred(cs._pred),
    216         _dist(cs._node_num)
     214        _node_num(cs._node_num), _geq(cs._sum_supply < 0),
     215        _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
     216        _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
     217        _pred(cs._pred), _dist(cs._node_num)
    217218      {}
    218219
     
    233234
    234235          // Traverse outgoing residual arcs
    235           for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
     236          int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
     237          for (int a = _first_out[u]; a != last_out; ++a) {
    236238            if (_res_cap[a] < delta) continue;
    237239            v = _target[a];
     
    688690      if (_sum_supply > 0) return INFEASIBLE;
    689691     
    690       // Initialize maps
     692      // Initialize vectors
    691693      for (int i = 0; i != _root; ++i) {
    692694        _pi[i] = 0;
     
    695697
    696698      // Remove non-zero lower bounds
     699      const Value MAX = std::numeric_limits<Value>::max();
     700      int last_out;
    697701      if (_have_lower) {
    698702        for (int i = 0; i != _root; ++i) {
    699           for (int j = _first_out[i]; j != _first_out[i+1]; ++j) {
     703          last_out = _first_out[i+1];
     704          for (int j = _first_out[i]; j != last_out; ++j) {
    700705            if (_forward[j]) {
    701706              Value c = _lower[j];
    702707              if (c >= 0) {
    703                 _res_cap[j] = _upper[j] < INF ? _upper[j] - c : INF;
     708                _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
    704709              } else {
    705                 _res_cap[j] = _upper[j] < INF + c ? _upper[j] - c : INF;
     710                _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
    706711              }
    707712              _excess[i] -= c;
     
    719724
    720725      // Handle negative costs
    721       for (int u = 0; u != _root; ++u) {
    722         for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
    723           Value rc = _res_cap[a];
    724           if (_cost[a] < 0 && rc > 0) {
    725             if (rc == INF) return UNBOUNDED;
    726             _excess[u] -= rc;
    727             _excess[_target[a]] += rc;
    728             _res_cap[a] = 0;
    729             _res_cap[_reverse[a]] += rc;
     726      for (int i = 0; i != _root; ++i) {
     727        last_out = _first_out[i+1] - 1;
     728        for (int j = _first_out[i]; j != last_out; ++j) {
     729          Value rc = _res_cap[j];
     730          if (_cost[j] < 0 && rc > 0) {
     731            if (rc >= MAX) return UNBOUNDED;
     732            _excess[i] -= rc;
     733            _excess[_target[j]] += rc;
     734            _res_cap[j] = 0;
     735            _res_cap[_reverse[j]] += rc;
    730736          }
    731737        }
     
    737743        _excess[_root] = -_sum_supply;
    738744        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
    739           int u = _target[a];
    740           if (_excess[u] < 0) {
    741             _res_cap[a] = -_excess[u] + 1;
    742           } else {
    743             _res_cap[a] = 1;
    744           }
    745           _res_cap[_reverse[a]] = 0;
     745          int ra = _reverse[a];
     746          _res_cap[a] = -_sum_supply + 1;
     747          _res_cap[ra] = 0;
    746748          _cost[a] = 0;
    747           _cost[_reverse[a]] = 0;
     749          _cost[ra] = 0;
    748750        }
    749751      } else {
     
    751753        _excess[_root] = 0;
    752754        for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
     755          int ra = _reverse[a];
    753756          _res_cap[a] = 1;
    754           _res_cap[_reverse[a]] = 0;
     757          _res_cap[ra] = 0;
    755758          _cost[a] = 0;
    756           _cost[_reverse[a]] = 0;
     759          _cost[ra] = 0;
    757760        }
    758761      }
     
    763766        Value max_sup = 0, max_dem = 0;
    764767        for (int i = 0; i != _node_num; ++i) {
    765           if ( _excess[i] > max_sup) max_sup =  _excess[i];
    766           if (-_excess[i] > max_dem) max_dem = -_excess[i];
     768          Value ex = _excess[i];
     769          if ( ex > max_sup) max_sup =  ex;
     770          if (-ex > max_dem) max_dem = -ex;
    767771        }
    768772        Value max_cap = 0;
     
    790794      // Handle non-zero lower bounds
    791795      if (_have_lower) {
    792         for (int j = 0; j != _res_arc_num - _node_num + 1; ++j) {
     796        int limit = _first_out[_root];
     797        for (int j = 0; j != limit; ++j) {
    793798          if (!_forward[j]) _res_cap[j] += _lower[j];
    794799        }
     
    813818      while (true) {
    814819        // Saturate all arcs not satisfying the optimality condition
     820        int last_out;
    815821        for (int u = 0; u != _node_num; ++u) {
    816           for (int a = _first_out[u]; a != _first_out[u+1]; ++a) {
     822          last_out = _sum_supply < 0 ?
     823            _first_out[u+1] : _first_out[u+1] - 1;
     824          for (int a = _first_out[u]; a != last_out; ++a) {
    817825            int v = _target[a];
    818826            Cost c = _cost[a] + _pi[u] - _pi[v];
     
    831839        _deficit_nodes.clear();
    832840        for (int u = 0; u != _node_num; ++u) {
    833           if (_excess[u] >=  _delta) _excess_nodes.push_back(u);
    834           if (_excess[u] <= -_delta) _deficit_nodes.push_back(u);
     841          Value ex = _excess[u];
     842          if (ex >=  _delta) _excess_nodes.push_back(u);
     843          if (ex <= -_delta) _deficit_nodes.push_back(u);
    835844        }
    836845        int next_node = 0, next_def_node = 0;
Note: See TracChangeset for help on using the changeset viewer.