Changeset 448:510c53fd06cd in lemon-0.x for src/work

Timestamp:

04/27/04 18:27:08 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@596

Message:

bfs, dfs, bfsiterator, dfsiterator for alpar's sake of being much more standardized.

File:

• src/work/marci/bfs_iterator.h (modified) (7 diffs)

src/work/marci/bfs_iterator.h

@@ -29 +29 @@
       own_reached_map(true) { }
     ~BfsIterator() { if (own_reached_map) delete &reached; }
-    //s is marcked reached.
-    //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
-    //is the queue is not empty, then is it pushed.
+    /// This method markes s reached.
+    /// If the queue is empty, then s is pushed in the bfs queue 
+    /// and the first OutEdgeIt is processed.
+    /// If the queue is not empty, then s is simply pushed.
     void pushAndSetReached(Node s) { 
       reached.set(s, true);
@@ -51 +52 @@
       }
     }
+    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
+    /// its \c operator++() iterates on the edges in a bfs order.
     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
     operator++() { 
@@ -84 +87 @@
     }
     bool finished() const { return bfs_queue.empty(); }
+    /// The conversion operator makes for converting the bfs-iterator 
+    /// to an \c out-edge-iterator.
     operator OutEdgeIt() const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
@@ -94 +99 @@
 
   /// Bfs searches from s for the nodes wich are not marked in 
-  /// reachedmap
+  /// \c reached_map
+  /// Reached is a read-write bool-map, Pred is a write-nodemap 
+  /// and dist is an rw-nodemap, have to be.
   template <typename Graph, 
             typename ReachedMap=typename Graph::template NodeMap<bool>, 
@@ -108 +115 @@
   public:
     Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
-    //s is marked to be reached and pushed in the bfs queue.
-    //if the queue is empty, then the first out-edge is processed
-    //If s was not marked previously, then 
-    //in addition its pred is set to be INVALID, and dist to 0. 
-    //if s was marked previuosly, then it is simply pushed.
+    /// s is marked to be reached and pushed in the bfs queue.
+    /// If the queue is empty, then the first out-edge is processed.
+    /// If s was not marked previously, then 
+    /// in addition its pred is set to be INVALID, and dist to 0. 
+    /// if s was marked previuosly, then it is simply pushed.
     void push(Node s) { 
       if (this->reached[s]) {
@@ -122 +129 @@
       }
     }
+    /// A bfs is processed from s.
     void run(Node s) {
       push(s);
@@ -201 +209 @@
   };
 
+  /// Dfs searches from s for the nodes wich are not marked in 
+  /// \c reached_map
+  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
+  template <typename Graph, 
+            typename ReachedMap=typename Graph::template NodeMap<bool>, 
+            typename PredMap
+            =typename Graph::template NodeMap<typename Graph::Edge> > 
+  class Dfs : public DfsIterator<Graph, ReachedMap> {
+    typedef DfsIterator<Graph, ReachedMap> Parent;
+  protected:
+    typedef typename Parent::Node Node;
+    PredMap& pred;
+  public:
+    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
+    /// s is marked to be reached and pushed in the bfs queue.
+    /// If the queue is empty, then the first out-edge is processed.
+    /// If s was not marked previously, then 
+    /// in addition its pred is set to be INVALID. 
+    /// if s was marked previuosly, then it is simply pushed.
+    void push(Node s) { 
+      if (this->reached[s]) {
+        Parent::pushAndSetReached(s);
+      } else {
+        Parent::pushAndSetReached(s);
+        pred.set(s, INVALID);
+      }
+    }
+    /// A bfs is processed from s.
+    void run(Node s) {
+      push(s);
+      while (!this->finished()) this->operator++();
+    }
+    Dfs<Graph, ReachedMap, PredMap> operator++() {
+      Parent::operator++();
+      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
+      {
+        pred.set(this->bNode(), this->actual_edge);
+      }
+      return *this;
+    }
+    const PredMap& getPredMap() const { return pred; }
+  };
+
+
 } // namespace hugo