Changeset 287:bb40b6db0a58 in lemon for lemon/bfs.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/bfs.h (modified) (9 diffs)
• lemon/bfs.h (modified) (5 diffs)

lemon/bfs.h

@@ -605 +605 @@
     ///
     ///This method runs the %BFS algorithm from the root node(s)
-    ///in order to compute the shortest path to \c dest.
+    ///in order to compute the shortest path to \c t.
     ///
     ///The algorithm computes
-    ///- the shortest path to \c dest,
-    ///- the distance of \c dest from the root(s).
+    ///- the shortest path to \c t,
+    ///- the distance of \c t from the root(s).
     ///
     ///\pre init() must be called and at least one root node should be
@@ -621 +621 @@
     ///  }
     ///\endcode
-    void start(Node dest)
+    void start(Node t)
     {
       bool reach = false;
-      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
     }
 
@@ -662 +662 @@
     }
 
-    ///Runs the algorithm from the given node.
+    ///Runs the algorithm from the given source node.
 
     ///This method runs the %BFS algorithm from node \c s
@@ -686 +686 @@
 
     ///This method runs the %BFS algorithm from node \c s
-    ///in order to compute the shortest path to \c t.
-    ///
-    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
-    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///in order to compute the shortest 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>b.run(s,t)</tt> is just a
@@ -698 +698 @@
     ///  b.start(t);
     ///\endcode
-    int run(Node s,Node t) {
+    bool run(Node s,Node t) {
       init();
       addSource(s);
       start(t);
-      return reached(t) ? _curr_dist : 0;
+      return reached(t);
     }
 
@@ -1617 +1617 @@
     ///
     /// This method runs the %BFS algorithm from the root node(s)
-    /// in order to compute the shortest path to \c dest.
+    /// in order to compute the shortest path to \c t.
     ///
     /// The algorithm computes
-    /// - the shortest path to \c dest,
-    /// - the distance of \c dest from the root(s).
+    /// - the shortest path to \c t,
+    /// - the distance of \c t from the root(s).
     ///
     /// \pre init() must be called and at least one root node should be
@@ -1633 +1633 @@
     ///   }
     /// \endcode
-    void start(Node dest) {
+    void start(Node t) {
       bool reach = false;
-      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
+      while ( !emptyQueue() && !reach ) processNextNode(t, reach);
     }
 
@@ -1673 +1673 @@
     }
 
-    /// \brief Runs the algorithm from the given node.
+    /// \brief Runs the algorithm from the given source node.
     ///
     /// This method runs the %BFS algorithm from node \c s
@@ -1692 +1692 @@
       addSource(s);
       start();
+    }
+
+    /// \brief Finds the shortest path between \c s and \c t.
+    ///
+    /// This method runs the %BFS algorithm from node \c s
+    /// in order to compute the shortest 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>b.run(s,t)</tt> is just a
+    /// shortcut of the following code.
+    ///\code
+    ///   b.init();
+    ///   b.addSource(s);
+    ///   b.start(t);
+    ///\endcode
+    bool run(Node s,Node t) {
+      init();
+      addSource(s);
+      start(t);
+      return reached(t);
     }
 

lemon/bfs.h

@@ -55 +55 @@
     ///\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)
     {
@@ -65 +64 @@
     ///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 _curr_dist;
 
-    ///Creates the maps if necessary.
-    ///\todo Better memory allocation (instead of new).
+    //Creates the maps if necessary.
     void create_maps()
     {
@@ -849 +846 @@
     ///\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)
     {
@@ -1371 +1367 @@
     int _list_front, _list_back;
 
-    ///Creates the maps if necessary.
-    ///\todo Better memory allocation (instead of new).
+    //Creates the maps if necessary.
     void create_maps() {
       if(!_reached) {