COIN-OR::LEMON - Graph Library

Changeset 286:da414906fe21 in lemon-1.2 for lemon/dfs.h


Ignore:
Timestamp:
09/26/08 12:40:11 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Improvements related to BFS/DFS/Dijkstra (ticket #96)

  • Add run(s,t) function to BfsVisit?.
  • Modify run(s,t) functions in the class interfaces to return bool value.
  • Bug fix in Dijkstra::start(t) function.
  • Improve Dijkstra::currentDist().
  • Extend test files to check named class template parameters.
  • Doc improvements.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/dfs.h

    r278 r286  
    559559    ///
    560560    ///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.
    562562    ///
    563563    ///The algorithm computes
    564     ///- the %DFS path to \c dest,
    565     ///- the distance of \c dest from the root in the %DFS tree.
     564    ///- the %DFS path to \c t,
     565    ///- the distance of \c t from the root in the %DFS tree.
    566566    ///
    567567    ///\pre init() must be called and a root node should be
    568568    ///added with addSource() before using this function.
    569     void start(Node dest)
    570     {
    571       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
     569    void start(Node t)
     570    {
     571      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
    572572        processNextArc();
    573573    }
     
    599599    }
    600600
    601     ///Runs the algorithm from the given node.
     601    ///Runs the algorithm from the given source node.
    602602
    603603    ///This method runs the %DFS algorithm from node \c s
     
    623623
    624624    ///This method runs the %DFS algorithm from node \c s
    625     ///in order to compute the DFS path to \c t.
    626     ///
    627     ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    628     ///if \c t is reachable form \c s, \c 0 otherwise.
     625    ///in order to compute the DFS path to node \c t
     626    ///(it stops searching when \c t is processed)
     627    ///
     628    ///\return \c true if \c t is reachable form \c s.
    629629    ///
    630630    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    635635    ///  d.start(t);
    636636    ///\endcode
    637     int run(Node s,Node t) {
     637    bool run(Node s,Node t) {
    638638      init();
    639639      addSource(s);
    640640      start(t);
    641       return reached(t)?_stack_head+1:0;
     641      return reached(t);
    642642    }
    643643
     
    15271527    ///
    15281528    /// 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.
    15301530    ///
    15311531    /// The algorithm computes
    1532     /// - the %DFS path to \c dest,
    1533     /// - the distance of \c dest from the root in the %DFS tree.
     1532    /// - the %DFS path to \c t,
     1533    /// - the distance of \c t from the root in the %DFS tree.
    15341534    ///
    15351535    /// \pre init() must be called and a root node should be added
    15361536    /// with addSource() before using this function.
    1537     void start(Node dest) {
    1538       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
     1537    void start(Node t) {
     1538      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
    15391539        processNextArc();
    15401540    }
     
    15651565    }
    15661566
    1567     /// \brief Runs the algorithm from the given node.
     1567    /// \brief Runs the algorithm from the given source node.
    15681568    ///
    15691569    /// This method runs the %DFS algorithm from node \c s.
     
    15891589
    15901590    /// This method runs the %DFS algorithm from node \c s
    1591     /// in order to compute the DFS path to \c t.
    1592     ///
    1593     /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
    1594     /// if \c t is reachable form \c s, \c 0 otherwise.
     1591    /// in order to compute the DFS path to node \c t
     1592    /// (it stops searching when \c t is processed).
     1593    ///
     1594    /// \return \c true if \c t is reachable form \c s.
    15951595    ///
    15961596    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
     
    16011601    ///   d.start(t);
    16021602    ///\endcode
    1603     int run(Node s,Node t) {
     1603    bool run(Node s,Node t) {
    16041604      init();
    16051605      addSource(s);
    16061606      start(t);
    1607       return reached(t)?_stack_head+1:0;
     1607      return reached(t);
    16081608    }
    16091609
Note: See TracChangeset for help on using the changeset viewer.