# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1250023955 -7200
# Node ID 11c946fa8d13774d947c57e30f3f72cc7b0b3425
# Parent 97744b6dabf8d706434e30dc3caadb99db050c06
Simplify comparisons in min mean cycle classes (#179)
using extreme INF values instead of bool flags.
diff -r 97744b6dabf8 -r 11c946fa8d13 lemon/hartmann_orlin.h
--- a/lemon/hartmann_orlin.h Tue Aug 11 21:53:39 2009 +0200
+++ b/lemon/hartmann_orlin.h Tue Aug 11 22:52:35 2009 +0200
@@ -150,11 +150,10 @@
// Data sturcture for path data
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) {}
};
typedef typename Digraph::template NodeMap<std::vector<PathData> >
@@ -191,6 +190,9 @@
Tolerance _tolerance;
+ // Infinite constant
+ const LargeValue INF;
+
public:
/// \name Named Template Parameters
@@ -245,7 +247,10 @@
const LengthMap &length ) :
_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())
{}
/// Destructor.
@@ -472,7 +477,7 @@
return false;
}
for (int i = 0; i < n; ++i) {
- _data[(*_nodes)[i]].resize(n + 1);
+ _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
}
return true;
}
@@ -482,7 +487,7 @@
// node to node v containing exactly k arcs.
void processRounds() {
Node start = (*_nodes)[0];
- _data[start][0] = PathData(true, 0);
+ _data[start][0] = PathData(0);
_process.clear();
_process.push_back(start);
@@ -517,12 +522,9 @@
e = _out_arcs[u][j];
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);
}
}
}
@@ -540,8 +542,8 @@
e = _out_arcs[u][j];
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);
}
}
}
@@ -561,7 +563,7 @@
_curr_found = false;
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) {
// A cycle is found
@@ -586,11 +588,11 @@
// Find node potentials
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;
}
}
}
diff -r 97744b6dabf8 -r 11c946fa8d13 lemon/howard.h
--- a/lemon/howard.h Tue Aug 11 21:53:39 2009 +0200
+++ b/lemon/howard.h Tue Aug 11 22:52:35 2009 +0200
@@ -178,6 +178,9 @@
Tolerance _tolerance;
+ // Infinite constant
+ const LargeValue INF;
+
public:
/// \name Named Template Parameters
@@ -230,9 +233,13 @@
/// \param length The lengths (costs) of the arcs.
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())
{}
/// Destructor.
@@ -307,7 +314,7 @@
if (!computeNodeDistances()) break;
}
// 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;
_best_length = _curr_length;
@@ -446,7 +453,7 @@
return false;
}
for (int i = 0; i < int(_nodes->size()); ++i) {
- _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
+ _dist[(*_nodes)[i]] = INF;
}
Node u, v;
Arc e;
diff -r 97744b6dabf8 -r 11c946fa8d13 lemon/karp.h
--- a/lemon/karp.h Tue Aug 11 21:53:39 2009 +0200
+++ b/lemon/karp.h Tue Aug 11 22:52:35 2009 +0200
@@ -148,11 +148,10 @@
// Data sturcture for path data
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) {}
};
typedef typename Digraph::template NodeMap<std::vector<PathData> >
@@ -186,6 +185,9 @@
std::vector<Node> _process;
Tolerance _tolerance;
+
+ // Infinite constant
+ const LargeValue INF;
public:
@@ -241,7 +243,10 @@
const LengthMap &length ) :
_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())
{}
/// Destructor.
@@ -458,7 +463,7 @@
return false;
}
for (int i = 0; i < n; ++i) {
- _data[(*_nodes)[i]].resize(n + 1);
+ _data[(*_nodes)[i]].resize(n + 1, PathData(INF));
}
return true;
}
@@ -468,7 +473,7 @@
// node to node v containing exactly k arcs.
void processRounds() {
Node start = (*_nodes)[0];
- _data[start][0] = PathData(true, 0);
+ _data[start][0] = PathData(0);
_process.clear();
_process.push_back(start);
@@ -493,12 +498,9 @@
e = _out_arcs[u][j];
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);
}
}
}
@@ -516,8 +518,8 @@
e = _out_arcs[u][j];
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);
}
}
}
@@ -528,12 +530,12 @@
int n = _nodes->size();
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;
if (!found_curr || length * max_size > max_length * size) {