lemon/dfs.h
 changeset 286 da414906fe21 parent 278 931190050520 child 287 bb40b6db0a58
equal inserted replaced
11:4a912b42f5b3 14:c4ddec17510e
`   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`