COIN-OR::LEMON - Graph Library

Changeset 767:11c946fa8d13 in lemon-1.2 for lemon


Ignore:
Timestamp:
08/11/09 22:52:35 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Simplify comparisons in min mean cycle classes (#179)
using extreme INF values instead of bool flags.

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/hartmann_orlin.h

    r766 r767  
    151151    struct PathData
    152152    {
    153       bool found;
    154153      LargeValue dist;
    155154      Arc pred;
    156       PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
    157         found(f), dist(d), pred(p) {}
     155      PathData(LargeValue d, Arc p = INVALID) :
     156        dist(d), pred(p) {}
    158157    };
    159158
     
    191190
    192191    Tolerance _tolerance;
     192
     193    // Infinite constant
     194    const LargeValue INF;
    193195
    194196  public:
     
    246248      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    247249      _best_found(false), _best_length(0), _best_size(1),
    248       _cycle_path(NULL), _local_path(false), _data(digraph)
     250      _cycle_path(NULL), _local_path(false), _data(digraph),
     251      INF(std::numeric_limits<LargeValue>::has_infinity ?
     252          std::numeric_limits<LargeValue>::infinity() :
     253          std::numeric_limits<LargeValue>::max())
    249254    {}
    250255
     
    473478      }     
    474479      for (int i = 0; i < n; ++i) {
    475         _data[(*_nodes)[i]].resize(n + 1);
     480        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
    476481      }
    477482      return true;
     
    483488    void processRounds() {
    484489      Node start = (*_nodes)[0];
    485       _data[start][0] = PathData(true, 0);
     490      _data[start][0] = PathData(0);
    486491      _process.clear();
    487492      _process.push_back(start);
     
    518523          v = _gr.target(e);
    519524          d = _data[u][k-1].dist + _length[e];
    520           if (!_data[v][k].found) {
    521             next.push_back(v);
    522             _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
    523           }
    524           else if (_tolerance.less(d, _data[v][k].dist)) {
    525             _data[v][k] = PathData(true, d, e);
     525          if (_tolerance.less(d, _data[v][k].dist)) {
     526            if (_data[v][k].dist == INF) next.push_back(v);
     527            _data[v][k] = PathData(d, e);
    526528          }
    527529        }
     
    541543          v = _gr.target(e);
    542544          d = _data[u][k-1].dist + _length[e];
    543           if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
    544             _data[v][k] = PathData(true, d, e);
     545          if (_tolerance.less(d, _data[v][k].dist)) {
     546            _data[v][k] = PathData(d, e);
    545547          }
    546548        }
     
    562564      for (int i = 0; i < n; ++i) {
    563565        u = (*_nodes)[i];
    564         if (!_data[u][k].found) continue;
     566        if (_data[u][k].dist == INF) continue;
    565567        for (int j = k; j >= 0; --j) {
    566568          if (level[u].first == i && level[u].second > 0) {
     
    587589        for (int i = 0; i < n; ++i) {
    588590          u = (*_nodes)[i];
    589           pi[u] = std::numeric_limits<LargeValue>::max();
     591          pi[u] = INF;
    590592          for (int j = 0; j <= k; ++j) {
    591             d = _data[u][j].dist * _curr_size - j * _curr_length;
    592             if (_data[u][j].found && _tolerance.less(d, pi[u])) {
    593               pi[u] = d;
     593            if (_data[u][j].dist < INF) {
     594              d = _data[u][j].dist * _curr_size - j * _curr_length;
     595              if (_tolerance.less(d, pi[u])) pi[u] = d;
    594596            }
    595597          }
  • lemon/howard.h

    r764 r767  
    179179    Tolerance _tolerance;
    180180 
     181    // Infinite constant
     182    const LargeValue INF;
     183
    181184  public:
    182185 
     
    231234    Howard( const Digraph &digraph,
    232235            const LengthMap &length ) :
    233       _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
     236      _gr(digraph), _length(length), _best_found(false),
     237      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
    234238      _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
    235       _comp(digraph), _in_arcs(digraph)
     239      _comp(digraph), _in_arcs(digraph),
     240      INF(std::numeric_limits<LargeValue>::has_infinity ?
     241          std::numeric_limits<LargeValue>::infinity() :
     242          std::numeric_limits<LargeValue>::max())
    236243    {}
    237244
     
    308315        }
    309316        // Update the best cycle (global minimum mean cycle)
    310         if ( !_best_found || (_curr_found &&
     317        if ( _curr_found && (!_best_found ||
    311318             _curr_length * _best_size < _best_length * _curr_size) ) {
    312319          _best_found = true;
     
    447454      }
    448455      for (int i = 0; i < int(_nodes->size()); ++i) {
    449         _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
     456        _dist[(*_nodes)[i]] = INF;
    450457      }
    451458      Node u, v;
  • lemon/karp.h

    r765 r767  
    149149    struct PathData
    150150    {
    151       bool found;
    152151      LargeValue dist;
    153152      Arc pred;
    154       PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
    155         found(f), dist(d), pred(p) {}
     153      PathData(LargeValue d, Arc p = INVALID) :
     154        dist(d), pred(p) {}
    156155    };
    157156
     
    187186
    188187    Tolerance _tolerance;
     188   
     189    // Infinite constant
     190    const LargeValue INF;
    189191
    190192  public:
     
    242244      _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    243245      _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
    244       _cycle_path(NULL), _local_path(false), _data(digraph)
     246      _cycle_path(NULL), _local_path(false), _data(digraph),
     247      INF(std::numeric_limits<LargeValue>::has_infinity ?
     248          std::numeric_limits<LargeValue>::infinity() :
     249          std::numeric_limits<LargeValue>::max())
    245250    {}
    246251
     
    459464      }     
    460465      for (int i = 0; i < n; ++i) {
    461         _data[(*_nodes)[i]].resize(n + 1);
     466        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
    462467      }
    463468      return true;
     
    469474    void processRounds() {
    470475      Node start = (*_nodes)[0];
    471       _data[start][0] = PathData(true, 0);
     476      _data[start][0] = PathData(0);
    472477      _process.clear();
    473478      _process.push_back(start);
     
    494499          v = _gr.target(e);
    495500          d = _data[u][k-1].dist + _length[e];
    496           if (!_data[v][k].found) {
    497             next.push_back(v);
    498             _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
    499           }
    500           else if (_tolerance.less(d, _data[v][k].dist)) {
    501             _data[v][k] = PathData(true, d, e);
     501          if (_tolerance.less(d, _data[v][k].dist)) {
     502            if (_data[v][k].dist == INF) next.push_back(v);
     503            _data[v][k] = PathData(d, e);
    502504          }
    503505        }
     
    517519          v = _gr.target(e);
    518520          d = _data[u][k-1].dist + _length[e];
    519           if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
    520             _data[v][k] = PathData(true, d, e);
     521          if (_tolerance.less(d, _data[v][k].dist)) {
     522            _data[v][k] = PathData(d, e);
    521523          }
    522524        }
     
    529531      for (int i = 0; i < n; ++i) {
    530532        Node u = (*_nodes)[i];
    531         if (!_data[u][n].found) continue;
     533        if (_data[u][n].dist == INF) continue;
    532534        LargeValue length, max_length = 0;
    533535        int size, max_size = 1;
    534536        bool found_curr = false;
    535537        for (int k = 0; k < n; ++k) {
    536           if (!_data[u][k].found) continue;
     538          if (_data[u][k].dist == INF) continue;
    537539          length = _data[u][n].dist - _data[u][k].dist;
    538540          size = n - k;
Note: See TracChangeset for help on using the changeset viewer.