# HG changeset patch
# User marci
# Date 1075898732 0
# Node ID f71840c04b2ab7439e439e1e71b99a940c8eea4b
# Parent  b180c196b4b7def9ec67a4e54e88b895da10e186
BfsIterator2

diff -r b180c196b4b7 -r f71840c04b2a src/work/bfs_iterator.hh
--- a/src/work/bfs_iterator.hh	Wed Feb 04 12:34:15 2004 +0000
+++ b/src/work/bfs_iterator.hh	Wed Feb 04 12:45:32 2004 +0000
@@ -1,5 +1,5 @@
-#ifndef MARCI_BFS_HH
-#define MARCI_BFS_HH
+#ifndef BFS_ITERATOR_HH
+#define BFS_ITERATOR_HH
 
 #include <queue>
 #include <stack>
@@ -395,6 +395,80 @@
     bool aNodeIsLeaved() { return !(actual_edge.valid()); }
   };
 
+  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