Changeset 75:87623302a68f in lemon-0.x for src/work/bfs_iterator.hh

Timestamp:

02/16/04 12:29:48 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

.

File:

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

src/work/bfs_iterator.hh

@@ -4 +4 @@
 #include <queue>
 #include <stack>
+#include <utility>
+#include <graph_wrapper.h>
 
 namespace marci {
@@ -467 +469 @@
  };
 
+
+  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+  class BfsIterator3 {
+    typedef typename Graph::NodeIt NodeIt;
+    const Graph& G;
+    std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
+        actual_edge=bfs_queue.front().second;
+        if (actual_edge.valid()) { 
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, 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(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
+      }
+    }
+    BfsIterator3<Graph, OutEdgeIt, ReachedMap>& 
+    operator++() { 
+      if (bfs_queue.front().second.valid()) { 
+        ++(bfs_queue.front().second);
+        actual_edge=bfs_queue.front().second;
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, 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().second;
+          if (actual_edge.valid()) {
+            NodeIt w=G.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, 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()); }
+    NodeIt aNode() const { return bfs_queue.front().first; }
+    NodeIt bNode() const { return G.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
+ };
+
+  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
+  class BfsIterator4 {
+    typedef typename Graph::NodeIt NodeIt;
+    const Graph& G;
+    std::queue<NodeIt> bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(s);
+        G.getFirst(actual_edge, s);
+        if (actual_edge.valid()) { 
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } 
+      } else {
+        bfs_queue.push(s);
+      }
+    }
+    BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 
+    operator++() { 
+      if (actual_edge.valid()) { 
+        ++actual_edge;
+        if (actual_edge.valid()) {
+          NodeIt w=G.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          G.getFirst(actual_edge, bfs_queue.front());
+          if (actual_edge.valid()) {
+            NodeIt w=G.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(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()); }
+    NodeIt aNode() const { return bfs_queue.front(); }
+    NodeIt bNode() const { return G.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
+ };
+
+
+  template <typename GraphWrapper, typename ReachedMap>
+  class BfsIterator5 {
+    typedef typename GraphWrapper::NodeIt NodeIt;
+    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
+    GraphWrapper gw;
+    std::queue<NodeIt> bfs_queue;
+    ReachedMap reached;
+    bool b_node_newly_reached;
+    OutEdgeIt actual_edge;
+  public:
+    BfsIterator5(GraphWrapper _gw) : 
+      gw(_gw), reached(_gw.getGraph()) { }
+    void pushAndSetReached(NodeIt s) { 
+      reached.set(s, true);
+      if (bfs_queue.empty()) {
+        bfs_queue.push(s);
+        gw.getFirst(actual_edge, s);
+        if (actual_edge.valid()) { 
+          NodeIt w=gw.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        } 
+      } else {
+        bfs_queue.push(s);
+      }
+    }
+    BfsIterator5<GraphWrapper, ReachedMap>& 
+    operator++() { 
+      if (actual_edge.valid()) { 
+        ++actual_edge;
+        if (actual_edge.valid()) {
+          NodeIt w=gw.bNode(actual_edge);
+          if (!reached.get(w)) {
+            bfs_queue.push(w);
+            reached.set(w, true);
+            b_node_newly_reached=true;
+          } else {
+            b_node_newly_reached=false;
+          }
+        }
+      } else {
+        bfs_queue.pop(); 
+        if (!bfs_queue.empty()) {
+          gw.getFirst(actual_edge, bfs_queue.front());
+          if (actual_edge.valid()) {
+            NodeIt w=gw.bNode(actual_edge);
+            if (!reached.get(w)) {
+              bfs_queue.push(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()); }
+    NodeIt aNode() const { return bfs_queue.front(); }
+    NodeIt bNode() const { return gw.bNode(actual_edge); }
+    const ReachedMap& getReachedMap() const { return reached; }
+    const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
+ };
+
+
+
 } // namespace marci