Simplify comparisons in min mean cycle classes (#179)
authorPeter Kovacs <kpeter@inf.elte.hu>
Tue, 11 Aug 2009 22:52:35 +0200
changeset 81411c946fa8d13
parent 813 97744b6dabf8
child 815 0a42883c8221
Simplify comparisons in min mean cycle classes (#179)
using extreme INF values instead of bool flags.
lemon/hartmann_orlin.h
lemon/howard.h
lemon/karp.h
     1.1 --- a/lemon/hartmann_orlin.h	Tue Aug 11 21:53:39 2009 +0200
     1.2 +++ b/lemon/hartmann_orlin.h	Tue Aug 11 22:52:35 2009 +0200
     1.3 @@ -150,11 +150,10 @@
     1.4      // Data sturcture for path data
     1.5      struct PathData
     1.6      {
     1.7 -      bool found;
     1.8        LargeValue dist;
     1.9        Arc pred;
    1.10 -      PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
    1.11 -        found(f), dist(d), pred(p) {}
    1.12 +      PathData(LargeValue d, Arc p = INVALID) :
    1.13 +        dist(d), pred(p) {}
    1.14      };
    1.15  
    1.16      typedef typename Digraph::template NodeMap<std::vector<PathData> >
    1.17 @@ -191,6 +190,9 @@
    1.18  
    1.19      Tolerance _tolerance;
    1.20  
    1.21 +    // Infinite constant
    1.22 +    const LargeValue INF;
    1.23 +
    1.24    public:
    1.25  
    1.26      /// \name Named Template Parameters
    1.27 @@ -245,7 +247,10 @@
    1.28                     const LengthMap &length ) :
    1.29        _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    1.30        _best_found(false), _best_length(0), _best_size(1),
    1.31 -      _cycle_path(NULL), _local_path(false), _data(digraph)
    1.32 +      _cycle_path(NULL), _local_path(false), _data(digraph),
    1.33 +      INF(std::numeric_limits<LargeValue>::has_infinity ?
    1.34 +          std::numeric_limits<LargeValue>::infinity() :
    1.35 +          std::numeric_limits<LargeValue>::max())
    1.36      {}
    1.37  
    1.38      /// Destructor.
    1.39 @@ -472,7 +477,7 @@
    1.40          return false;
    1.41        }      
    1.42        for (int i = 0; i < n; ++i) {
    1.43 -        _data[(*_nodes)[i]].resize(n + 1);
    1.44 +        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
    1.45        }
    1.46        return true;
    1.47      }
    1.48 @@ -482,7 +487,7 @@
    1.49      // node to node v containing exactly k arcs.
    1.50      void processRounds() {
    1.51        Node start = (*_nodes)[0];
    1.52 -      _data[start][0] = PathData(true, 0);
    1.53 +      _data[start][0] = PathData(0);
    1.54        _process.clear();
    1.55        _process.push_back(start);
    1.56  
    1.57 @@ -517,12 +522,9 @@
    1.58            e = _out_arcs[u][j];
    1.59            v = _gr.target(e);
    1.60            d = _data[u][k-1].dist + _length[e];
    1.61 -          if (!_data[v][k].found) {
    1.62 -            next.push_back(v);
    1.63 -            _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
    1.64 -          }
    1.65 -          else if (_tolerance.less(d, _data[v][k].dist)) {
    1.66 -            _data[v][k] = PathData(true, d, e);
    1.67 +          if (_tolerance.less(d, _data[v][k].dist)) {
    1.68 +            if (_data[v][k].dist == INF) next.push_back(v);
    1.69 +            _data[v][k] = PathData(d, e);
    1.70            }
    1.71          }
    1.72        }
    1.73 @@ -540,8 +542,8 @@
    1.74            e = _out_arcs[u][j];
    1.75            v = _gr.target(e);
    1.76            d = _data[u][k-1].dist + _length[e];
    1.77 -          if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
    1.78 -            _data[v][k] = PathData(true, d, e);
    1.79 +          if (_tolerance.less(d, _data[v][k].dist)) {
    1.80 +            _data[v][k] = PathData(d, e);
    1.81            }
    1.82          }
    1.83        }
    1.84 @@ -561,7 +563,7 @@
    1.85        _curr_found = false;
    1.86        for (int i = 0; i < n; ++i) {
    1.87          u = (*_nodes)[i];
    1.88 -        if (!_data[u][k].found) continue;
    1.89 +        if (_data[u][k].dist == INF) continue;
    1.90          for (int j = k; j >= 0; --j) {
    1.91            if (level[u].first == i && level[u].second > 0) {
    1.92              // A cycle is found
    1.93 @@ -586,11 +588,11 @@
    1.94          // Find node potentials
    1.95          for (int i = 0; i < n; ++i) {
    1.96            u = (*_nodes)[i];
    1.97 -          pi[u] = std::numeric_limits<LargeValue>::max();
    1.98 +          pi[u] = INF;
    1.99            for (int j = 0; j <= k; ++j) {
   1.100 -            d = _data[u][j].dist * _curr_size - j * _curr_length;
   1.101 -            if (_data[u][j].found && _tolerance.less(d, pi[u])) {
   1.102 -              pi[u] = d;
   1.103 +            if (_data[u][j].dist < INF) {
   1.104 +              d = _data[u][j].dist * _curr_size - j * _curr_length;
   1.105 +              if (_tolerance.less(d, pi[u])) pi[u] = d;
   1.106              }
   1.107            }
   1.108          }
     2.1 --- a/lemon/howard.h	Tue Aug 11 21:53:39 2009 +0200
     2.2 +++ b/lemon/howard.h	Tue Aug 11 22:52:35 2009 +0200
     2.3 @@ -178,6 +178,9 @@
     2.4  
     2.5      Tolerance _tolerance;
     2.6    
     2.7 +    // Infinite constant
     2.8 +    const LargeValue INF;
     2.9 +
    2.10    public:
    2.11    
    2.12      /// \name Named Template Parameters
    2.13 @@ -230,9 +233,13 @@
    2.14      /// \param length The lengths (costs) of the arcs.
    2.15      Howard( const Digraph &digraph,
    2.16              const LengthMap &length ) :
    2.17 -      _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
    2.18 +      _gr(digraph), _length(length), _best_found(false),
    2.19 +      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
    2.20        _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
    2.21 -      _comp(digraph), _in_arcs(digraph)
    2.22 +      _comp(digraph), _in_arcs(digraph),
    2.23 +      INF(std::numeric_limits<LargeValue>::has_infinity ?
    2.24 +          std::numeric_limits<LargeValue>::infinity() :
    2.25 +          std::numeric_limits<LargeValue>::max())
    2.26      {}
    2.27  
    2.28      /// Destructor.
    2.29 @@ -307,7 +314,7 @@
    2.30            if (!computeNodeDistances()) break;
    2.31          }
    2.32          // Update the best cycle (global minimum mean cycle)
    2.33 -        if ( !_best_found || (_curr_found &&
    2.34 +        if ( _curr_found && (!_best_found ||
    2.35               _curr_length * _best_size < _best_length * _curr_size) ) {
    2.36            _best_found = true;
    2.37            _best_length = _curr_length;
    2.38 @@ -446,7 +453,7 @@
    2.39          return false;
    2.40        }
    2.41        for (int i = 0; i < int(_nodes->size()); ++i) {
    2.42 -        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
    2.43 +        _dist[(*_nodes)[i]] = INF;
    2.44        }
    2.45        Node u, v;
    2.46        Arc e;
     3.1 --- a/lemon/karp.h	Tue Aug 11 21:53:39 2009 +0200
     3.2 +++ b/lemon/karp.h	Tue Aug 11 22:52:35 2009 +0200
     3.3 @@ -148,11 +148,10 @@
     3.4      // Data sturcture for path data
     3.5      struct PathData
     3.6      {
     3.7 -      bool found;
     3.8        LargeValue dist;
     3.9        Arc pred;
    3.10 -      PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
    3.11 -        found(f), dist(d), pred(p) {}
    3.12 +      PathData(LargeValue d, Arc p = INVALID) :
    3.13 +        dist(d), pred(p) {}
    3.14      };
    3.15  
    3.16      typedef typename Digraph::template NodeMap<std::vector<PathData> >
    3.17 @@ -186,6 +185,9 @@
    3.18      std::vector<Node> _process;
    3.19  
    3.20      Tolerance _tolerance;
    3.21 +    
    3.22 +    // Infinite constant
    3.23 +    const LargeValue INF;
    3.24  
    3.25    public:
    3.26  
    3.27 @@ -241,7 +243,10 @@
    3.28            const LengthMap &length ) :
    3.29        _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
    3.30        _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
    3.31 -      _cycle_path(NULL), _local_path(false), _data(digraph)
    3.32 +      _cycle_path(NULL), _local_path(false), _data(digraph),
    3.33 +      INF(std::numeric_limits<LargeValue>::has_infinity ?
    3.34 +          std::numeric_limits<LargeValue>::infinity() :
    3.35 +          std::numeric_limits<LargeValue>::max())
    3.36      {}
    3.37  
    3.38      /// Destructor.
    3.39 @@ -458,7 +463,7 @@
    3.40          return false;
    3.41        }      
    3.42        for (int i = 0; i < n; ++i) {
    3.43 -        _data[(*_nodes)[i]].resize(n + 1);
    3.44 +        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
    3.45        }
    3.46        return true;
    3.47      }
    3.48 @@ -468,7 +473,7 @@
    3.49      // node to node v containing exactly k arcs.
    3.50      void processRounds() {
    3.51        Node start = (*_nodes)[0];
    3.52 -      _data[start][0] = PathData(true, 0);
    3.53 +      _data[start][0] = PathData(0);
    3.54        _process.clear();
    3.55        _process.push_back(start);
    3.56  
    3.57 @@ -493,12 +498,9 @@
    3.58            e = _out_arcs[u][j];
    3.59            v = _gr.target(e);
    3.60            d = _data[u][k-1].dist + _length[e];
    3.61 -          if (!_data[v][k].found) {
    3.62 -            next.push_back(v);
    3.63 -            _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
    3.64 -          }
    3.65 -          else if (_tolerance.less(d, _data[v][k].dist)) {
    3.66 -            _data[v][k] = PathData(true, d, e);
    3.67 +          if (_tolerance.less(d, _data[v][k].dist)) {
    3.68 +            if (_data[v][k].dist == INF) next.push_back(v);
    3.69 +            _data[v][k] = PathData(d, e);
    3.70            }
    3.71          }
    3.72        }
    3.73 @@ -516,8 +518,8 @@
    3.74            e = _out_arcs[u][j];
    3.75            v = _gr.target(e);
    3.76            d = _data[u][k-1].dist + _length[e];
    3.77 -          if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
    3.78 -            _data[v][k] = PathData(true, d, e);
    3.79 +          if (_tolerance.less(d, _data[v][k].dist)) {
    3.80 +            _data[v][k] = PathData(d, e);
    3.81            }
    3.82          }
    3.83        }
    3.84 @@ -528,12 +530,12 @@
    3.85        int n = _nodes->size();
    3.86        for (int i = 0; i < n; ++i) {
    3.87          Node u = (*_nodes)[i];
    3.88 -        if (!_data[u][n].found) continue;
    3.89 +        if (_data[u][n].dist == INF) continue;
    3.90          LargeValue length, max_length = 0;
    3.91          int size, max_size = 1;
    3.92          bool found_curr = false;
    3.93          for (int k = 0; k < n; ++k) {
    3.94 -          if (!_data[u][k].found) continue;
    3.95 +          if (_data[u][k].dist == INF) continue;
    3.96            length = _data[u][n].dist - _data[u][k].dist;
    3.97            size = n - k;
    3.98            if (!found_curr || length * max_size > max_length * size) {