diff -r c43e7d0f075b -r a6e2b02f496a src/work/marci/bfs_iterator.h --- a/src/work/marci/bfs_iterator.h Mon May 10 15:15:37 2004 +0000 +++ b/src/work/marci/bfs_iterator.h Mon May 10 16:31:48 2004 +0000 @@ -10,6 +10,9 @@ namespace hugo { + /// Bfs searches for the nodes wich are not marked in + /// \c reached_map + /// Reached have to work as read-write bool Node-map. template */ > class BfsIterator { @@ -23,17 +26,24 @@ OutEdgeIt actual_edge; bool own_reached_map; public: + /// In that constructor \c _reached have to be a reference + /// for a bool Node-map. The algorithm will search in a bfs order for + /// the nodes which are \c false initially BfsIterator(const Graph& _graph, ReachedMap& _reached) : graph(&_graph), reached(_reached), own_reached_map(false) { } + /// The same as above, but the map storing the reached nodes + /// is constructed dynamically to everywhere false. BfsIterator(const Graph& _graph) : graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), own_reached_map(true) { } + /// The storing the reached nodes have to be destroyed if + /// it was constructed dynamically ~BfsIterator() { if (own_reached_map) delete &reached; } - /// This method markes s reached. - /// If the queue is empty, then s is pushed in the bfs queue - /// and the first OutEdgeIt is processed. - /// If the queue is not empty, then s is simply pushed. + /// This method markes \c s reached. + /// If the queue is empty, then \c s is pushed in the bfs queue + /// and the first out-edge is processed. + /// If the queue is not empty, then \c s is simply pushed. void pushAndSetReached(Node s) { reached.set(s, true); if (bfs_queue.empty()) { @@ -87,22 +97,33 @@ } return *this; } + /// bool finished() const { return bfs_queue.empty(); } /// The conversion operator makes for converting the bfs-iterator /// to an \c out-edge-iterator. + ///\bug Edge have to be in HUGO 0.2 operator OutEdgeIt() const { return actual_edge; } + /// bool isBNodeNewlyReached() const { return b_node_newly_reached; } + /// bool isANodeExamined() const { return !(graph->valid(actual_edge)); } + /// Node aNode() const { return bfs_queue.front(); } + /// Node bNode() const { return graph->bNode(actual_edge); } + /// const ReachedMap& getReachedMap() const { return reached; } + /// const std::queue& getBfsQueue() const { return bfs_queue; } }; - /// Bfs searches from s for the nodes wich are not marked in + /// Bfs searches for the nodes wich are not marked in /// \c reached_map - /// Reached is a read-write bool-map, Pred is a write-nodemap - /// and dist is an rw-nodemap, have to be. + /// Reached have to work as a read-write bool Node-map, + /// Pred is a write Edge Node-map and + /// Dist is a read-write int Node-map, have to be. + ///\todo In fact onsly simple operations requirement are needed for + /// Dist::Value. template , typename PredMap @@ -115,12 +136,15 @@ PredMap& pred; DistMap& dist; public: + /// The algorithm will search in a bfs order for + /// the nodes which are \c false initially. + /// The constructor makes no initial changes on the maps. Bfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator(_graph, _reached), pred(&_pred), dist(&_dist) { } - /// s is marked to be reached and pushed in the bfs queue. + /// \c s is marked to be reached and pushed in the bfs queue. /// If the queue is empty, then the first out-edge is processed. - /// If s was not marked previously, then - /// in addition its pred is set to be INVALID, and dist to 0. - /// if s was marked previuosly, then it is simply pushed. + /// If \c s was not marked previously, then + /// in addition its pred is set to be \c INVALID, and dist to \c 0. + /// if \c s was marked previuosly, then it is simply pushed. void push(Node s) { if (this->reached[s]) { Parent::pushAndSetReached(s); @@ -130,11 +154,13 @@ dist.set(s, 0); } } - /// A bfs is processed from s. + /// A bfs is processed from \c s. void run(Node s) { push(s); while (!this->finished()) this->operator++(); } + /// Beside the bfs iteration, \c pred and \dist are saved in a + /// newly reached node. Bfs operator++() { Parent::operator++(); if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) @@ -144,10 +170,15 @@ } return *this; } + /// const PredMap& getPredMap() const { return pred; } + /// const DistMap& getDistMap() const { return dist; } }; + /// Dfs searches for the nodes wich are not marked in + /// \c reached_map + /// Reached have to be a read-write bool Node-map. template */ > class DfsIterator { @@ -162,13 +193,20 @@ ReachedMap& reached; bool own_reached_map; public: + /// In that constructor \c _reached have to be a reference + /// for a bool Node-map. The algorithm will search in a dfs order for + /// the nodes which are \c false initially DfsIterator(const Graph& _graph, ReachedMap& _reached) : graph(&_graph), reached(_reached), own_reached_map(false) { } + /// The same as above, but the map of reached nodes is + /// constructed dynamically + /// to everywhere false. DfsIterator(const Graph& _graph) : graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), own_reached_map(true) { } ~DfsIterator() { if (own_reached_map) delete &reached; } + /// This method markes s reached and first out-edge is processed. void pushAndSetReached(Node s) { actual_node=s; reached.set(s, true); @@ -176,6 +214,8 @@ graph->first(e, s); dfs_stack.push(e); } + /// As \c DfsIterator works as an edge-iterator, + /// its \c operator++() iterates on the edges in a dfs order. DfsIterator& operator++() { actual_edge=dfs_stack.top(); @@ -200,19 +240,28 @@ } return *this; } + /// bool finished() const { return dfs_stack.empty(); } + /// operator OutEdgeIt() const { return actual_edge; } + /// bool isBNodeNewlyReached() const { return b_node_newly_reached; } + /// bool isANodeExamined() const { return !(graph->valid(actual_edge)); } + /// Node aNode() const { return actual_node; /*FIXME*/} + /// Node bNode() const { return graph->bNode(actual_edge); } + /// const ReachedMap& getReachedMap() const { return reached; } + /// const std::stack& getDfsStack() const { return dfs_stack; } }; - /// Dfs searches from s for the nodes wich are not marked in + /// Dfs searches for the nodes wich are not marked in /// \c reached_map - /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be. + /// Reached is a read-write bool Node-map, + /// Pred is a write Node-map, have to be. template , typename PredMap @@ -223,12 +272,15 @@ typedef typename Parent::Node Node; PredMap& pred; public: + /// The algorithm will search in a dfs order for + /// the nodes which are \c false initially. + /// The constructor makes no initial changes on the maps. Dfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator(_graph, _reached), pred(&_pred) { } - /// s is marked to be reached and pushed in the bfs queue. + /// \c s is marked to be reached and pushed in the bfs queue. /// If the queue is empty, then the first out-edge is processed. - /// If s was not marked previously, then - /// in addition its pred is set to be INVALID. - /// if s was marked previuosly, then it is simply pushed. + /// If \c s was not marked previously, then + /// in addition its pred is set to be \c INVALID. + /// if \c s was marked previuosly, then it is simply pushed. void push(Node s) { if (this->reached[s]) { Parent::pushAndSetReached(s); @@ -237,11 +289,13 @@ pred.set(s, INVALID); } } - /// A bfs is processed from s. + /// A bfs is processed from \c s. void run(Node s) { push(s); while (!this->finished()) this->operator++(); } + /// Beside the dfs iteration, \c pred is saved in a + /// newly reached node. Dfs operator++() { Parent::operator++(); if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) @@ -250,6 +304,7 @@ } return *this; } + /// const PredMap& getPredMap() const { return pred; } };