Changeset 2300:69330d717235 in lemon-0.x
- Timestamp:
- 11/13/06 13:30:59 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3073
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/bfs.h
r2260 r2300 479 479 return n; 480 480 } 481 482 ///Processes the next node. 483 484 ///Processes the next node. And checks that the given target node 485 ///is reached. If the target node is reachable from the processed 486 ///node then the reached parameter will be set true. The reached 487 ///parameter should be initially false. 488 /// 489 ///\param target The target node. 490 ///\retval reached Indicates that the target node is reached. 491 ///\return The processed node. 492 /// 493 ///\warning The queue must not be empty! 494 Node processNextNode(Node target, bool& reached) 495 { 496 if(_queue_tail==_queue_next_dist) { 497 _curr_dist++; 498 _queue_next_dist=_queue_head; 499 } 500 Node n=_queue[_queue_tail++]; 501 _processed->set(n,true); 502 Node m; 503 for(OutEdgeIt e(*G,n);e!=INVALID;++e) 504 if(!(*_reached)[m=G->target(e)]) { 505 _queue[_queue_head++]=m; 506 _reached->set(m,true); 507 _pred->set(m,e); 508 _dist->set(m,_curr_dist); 509 reached = reached || (target == m); 510 } 511 return n; 512 } 513 514 ///Processes the next node. 515 516 ///Processes the next node. And checks that at least one of 517 ///reached node has true value in the \c nm nodemap. If one node 518 ///with true value is reachable from the processed node then the 519 ///reached parameter will be set true. The reached parameter 520 ///should be initially false. 521 /// 522 ///\param target The nodemaps of possible targets. 523 ///\retval reached Indicates that one of the target nodes is reached. 524 ///\return The processed node. 525 /// 526 ///\warning The queue must not be empty! 527 template<class NM> 528 Node processNextNode(const NM& nm, bool& reached) 529 { 530 if(_queue_tail==_queue_next_dist) { 531 _curr_dist++; 532 _queue_next_dist=_queue_head; 533 } 534 Node n=_queue[_queue_tail++]; 535 _processed->set(n,true); 536 Node m; 537 for(OutEdgeIt e(*G,n);e!=INVALID;++e) 538 if(!(*_reached)[m=G->target(e)]) { 539 _queue[_queue_head++]=m; 540 _reached->set(m,true); 541 _pred->set(m,e); 542 _dist->set(m,_curr_dist); 543 reached = reached || nm[m]; 544 } 545 return n; 546 } 481 547 482 548 ///Next node to be processed. … … 538 604 void start(Node dest) 539 605 { 540 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode(); 606 bool reached = false; 607 while ( !emptyQueue() && !reached) processNextNode(dest, reached); 541 608 } 542 609 … … 550 617 ///\param nm must be a bool (or convertible) node map. The algorithm 551 618 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. 619 ///\todo query the reached target 552 620 template<class NM> 553 621 void start(const NM &nm) 554 622 { 555 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode(); 623 bool reached = false; 624 while ( !emptyQueue() && !reached) processNextNode(nm, reached); 556 625 } 557 626 … … 594 663 addSource(s); 595 664 start(t); 596 return reached(t)? _curr_dist-1+(_queue_tail==_queue_next_dist):0;665 return reached(t)? _curr_dist : 0; 597 666 } 598 667
Note: See TracChangeset
for help on using the changeset viewer.