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) {