476 _pred->set(m,e); |
476 _pred->set(m,e); |
477 _dist->set(m,_curr_dist); |
477 _dist->set(m,_curr_dist); |
478 } |
478 } |
479 return n; |
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 ///Next node to be processed. |
548 ///Next node to be processed. |
483 |
549 |
484 ///Next node to be processed. |
550 ///Next node to be processed. |
485 /// |
551 /// |
535 ///- The shortest path to \c dest. |
601 ///- The shortest path to \c dest. |
536 ///- The distance of \c dest from the root(s). |
602 ///- The distance of \c dest from the root(s). |
537 /// |
603 /// |
538 void start(Node dest) |
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 |
543 ///Executes the algorithm until a condition is met. |
610 ///Executes the algorithm until a condition is met. |
544 |
611 |
545 ///Executes the algorithm until a condition is met. |
612 ///Executes the algorithm until a condition is met. |
547 ///\pre init() must be called and at least one node should be added |
614 ///\pre init() must be called and at least one node should be added |
548 ///with addSource() before using this function. |
615 ///with addSource() before using this function. |
549 /// |
616 /// |
550 ///\param nm must be a bool (or convertible) node map. The algorithm |
617 ///\param nm must be a bool (or convertible) node map. The algorithm |
551 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
618 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
|
619 ///\todo query the reached target |
552 template<class NM> |
620 template<class NM> |
553 void start(const NM &nm) |
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 |
558 ///Runs %BFS algorithm from node \c s. |
627 ///Runs %BFS algorithm from node \c s. |
559 |
628 |
560 ///This method runs the %BFS algorithm from a root node \c s |
629 ///This method runs the %BFS algorithm from a root node \c s |