r767:11c946fa8d13
Tue, 11 Aug 2009 22:52:35
[Not Reviewed]
0 comments (0 inline)
0
3
0
| ... | ... |
@@ -149,13 +149,12 @@ |
| 149 | 149 |
|
| 150 | 150 |
// Data sturcture for path data |
| 151 | 151 |
struct PathData |
| 152 | 152 |
{
|
| 153 |
bool found; |
|
| 154 | 153 |
LargeValue dist; |
| 155 | 154 |
Arc pred; |
| 156 |
PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) : |
|
| 157 |
found(f), dist(d), pred(p) {}
|
|
| 155 |
PathData(LargeValue d, Arc p = INVALID) : |
|
| 156 |
dist(d), pred(p) {}
|
|
| 158 | 157 |
}; |
| 159 | 158 |
|
| 160 | 159 |
typedef typename Digraph::template NodeMap<std::vector<PathData> > |
| 161 | 160 |
PathDataNodeMap; |
| ... | ... |
@@ -190,8 +189,11 @@ |
| 190 | 189 |
std::vector<Node> _process; |
| 191 | 190 |
|
| 192 | 191 |
Tolerance _tolerance; |
| 193 | 192 |
|
| 193 |
// Infinite constant |
|
| 194 |
const LargeValue INF; |
|
| 195 |
|
|
| 194 | 196 |
public: |
| 195 | 197 |
|
| 196 | 198 |
/// \name Named Template Parameters |
| 197 | 199 |
/// @{
|
| ... | ... |
@@ -244,9 +246,12 @@ |
| 244 | 246 |
HartmannOrlin( const Digraph &digraph, |
| 245 | 247 |
const LengthMap &length ) : |
| 246 | 248 |
_gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph), |
| 247 | 249 |
_best_found(false), _best_length(0), _best_size(1), |
| 248 |
_cycle_path(NULL), _local_path(false), _data(digraph) |
|
| 250 |
_cycle_path(NULL), _local_path(false), _data(digraph), |
|
| 251 |
INF(std::numeric_limits<LargeValue>::has_infinity ? |
|
| 252 |
std::numeric_limits<LargeValue>::infinity() : |
|
| 253 |
std::numeric_limits<LargeValue>::max()) |
|
| 249 | 254 |
{}
|
| 250 | 255 |
|
| 251 | 256 |
/// Destructor. |
| 252 | 257 |
~HartmannOrlin() {
|
| ... | ... |
@@ -471,9 +476,9 @@ |
| 471 | 476 |
if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
|
| 472 | 477 |
return false; |
| 473 | 478 |
} |
| 474 | 479 |
for (int i = 0; i < n; ++i) {
|
| 475 |
_data[(*_nodes)[i]].resize(n + 1); |
|
| 480 |
_data[(*_nodes)[i]].resize(n + 1, PathData(INF)); |
|
| 476 | 481 |
} |
| 477 | 482 |
return true; |
| 478 | 483 |
} |
| 479 | 484 |
|
| ... | ... |
@@ -481,9 +486,9 @@ |
| 481 | 486 |
// _data[v][k] is the length of a shortest directed walk from the root |
| 482 | 487 |
// node to node v containing exactly k arcs. |
| 483 | 488 |
void processRounds() {
|
| 484 | 489 |
Node start = (*_nodes)[0]; |
| 485 |
_data[start][0] = PathData( |
|
| 490 |
_data[start][0] = PathData(0); |
|
| 486 | 491 |
_process.clear(); |
| 487 | 492 |
_process.push_back(start); |
| 488 | 493 |
|
| 489 | 494 |
int k, n = _nodes->size(); |
| ... | ... |
@@ -516,14 +521,11 @@ |
| 516 | 521 |
for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
|
| 517 | 522 |
e = _out_arcs[u][j]; |
| 518 | 523 |
v = _gr.target(e); |
| 519 | 524 |
d = _data[u][k-1].dist + _length[e]; |
| 520 |
if (!_data[v][k].found) {
|
|
| 521 |
next.push_back(v); |
|
| 522 |
_data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e); |
|
| 523 |
} |
|
| 524 |
else if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 525 |
_data[v][k] = PathData(true, d, e); |
|
| 525 |
if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 526 |
if (_data[v][k].dist == INF) next.push_back(v); |
|
| 527 |
_data[v][k] = PathData(d, e); |
|
| 526 | 528 |
} |
| 527 | 529 |
} |
| 528 | 530 |
} |
| 529 | 531 |
_process.swap(next); |
| ... | ... |
@@ -539,10 +541,10 @@ |
| 539 | 541 |
for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
|
| 540 | 542 |
e = _out_arcs[u][j]; |
| 541 | 543 |
v = _gr.target(e); |
| 542 | 544 |
d = _data[u][k-1].dist + _length[e]; |
| 543 |
if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
|
|
| 544 |
_data[v][k] = PathData(true, d, e); |
|
| 545 |
if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 546 |
_data[v][k] = PathData(d, e); |
|
| 545 | 547 |
} |
| 546 | 548 |
} |
| 547 | 549 |
} |
| 548 | 550 |
} |
| ... | ... |
@@ -560,9 +562,9 @@ |
| 560 | 562 |
// Search for cycles that are already found |
| 561 | 563 |
_curr_found = false; |
| 562 | 564 |
for (int i = 0; i < n; ++i) {
|
| 563 | 565 |
u = (*_nodes)[i]; |
| 564 |
if ( |
|
| 566 |
if (_data[u][k].dist == INF) continue; |
|
| 565 | 567 |
for (int j = k; j >= 0; --j) {
|
| 566 | 568 |
if (level[u].first == i && level[u].second > 0) {
|
| 567 | 569 |
// A cycle is found |
| 568 | 570 |
length = _data[u][level[u].second].dist - _data[u][j].dist; |
| ... | ... |
@@ -585,13 +587,13 @@ |
| 585 | 587 |
if (_curr_found && k < n) {
|
| 586 | 588 |
// Find node potentials |
| 587 | 589 |
for (int i = 0; i < n; ++i) {
|
| 588 | 590 |
u = (*_nodes)[i]; |
| 589 |
pi[u] = |
|
| 591 |
pi[u] = INF; |
|
| 590 | 592 |
for (int j = 0; j <= k; ++j) {
|
| 591 |
d = _data[u][j].dist * _curr_size - j * _curr_length; |
|
| 592 |
if (_data[u][j].found && _tolerance.less(d, pi[u])) {
|
|
| 593 |
|
|
| 593 |
if (_data[u][j].dist < INF) {
|
|
| 594 |
d = _data[u][j].dist * _curr_size - j * _curr_length; |
|
| 595 |
if (_tolerance.less(d, pi[u])) pi[u] = d; |
|
| 594 | 596 |
} |
| 595 | 597 |
} |
| 596 | 598 |
} |
| 597 | 599 |
| ... | ... |
@@ -177,8 +177,11 @@ |
| 177 | 177 |
int _qfront, _qback; |
| 178 | 178 |
|
| 179 | 179 |
Tolerance _tolerance; |
| 180 | 180 |
|
| 181 |
// Infinite constant |
|
| 182 |
const LargeValue INF; |
|
| 183 |
|
|
| 181 | 184 |
public: |
| 182 | 185 |
|
| 183 | 186 |
/// \name Named Template Parameters |
| 184 | 187 |
/// @{
|
| ... | ... |
@@ -229,11 +232,15 @@ |
| 229 | 232 |
/// \param digraph The digraph the algorithm runs on. |
| 230 | 233 |
/// \param length The lengths (costs) of the arcs. |
| 231 | 234 |
Howard( const Digraph &digraph, |
| 232 | 235 |
const LengthMap &length ) : |
| 233 |
_gr(digraph), _length(length), |
|
| 236 |
_gr(digraph), _length(length), _best_found(false), |
|
| 237 |
_best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false), |
|
| 234 | 238 |
_policy(digraph), _reached(digraph), _level(digraph), _dist(digraph), |
| 235 |
_comp(digraph), _in_arcs(digraph) |
|
| 239 |
_comp(digraph), _in_arcs(digraph), |
|
| 240 |
INF(std::numeric_limits<LargeValue>::has_infinity ? |
|
| 241 |
std::numeric_limits<LargeValue>::infinity() : |
|
| 242 |
std::numeric_limits<LargeValue>::max()) |
|
| 236 | 243 |
{}
|
| 237 | 244 |
|
| 238 | 245 |
/// Destructor. |
| 239 | 246 |
~Howard() {
|
| ... | ... |
@@ -306,9 +313,9 @@ |
| 306 | 313 |
findPolicyCycle(); |
| 307 | 314 |
if (!computeNodeDistances()) break; |
| 308 | 315 |
} |
| 309 | 316 |
// Update the best cycle (global minimum mean cycle) |
| 310 |
if ( !_best_found || |
|
| 317 |
if ( _curr_found && (!_best_found || |
|
| 311 | 318 |
_curr_length * _best_size < _best_length * _curr_size) ) {
|
| 312 | 319 |
_best_found = true; |
| 313 | 320 |
_best_length = _curr_length; |
| 314 | 321 |
_best_size = _curr_size; |
| ... | ... |
@@ -445,9 +452,9 @@ |
| 445 | 452 |
(_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
|
| 446 | 453 |
return false; |
| 447 | 454 |
} |
| 448 | 455 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
| 449 |
_dist[(*_nodes)[i]] = |
|
| 456 |
_dist[(*_nodes)[i]] = INF; |
|
| 450 | 457 |
} |
| 451 | 458 |
Node u, v; |
| 452 | 459 |
Arc e; |
| 453 | 460 |
for (int i = 0; i < int(_nodes->size()); ++i) {
|
| ... | ... |
@@ -147,13 +147,12 @@ |
| 147 | 147 |
|
| 148 | 148 |
// Data sturcture for path data |
| 149 | 149 |
struct PathData |
| 150 | 150 |
{
|
| 151 |
bool found; |
|
| 152 | 151 |
LargeValue dist; |
| 153 | 152 |
Arc pred; |
| 154 |
PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) : |
|
| 155 |
found(f), dist(d), pred(p) {}
|
|
| 153 |
PathData(LargeValue d, Arc p = INVALID) : |
|
| 154 |
dist(d), pred(p) {}
|
|
| 156 | 155 |
}; |
| 157 | 156 |
|
| 158 | 157 |
typedef typename Digraph::template NodeMap<std::vector<PathData> > |
| 159 | 158 |
PathDataNodeMap; |
| ... | ... |
@@ -185,8 +184,11 @@ |
| 185 | 184 |
// The processed nodes in the last round |
| 186 | 185 |
std::vector<Node> _process; |
| 187 | 186 |
|
| 188 | 187 |
Tolerance _tolerance; |
| 188 |
|
|
| 189 |
// Infinite constant |
|
| 190 |
const LargeValue INF; |
|
| 189 | 191 |
|
| 190 | 192 |
public: |
| 191 | 193 |
|
| 192 | 194 |
/// \name Named Template Parameters |
| ... | ... |
@@ -240,9 +242,12 @@ |
| 240 | 242 |
Karp( const Digraph &digraph, |
| 241 | 243 |
const LengthMap &length ) : |
| 242 | 244 |
_gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph), |
| 243 | 245 |
_cycle_length(0), _cycle_size(1), _cycle_node(INVALID), |
| 244 |
_cycle_path(NULL), _local_path(false), _data(digraph) |
|
| 246 |
_cycle_path(NULL), _local_path(false), _data(digraph), |
|
| 247 |
INF(std::numeric_limits<LargeValue>::has_infinity ? |
|
| 248 |
std::numeric_limits<LargeValue>::infinity() : |
|
| 249 |
std::numeric_limits<LargeValue>::max()) |
|
| 245 | 250 |
{}
|
| 246 | 251 |
|
| 247 | 252 |
/// Destructor. |
| 248 | 253 |
~Karp() {
|
| ... | ... |
@@ -457,9 +462,9 @@ |
| 457 | 462 |
if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) {
|
| 458 | 463 |
return false; |
| 459 | 464 |
} |
| 460 | 465 |
for (int i = 0; i < n; ++i) {
|
| 461 |
_data[(*_nodes)[i]].resize(n + 1); |
|
| 466 |
_data[(*_nodes)[i]].resize(n + 1, PathData(INF)); |
|
| 462 | 467 |
} |
| 463 | 468 |
return true; |
| 464 | 469 |
} |
| 465 | 470 |
|
| ... | ... |
@@ -467,9 +472,9 @@ |
| 467 | 472 |
// _data[v][k] is the length of a shortest directed walk from the root |
| 468 | 473 |
// node to node v containing exactly k arcs. |
| 469 | 474 |
void processRounds() {
|
| 470 | 475 |
Node start = (*_nodes)[0]; |
| 471 |
_data[start][0] = PathData( |
|
| 476 |
_data[start][0] = PathData(0); |
|
| 472 | 477 |
_process.clear(); |
| 473 | 478 |
_process.push_back(start); |
| 474 | 479 |
|
| 475 | 480 |
int k, n = _nodes->size(); |
| ... | ... |
@@ -492,14 +497,11 @@ |
| 492 | 497 |
for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
|
| 493 | 498 |
e = _out_arcs[u][j]; |
| 494 | 499 |
v = _gr.target(e); |
| 495 | 500 |
d = _data[u][k-1].dist + _length[e]; |
| 496 |
if (!_data[v][k].found) {
|
|
| 497 |
next.push_back(v); |
|
| 498 |
_data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e); |
|
| 499 |
} |
|
| 500 |
else if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 501 |
_data[v][k] = PathData(true, d, e); |
|
| 501 |
if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 502 |
if (_data[v][k].dist == INF) next.push_back(v); |
|
| 503 |
_data[v][k] = PathData(d, e); |
|
| 502 | 504 |
} |
| 503 | 505 |
} |
| 504 | 506 |
} |
| 505 | 507 |
_process.swap(next); |
| ... | ... |
@@ -515,10 +517,10 @@ |
| 515 | 517 |
for (int j = 0; j < int(_out_arcs[u].size()); ++j) {
|
| 516 | 518 |
e = _out_arcs[u][j]; |
| 517 | 519 |
v = _gr.target(e); |
| 518 | 520 |
d = _data[u][k-1].dist + _length[e]; |
| 519 |
if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) {
|
|
| 520 |
_data[v][k] = PathData(true, d, e); |
|
| 521 |
if (_tolerance.less(d, _data[v][k].dist)) {
|
|
| 522 |
_data[v][k] = PathData(d, e); |
|
| 521 | 523 |
} |
| 522 | 524 |
} |
| 523 | 525 |
} |
| 524 | 526 |
} |
| ... | ... |
@@ -527,14 +529,14 @@ |
| 527 | 529 |
void updateMinMean() {
|
| 528 | 530 |
int n = _nodes->size(); |
| 529 | 531 |
for (int i = 0; i < n; ++i) {
|
| 530 | 532 |
Node u = (*_nodes)[i]; |
| 531 |
if ( |
|
| 533 |
if (_data[u][n].dist == INF) continue; |
|
| 532 | 534 |
LargeValue length, max_length = 0; |
| 533 | 535 |
int size, max_size = 1; |
| 534 | 536 |
bool found_curr = false; |
| 535 | 537 |
for (int k = 0; k < n; ++k) {
|
| 536 |
if ( |
|
| 538 |
if (_data[u][k].dist == INF) continue; |
|
| 537 | 539 |
length = _data[u][n].dist - _data[u][k].dist; |
| 538 | 540 |
size = n - k; |
| 539 | 541 |
if (!found_curr || length * max_size > max_length * size) {
|
| 540 | 542 |
found_curr = true; |
0 comments (0 inline)