1.1 --- a/src/work/bfs_iterator.hh	Wed Feb 04 12:34:15 2004 +0000
     1.2 +++ b/src/work/bfs_iterator.hh	Wed Feb 04 12:45:32 2004 +0000
     1.3 @@ -1,5 +1,5 @@
     1.4 -#ifndef MARCI_BFS_HH
     1.5 -#define MARCI_BFS_HH
     1.6 +#ifndef BFS_ITERATOR_HH
     1.7 +#define BFS_ITERATOR_HH
     1.8  
     1.9  #include <queue>
    1.10  #include <stack>
    1.11 @@ -395,6 +395,80 @@
    1.12      bool aNodeIsLeaved() { return !(actual_edge.valid()); }
    1.13    };
    1.14  
    1.15 +  template <typename Graph, typename OutEdgeIt, typename ReachedMap>
    1.16 +  class BfsIterator2 {
    1.17 +    typedef typename Graph::NodeIt NodeIt;
    1.18 +    const Graph& G;
    1.19 +    std::queue<OutEdgeIt> bfs_queue;
    1.20 +    ReachedMap reached;
    1.21 +    bool b_node_newly_reached;
    1.22 +    OutEdgeIt actual_edge;
    1.23 +  public:
    1.24 +    BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
    1.25 +    void pushAndSetReached(const NodeIt s) { 
    1.26 +      reached.set(s, true);
    1.27 +      if (bfs_queue.empty()) {
    1.28 +	bfs_queue.push(G.template first<OutEdgeIt>(s));
    1.29 +	actual_edge=bfs_queue.front();
    1.30 +	if (actual_edge.valid()) { 
    1.31 +	  NodeIt w=G.bNode(actual_edge);
    1.32 +	  if (!reached.get(w)) {
    1.33 +	    bfs_queue.push(G.template first<OutEdgeIt>(w));
    1.34 +	    reached.set(w, true);
    1.35 +	    b_node_newly_reached=true;
    1.36 +	  } else {
    1.37 +	    b_node_newly_reached=false;
    1.38 +	  }
    1.39 +	} //else {
    1.40 +	//}
    1.41 +      } else {
    1.42 +	bfs_queue.push(G.template first<OutEdgeIt>(s));
    1.43 +      }
    1.44 +    }
    1.45 +    BfsIterator2<Graph, OutEdgeIt, ReachedMap>& 
    1.46 +    operator++() { 
    1.47 +      if (bfs_queue.front().valid()) { 
    1.48 +	++(bfs_queue.front());
    1.49 +	actual_edge=bfs_queue.front();
    1.50 +	if (actual_edge.valid()) {
    1.51 +	  NodeIt w=G.bNode(actual_edge);
    1.52 +	  if (!reached.get(w)) {
    1.53 +	    bfs_queue.push(G.template first<OutEdgeIt>(w));
    1.54 +	    reached.set(w, true);
    1.55 +	    b_node_newly_reached=true;
    1.56 +	  } else {
    1.57 +	    b_node_newly_reached=false;
    1.58 +	  }
    1.59 +	}
    1.60 +      } else {
    1.61 +	bfs_queue.pop(); 
    1.62 +	if (!bfs_queue.empty()) {
    1.63 +	  actual_edge=bfs_queue.front();
    1.64 +	} else {
    1.65 +	  actual_edge=OutEdgeIt();
    1.66 +	}
    1.67 +	if (actual_edge.valid()) {
    1.68 +	  NodeIt w=G.bNode(actual_edge);
    1.69 +	  if (!reached.get(w)) {
    1.70 +	    bfs_queue.push(G.template first<OutEdgeIt>(w));
    1.71 +	    reached.set(w, true);
    1.72 +	    b_node_newly_reached=true;
    1.73 +	  } else {
    1.74 +	    b_node_newly_reached=false;
    1.75 +	  }
    1.76 +	}
    1.77 +      }
    1.78 +      return *this;
    1.79 +    }
    1.80 +    bool finished() const { return bfs_queue.empty(); }
    1.81 +    operator OutEdgeIt () const { return actual_edge; }
    1.82 +    bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    1.83 +    bool isANodeExamined() const { return !(actual_edge.valid()); }
    1.84 +    const ReachedMap& getReachedMap() const { return reached; }
    1.85 +    const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
    1.86 + };
    1.87 +
    1.88 +
    1.89  } // namespace marci
    1.90  
    1.91 -#endif //MARCI_BFS_HH
    1.92 +#endif //BFS_ITERATOR_HH