LEMON/LEMON-main Changeset - r767:11c946fa8d13

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r767:11c946fa8d13

« 766:97744b

768:0a4288 »

r767:11c946fa8d13

Tue, 11 Aug 2009 22:52:35

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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

0 3 0

default

3 files changed with 50 insertions and 39 deletions:

lemon/hartmann_orlin.h

lemon/howard.h

lemon/karp.h

↑ Collapse diff ↑

lemon/hartmann_orlin.h

Show inline comments

@@ -152,7 +152,6 @@
+		    {
 		      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) {}
 		    };
@@ -193,2 +192,5 @@
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
@@ -247,3 +249,6 @@
 		      _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())
 		    {}
@@ -474,3 +479,3 @@
 		      for (int i = 0; i < n; ++i) {
 		        _data[(*_nodes)[i]].resize(n + 1);
+		        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+		      }
@@ -484,3 +489,3 @@
 		      Node start = (*_nodes)[0];
-		      _data[start][0] = PathData(true, 0);
 		      _data[start][0] = PathData(0);
 		      _process.clear();
@@ -519,8 +524,5 @@
 		          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);
+		          }
@@ -542,4 +544,4 @@
 		          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);
+		          }
@@ -563,3 +565,3 @@
 		        u = (*_nodes)[i];
-		        if (!_data[u][k].found) continue;
+		        if (_data[u][k].dist == INF) continue;
 		        for (int j = k; j >= 0; --j) {
@@ -588,7 +590,7 @@
 		          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

Show inline comments

@@ -180,2 +180,5 @@
 		    // Infinite constant
 		    const LargeValue INF;
 		  public:
@@ -232,5 +235,9 @@
 		            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())
 		    {}
@@ -309,3 +316,3 @@
 		        // 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) ) {
@@ -448,3 +455,3 @@
 		      for (int i = 0; i < int(_nodes->size()); ++i) {
-		        _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
+		        _dist[(*_nodes)[i]] = INF;
+		      }

lemon/karp.h

Show inline comments

@@ -150,7 +150,6 @@
+		    {
 		      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) {}
 		    };
@@ -188,2 +187,5 @@
 		    Tolerance _tolerance;
 		    // Infinite constant
 		    const LargeValue INF;
@@ -243,3 +245,6 @@
 		      _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())
 		    {}
@@ -460,3 +465,3 @@
 		      for (int i = 0; i < n; ++i) {
 		        _data[(*_nodes)[i]].resize(n + 1);
+		        _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
+		      }
@@ -470,3 +475,3 @@
 		      Node start = (*_nodes)[0];
-		      _data[start][0] = PathData(true, 0);
 		      _data[start][0] = PathData(0);
 		      _process.clear();
@@ -495,8 +500,5 @@
 		          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);
+		          }
@@ -518,4 +520,4 @@
 		          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);
+		          }
@@ -530,3 +532,3 @@
 		        Node u = (*_nodes)[i];
-		        if (!_data[u][n].found) continue;
+		        if (_data[u][n].dist == INF) continue;
 		        LargeValue length, max_length = 0;
@@ -535,3 +537,3 @@
 		        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;

0 comments (0 inline)

RhodeCode

Login to your account