Changeset 1781:dca4c8a54e0a in lemon0.x for lemon/belmann_ford.h
 Timestamp:
 11/09/05 13:07:00 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2316
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/belmann_ford.h
r1765 r1781 204 204 typedef typename Graph::NodeIt NodeIt; 205 205 typedef typename Graph::Edge Edge; 206 typedef typename Graph:: EdgeItEdgeIt;206 typedef typename Graph::OutEdgeIt OutEdgeIt; 207 207 208 208 /// \brief The type of the length of the edges. … … 231 231 bool local_dist; 232 232 233 typedef typename Graph::template NodeMap<bool> MaskMap; 234 MaskMap *_mask; 235 236 std::vector<Node> _process; 237 233 238 /// Creates the maps if necessary. 234 239 void create_maps() { … … 241 246 _dist = Traits::createDistMap(*graph); 242 247 } 248 _mask = new MaskMap(*graph, false); 243 249 } 244 250 … … 325 331 if(local_pred) delete _pred; 326 332 if(local_dist) delete _dist; 333 delete _mask; 327 334 } 328 335 … … 389 396 _dist>set(it, value); 390 397 } 398 _process.clear(); 399 if (OperationTraits::less(value, OperationTraits::infinity())) { 400 for (NodeIt it(*graph); it != INVALID; ++it) { 401 _process.push_back(it); 402 } 403 } 391 404 } 392 405 … … 397 410 void addSource(Node source, Value dst = OperationTraits::zero()) { 398 411 _dist>set(source, dst); 412 if (!(*_mask)[source]) { 413 _process.push_back(source); 414 _mask>set(source, true); 415 } 416 } 417 418 /// \brief Executes one round from the belmann ford algorithm. 419 /// 420 /// If the algoritm calculated the distances in the previous round 421 /// strictly for all at most k length pathes then it will calculate the 422 /// distances strictly for all at most k + 1 length pathes. With k 423 /// iteration this function calculates the at most k length pathes. 424 bool processNextRound() { 425 for (int i = 0; i < (int)_process.size(); ++i) { 426 _mask>set(_process[i], false); 427 } 428 std::vector<Node> nextProcess; 429 std::vector<Value> values(_process.size()); 430 for (int i = 0; i < (int)_process.size(); ++i) { 431 values[i] = _dist[_process[i]]; 432 } 433 for (int i = 0; i < (int)_process.size(); ++i) { 434 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { 435 Node target = graph>target(it); 436 Value relaxed = OperationTraits::plus(values[i], (*length)[it]); 437 if (OperationTraits::less(relaxed, (*_dist)[target])) { 438 _pred>set(target, it); 439 _dist>set(target, relaxed); 440 if (!(*_mask)[target]) { 441 _mask>set(target, true); 442 nextProcess.push_back(target); 443 } 444 } 445 } 446 } 447 _process.swap(nextProcess); 448 return _process.empty(); 449 } 450 451 /// \brief Executes one weak round from the belmann ford algorithm. 452 /// 453 /// If the algorithm calculated the distances in the 454 /// previous round at least for all at most k length pathes then it will 455 /// calculate the distances at least for all at most k + 1 length pathes. 456 /// This function does not make possible to calculate strictly the 457 /// at most k length minimal pathes, this way it called just weak round. 458 bool processNextWeakRound() { 459 for (int i = 0; i < (int)_process.size(); ++i) { 460 _mask>set(_process[i], false); 461 } 462 std::vector<Node> nextProcess; 463 for (int i = 0; i < (int)_process.size(); ++i) { 464 for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) { 465 Node target = graph>target(it); 466 Value relaxed = 467 OperationTraits::plus((*_dist)[_process[i]], (*length)[it]); 468 if (OperationTraits::less(relaxed, (*_dist)[target])) { 469 _pred>set(target, it); 470 _dist>set(target, relaxed); 471 if (!(*_mask)[target]) { 472 _mask>set(target, true); 473 nextProcess.push_back(target); 474 } 475 } 476 } 477 } 478 for (int i = 0; i < (int)nextProcess.size(); ++i) { 479 _mask>set(nextProcess[i], false); 480 } 481 _process.swap(nextProcess); 482 return _process.empty(); 399 483 } 400 484 … … 412 496 int num = countNodes(*graph)  1; 413 497 for (int i = 0; i < num; ++i) { 414 bool done = true; 415 for (EdgeIt it(*graph); it != INVALID; ++it) { 416 Node source = graph>source(it); 417 Node target = graph>target(it); 418 Value relaxed = 419 OperationTraits::plus((*_dist)[source], (*length)[it]); 420 if (OperationTraits::less(relaxed, (*_dist)[target])) { 421 _pred>set(target, it); 422 _dist>set(target, relaxed); 423 done = false; 424 } 425 } 426 if (done) return; 498 if (processNextWeakRound()) break; 427 499 } 428 500 } … … 442 514 int num = countNodes(*graph); 443 515 for (int i = 0; i < num; ++i) { 444 bool done = true; 445 for (EdgeIt it(*graph); it != INVALID; ++it) { 446 Node source = graph>source(it); 447 Node target = graph>target(it); 448 Value relaxed = 449 OperationTraits::plus((*_dist)[source], (*length)[it]); 450 if (OperationTraits::less(relaxed, (*_dist)[target])) { 451 _pred>set(target, it); 452 _dist>set(target, relaxed); 453 done = false; 454 } 455 } 456 if (done) return true; 516 if (processNextWeakRound()) return true; 457 517 } 458 518 return false; 519 } 520 521 /// \brief Executes the algorithm with path length limit. 522 /// 523 /// \pre init() must be called and at least one node should be added 524 /// with addSource() before using this function. 525 /// 526 /// This method runs the %BelmannFord algorithm from the root node(s) 527 /// in order to compute the shortest path with at most \c length edge 528 /// long pathes to each node. The algorithm computes 529 ///  The shortest path tree. 530 ///  The limited distance of each node from the root(s). 531 void limitedStart(int length) { 532 for (int i = 0; i < length; ++i) { 533 if (processNextRound()) break; 534 } 459 535 } 460 536
Note: See TracChangeset
for help on using the changeset viewer.