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

Timestamp:

09/26/08 12:40:11 (16 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:

• lemon/dfs.h (modified) (8 diffs)

lemon/dfs.h

@@ -559 +559 @@
     ///
     ///This method runs the %DFS algorithm from the root node
-    ///in order to compute the DFS path to \c dest.
+    ///in order to compute the DFS path to \c t.
     ///
     ///The algorithm computes
-    ///- the %DFS path to \c dest,
-    ///- the distance of \c dest from the root in the %DFS tree.
+    ///- the %DFS path to \c t,
+    ///- the distance of \c t from the root in the %DFS tree.
     ///
     ///\pre init() must be called and a root node should be
     ///added with addSource() before using this function.
-    void start(Node dest)
-    {
-      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
+    void start(Node t)
+    {
+      while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
         processNextArc();
     }
@@ -599 +599 @@
     }
 
-    ///Runs the algorithm from the given node.
+    ///Runs the algorithm from the given source node.
 
     ///This method runs the %DFS algorithm from node \c s
@@ -623 +623 @@
 
     ///This method runs the %DFS algorithm from node \c s
-    ///in order to compute the DFS path to \c t.
-    ///
-    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
-    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///in order to compute the DFS path to node \c t
+    ///(it stops searching when \c t is processed)
+    ///
+    ///\return \c true if \c t is reachable form \c s.
     ///
     ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
@@ -635 +635 @@
     ///  d.start(t);
     ///\endcode
-    int run(Node s,Node t) {
+    bool run(Node s,Node t) {
       init();
       addSource(s);
       start(t);
-      return reached(t)?_stack_head+1:0;
+      return reached(t);
     }
 
@@ -1527 +1527 @@
     ///
     /// This method runs the %DFS algorithm from the root node
-    /// in order to compute the DFS path to \c dest.
+    /// in order to compute the DFS path to \c t.
     ///
     /// The algorithm computes
-    /// - the %DFS path to \c dest,
-    /// - the distance of \c dest from the root in the %DFS tree.
+    /// - the %DFS path to \c t,
+    /// - the distance of \c t from the root in the %DFS tree.
     ///
     /// \pre init() must be called and a root node should be added
     /// with addSource() before using this function.
-    void start(Node dest) {
-      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
+    void start(Node t) {
+      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t )
         processNextArc();
     }
@@ -1565 +1565 @@
     }
 
-    /// \brief Runs the algorithm from the given node.
+    /// \brief Runs the algorithm from the given source node.
     ///
     /// This method runs the %DFS algorithm from node \c s.
@@ -1589 +1589 @@
 
     /// This method runs the %DFS algorithm from node \c s
-    /// in order to compute the DFS path to \c t.
-    ///
-    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
-    /// if \c t is reachable form \c s, \c 0 otherwise.
+    /// in order to compute the DFS path to node \c t
+    /// (it stops searching when \c t is processed).
+    ///
+    /// \return \c true if \c t is reachable form \c s.
     ///
     /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
@@ -1601 +1601 @@
     ///   d.start(t);
     ///\endcode
-    int run(Node s,Node t) {
+    bool run(Node s,Node t) {
       init();
       addSource(s);
       start(t);
-      return reached(t)?_stack_head+1:0;
+      return reached(t);
     }