marci@301: // -*- c++ -*- marci@301: #ifndef HUGO_BFS_ITERATOR_H marci@301: #define HUGO_BFS_ITERATOR_H marci@301: marci@301: #include marci@301: #include marci@301: #include marci@301: marci@301: namespace hugo { marci@301: marci@303: template */ > marci@360: class BfsIterator { marci@303: protected: marci@303: typedef typename Graph::Node Node; marci@303: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@303: const Graph* graph; marci@301: std::queue bfs_queue; marci@301: ReachedMap& reached; marci@301: bool b_node_newly_reached; marci@301: OutEdgeIt actual_edge; marci@301: bool own_reached_map; marci@301: public: marci@360: BfsIterator(const Graph& _graph, ReachedMap& _reached) : marci@303: graph(&_graph), reached(_reached), marci@301: own_reached_map(false) { } marci@360: BfsIterator(const Graph& _graph) : marci@303: graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), marci@301: own_reached_map(true) { } marci@360: ~BfsIterator() { if (own_reached_map) delete &reached; } marci@409: //s is marcked reached. marci@409: //if the queue is empty, then the its is pushed ant the first OutEdgeIt is processe. marci@409: //is the queue is not empty, then is it pushed. marci@301: void pushAndSetReached(Node s) { marci@301: reached.set(s, true); marci@301: if (bfs_queue.empty()) { marci@301: bfs_queue.push(s); marci@303: graph->first(actual_edge, s); marci@303: if (graph->valid(actual_edge)) { marci@303: Node w=graph->bNode(actual_edge); marci@303: if (!reached[w]) { marci@301: bfs_queue.push(w); marci@301: reached.set(w, true); marci@301: b_node_newly_reached=true; marci@301: } else { marci@301: b_node_newly_reached=false; marci@301: } marci@301: } marci@301: } else { marci@301: bfs_queue.push(s); marci@301: } marci@301: } marci@360: BfsIterator& marci@301: operator++() { marci@303: if (graph->valid(actual_edge)) { marci@303: graph->next(actual_edge); marci@303: if (graph->valid(actual_edge)) { marci@303: Node w=graph->bNode(actual_edge); marci@303: if (!reached[w]) { marci@301: bfs_queue.push(w); marci@301: reached.set(w, true); marci@301: b_node_newly_reached=true; marci@301: } else { marci@301: b_node_newly_reached=false; marci@301: } marci@301: } marci@301: } else { marci@301: bfs_queue.pop(); marci@301: if (!bfs_queue.empty()) { marci@303: graph->first(actual_edge, bfs_queue.front()); marci@303: if (graph->valid(actual_edge)) { marci@303: Node w=graph->bNode(actual_edge); marci@303: if (!reached[w]) { marci@301: bfs_queue.push(w); marci@301: reached.set(w, true); marci@301: b_node_newly_reached=true; marci@301: } else { marci@301: b_node_newly_reached=false; marci@301: } marci@301: } marci@301: } marci@301: } marci@301: return *this; marci@301: } marci@301: bool finished() const { return bfs_queue.empty(); } marci@409: operator OutEdgeIt() const { return actual_edge; } marci@301: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@303: bool isANodeExamined() const { return !(graph->valid(actual_edge)); } marci@301: Node aNode() const { return bfs_queue.front(); } marci@303: Node bNode() const { return graph->bNode(actual_edge); } marci@301: const ReachedMap& getReachedMap() const { return reached; } marci@301: const std::queue& getBfsQueue() const { return bfs_queue; } marci@301: }; marci@301: marci@409: /// Bfs searches from s for the nodes wich are not marked in marci@409: /// reachedmap marci@409: template , marci@409: typename PredMap marci@409: =typename Graph::template NodeMap, marci@409: typename DistMap=typename Graph::template NodeMap > marci@409: class Bfs : public BfsIterator { marci@409: typedef BfsIterator Parent; marci@409: protected: marci@409: typedef typename Parent::Node Node; marci@409: PredMap& pred; marci@409: DistMap& dist; marci@409: public: marci@409: Bfs(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator(_graph, _reached), pred(&_pred), dist(&_dist) { } marci@409: //s is marked to be reached and pushed in the bfs queue. marci@409: //if the queue is empty, then the first out-edge is processed marci@409: //If s was not marked previously, then marci@409: //in addition its pred is set to be INVALID, and dist to 0. marci@409: //if s was marked previuosly, then it is simply pushed. marci@409: void push(Node s) { marci@409: if (this->reached[s]) { marci@409: Parent::pushAndSetReached(s); marci@409: } else { marci@409: Parent::pushAndSetReached(s); marci@409: pred.set(s, INVALID); marci@409: dist.set(s, 0); marci@409: } marci@409: } marci@409: void run(Node s) { marci@409: push(s); marci@409: while (!this->finished()) this->operator++(); marci@409: } marci@409: Bfs operator++() { marci@409: Parent::operator++(); marci@415: if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) marci@415: { marci@415: pred.set(this->bNode(), this->actual_edge); marci@415: dist.set(this->bNode(), dist[this->aNode()]); marci@409: } marci@409: return *this; marci@409: } marci@409: const PredMap& getPredMap() const { return pred; } marci@409: const DistMap& getDistMap() const { return dist; } marci@409: }; marci@409: marci@303: template */ > marci@360: class DfsIterator { marci@303: protected: marci@303: typedef typename Graph::Node Node; marci@303: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@303: const Graph* graph; marci@301: std::stack dfs_stack; marci@301: bool b_node_newly_reached; marci@301: OutEdgeIt actual_edge; marci@301: Node actual_node; marci@301: ReachedMap& reached; marci@301: bool own_reached_map; marci@301: public: marci@360: DfsIterator(const Graph& _graph, ReachedMap& _reached) : marci@303: graph(&_graph), reached(_reached), marci@301: own_reached_map(false) { } marci@360: DfsIterator(const Graph& _graph) : marci@303: graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), marci@301: own_reached_map(true) { } marci@360: ~DfsIterator() { if (own_reached_map) delete &reached; } marci@301: void pushAndSetReached(Node s) { marci@301: actual_node=s; marci@301: reached.set(s, true); marci@301: OutEdgeIt e; marci@303: graph->first(e, s); marci@301: dfs_stack.push(e); marci@301: } marci@360: DfsIterator& marci@301: operator++() { marci@301: actual_edge=dfs_stack.top(); marci@301: //actual_node=G.aNode(actual_edge); marci@303: if (graph->valid(actual_edge)/*.valid()*/) { marci@303: Node w=graph->bNode(actual_edge); marci@301: actual_node=w; marci@303: if (!reached[w]) { marci@301: OutEdgeIt e; marci@303: graph->first(e, w); marci@301: dfs_stack.push(e); marci@301: reached.set(w, true); marci@301: b_node_newly_reached=true; marci@301: } else { marci@303: actual_node=graph->aNode(actual_edge); marci@303: graph->next(dfs_stack.top()); marci@301: b_node_newly_reached=false; marci@301: } marci@301: } else { marci@301: //actual_node=G.aNode(dfs_stack.top()); marci@301: dfs_stack.pop(); marci@301: } marci@301: return *this; marci@301: } marci@301: bool finished() const { return dfs_stack.empty(); } marci@409: operator OutEdgeIt() const { return actual_edge; } marci@301: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@303: bool isANodeExamined() const { return !(graph->valid(actual_edge)); } marci@301: Node aNode() const { return actual_node; /*FIXME*/} marci@389: Node bNode() const { return graph->bNode(actual_edge); } marci@301: const ReachedMap& getReachedMap() const { return reached; } marci@301: const std::stack& getDfsStack() const { return dfs_stack; } marci@301: }; marci@301: marci@301: } // namespace hugo marci@301: marci@301: #endif //HUGO_BFS_ITERATOR_H