marci@602: // -*- c++ -*- marci@602: #ifndef HUGO_BFS_DFS_H marci@602: #define HUGO_BFS_DFS_H marci@602: marci@615: /// \ingroup galgs marci@615: /// \file marci@615: /// \brief Bfs and dfs iterators. marci@604: /// marci@615: /// This file contains bfs and dfs iterator classes. marci@604: /// marci@615: // /// \author Marton Makai marci@604: marci@602: #include marci@602: #include marci@602: #include marci@602: marci@602: #include marci@602: marci@602: namespace hugo { marci@602: marci@602: /// Bfs searches for the nodes wich are not marked in marci@602: /// \c reached_map marci@602: /// Reached have to work as read-write bool Node-map. marci@615: /// \ingroup galgs marci@602: template */ > marci@602: class BfsIterator { marci@602: protected: marci@602: typedef typename Graph::Node Node; marci@602: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@602: const Graph* graph; marci@602: std::queue bfs_queue; marci@602: ReachedMap& reached; marci@602: bool b_node_newly_reached; marci@602: OutEdgeIt actual_edge; marci@602: bool own_reached_map; marci@602: public: marci@602: /// In that constructor \c _reached have to be a reference marci@602: /// for a bool Node-map. The algorithm will search in a bfs order for marci@602: /// the nodes which are \c false initially marci@602: BfsIterator(const Graph& _graph, ReachedMap& _reached) : marci@602: graph(&_graph), reached(_reached), marci@602: own_reached_map(false) { } marci@602: /// The same as above, but the map storing the reached nodes marci@602: /// is constructed dynamically to everywhere false. marci@602: BfsIterator(const Graph& _graph) : marci@602: graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), marci@602: own_reached_map(true) { } marci@604: /// The map storing the reached nodes have to be destroyed if marci@602: /// it was constructed dynamically marci@602: ~BfsIterator() { if (own_reached_map) delete &reached; } marci@602: /// This method markes \c s reached. marci@602: /// If the queue is empty, then \c s is pushed in the bfs queue marci@602: /// and the first out-edge is processed. marci@602: /// If the queue is not empty, then \c s is simply pushed. marci@602: void pushAndSetReached(Node s) { marci@602: reached.set(s, true); marci@602: if (bfs_queue.empty()) { marci@602: bfs_queue.push(s); marci@602: graph->first(actual_edge, s); marci@602: if (graph->valid(actual_edge)) { marci@602: Node w=graph->bNode(actual_edge); marci@602: if (!reached[w]) { marci@602: bfs_queue.push(w); marci@602: reached.set(w, true); marci@602: b_node_newly_reached=true; marci@602: } else { marci@602: b_node_newly_reached=false; marci@602: } marci@602: } marci@602: } else { marci@602: bfs_queue.push(s); marci@602: } marci@602: } marci@602: /// As \c BfsIterator works as an edge-iterator, marci@602: /// its \c operator++() iterates on the edges in a bfs order. marci@602: BfsIterator& marci@602: operator++() { marci@602: if (graph->valid(actual_edge)) { marci@602: graph->next(actual_edge); marci@602: if (graph->valid(actual_edge)) { marci@602: Node w=graph->bNode(actual_edge); marci@602: if (!reached[w]) { marci@602: bfs_queue.push(w); marci@602: reached.set(w, true); marci@602: b_node_newly_reached=true; marci@602: } else { marci@602: b_node_newly_reached=false; marci@602: } marci@602: } marci@602: } else { marci@602: bfs_queue.pop(); marci@602: if (!bfs_queue.empty()) { marci@602: graph->first(actual_edge, bfs_queue.front()); marci@602: if (graph->valid(actual_edge)) { marci@602: Node w=graph->bNode(actual_edge); marci@602: if (!reached[w]) { marci@602: bfs_queue.push(w); marci@602: reached.set(w, true); marci@602: b_node_newly_reached=true; marci@602: } else { marci@602: b_node_newly_reached=false; marci@602: } marci@602: } marci@602: } marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@602: bool finished() const { return bfs_queue.empty(); } marci@602: /// The conversion operator makes for converting the bfs-iterator marci@602: /// to an \c out-edge-iterator. marci@602: ///\bug Edge have to be in HUGO 0.2 marci@602: operator OutEdgeIt() const { return actual_edge; } marci@615: /// Guess what? marci@602: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@615: /// Guess what? marci@602: bool isANodeExamined() const { return !(graph->valid(actual_edge)); } marci@615: /// Guess what? marci@602: Node aNode() const { return bfs_queue.front(); } marci@615: /// Guess what? marci@602: Node bNode() const { return graph->bNode(actual_edge); } marci@615: /// Guess what? marci@602: const ReachedMap& getReachedMap() const { return reached; } marci@615: /// Guess what? marci@602: const std::queue& getBfsQueue() const { return bfs_queue; } marci@615: }; marci@602: marci@602: /// Bfs searches for the nodes wich are not marked in marci@602: /// \c reached_map marci@602: /// Reached have to work as a read-write bool Node-map, marci@602: /// Pred is a write Edge Node-map and marci@615: /// Dist is a read-write Node-map of integral value, have to be. marci@615: /// \ingroup galgs marci@602: template , marci@602: typename PredMap marci@602: =typename Graph::template NodeMap, marci@602: typename DistMap=typename Graph::template NodeMap > marci@602: class Bfs : public BfsIterator { marci@602: typedef BfsIterator Parent; marci@602: protected: marci@602: typedef typename Parent::Node Node; marci@602: PredMap& pred; marci@602: DistMap& dist; marci@602: public: marci@602: /// The algorithm will search in a bfs order for marci@602: /// the nodes which are \c false initially. marci@602: /// The constructor makes no initial changes on the maps. marci@602: Bfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator(_graph, _reached), pred(&_pred), dist(&_dist) { } marci@602: /// \c s is marked to be reached and pushed in the bfs queue. marci@602: /// If the queue is empty, then the first out-edge is processed. marci@602: /// If \c s was not marked previously, then marci@602: /// in addition its pred is set to be \c INVALID, and dist to \c 0. marci@602: /// if \c s was marked previuosly, then it is simply pushed. marci@602: void push(Node s) { marci@602: if (this->reached[s]) { marci@602: Parent::pushAndSetReached(s); marci@602: } else { marci@602: Parent::pushAndSetReached(s); marci@602: pred.set(s, INVALID); marci@602: dist.set(s, 0); marci@602: } marci@602: } marci@602: /// A bfs is processed from \c s. marci@602: void run(Node s) { marci@602: push(s); marci@602: while (!this->finished()) this->operator++(); marci@602: } marci@602: /// Beside the bfs iteration, \c pred and \dist are saved in a marci@602: /// newly reached node. marci@604: Bfs& operator++() { marci@602: Parent::operator++(); marci@602: if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) marci@602: { marci@602: pred.set(this->bNode(), this->actual_edge); marci@602: dist.set(this->bNode(), dist[this->aNode()]); marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@602: const PredMap& getPredMap() const { return pred; } marci@615: /// Guess what? marci@602: const DistMap& getDistMap() const { return dist; } marci@602: }; marci@602: marci@602: /// Dfs searches for the nodes wich are not marked in marci@602: /// \c reached_map marci@602: /// Reached have to be a read-write bool Node-map. marci@615: /// \ingroup galgs marci@602: template */ > marci@602: class DfsIterator { marci@602: protected: marci@602: typedef typename Graph::Node Node; marci@602: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@602: const Graph* graph; marci@602: std::stack dfs_stack; marci@602: bool b_node_newly_reached; marci@602: OutEdgeIt actual_edge; marci@602: Node actual_node; marci@602: ReachedMap& reached; marci@602: bool own_reached_map; marci@602: public: marci@602: /// In that constructor \c _reached have to be a reference marci@602: /// for a bool Node-map. The algorithm will search in a dfs order for marci@602: /// the nodes which are \c false initially marci@602: DfsIterator(const Graph& _graph, ReachedMap& _reached) : marci@602: graph(&_graph), reached(_reached), marci@602: own_reached_map(false) { } marci@602: /// The same as above, but the map of reached nodes is marci@602: /// constructed dynamically marci@602: /// to everywhere false. marci@602: DfsIterator(const Graph& _graph) : marci@602: graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), marci@602: own_reached_map(true) { } marci@602: ~DfsIterator() { if (own_reached_map) delete &reached; } marci@602: /// This method markes s reached and first out-edge is processed. marci@602: void pushAndSetReached(Node s) { marci@602: actual_node=s; marci@602: reached.set(s, true); marci@602: OutEdgeIt e; marci@602: graph->first(e, s); marci@602: dfs_stack.push(e); marci@602: } marci@602: /// As \c DfsIterator works as an edge-iterator, marci@602: /// its \c operator++() iterates on the edges in a dfs order. marci@602: DfsIterator& marci@602: operator++() { marci@602: actual_edge=dfs_stack.top(); marci@602: //actual_node=G.aNode(actual_edge); marci@602: if (graph->valid(actual_edge)/*.valid()*/) { marci@602: Node w=graph->bNode(actual_edge); marci@602: actual_node=w; marci@602: if (!reached[w]) { marci@602: OutEdgeIt e; marci@602: graph->first(e, w); marci@602: dfs_stack.push(e); marci@602: reached.set(w, true); marci@602: b_node_newly_reached=true; marci@602: } else { marci@602: actual_node=graph->aNode(actual_edge); marci@602: graph->next(dfs_stack.top()); marci@602: b_node_newly_reached=false; marci@602: } marci@602: } else { marci@602: //actual_node=G.aNode(dfs_stack.top()); marci@602: dfs_stack.pop(); marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@602: bool finished() const { return dfs_stack.empty(); } marci@615: /// Guess what? marci@602: operator OutEdgeIt() const { return actual_edge; } marci@615: /// Guess what? marci@602: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@615: /// Guess what? marci@602: bool isANodeExamined() const { return !(graph->valid(actual_edge)); } marci@615: /// Guess what? marci@602: Node aNode() const { return actual_node; /*FIXME*/} marci@615: /// Guess what? marci@602: Node bNode() const { return graph->bNode(actual_edge); } marci@615: /// Guess what? marci@602: const ReachedMap& getReachedMap() const { return reached; } marci@615: /// Guess what? marci@602: const std::stack& getDfsStack() const { return dfs_stack; } marci@602: }; marci@602: marci@602: /// Dfs searches for the nodes wich are not marked in marci@602: /// \c reached_map marci@602: /// Reached is a read-write bool Node-map, marci@602: /// Pred is a write Node-map, have to be. marci@615: /// \ingroup galgs marci@602: template , marci@602: typename PredMap marci@602: =typename Graph::template NodeMap > marci@602: class Dfs : public DfsIterator { marci@602: typedef DfsIterator Parent; marci@602: protected: marci@602: typedef typename Parent::Node Node; marci@602: PredMap& pred; marci@602: public: marci@602: /// The algorithm will search in a dfs order for marci@602: /// the nodes which are \c false initially. marci@602: /// The constructor makes no initial changes on the maps. marci@602: Dfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator(_graph, _reached), pred(&_pred) { } marci@602: /// \c s is marked to be reached and pushed in the bfs queue. marci@602: /// If the queue is empty, then the first out-edge is processed. marci@602: /// If \c s was not marked previously, then marci@602: /// in addition its pred is set to be \c INVALID. marci@602: /// if \c s was marked previuosly, then it is simply pushed. marci@602: void push(Node s) { marci@602: if (this->reached[s]) { marci@602: Parent::pushAndSetReached(s); marci@602: } else { marci@602: Parent::pushAndSetReached(s); marci@602: pred.set(s, INVALID); marci@602: } marci@602: } marci@602: /// A bfs is processed from \c s. marci@602: void run(Node s) { marci@602: push(s); marci@602: while (!this->finished()) this->operator++(); marci@602: } marci@602: /// Beside the dfs iteration, \c pred is saved in a marci@602: /// newly reached node. marci@604: Dfs& operator++() { marci@602: Parent::operator++(); marci@602: if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) marci@602: { marci@602: pred.set(this->bNode(), this->actual_edge); marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@602: const PredMap& getPredMap() const { return pred; } marci@602: }; marci@602: marci@602: marci@602: } // namespace hugo marci@602: marci@602: #endif //HUGO_BFS_DFS_H