bfs, dfs docs
authormarci
Mon, 10 May 2004 16:31:48 +0000
changeset 597a6e2b02f496a
parent 596 c43e7d0f075b
child 598 1faa5bec1717
bfs, dfs docs
src/work/marci/bfs_iterator.h
     1.1 --- a/src/work/marci/bfs_iterator.h	Mon May 10 15:15:37 2004 +0000
     1.2 +++ b/src/work/marci/bfs_iterator.h	Mon May 10 16:31:48 2004 +0000
     1.3 @@ -10,6 +10,9 @@
     1.4  
     1.5  namespace hugo {
     1.6  
     1.7 +  /// Bfs searches for the nodes wich are not marked in 
     1.8 +  /// \c reached_map
     1.9 +  /// Reached have to work as read-write bool Node-map.
    1.10    template <typename Graph, /*typename OutEdgeIt,*/ 
    1.11  	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
    1.12    class BfsIterator {
    1.13 @@ -23,17 +26,24 @@
    1.14      OutEdgeIt actual_edge;
    1.15      bool own_reached_map;
    1.16    public:
    1.17 +    /// In that constructor \c _reached have to be a reference 
    1.18 +    /// for a bool Node-map. The algorithm will search in a bfs order for 
    1.19 +    /// the nodes which are \c false initially
    1.20      BfsIterator(const Graph& _graph, ReachedMap& _reached) : 
    1.21        graph(&_graph), reached(_reached), 
    1.22        own_reached_map(false) { }
    1.23 +    /// The same as above, but the map storing the reached nodes 
    1.24 +    /// is constructed dynamically to everywhere false.
    1.25      BfsIterator(const Graph& _graph) : 
    1.26        graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
    1.27        own_reached_map(true) { }
    1.28 +    /// The storing the reached nodes have to be destroyed if 
    1.29 +    /// it was constructed dynamically
    1.30      ~BfsIterator() { if (own_reached_map) delete &reached; }
    1.31 -    /// This method markes s reached.
    1.32 -    /// If the queue is empty, then s is pushed in the bfs queue 
    1.33 -    /// and the first OutEdgeIt is processed.
    1.34 -    /// If the queue is not empty, then s is simply pushed.
    1.35 +    /// This method markes \c s reached.
    1.36 +    /// If the queue is empty, then \c s is pushed in the bfs queue 
    1.37 +    /// and the first out-edge is processed.
    1.38 +    /// If the queue is not empty, then \c s is simply pushed.
    1.39      void pushAndSetReached(Node s) { 
    1.40        reached.set(s, true);
    1.41        if (bfs_queue.empty()) {
    1.42 @@ -87,22 +97,33 @@
    1.43        }
    1.44        return *this;
    1.45      }
    1.46 +    ///
    1.47      bool finished() const { return bfs_queue.empty(); }
    1.48      /// The conversion operator makes for converting the bfs-iterator 
    1.49      /// to an \c out-edge-iterator.
    1.50 +    ///\bug Edge have to be in HUGO 0.2
    1.51      operator OutEdgeIt() const { return actual_edge; }
    1.52 +    ///
    1.53      bool isBNodeNewlyReached() const { return b_node_newly_reached; }
    1.54 +    ///
    1.55      bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
    1.56 +    ///
    1.57      Node aNode() const { return bfs_queue.front(); }
    1.58 +    ///
    1.59      Node bNode() const { return graph->bNode(actual_edge); }
    1.60 +    ///
    1.61      const ReachedMap& getReachedMap() const { return reached; }
    1.62 +    ///
    1.63      const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
    1.64    };  
    1.65  
    1.66 -  /// Bfs searches from s for the nodes wich are not marked in 
    1.67 +  /// Bfs searches for the nodes wich are not marked in 
    1.68    /// \c reached_map
    1.69 -  /// Reached is a read-write bool-map, Pred is a write-nodemap 
    1.70 -  /// and dist is an rw-nodemap, have to be.
    1.71 +  /// Reached have to work as a read-write bool Node-map, 
    1.72 +  /// Pred is a write Edge Node-map and
    1.73 +  /// Dist is a read-write int Node-map, have to be. 
    1.74 +  ///\todo In fact onsly simple operations requirement are needed for 
    1.75 +  /// Dist::Value.
    1.76    template <typename Graph, 
    1.77  	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
    1.78  	    typename PredMap
    1.79 @@ -115,12 +136,15 @@
    1.80      PredMap& pred;
    1.81      DistMap& dist;
    1.82    public:
    1.83 +    /// The algorithm will search in a bfs order for 
    1.84 +    /// the nodes which are \c false initially. 
    1.85 +    /// The constructor makes no initial changes on the maps.
    1.86      Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
    1.87 -    /// s is marked to be reached and pushed in the bfs queue.
    1.88 +    /// \c s is marked to be reached and pushed in the bfs queue.
    1.89      /// If the queue is empty, then the first out-edge is processed.
    1.90 -    /// If s was not marked previously, then 
    1.91 -    /// in addition its pred is set to be INVALID, and dist to 0. 
    1.92 -    /// if s was marked previuosly, then it is simply pushed.
    1.93 +    /// If \c s was not marked previously, then 
    1.94 +    /// in addition its pred is set to be \c INVALID, and dist to \c 0. 
    1.95 +    /// if \c s was marked previuosly, then it is simply pushed.
    1.96      void push(Node s) { 
    1.97        if (this->reached[s]) {
    1.98  	Parent::pushAndSetReached(s);
    1.99 @@ -130,11 +154,13 @@
   1.100  	dist.set(s, 0);
   1.101        }
   1.102      }
   1.103 -    /// A bfs is processed from s.
   1.104 +    /// A bfs is processed from \c s.
   1.105      void run(Node s) {
   1.106        push(s);
   1.107        while (!this->finished()) this->operator++();
   1.108      }
   1.109 +    /// Beside the bfs iteration, \c pred and \dist are saved in a 
   1.110 +    /// newly reached node. 
   1.111      Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() {
   1.112        Parent::operator++();
   1.113        if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
   1.114 @@ -144,10 +170,15 @@
   1.115        }
   1.116        return *this;
   1.117      }
   1.118 +    ///
   1.119      const PredMap& getPredMap() const { return pred; }
   1.120 +    ///
   1.121      const DistMap& getDistMap() const { return dist; }
   1.122    };
   1.123  
   1.124 +  /// Dfs searches for the nodes wich are not marked in 
   1.125 +  /// \c reached_map
   1.126 +  /// Reached have to be a read-write bool Node-map.
   1.127    template <typename Graph, /*typename OutEdgeIt,*/ 
   1.128  	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
   1.129    class DfsIterator {
   1.130 @@ -162,13 +193,20 @@
   1.131      ReachedMap& reached;
   1.132      bool own_reached_map;
   1.133    public:
   1.134 +    /// In that constructor \c _reached have to be a reference 
   1.135 +    /// for a bool Node-map. The algorithm will search in a dfs order for 
   1.136 +    /// the nodes which are \c false initially
   1.137      DfsIterator(const Graph& _graph, ReachedMap& _reached) : 
   1.138        graph(&_graph), reached(_reached), 
   1.139        own_reached_map(false) { }
   1.140 +    /// The same as above, but the map of reached nodes is 
   1.141 +    /// constructed dynamically 
   1.142 +    /// to everywhere false.
   1.143      DfsIterator(const Graph& _graph) : 
   1.144        graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 
   1.145        own_reached_map(true) { }
   1.146      ~DfsIterator() { if (own_reached_map) delete &reached; }
   1.147 +    /// This method markes s reached and first out-edge is processed.
   1.148      void pushAndSetReached(Node s) { 
   1.149        actual_node=s;
   1.150        reached.set(s, true);
   1.151 @@ -176,6 +214,8 @@
   1.152        graph->first(e, s);
   1.153        dfs_stack.push(e); 
   1.154      }
   1.155 +    /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator, 
   1.156 +    /// its \c operator++() iterates on the edges in a dfs order.
   1.157      DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
   1.158      operator++() { 
   1.159        actual_edge=dfs_stack.top();
   1.160 @@ -200,19 +240,28 @@
   1.161        }
   1.162        return *this;
   1.163      }
   1.164 +    ///
   1.165      bool finished() const { return dfs_stack.empty(); }
   1.166 +    ///
   1.167      operator OutEdgeIt() const { return actual_edge; }
   1.168 +    ///
   1.169      bool isBNodeNewlyReached() const { return b_node_newly_reached; }
   1.170 +    ///
   1.171      bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
   1.172 +    ///
   1.173      Node aNode() const { return actual_node; /*FIXME*/}
   1.174 +    ///
   1.175      Node bNode() const { return graph->bNode(actual_edge); }
   1.176 +    ///
   1.177      const ReachedMap& getReachedMap() const { return reached; }
   1.178 +    ///
   1.179      const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
   1.180    };
   1.181  
   1.182 -  /// Dfs searches from s for the nodes wich are not marked in 
   1.183 +  /// Dfs searches for the nodes wich are not marked in 
   1.184    /// \c reached_map
   1.185 -  /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
   1.186 +  /// Reached is a read-write bool Node-map, 
   1.187 +  /// Pred is a write Node-map, have to be.
   1.188    template <typename Graph, 
   1.189  	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
   1.190  	    typename PredMap
   1.191 @@ -223,12 +272,15 @@
   1.192      typedef typename Parent::Node Node;
   1.193      PredMap& pred;
   1.194    public:
   1.195 +    /// The algorithm will search in a dfs order for 
   1.196 +    /// the nodes which are \c false initially. 
   1.197 +    /// The constructor makes no initial changes on the maps.
   1.198      Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
   1.199 -    /// s is marked to be reached and pushed in the bfs queue.
   1.200 +    /// \c s is marked to be reached and pushed in the bfs queue.
   1.201      /// If the queue is empty, then the first out-edge is processed.
   1.202 -    /// If s was not marked previously, then 
   1.203 -    /// in addition its pred is set to be INVALID. 
   1.204 -    /// if s was marked previuosly, then it is simply pushed.
   1.205 +    /// If \c s was not marked previously, then 
   1.206 +    /// in addition its pred is set to be \c INVALID. 
   1.207 +    /// if \c s was marked previuosly, then it is simply pushed.
   1.208      void push(Node s) { 
   1.209        if (this->reached[s]) {
   1.210  	Parent::pushAndSetReached(s);
   1.211 @@ -237,11 +289,13 @@
   1.212  	pred.set(s, INVALID);
   1.213        }
   1.214      }
   1.215 -    /// A bfs is processed from s.
   1.216 +    /// A bfs is processed from \c s.
   1.217      void run(Node s) {
   1.218        push(s);
   1.219        while (!this->finished()) this->operator++();
   1.220      }
   1.221 +    /// Beside the dfs iteration, \c pred is saved in a 
   1.222 +    /// newly reached node. 
   1.223      Dfs<Graph, ReachedMap, PredMap> operator++() {
   1.224        Parent::operator++();
   1.225        if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
   1.226 @@ -250,6 +304,7 @@
   1.227        }
   1.228        return *this;
   1.229      }
   1.230 +    ///
   1.231      const PredMap& getPredMap() const { return pred; }
   1.232    };
   1.233