Changeset 814:11c946fa8d13 in lemon for lemon/hartmann_orlin.h
- Timestamp:
- 08/11/09 22:52:35 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/hartmann_orlin.h
r813 r814 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 … … 191 190 192 191 Tolerance _tolerance; 192 193 // Infinite constant 194 const LargeValue INF; 193 195 194 196 public: … … 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 … … 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; … … 483 488 void processRounds() { 484 489 Node start = (*_nodes)[0]; 485 _data[start][0] = PathData( true,0);490 _data[start][0] = PathData(0); 486 491 _process.clear(); 487 492 _process.push_back(start); … … 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 } … … 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 } … … 562 564 for (int i = 0; i < n; ++i) { 563 565 u = (*_nodes)[i]; 564 if ( !_data[u][k].found) continue;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) { … … 587 589 for (int i = 0; i < n; ++i) { 588 590 u = (*_nodes)[i]; 589 pi[u] = std::numeric_limits<LargeValue>::max();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 pi[u] = d;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 }
Note: See TracChangeset
for help on using the changeset viewer.