COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 877:fe80a8145653 in lemon


Ignore:
Timestamp:
11/12/09 23:45:15 (15 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.
Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • lemon/capacity_scaling.h

    r876 r877  
    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;

  • lemon/network_simplex.h

    r835 r877  
    165165
    166166    typedef std::vector<int> IntVector;
    167     typedef std::vector<bool> BoolVector;
     167    typedef std::vector<char> CharVector;
    168168    typedef std::vector<Value> ValueVector;
    169169    typedef std::vector<Cost> CostVector;
    … …  
    213213    IntVector _last_succ;
    214214    IntVector _dirty_revs;
    215     BoolVector _forward;
    216     IntVector _state;
     215    CharVector _forward;
     216    CharVector _state;
    217217    int _root;
    218218
    … …  
    222222    int stem, par_stem, new_stem;
    223223    Value delta;
     224   
     225    const Value MAX;
    224226
    225227  public:
    … …  
    243245      const IntVector  &_target;
    244246      const CostVector &_cost;
    245       const IntVector &_state;
     247      const CharVector &_state;
    246248      const CostVector &_pi;
    247249      int &_in_arc;
    … …  
    295297      const IntVector  &_target;
    296298      const CostVector &_cost;
    297       const IntVector &_state;
     299      const CharVector &_state;
    298300      const CostVector &_pi;
    299301      int &_in_arc;
    … …  
    334336      const IntVector  &_target;
    335337      const CostVector &_cost;
    336       const IntVector &_state;
     338      const CharVector &_state;
    337339      const CostVector &_pi;
    338340      int &_in_arc;
    … …  
    407409      const IntVector  &_target;
    408410      const CostVector &_cost;
    409       const IntVector &_state;
     411      const CharVector &_state;
    410412      const CostVector &_pi;
    411413      int &_in_arc;
    … …  
    510512      const IntVector  &_target;
    511513      const CostVector &_cost;
    512       const IntVector &_state;
     514      const CharVector &_state;
    513515      const CostVector &_pi;
    514516      int &_in_arc;
    … …  
    632634    NetworkSimplex(const GR& graph, bool arc_mixing = false) :
    633635      _graph(graph), _node_id(graph), _arc_id(graph),
     636      MAX(std::numeric_limits<Value>::max()),
    634637      INF(std::numeric_limits<Value>::has_infinity ?
    635           std::numeric_limits<Value>::infinity() :
    636           std::numeric_limits<Value>::max())
     638          std::numeric_limits<Value>::infinity() : MAX)
    637639    {
    638640      // Check the value types
    … …  
    10211023          Value c = _lower[i];
    10221024          if (c >= 0) {
    1023             _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1025            _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF;
    10241026          } else {
    1025             _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1027            _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF;
    10261028          }
    10271029          _supply[_source[i]] -= c;
    … …  
    12151217        e = _pred[u];
    12161218        d = _forward[u] ?
    1217           _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
     1219          _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]);
    12181220        if (d < delta) {
    12191221          delta = d;
    … …  
    12261228        e = _pred[u];
    12271229        d = _forward[u] ?
    1228           (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
     1230          (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e];
    12291231        if (d <= delta) {
    12301232          delta = d;
    … …  
    14251427        findJoinNode();
    14261428        bool change = findLeavingArc();
    1427         if (delta >= INF) return UNBOUNDED;
     1429        if (delta >= MAX) return UNBOUNDED;
    14281430        changeFlow(change);
    14291431        if (change) {
Note: See TracChangeset for help on using the changeset viewer.