marci@602: // -*- c++ -*- alpar@921: #ifndef LEMON_BFS_DFS_H alpar@921: #define LEMON_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: alpar@921: #include marci@602: alpar@921: namespace lemon { marci@944: namespace marci { marci@602: marci@602: /// Bfs searches for the nodes wich are not marked in marci@602: /// \c reached_map marci@944: /// RM have to be a read-write bool node-map. marci@615: /// \ingroup galgs marci@602: template */ > marci@602: class BfsIterator { marci@944: public: marci@944: typedef RM ReachedMap; marci@602: protected: marci@602: typedef typename Graph::Node Node; marci@777: typedef typename Graph::Edge Edge; marci@602: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@602: const Graph* graph; marci@602: std::queue bfs_queue; marci@944: ReachedMap* reached_map; marci@602: bool b_node_newly_reached; marci@944: //OutEdgeIt actual_edge; marci@777: Edge actual_edge; marci@944: /// \e marci@944: BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { } marci@944: /// RM have to be set before any bfs operation. marci@944: BfsIterator& setReached(RM& _reached_map) { marci@944: reached_map=&_reached_map; marci@944: } marci@602: public: marci@944: /// In that constructor \c _reached_map have to be a reference marci@650: /// for a bool bode-map. The algorithm will search for the marci@650: /// initially \c false nodes marci@650: /// in a bfs order. marci@944: BfsIterator(const Graph& _graph, ReachedMap& _reached_map) : marci@944: graph(&_graph), reached_map(&_reached_map) { } marci@602: /// The same as above, but the map storing the reached nodes marci@602: /// is constructed dynamically to everywhere false. marci@650: /// \deprecated marci@944: // BfsIterator(const Graph& _graph) : marci@944: // graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)), marci@944: // own_reached_map(true) { } marci@944: // /// The map storing the reached nodes have to be destroyed if marci@944: // /// it was constructed dynamically marci@944: // ~BfsIterator() { if (own_reached_map) delete reached_map; } 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@777: BfsIterator& pushAndSetReached(Node s) { marci@944: reached_map->set(s, true); marci@602: if (bfs_queue.empty()) { marci@602: bfs_queue.push(s); marci@777: actual_edge=OutEdgeIt(*graph, s); marci@777: //graph->first(actual_edge, s); alpar@774: if (actual_edge!=INVALID) { alpar@774: Node w=graph->head(actual_edge); marci@944: if (!(*reached_map)[w]) { marci@602: bfs_queue.push(w); marci@944: reached_map->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@777: return *this; 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++() { alpar@774: if (actual_edge!=INVALID) { marci@777: actual_edge=++OutEdgeIt(*graph, actual_edge); marci@777: //++actual_edge; alpar@774: if (actual_edge!=INVALID) { alpar@774: Node w=graph->head(actual_edge); marci@944: if (!(*reached_map)[w]) { marci@602: bfs_queue.push(w); marci@944: reached_map->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@777: actual_edge=OutEdgeIt(*graph, bfs_queue.front()); marci@777: //graph->first(actual_edge, bfs_queue.front()); alpar@774: if (actual_edge!=INVALID) { alpar@774: Node w=graph->head(actual_edge); marci@944: if (!(*reached_map)[w]) { marci@602: bfs_queue.push(w); marci@944: reached_map->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@646: /// Returns true iff the algorithm is finished. 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. alpar@921: ///\bug Edge have to be in LEMON 0.2 marci@777: operator Edge() const { return actual_edge; } marci@646: /// Returns if b-node has been reached just now. marci@602: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@646: /// Returns if a-node is examined. alpar@774: bool isANodeExamined() const { return actual_edge==INVALID; } marci@646: /// Returns a-node of the actual edge, so does if the edge is invalid. marci@777: Node tail() const { return bfs_queue.front(); } marci@646: /// \pre The actual edge have to be valid. marci@777: Node head() const { return graph->head(actual_edge); } marci@615: /// Guess what? marci@650: /// \deprecated marci@944: const ReachedMap& reachedMap() const { return *reached_map; } marci@944: /// Guess what? marci@944: /// \deprecated marci@944: typename ReachedMap::ValueType reached(const Node& n) const { marci@944: return (*reached_map)[n]; marci@944: } marci@615: /// Guess what? marci@650: /// \deprecated 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@944: /// RM have to work as a read-write bool Node-map, marci@944: /// PM is a write edge node-map and marci@944: /// PNM is a write node node-map and marci@944: /// DM is a read-write node-map of integral value, have to be. marci@615: /// \ingroup galgs marci@602: template , marci@944: typename PM marci@602: =typename Graph::template NodeMap, marci@944: typename PNM marci@944: =typename Graph::template NodeMap, marci@944: typename DM=typename Graph::template NodeMap > marci@944: class Bfs : public BfsIterator { marci@944: typedef BfsIterator Parent; marci@944: public: marci@944: typedef RM ReachedMap; marci@944: typedef PM PredMap; marci@944: typedef PNM PredNodeMap; marci@944: typedef DM DistMap; marci@602: protected: marci@602: typedef typename Parent::Node Node; marci@944: PredMap* pred_map; marci@944: PredNodeMap* pred_node_map; marci@944: DistMap* dist_map; marci@944: /// \e marci@944: Bfs marci@944: (const Graph& _graph) : BfsIterator(_graph) { } marci@944: /// PM have to be set before any bfs operation. marci@944: Bfs& marci@944: setPredMap(PredMap& _pred_map) { marci@944: pred_map=&_pred_map; marci@944: } marci@944: /// PredNodeMap have to be set before any bfs operation. marci@944: Bfs& marci@944: setPredNodeMap(PredNodeMap& _pred_node_map) { marci@944: pred_node_map=&_pred_node_map; marci@944: } marci@944: /// DistMap have to be set before any bfs operation. marci@944: Bfs& marci@944: setDistMap(DistMap& _dist_map) { marci@944: dist_map=&_dist_map; marci@944: } 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@944: Bfs marci@944: (const Graph& _graph, ReachedMap& _reached_map, marci@944: PredMap& _pred_map, PredNodeMap& _pred_node_map, marci@944: DistMap& _dist_map) : BfsIterator(_graph, _reached_map), marci@944: pred_map(&_pred_map), pred_node_map(&_pred_node_map), marci@944: dist_map(&_dist_map) { } 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@944: /// in addition its pred_map is set to be \c INVALID, marci@944: /// and dist_map to \c 0. marci@602: /// if \c s was marked previuosly, then it is simply pushed. marci@944: Bfs& push(Node s) { marci@944: if ((*(this->reached_map))[s]) { marci@602: Parent::pushAndSetReached(s); marci@602: } else { marci@602: Parent::pushAndSetReached(s); marci@944: pred_map->set(s, INVALID); marci@944: pred_node_map->set(s, INVALID); marci@944: dist_map->set(s, 0); marci@602: } marci@777: return *this; marci@602: } marci@602: /// A bfs is processed from \c s. marci@944: Bfs& run(Node s) { marci@602: push(s); marci@602: while (!this->finished()) this->operator++(); marci@777: return *this; marci@602: } marci@944: /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a marci@602: /// newly reached node. marci@944: Bfs& operator++() { marci@602: Parent::operator++(); marci@944: if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) marci@602: { marci@944: pred_map->set(this->head(), this->actual_edge); marci@944: pred_node_map->set(this->head(), this->tail()); marci@944: dist_map->set(this->head(), (*dist_map)[this->tail()]); marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@650: /// \deprecated marci@944: const PredMap& predMap() const { return *pred_map; } marci@944: /// Guess what? marci@944: /// \deprecated marci@944: typename PredMap::ValueType pred(const Node& n) const { marci@944: return (*pred_map)[n]; marci@944: } marci@944: /// Guess what? marci@944: /// \deprecated marci@944: const PredNodeMap& predNodeMap() const { return *pred_node_map; } marci@944: /// Guess what? marci@944: /// \deprecated marci@944: typename PredNodeMap::ValueType predNode(const Node& n) const { marci@944: return (*pred_node_map)[n]; marci@944: } marci@615: /// Guess what? marci@650: /// \deprecated marci@944: const DistMap& distMap() const { return *dist_map; } marci@944: /// Guess what? marci@944: /// \deprecated marci@944: typename DistMap::ValueType dist(const Node& n) const { marci@944: return (*dist_map)[n]; marci@944: } marci@602: }; marci@602: marci@944: // template , marci@944: // typename PM marci@944: // =typename Graph::template NodeMap, marci@944: // typename PredNodeMap marci@944: // =typename Graph::template NodeMap, marci@944: // typename DistMap=typename Graph::template NodeMap > marci@944: // class BfsWizard : public Bfs { marci@944: // public: marci@944: // typedef Bfs Parent; marci@944: // protected: marci@944: // typedef typename Parent::Node Node; marci@944: // bool own_reached_map; marci@944: // bool own_pred_map; marci@944: // bool own_pred_node_map; marci@944: // bool own_dist_map; marci@944: marci@944: // BfsWizard& marci@944: // makeRreached() { marci@944: // own_reached_map=true; marci@944: // reached=new ReachedMap(*graph, false); marci@944: // } marci@944: // BfsWizard& marci@944: // deleteReachedMap() { marci@944: // own_reached_map=false; marci@944: // delete reached; marci@944: // } marci@944: marci@944: // BfsWizard& marci@944: // makePM() { marci@944: // own_pred_map=true; marci@944: // pred_map=new PM(*graph, INVALID); marci@944: // } marci@944: // BfsWizard& marci@944: // deletePM() { marci@944: // own_pred_map=false; marci@944: // delete pred_map; marci@944: // } marci@944: marci@944: // BfsWizard& marci@944: // makePredNodeMap() { marci@944: // own_pred_node_map=true; marci@944: // pred_node_map=new PredNodeMap(*graph, INVALID); marci@944: // } marci@944: // BfsWizard& marci@944: // deletePredNodeMap() { marci@944: // own_pred_node_map=false; marci@944: // delete pred_node_map; marci@944: // } marci@944: marci@944: // BfsWizard& marci@944: // makeDistMap() { marci@944: // own_dist_map=true; marci@944: // dist_map=new DistMap(*graph, 0); marci@944: // } marci@944: // BfsWizard& marci@944: // deleteDistMap() { marci@944: // own_dist_map=false; marci@944: // delete dist_map; marci@944: // } marci@944: marci@944: // public: marci@944: // /// User friendly Bfs class. marci@944: // /// The maps which are not explicitly given by the user are marci@944: // /// constructed with false, INVALID, INVALID and 0 values. marci@944: // /// For the user defined maps, the values are not modified, and marci@944: // /// the bfs is processed without any preset on maps. Therefore, marci@944: // /// the bfs will search only the nodes which are set false previously marci@944: // /// in reached, and in the nodes wich are not newly reached by the marci@944: // /// search, the map values are not modified. marci@944: // BfsWizard marci@944: // (const Graph& _graph) : marci@944: // own_reached_map(false), marci@944: // own_pred_map(false), marci@944: // own_pred_node_map(false), marci@944: // own_dist_map(false) { marci@944: // } marci@944: marci@944: // /// \e marci@944: // ~BfsWizard() { marci@944: // if (own_reached_map) deleteReachedMap(); marci@944: // if (own_pred_map) deletePM(); marci@944: // if (own_pred_node_map) deletePredNodeMap(); marci@944: // if (own_dist_map) deleteDistMap(); marci@944: // } marci@944: marci@944: // /// \e marci@944: // BfsWizard& marci@944: // setReachedMap(ReachedMap& _reached) { marci@944: // if (own_reached_map) deleteReachedMap(); marci@944: // Parent::setReachedMap(_reached); marci@944: // } marci@944: // /// \e marci@944: // BfsWizard& marci@944: // setPM(PM& _pred) { marci@944: // if (own_pred_map) deletePM(); marci@944: // Parent::setPM(_pred); marci@944: // } marci@944: // /// \e marci@944: // BfsWizard& marci@944: // setPredNodeMap(PredNodeMap& _pred_node) { marci@944: // if (own_pred_node_map) deletePredNodeMap(); marci@944: // Parent::setPredNodeMap(_pred_node); marci@944: // } marci@944: // /// \e marci@944: // BfsWizard& marci@944: // setDistMap(DistMap& _dist) { marci@944: // if (own_dist_map) deleteDistMap(); marci@944: // Parent::setDistMap(_dist); marci@944: // } marci@944: marci@944: // /// \e marci@944: // BfsWizard& marci@944: // push(Node s) { marci@944: // if (!reached) makeReachedMap(); marci@944: // if (!pred_map) makePMMap(); marci@944: // if (!pred_node_map) makePredNodeMap(); marci@944: // if (!dist_map) makeDistMap(); marci@944: // push(s); marci@944: // return *this; marci@944: // } marci@944: marci@944: // /// \e marci@944: // BfsWizard& marci@944: // operator++() { marci@944: // if (!reached) makeRM(); marci@944: // if (!pred_map) makePMMap(); marci@944: // if (!pred_node_map) makePredNodeMap(); marci@944: // if (!dist_map) makeDistMap(); marci@944: // ++(*this); marci@944: // return *this; marci@944: // } marci@944: marci@944: // /// \e marci@944: // BfsWizard& marci@944: // run(Node s) { marci@944: // if (!reached) makeRM(); marci@944: // if (!pred_map) makePMMap(); marci@944: // if (!pred_node_map) makePredNodeMap(); marci@944: // if (!dist_map) makeDistMap(); marci@944: // run(s); marci@944: // return *this; marci@944: // } marci@944: marci@944: // }; marci@944: marci@944: 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@777: typedef typename Graph::Edge Edge; 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@777: Edge 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@650: /// 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@777: DfsIterator& pushAndSetReached(Node s) { marci@602: actual_node=s; marci@602: reached.set(s, true); marci@777: OutEdgeIt e(*graph, s); marci@777: //graph->first(e, s); marci@602: dfs_stack.push(e); marci@777: return *this; 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(); alpar@774: if (actual_edge!=INVALID/*.valid()*/) { alpar@774: Node w=graph->head(actual_edge); marci@602: actual_node=w; marci@602: if (!reached[w]) { marci@777: OutEdgeIt e(*graph, w); marci@777: //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 { alpar@774: actual_node=graph->tail(actual_edge); alpar@774: ++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@646: /// Returns true iff the algorithm is finished. marci@602: bool finished() const { return dfs_stack.empty(); } marci@646: /// The conversion operator makes for converting the bfs-iterator marci@646: /// to an \c out-edge-iterator. alpar@921: ///\bug Edge have to be in LEMON 0.2 marci@777: operator Edge() const { return actual_edge; } marci@646: /// Returns if b-node has been reached just now. marci@602: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@646: /// Returns if a-node is examined. alpar@774: bool isANodeExamined() const { return actual_edge==INVALID; } marci@646: /// Returns a-node of the actual edge, so does if the edge is invalid. marci@777: Node tail() const { return actual_node; /*FIXME*/} marci@646: /// Returns b-node of the actual edge. marci@646: /// \pre The actual edge have to be valid. marci@777: Node head() const { return graph->head(actual_edge); } marci@615: /// Guess what? marci@650: /// \deprecated marci@602: const ReachedMap& getReachedMap() const { return reached; } marci@615: /// Guess what? marci@650: /// \deprecated 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@650: /// Reached is a read-write bool node-map, marci@650: /// 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. athos@671: 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@777: Dfs& 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@777: return *this; marci@602: } marci@602: /// A bfs is processed from \c s. marci@777: Dfs& run(Node s) { marci@602: push(s); marci@602: while (!this->finished()) this->operator++(); marci@777: return *this; 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@777: pred.set(this->head(), this->actual_edge); marci@602: } marci@602: return *this; marci@602: } marci@615: /// Guess what? marci@650: /// \deprecated marci@602: const PredMap& getPredMap() const { return pred; } marci@602: }; marci@602: marci@944: } // namespace marci alpar@921: } // namespace lemon marci@602: alpar@921: #endif //LEMON_BFS_DFS_H