COIN-OR::LEMON - Graph Library

Changeset 811:fe80a8145653 in lemon-1.2 for lemon/network_simplex.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/network_simplex.h

    r788 r811  
    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.