1.1 --- a/src/work/marci/bfs_iterator.h	Tue Apr 27 14:17:13 2004 +0000
     1.2 +++ b/src/work/marci/bfs_iterator.h	Tue Apr 27 16:27:08 2004 +0000
     1.3 @@ -28,9 +28,10 @@
     1.4        graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
     1.5        own_reached_map(true) { }
     1.6      ~BfsIterator() { if (own_reached_map) delete &reached; }
     1.7 -    //s is marcked reached.
     1.8 -    //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe.
     1.9 -    //is the queue is not empty, then is it pushed.
    1.10 +    /// This method markes s reached.
    1.11 +    /// If the queue is empty, then s is pushed in the bfs queue 
    1.12 +    /// and the first OutEdgeIt is processed.
    1.13 +    /// If the queue is not empty, then s is simply pushed.
    1.14      void pushAndSetReached(Node s) { 
    1.15        reached.set(s, true);
    1.16        if (bfs_queue.empty()) {
    1.17 @@ -50,6 +51,8 @@
    1.18  	bfs_queue.push(s);
    1.19        }
    1.20      }
    1.21 +    /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
    1.22 +    /// its \c operator++() iterates on the edges in a bfs order.
    1.23      BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
    1.24      operator++() { 
    1.25        if (graph->valid(actual_edge)) { 
    1.26 @@ -83,6 +86,8 @@
    1.27        return *this;
    1.28      }
    1.29      bool finished() const { return bfs_queue.empty(); }
    1.30 +    /// The conversion operator makes for converting the bfs-iterator 
    1.31 +    /// to an \c out-edge-iterator.
    1.32      operator OutEdgeIt() const { return actual_edge; }
    1.33      bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    1.34      bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    1.35 @@ -93,7 +98,9 @@
    1.36    };  
    1.37  
    1.38    /// Bfs searches from s for the nodes wich are not marked in 
    1.39 -  /// reachedmap
    1.40 +  /// \c reached_map
    1.41 +  /// Reached is a read-write bool-map, Pred is a write-nodemap 
    1.42 +  /// and dist is an rw-nodemap, have to be.
    1.43    template <typename Graph, 
    1.44  	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
    1.45  	    typename PredMap
    1.46 @@ -107,11 +114,11 @@
    1.47      DistMap& dist;
    1.48    public:
    1.49      Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
    1.50 -    //s is marked to be reached and pushed in the bfs queue.
    1.51 -    //if the queue is empty, then the first out-edge is processed
    1.52 -    //If s was not marked previously, then 
    1.53 -    //in addition its pred is set to be INVALID, and dist to 0. 
    1.54 -    //if s was marked previuosly, then it is simply pushed.
    1.55 +    /// s is marked to be reached and pushed in the bfs queue.
    1.56 +    /// If the queue is empty, then the first out-edge is processed.
    1.57 +    /// If s was not marked previously, then 
    1.58 +    /// in addition its pred is set to be INVALID, and dist to 0. 
    1.59 +    /// if s was marked previuosly, then it is simply pushed.
    1.60      void push(Node s) { 
    1.61        if (this->reached[s]) {
    1.62  	Parent::pushAndSetReached(s);
    1.63 @@ -121,6 +128,7 @@
    1.64  	dist.set(s, 0);
    1.65        }
    1.66      }
    1.67 +    /// A bfs is processed from s.
    1.68      void run(Node s) {
    1.69        push(s);
    1.70        while (!this->finished()) this->operator++();
    1.71 @@ -200,6 +208,50 @@
    1.72      const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
    1.73    };
    1.74  
    1.75 +  /// Dfs searches from s for the nodes wich are not marked in 
    1.76 +  /// \c reached_map
    1.77 +  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
    1.78 +  template <typename Graph, 
    1.79 +	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
    1.80 +	    typename PredMap
    1.81 +	    =typename Graph::template NodeMap<typename Graph::Edge> > 
    1.82 +  class Dfs : public DfsIterator<Graph, ReachedMap> {
    1.83 +    typedef DfsIterator<Graph, ReachedMap> Parent;
    1.84 +  protected:
    1.85 +    typedef typename Parent::Node Node;
    1.86 +    PredMap& pred;
    1.87 +  public:
    1.88 +    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
    1.89 +    /// s is marked to be reached and pushed in the bfs queue.
    1.90 +    /// If the queue is empty, then the first out-edge is processed.
    1.91 +    /// If s was not marked previously, then 
    1.92 +    /// in addition its pred is set to be INVALID. 
    1.93 +    /// if s was marked previuosly, then it is simply pushed.
    1.94 +    void push(Node s) { 
    1.95 +      if (this->reached[s]) {
    1.96 +	Parent::pushAndSetReached(s);
    1.97 +      } else {
    1.98 +	Parent::pushAndSetReached(s);
    1.99 +	pred.set(s, INVALID);
   1.100 +      }
   1.101 +    }
   1.102 +    /// A bfs is processed from s.
   1.103 +    void run(Node s) {
   1.104 +      push(s);
   1.105 +      while (!this->finished()) this->operator++();
   1.106 +    }
   1.107 +    Dfs<Graph, ReachedMap, PredMap> operator++() {
   1.108 +      Parent::operator++();
   1.109 +      if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
   1.110 +      {
   1.111 +	pred.set(this->bNode(), this->actual_edge);
   1.112 +      }
   1.113 +      return *this;
   1.114 +    }
   1.115 +    const PredMap& getPredMap() const { return pred; }
   1.116 +  };
   1.117 +
   1.118 +
   1.119  } // namespace hugo
   1.120  
   1.121  #endif //HUGO_BFS_ITERATOR_H