1.1 --- a/src/work/marci_bfs.hh	Fri Jan 09 14:57:01 2004 +0000
     1.2 +++ b/src/work/marci_bfs.hh	Mon Jan 12 11:48:49 2004 +0000
     1.3 @@ -127,6 +127,56 @@
     1.4  
     1.5    };
     1.6  
     1.7 +  template <typename graph_type, typename reached_type>
     1.8 +  struct bfs_iterator1 {
     1.9 +    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    1.10 +    typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    1.11 +    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    1.12 +    typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    1.13 +
    1.14 +    graph_type& G;
    1.15 +    std::queue<out_edge_iterator>& bfs_queue;
    1.16 +    reached_type& reached;
    1.17 +    bool newly_reached;
    1.18 +    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 
    1.19 +      is_valid();
    1.20 +      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
    1.21 +	out_edge_iterator e=bfs_queue.front();
    1.22 +	node_iterator w=G.head(e);
    1.23 +	if (!reached.get(w)) {
    1.24 +	  bfs_queue.push(G.first_out_edge(w));
    1.25 +	  reached.put(w, true);
    1.26 +	  newly_reached=true;
    1.27 +	} else {
    1.28 +	  newly_reached=false;
    1.29 +	}
    1.30 +      }
    1.31 +    }
    1.32 +    bfs_iterator1<graph_type, reached_type>& operator++() { 
    1.33 +      if (!is_valid()) return *this;
    1.34 +      ++(bfs_queue.front());
    1.35 +      is_valid();
    1.36 +      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) { 
    1.37 +	out_edge_iterator e=bfs_queue.front();
    1.38 +	node_iterator w=G.head(e);
    1.39 +	if (!reached.get(w)) {
    1.40 +	  bfs_queue.push(G.first_out_edge(w));
    1.41 +	  reached.put(w, true);
    1.42 +	  newly_reached=true;
    1.43 +	} else {
    1.44 +	  newly_reached=false;
    1.45 +	}
    1.46 +      }
    1.47 +      return *this;
    1.48 +    }
    1.49 +    bool is_valid() { 
    1.50 +      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
    1.51 +      if (bfs_queue.empty()) return false; else return true;
    1.52 +    }
    1.53 +    operator edge_iterator () { return bfs_queue.front(); }
    1.54 +    bool is_newly_reached() { return newly_reached; }
    1.55 +
    1.56 +  };
    1.57  
    1.58  } // namespace marci
    1.59