equal
deleted
inserted
replaced
605 ///Executes the algorithm until the given target node is reached. |
605 ///Executes the algorithm until the given target node is reached. |
606 |
606 |
607 ///Executes the algorithm until the given target node is reached. |
607 ///Executes the algorithm until the given target node is reached. |
608 /// |
608 /// |
609 ///This method runs the %BFS algorithm from the root node(s) |
609 ///This method runs the %BFS algorithm from the root node(s) |
610 ///in order to compute the shortest path to \c dest. |
610 ///in order to compute the shortest path to \c t. |
611 /// |
611 /// |
612 ///The algorithm computes |
612 ///The algorithm computes |
613 ///- the shortest path to \c dest, |
613 ///- the shortest path to \c t, |
614 ///- the distance of \c dest from the root(s). |
614 ///- the distance of \c t from the root(s). |
615 /// |
615 /// |
616 ///\pre init() must be called and at least one root node should be |
616 ///\pre init() must be called and at least one root node should be |
617 ///added with addSource() before using this function. |
617 ///added with addSource() before using this function. |
618 /// |
618 /// |
619 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code. |
619 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code. |
621 /// bool reach = false; |
621 /// bool reach = false; |
622 /// while ( !b.emptyQueue() && !reach ) { |
622 /// while ( !b.emptyQueue() && !reach ) { |
623 /// b.processNextNode(t, reach); |
623 /// b.processNextNode(t, reach); |
624 /// } |
624 /// } |
625 ///\endcode |
625 ///\endcode |
626 void start(Node dest) |
626 void start(Node t) |
627 { |
627 { |
628 bool reach = false; |
628 bool reach = false; |
629 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
629 while ( !emptyQueue() && !reach ) processNextNode(t, reach); |
630 } |
630 } |
631 |
631 |
632 ///Executes the algorithm until a condition is met. |
632 ///Executes the algorithm until a condition is met. |
633 |
633 |
634 ///Executes the algorithm until a condition is met. |
634 ///Executes the algorithm until a condition is met. |
662 processNextNode(nm, rnode); |
662 processNextNode(nm, rnode); |
663 } |
663 } |
664 return rnode; |
664 return rnode; |
665 } |
665 } |
666 |
666 |
667 ///Runs the algorithm from the given node. |
667 ///Runs the algorithm from the given source node. |
668 |
668 |
669 ///This method runs the %BFS algorithm from node \c s |
669 ///This method runs the %BFS algorithm from node \c s |
670 ///in order to compute the shortest path to each node. |
670 ///in order to compute the shortest path to each node. |
671 /// |
671 /// |
672 ///The algorithm computes |
672 ///The algorithm computes |
686 } |
686 } |
687 |
687 |
688 ///Finds the shortest path between \c s and \c t. |
688 ///Finds the shortest path between \c s and \c t. |
689 |
689 |
690 ///This method runs the %BFS algorithm from node \c s |
690 ///This method runs the %BFS algorithm from node \c s |
691 ///in order to compute the shortest path to \c t. |
691 ///in order to compute the shortest path to node \c t |
692 /// |
692 ///(it stops searching when \c t is processed). |
693 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path, |
693 /// |
694 ///if \c t is reachable form \c s, \c 0 otherwise. |
694 ///\return \c true if \c t is reachable form \c s. |
695 /// |
695 /// |
696 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a |
696 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a |
697 ///shortcut of the following code. |
697 ///shortcut of the following code. |
698 ///\code |
698 ///\code |
699 /// b.init(); |
699 /// b.init(); |
700 /// b.addSource(s); |
700 /// b.addSource(s); |
701 /// b.start(t); |
701 /// b.start(t); |
702 ///\endcode |
702 ///\endcode |
703 int run(Node s,Node t) { |
703 bool run(Node s,Node t) { |
704 init(); |
704 init(); |
705 addSource(s); |
705 addSource(s); |
706 start(t); |
706 start(t); |
707 return reached(t) ? _curr_dist : 0; |
707 return reached(t); |
708 } |
708 } |
709 |
709 |
710 ///Runs the algorithm to visit all nodes in the digraph. |
710 ///Runs the algorithm to visit all nodes in the digraph. |
711 |
711 |
712 ///This method runs the %BFS algorithm in order to |
712 ///This method runs the %BFS algorithm in order to |
1619 /// \brief Executes the algorithm until the given target node is reached. |
1619 /// \brief Executes the algorithm until the given target node is reached. |
1620 /// |
1620 /// |
1621 /// Executes the algorithm until the given target node is reached. |
1621 /// Executes the algorithm until the given target node is reached. |
1622 /// |
1622 /// |
1623 /// This method runs the %BFS algorithm from the root node(s) |
1623 /// This method runs the %BFS algorithm from the root node(s) |
1624 /// in order to compute the shortest path to \c dest. |
1624 /// in order to compute the shortest path to \c t. |
1625 /// |
1625 /// |
1626 /// The algorithm computes |
1626 /// The algorithm computes |
1627 /// - the shortest path to \c dest, |
1627 /// - the shortest path to \c t, |
1628 /// - the distance of \c dest from the root(s). |
1628 /// - the distance of \c t from the root(s). |
1629 /// |
1629 /// |
1630 /// \pre init() must be called and at least one root node should be |
1630 /// \pre init() must be called and at least one root node should be |
1631 /// added with addSource() before using this function. |
1631 /// added with addSource() before using this function. |
1632 /// |
1632 /// |
1633 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code. |
1633 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code. |
1635 /// bool reach = false; |
1635 /// bool reach = false; |
1636 /// while ( !b.emptyQueue() && !reach ) { |
1636 /// while ( !b.emptyQueue() && !reach ) { |
1637 /// b.processNextNode(t, reach); |
1637 /// b.processNextNode(t, reach); |
1638 /// } |
1638 /// } |
1639 /// \endcode |
1639 /// \endcode |
1640 void start(Node dest) { |
1640 void start(Node t) { |
1641 bool reach = false; |
1641 bool reach = false; |
1642 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
1642 while ( !emptyQueue() && !reach ) processNextNode(t, reach); |
1643 } |
1643 } |
1644 |
1644 |
1645 /// \brief Executes the algorithm until a condition is met. |
1645 /// \brief Executes the algorithm until a condition is met. |
1646 /// |
1646 /// |
1647 /// Executes the algorithm until a condition is met. |
1647 /// Executes the algorithm until a condition is met. |
1675 processNextNode(nm, rnode); |
1675 processNextNode(nm, rnode); |
1676 } |
1676 } |
1677 return rnode; |
1677 return rnode; |
1678 } |
1678 } |
1679 |
1679 |
1680 /// \brief Runs the algorithm from the given node. |
1680 /// \brief Runs the algorithm from the given source node. |
1681 /// |
1681 /// |
1682 /// This method runs the %BFS algorithm from node \c s |
1682 /// This method runs the %BFS algorithm from node \c s |
1683 /// in order to compute the shortest path to each node. |
1683 /// in order to compute the shortest path to each node. |
1684 /// |
1684 /// |
1685 /// The algorithm computes |
1685 /// The algorithm computes |
1694 ///\endcode |
1694 ///\endcode |
1695 void run(Node s) { |
1695 void run(Node s) { |
1696 init(); |
1696 init(); |
1697 addSource(s); |
1697 addSource(s); |
1698 start(); |
1698 start(); |
|
1699 } |
|
1700 |
|
1701 /// \brief Finds the shortest path between \c s and \c t. |
|
1702 /// |
|
1703 /// This method runs the %BFS algorithm from node \c s |
|
1704 /// in order to compute the shortest path to node \c t |
|
1705 /// (it stops searching when \c t is processed). |
|
1706 /// |
|
1707 /// \return \c true if \c t is reachable form \c s. |
|
1708 /// |
|
1709 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a |
|
1710 /// shortcut of the following code. |
|
1711 ///\code |
|
1712 /// b.init(); |
|
1713 /// b.addSource(s); |
|
1714 /// b.start(t); |
|
1715 ///\endcode |
|
1716 bool run(Node s,Node t) { |
|
1717 init(); |
|
1718 addSource(s); |
|
1719 start(t); |
|
1720 return reached(t); |
1699 } |
1721 } |
1700 |
1722 |
1701 /// \brief Runs the algorithm to visit all nodes in the digraph. |
1723 /// \brief Runs the algorithm to visit all nodes in the digraph. |
1702 /// |
1724 /// |
1703 /// This method runs the %BFS algorithm in order to |
1725 /// This method runs the %BFS algorithm in order to |