COIN-OR::LEMON - Graph Library

Changeset 814:11c946fa8d13 in lemon for lemon/karp.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/karp.h

    r812 r814  
    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.