Changeset 814:11c946fa8d13 in lemon
 Timestamp:
 08/11/09 22:52:35 (10 years ago)
 Branch:
 default
 Phase:
 public
 Location:
 lemon
 Files:

 3 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][k1].dist + _length[e]; 520 if (!_data[v][k].found) { 521 next.push_back(v); 522 _data[v][k] = PathData(true, _data[u][k1].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][k1].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 } 
lemon/howard.h
r811 r814 179 179 Tolerance _tolerance; 180 180 181 // Infinite constant 182 const LargeValue INF; 183 181 184 public: 182 185 … … 231 234 Howard( const Digraph &digraph, 232 235 const LengthMap &length ) : 233 _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false), 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 … … 308 315 } 309 316 // Update the best cycle (global minimum mean cycle) 310 if ( !_best_found  (_curr_found &&317 if ( _curr_found && (!_best_found  311 318 _curr_length * _best_size < _best_length * _curr_size) ) { 312 319 _best_found = true; … … 447 454 } 448 455 for (int i = 0; i < int(_nodes>size()); ++i) { 449 _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();456 _dist[(*_nodes)[i]] = INF; 450 457 } 451 458 Node u, v; 
lemon/karp.h
r812 r814 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 … … 187 186 188 187 Tolerance _tolerance; 188 189 // Infinite constant 190 const LargeValue INF; 189 191 190 192 public: … … 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 … … 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; … … 469 474 void processRounds() { 470 475 Node start = (*_nodes)[0]; 471 _data[start][0] = PathData( true,0);476 _data[start][0] = PathData(0); 472 477 _process.clear(); 473 478 _process.push_back(start); … … 494 499 v = _gr.target(e); 495 500 d = _data[u][k1].dist + _length[e]; 496 if (!_data[v][k].found) { 497 next.push_back(v); 498 _data[v][k] = PathData(true, _data[u][k1].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 } … … 517 519 v = _gr.target(e); 518 520 d = _data[u][k1].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 } … … 529 531 for (int i = 0; i < n; ++i) { 530 532 Node u = (*_nodes)[i]; 531 if ( !_data[u][n].found) continue;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 ( !_data[u][k].found) continue;538 if (_data[u][k].dist == INF) continue; 537 539 length = _data[u][n].dist  _data[u][k].dist; 538 540 size = n  k;
Note: See TracChangeset
for help on using the changeset viewer.