Changeset 58:f71840c04b2a in lemon-0.x

Timestamp:

02/04/04 13:45:32 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

BfsIterator2

File:

• src/work/bfs_iterator.hh (modified) (2 diffs)

src/work/bfs_iterator.hh

@@ -1 @@
-#ifndef MARCI_BFS_HH
-#define MARCI_BFS_HH
+#ifndef BFS_ITERATOR_HH
+#define BFS_ITERATOR_HH
 
 #include <queue>
@@ -396 +396 @@
   };
 
+  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+  class BfsIterator2 {
+    typedef typename Graph::NodeIt NodeIt;
+    const Graph& G;
+    std::queue<OutEdgeIt> bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
+    void pushAndSetReached(const NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(G.template first<OutEdgeIt>(s));
+        actual_edge=bfs_queue.front();
+        if (actual_edge.valid()) { 
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(G.template first<OutEdgeIt>(w));
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } //else {
+        //}
+      } else {
+        bfs_queue.push(G.template first<OutEdgeIt>(s));
+      }
+    }
+    BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
+    operator++() { 
+      if (bfs_queue.front().valid()) { 
+        ++(bfs_queue.front());
+        actual_edge=bfs_queue.front();
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(G.template first<OutEdgeIt>(w));
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          actual_edge=bfs_queue.front();
+        } else {
+          actual_edge=OutEdgeIt();
+        }
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(G.template first<OutEdgeIt>(w));
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      }
+      return *this;
+    }
+    bool finished() const { return bfs_queue.empty(); }
+    operator OutEdgeIt () const { return actual_edge; }
+    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
+    bool isANodeExamined() const { return !(actual_edge.valid()); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
+ };
+
+
 } // namespace marci
 
-#endif //MARCI_BFS_HH
+#endif //BFS_ITERATOR_HH