# HG changeset patch
# User marci
# Date 1073908129 0
# Node ID 33a84426c22168dc9cf44801ed595c86897dc710
# Parent  436df3c980d18b8f6335973581bb78277fcc3fce
bfs_iterator1

diff -r 436df3c980d1 -r 33a84426c221 src/work/marci_bfs.hh
--- a/src/work/marci_bfs.hh	Fri Jan 09 14:57:01 2004 +0000
+++ b/src/work/marci_bfs.hh	Mon Jan 12 11:48:49 2004 +0000
@@ -127,6 +127,56 @@
 
   };
 
+  template <typename graph_type, typename reached_type>
+  struct bfs_iterator1 {
+    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
+    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
+    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
+    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+
+    graph_type& G;
+    std::queue<out_edge_iterator>& bfs_queue;
+    reached_type& reached;
+    bool newly_reached;
+    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
+      is_valid();
+      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
+	out_edge_iterator e=bfs_queue.front();
+	node_iterator w=G.head(e);
+	if (!reached.get(w)) {
+	  bfs_queue.push(G.first_out_edge(w));
+	  reached.put(w, true);
+	  newly_reached=true;
+	} else {
+	  newly_reached=false;
+	}
+      }
+    }
+    bfs_iterator1<graph_type, reached_type>& operator++() { 
+      if (!is_valid()) return *this;
+      ++(bfs_queue.front());
+      is_valid();
+      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
+	out_edge_iterator e=bfs_queue.front();
+	node_iterator w=G.head(e);
+	if (!reached.get(w)) {
+	  bfs_queue.push(G.first_out_edge(w));
+	  reached.put(w, true);
+	  newly_reached=true;
+	} else {
+	  newly_reached=false;
+	}
+      }
+      return *this;
+    }
+    bool is_valid() { 
+      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+      if (bfs_queue.empty()) return false; else return true;
+    }
+    operator edge_iterator () { return bfs_queue.front(); }
+    bool is_newly_reached() { return newly_reached; }
+
+  };
 
 } // namespace marci