Changeset 409:7ab7f083760a in lemon-0.x for src/work/marci/bfs_iterator.h

Timestamp:

04/26/04 11:54:24 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

stGraphWrapper is almost working

File:

• src/work/marci/bfs_iterator.h (modified) (4 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.
     void pushAndSetReached(Node s) { 
       reached.set(s, true);
@@ -81 +84 @@
     }
     bool finished() const { return bfs_queue.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
+    operator OutEdgeIt() const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
@@ -89 +92 @@
     const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
   };  
+
+  /// Bfs searches from s for the nodes wich are not marked in 
+  /// reachedmap
+  template <typename Graph, 
+            typename ReachedMap=typename Graph::template NodeMap<bool>, 
+            typename PredMap
+            =typename Graph::template NodeMap<typename Graph::Edge>, 
+            typename DistMap=typename Graph::template NodeMap<int> > 
+  class Bfs : public BfsIterator<Graph, ReachedMap> {
+    typedef BfsIterator<Graph, ReachedMap> Parent;
+  protected:
+    typedef typename Parent::Node Node;
+    PredMap& pred;
+    DistMap& dist;
+  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.
+    void push(Node s) { 
+      if (this->reached[s]) {
+        Parent::pushAndSetReached(s);
+      } else {
+        Parent::pushAndSetReached(s);
+        pred.set(s, INVALID);
+        dist.set(s, 0);
+      }
+    }
+    void run(Node s) {
+      push(s);
+      while (!this->finished()) this->operator++();
+    }
+    Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
+      Parent::operator++();
+      if (this->graph->valid(actual_edge) && this->b_node_newly_reached) {
+        pred.set(s, actual_edge);
+        dist.set(s, dist[this->aNode()]);
+      }
+      return *this;
+    }
+    const PredMap& getPredMap() const { return pred; }
+    const DistMap& getDistMap() const { return dist; }
+  };
 
   template <typename Graph, /*typename OutEdgeIt,*/ 
@@ -143 +191 @@
     }
     bool finished() const { return dfs_stack.empty(); }
-    operator OutEdgeIt () const { return actual_edge; }
+    operator OutEdgeIt() const { return actual_edge; }
     bool isBNodeNewlyReached() const { return b_node_newly_reached; }
     bool isANodeExamined() const { return !(graph->valid(actual_edge)); }