Changeset 767:11c946fa8d13 in lemon-main for lemon/karp.h
- Timestamp:
- 08/11/09 22:52:35 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/karp.h
r765 r767 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][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 } … … 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 } … … 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.