Changeset 767:11c946fa8d13 in lemon-main

Timestamp:

08/11/09 22:52:35 (15 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:

• hartmann_orlin.h (modified) (9 diffs)
• howard.h (modified) (4 diffs)
• karp.h (modified) (8 diffs)

lemon/hartmann_orlin.h

@@ -151 +151 @@
     struct PathData
     {
-      bool found;
       LargeValue dist;
       Arc pred;
-      PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
-        found(f), dist(d), pred(p) {}
+      PathData(LargeValue d, Arc p = INVALID) :
+        dist(d), pred(p) {}
     };
 
@@ -191 +190 @@
 
     Tolerance _tolerance;
+
+    // Infinite constant
+    const LargeValue INF;
 
   public:
@@ -246 +248 @@
       _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
       _best_found(false), _best_length(0), _best_size(1),
-      _cycle_path(NULL), _local_path(false), _data(digraph)
+      _cycle_path(NULL), _local_path(false), _data(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
     {}
 
@@ -473 +478 @@
       }      
       for (int i = 0; i < n; ++i) {
-        _data[(*_nodes)[i]].resize(n + 1);
+        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
       }
       return true;
@@ -483 +488 @@
     void processRounds() {
       Node start = (*_nodes)[0];
-      _data[start][0] = PathData(true, 0);
+      _data[start][0] = PathData(0);
       _process.clear();
       _process.push_back(start);
@@ -518 +523 @@
           v = _gr.target(e);
           d = _data[u][k-1].dist + _length[e];
-          if (!_data[v][k].found) {
-            next.push_back(v);
-            _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
-          }
-          else if (_tolerance.less(d, _data[v][k].dist)) {
-            _data[v][k] = PathData(true, d, e);
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            if (_data[v][k].dist == INF) next.push_back(v);
+            _data[v][k] = PathData(d, e);
           }
         }
@@ -541 +543 @@
           v = _gr.target(e);
           d = _data[u][k-1].dist + _length[e];
-          if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
-            _data[v][k] = PathData(true, d, e);
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            _data[v][k] = PathData(d, e);
           }
         }
@@ -562 +564 @@
       for (int i = 0; i < n; ++i) {
         u = (*_nodes)[i];
-        if (!_data[u][k].found) continue;
+        if (_data[u][k].dist == INF) continue;
         for (int j = k; j >= 0; --j) {
           if (level[u].first == i && level[u].second > 0) {
@@ -587 +589 @@
         for (int i = 0; i < n; ++i) {
           u = (*_nodes)[i];
-          pi[u] = std::numeric_limits<LargeValue>::max();
+          pi[u] = INF;
           for (int j = 0; j <= k; ++j) {
-            d = _data[u][j].dist * _curr_size - j * _curr_length;
-            if (_data[u][j].found && _tolerance.less(d, pi[u])) {
-              pi[u] = d;
+            if (_data[u][j].dist < INF) {
+              d = _data[u][j].dist * _curr_size - j * _curr_length;
+              if (_tolerance.less(d, pi[u])) pi[u] = d;
             }
           }

lemon/howard.h

@@ -179 +179 @@
     Tolerance _tolerance;
   
+    // Infinite constant
+    const LargeValue INF;
+
   public:
   
@@ -231 +234 @@
     Howard( const Digraph &digraph,
             const LengthMap &length ) :
-      _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
+      _gr(digraph), _length(length), _best_found(false),
+      _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false),
       _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
-      _comp(digraph), _in_arcs(digraph)
+      _comp(digraph), _in_arcs(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
     {}
 
@@ -308 +315 @@
         }
         // Update the best cycle (global minimum mean cycle)
-        if ( !_best_found || (_curr_found &&
+        if ( _curr_found && (!_best_found ||
              _curr_length * _best_size < _best_length * _curr_size) ) {
           _best_found = true;
@@ -447 +454 @@
       }
       for (int i = 0; i < int(_nodes->size()); ++i) {
-        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
+        _dist[(*_nodes)[i]] = INF;
       }
       Node u, v;

lemon/karp.h

@@ -149 +149 @@
     struct PathData
     {
-      bool found;
       LargeValue dist;
       Arc pred;
-      PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) :
-        found(f), dist(d), pred(p) {}
+      PathData(LargeValue d, Arc p = INVALID) :
+        dist(d), pred(p) {}
     };
 
@@ -187 +186 @@
 
     Tolerance _tolerance;
+    
+    // Infinite constant
+    const LargeValue INF;
 
   public:
@@ -242 +244 @@
       _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph),
       _cycle_length(0), _cycle_size(1), _cycle_node(INVALID),
-      _cycle_path(NULL), _local_path(false), _data(digraph)
+      _cycle_path(NULL), _local_path(false), _data(digraph),
+      INF(std::numeric_limits<LargeValue>::has_infinity ?
+          std::numeric_limits<LargeValue>::infinity() :
+          std::numeric_limits<LargeValue>::max())
     {}
 
@@ -459 +464 @@
       }      
       for (int i = 0; i < n; ++i) {
-        _data[(*_nodes)[i]].resize(n + 1);
+        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
       }
       return true;
@@ -469 +474 @@
     void processRounds() {
       Node start = (*_nodes)[0];
-      _data[start][0] = PathData(true, 0);
+      _data[start][0] = PathData(0);
       _process.clear();
       _process.push_back(start);
@@ -494 +499 @@
           v = _gr.target(e);
           d = _data[u][k-1].dist + _length[e];
-          if (!_data[v][k].found) {
-            next.push_back(v);
-            _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e);
-          }
-          else if (_tolerance.less(d, _data[v][k].dist)) {
-            _data[v][k] = PathData(true, d, e);
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            if (_data[v][k].dist == INF) next.push_back(v);
+            _data[v][k] = PathData(d, e);
           }
         }
@@ -517 +519 @@
           v = _gr.target(e);
           d = _data[u][k-1].dist + _length[e];
-          if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
-            _data[v][k] = PathData(true, d, e);
+          if (_tolerance.less(d, _data[v][k].dist)) {
+            _data[v][k] = PathData(d, e);
           }
         }
@@ -529 +531 @@
       for (int i = 0; i < n; ++i) {
         Node u = (*_nodes)[i];
-        if (!_data[u][n].found) continue;
+        if (_data[u][n].dist == INF) continue;
         LargeValue length, max_length = 0;
         int size, max_size = 1;
         bool found_curr = false;
         for (int k = 0; k < n; ++k) {
-          if (!_data[u][k].found) continue;
+          if (_data[u][k].dist == INF) continue;
           length = _data[u][n].dist - _data[u][k].dist;
           size = n - k;