Changeset 11:33a84426c221 in lemon-0.x for src/work/marci_bfs.hh

Timestamp:

01/12/04 12:48:49 (20 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

bfs_iterator1

File:

• src/work/marci_bfs.hh (modified) (1 diff)

src/work/marci_bfs.hh

@@ -128 +128 @@
   };
 
+  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