COIN-OR::LEMON - Graph Library

Changeset 814:11c946fa8d13 in lemon for lemon/hartmann_orlin.h


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.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/hartmann_orlin.h

    r813 r814  
    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          }
Note: See TracChangeset for help on using the changeset viewer.