equal
deleted
inserted
replaced
556 ///Executes the algorithm until the given target node is reached. |
556 ///Executes the algorithm until the given target node is reached. |
557 |
557 |
558 ///Executes the algorithm until the given target node is reached. |
558 ///Executes the algorithm until the given target node is reached. |
559 /// |
559 /// |
560 ///This method runs the %DFS algorithm from the root node |
560 ///This method runs the %DFS algorithm from the root node |
561 ///in order to compute the DFS path to \c dest. |
561 ///in order to compute the DFS path to \c t. |
562 /// |
562 /// |
563 ///The algorithm computes |
563 ///The algorithm computes |
564 ///- the %DFS path to \c dest, |
564 ///- the %DFS path to \c t, |
565 ///- the distance of \c dest from the root in the %DFS tree. |
565 ///- the distance of \c t from the root in the %DFS tree. |
566 /// |
566 /// |
567 ///\pre init() must be called and a root node should be |
567 ///\pre init() must be called and a root node should be |
568 ///added with addSource() before using this function. |
568 ///added with addSource() before using this function. |
569 void start(Node dest) |
569 void start(Node t) |
570 { |
570 { |
571 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) |
571 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t ) |
572 processNextArc(); |
572 processNextArc(); |
573 } |
573 } |
574 |
574 |
575 ///Executes the algorithm until a condition is met. |
575 ///Executes the algorithm until a condition is met. |
576 |
576 |
596 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
596 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
597 processNextArc(); |
597 processNextArc(); |
598 return emptyQueue() ? INVALID : _stack[_stack_head]; |
598 return emptyQueue() ? INVALID : _stack[_stack_head]; |
599 } |
599 } |
600 |
600 |
601 ///Runs the algorithm from the given node. |
601 ///Runs the algorithm from the given source node. |
602 |
602 |
603 ///This method runs the %DFS algorithm from node \c s |
603 ///This method runs the %DFS algorithm from node \c s |
604 ///in order to compute the DFS path to each node. |
604 ///in order to compute the DFS path to each node. |
605 /// |
605 /// |
606 ///The algorithm computes |
606 ///The algorithm computes |
620 } |
620 } |
621 |
621 |
622 ///Finds the %DFS path between \c s and \c t. |
622 ///Finds the %DFS path between \c s and \c t. |
623 |
623 |
624 ///This method runs the %DFS algorithm from node \c s |
624 ///This method runs the %DFS algorithm from node \c s |
625 ///in order to compute the DFS path to \c t. |
625 ///in order to compute the DFS path to node \c t |
626 /// |
626 ///(it stops searching when \c t is processed) |
627 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path, |
627 /// |
628 ///if \c t is reachable form \c s, \c 0 otherwise. |
628 ///\return \c true if \c t is reachable form \c s. |
629 /// |
629 /// |
630 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is |
630 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is |
631 ///just a shortcut of the following code. |
631 ///just a shortcut of the following code. |
632 ///\code |
632 ///\code |
633 /// d.init(); |
633 /// d.init(); |
634 /// d.addSource(s); |
634 /// d.addSource(s); |
635 /// d.start(t); |
635 /// d.start(t); |
636 ///\endcode |
636 ///\endcode |
637 int run(Node s,Node t) { |
637 bool run(Node s,Node t) { |
638 init(); |
638 init(); |
639 addSource(s); |
639 addSource(s); |
640 start(t); |
640 start(t); |
641 return reached(t)?_stack_head+1:0; |
641 return reached(t); |
642 } |
642 } |
643 |
643 |
644 ///Runs the algorithm to visit all nodes in the digraph. |
644 ///Runs the algorithm to visit all nodes in the digraph. |
645 |
645 |
646 ///This method runs the %DFS algorithm in order to compute the |
646 ///This method runs the %DFS algorithm in order to compute the |
1524 /// \brief Executes the algorithm until the given target node is reached. |
1524 /// \brief Executes the algorithm until the given target node is reached. |
1525 /// |
1525 /// |
1526 /// Executes the algorithm until the given target node is reached. |
1526 /// Executes the algorithm until the given target node is reached. |
1527 /// |
1527 /// |
1528 /// This method runs the %DFS algorithm from the root node |
1528 /// This method runs the %DFS algorithm from the root node |
1529 /// in order to compute the DFS path to \c dest. |
1529 /// in order to compute the DFS path to \c t. |
1530 /// |
1530 /// |
1531 /// The algorithm computes |
1531 /// The algorithm computes |
1532 /// - the %DFS path to \c dest, |
1532 /// - the %DFS path to \c t, |
1533 /// - the distance of \c dest from the root in the %DFS tree. |
1533 /// - the distance of \c t from the root in the %DFS tree. |
1534 /// |
1534 /// |
1535 /// \pre init() must be called and a root node should be added |
1535 /// \pre init() must be called and a root node should be added |
1536 /// with addSource() before using this function. |
1536 /// with addSource() before using this function. |
1537 void start(Node dest) { |
1537 void start(Node t) { |
1538 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) |
1538 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t ) |
1539 processNextArc(); |
1539 processNextArc(); |
1540 } |
1540 } |
1541 |
1541 |
1542 /// \brief Executes the algorithm until a condition is met. |
1542 /// \brief Executes the algorithm until a condition is met. |
1543 /// |
1543 /// |
1562 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
1562 while ( !emptyQueue() && !am[_stack[_stack_head]] ) |
1563 processNextArc(); |
1563 processNextArc(); |
1564 return emptyQueue() ? INVALID : _stack[_stack_head]; |
1564 return emptyQueue() ? INVALID : _stack[_stack_head]; |
1565 } |
1565 } |
1566 |
1566 |
1567 /// \brief Runs the algorithm from the given node. |
1567 /// \brief Runs the algorithm from the given source node. |
1568 /// |
1568 /// |
1569 /// This method runs the %DFS algorithm from node \c s. |
1569 /// This method runs the %DFS algorithm from node \c s. |
1570 /// in order to compute the DFS path to each node. |
1570 /// in order to compute the DFS path to each node. |
1571 /// |
1571 /// |
1572 /// The algorithm computes |
1572 /// The algorithm computes |
1586 } |
1586 } |
1587 |
1587 |
1588 /// \brief Finds the %DFS path between \c s and \c t. |
1588 /// \brief Finds the %DFS path between \c s and \c t. |
1589 |
1589 |
1590 /// This method runs the %DFS algorithm from node \c s |
1590 /// This method runs the %DFS algorithm from node \c s |
1591 /// in order to compute the DFS path to \c t. |
1591 /// in order to compute the DFS path to node \c t |
1592 /// |
1592 /// (it stops searching when \c t is processed). |
1593 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path, |
1593 /// |
1594 /// if \c t is reachable form \c s, \c 0 otherwise. |
1594 /// \return \c true if \c t is reachable form \c s. |
1595 /// |
1595 /// |
1596 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is |
1596 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is |
1597 /// just a shortcut of the following code. |
1597 /// just a shortcut of the following code. |
1598 ///\code |
1598 ///\code |
1599 /// d.init(); |
1599 /// d.init(); |
1600 /// d.addSource(s); |
1600 /// d.addSource(s); |
1601 /// d.start(t); |
1601 /// d.start(t); |
1602 ///\endcode |
1602 ///\endcode |
1603 int run(Node s,Node t) { |
1603 bool run(Node s,Node t) { |
1604 init(); |
1604 init(); |
1605 addSource(s); |
1605 addSource(s); |
1606 start(t); |
1606 start(t); |
1607 return reached(t)?_stack_head+1:0; |
1607 return reached(t); |
1608 } |
1608 } |
1609 |
1609 |
1610 /// \brief Runs the algorithm to visit all nodes in the digraph. |
1610 /// \brief Runs the algorithm to visit all nodes in the digraph. |
1611 |
1611 |
1612 /// This method runs the %DFS algorithm in order to |
1612 /// This method runs the %DFS algorithm in order to |