Changeset 287:bb40b6db0a58 in lemon for lemon/dfs.h

Timestamp:

09/27/08 14:33:28 (16 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

288:47b3a3b67837, 290:f6899946c1ac

Parents:

286:da414906fe21 (diff), 285:d8dc5acf739b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge

Files:

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

lemon/dfs.h

@@ -556 +556 @@
     ///
     ///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();
     }
@@ -596 +596 @@
     }
 
-    ///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
@@ -620 +620 @@
 
     ///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
@@ -632 +632 @@
     ///  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);
     }
 
@@ -1522 +1522 @@
     ///
     /// 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();
     }
@@ -1560 +1560 @@
     }
 
-    /// \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.
@@ -1584 +1584 @@
 
     /// 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
@@ -1596 +1596 @@
     ///   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);
     }
 

lemon/dfs.h

@@ -56 +56 @@
     ///\param g is the digraph, to which we would like to define the
     ///\ref PredMap.
-    ///\todo The digraph alone may be insufficient to initialize
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -66 +65 @@
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \ref ProcessedMap.
@@ -197 +195 @@
     int _stack_head;
 
-    ///Creates the maps if necessary.
-    ///\todo Better memory allocation (instead of new).
+    //Creates the maps if necessary.
     void create_maps()
     {
@@ -783 +780 @@
     ///\param g is the digraph, to which we would like to define the
     ///\ref PredMap.
-    ///\todo The digraph alone may be insufficient to initialize
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -1318 +1314 @@
     int _stack_head;
 
-    ///Creates the maps if necessary.
-    ///\todo Better memory allocation (instead of new).
+    //Creates the maps if necessary.
     void create_maps() {
       if(!_reached) {