marci@301: // -*- c++ -*-
marci@301: #ifndef HUGO_BFS_ITERATOR_H
marci@301: #define HUGO_BFS_ITERATOR_H
marci@301: 
marci@301: #include <queue>
marci@301: #include <stack>
marci@301: #include <utility>
marci@301: 
marci@560: #include <hugo/invalid.h>
marci@560: 
marci@301: namespace hugo {
marci@301: 
marci@303:   template <typename Graph, /*typename OutEdgeIt,*/ 
marci@303: 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
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<Node> 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@448:     /// This method markes s reached.
marci@448:     /// If the queue is empty, then s is pushed in the bfs queue 
marci@448:     /// and the first OutEdgeIt is processed.
marci@448:     /// If the queue is not empty, then s is simply 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@448:     /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator, 
marci@448:     /// its \c operator++() iterates on the edges in a bfs order.
marci@360:     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
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@448:     /// The conversion operator makes for converting the bfs-iterator 
marci@448:     /// to an \c out-edge-iterator.
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<Node>& getBfsQueue() const { return bfs_queue; }
marci@301:   };  
marci@301: 
marci@409:   /// Bfs searches from s for the nodes wich are not marked in 
marci@448:   /// \c reached_map
marci@448:   /// Reached is a read-write bool-map, Pred is a write-nodemap 
marci@448:   /// and dist is an rw-nodemap, have to be.
marci@409:   template <typename Graph, 
marci@409: 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
marci@409: 	    typename PredMap
marci@409: 	    =typename Graph::template NodeMap<typename Graph::Edge>, 
marci@409: 	    typename DistMap=typename Graph::template NodeMap<int> > 
marci@409:   class Bfs : public BfsIterator<Graph, ReachedMap> {
marci@409:     typedef BfsIterator<Graph, ReachedMap> 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<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
marci@448:     /// s is marked to be reached and pushed in the bfs queue.
marci@448:     /// If the queue is empty, then the first out-edge is processed.
marci@448:     /// If s was not marked previously, then 
marci@448:     /// in addition its pred is set to be INVALID, and dist to 0. 
marci@448:     /// 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@448:     /// A bfs is processed from s.
marci@409:     void run(Node s) {
marci@409:       push(s);
marci@409:       while (!this->finished()) this->operator++();
marci@409:     }
marci@409:     Bfs<Graph, ReachedMap, PredMap, DistMap> 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 <typename Graph, /*typename OutEdgeIt,*/ 
marci@303: 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
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<OutEdgeIt> 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<Graph, /*OutEdgeIt,*/ ReachedMap>& 
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<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
marci@301:   };
marci@301: 
marci@448:   /// Dfs searches from s for the nodes wich are not marked in 
marci@448:   /// \c reached_map
marci@448:   /// Reached is a read-write bool-map, Pred is a write-nodemap, have to be.
marci@448:   template <typename Graph, 
marci@448: 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
marci@448: 	    typename PredMap
marci@448: 	    =typename Graph::template NodeMap<typename Graph::Edge> > 
marci@448:   class Dfs : public DfsIterator<Graph, ReachedMap> {
marci@448:     typedef DfsIterator<Graph, ReachedMap> Parent;
marci@448:   protected:
marci@448:     typedef typename Parent::Node Node;
marci@448:     PredMap& pred;
marci@448:   public:
marci@448:     Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
marci@448:     /// s is marked to be reached and pushed in the bfs queue.
marci@448:     /// If the queue is empty, then the first out-edge is processed.
marci@448:     /// If s was not marked previously, then 
marci@448:     /// in addition its pred is set to be INVALID. 
marci@448:     /// if s was marked previuosly, then it is simply pushed.
marci@448:     void push(Node s) { 
marci@448:       if (this->reached[s]) {
marci@448: 	Parent::pushAndSetReached(s);
marci@448:       } else {
marci@448: 	Parent::pushAndSetReached(s);
marci@448: 	pred.set(s, INVALID);
marci@448:       }
marci@448:     }
marci@448:     /// A bfs is processed from s.
marci@448:     void run(Node s) {
marci@448:       push(s);
marci@448:       while (!this->finished()) this->operator++();
marci@448:     }
marci@448:     Dfs<Graph, ReachedMap, PredMap> operator++() {
marci@448:       Parent::operator++();
marci@448:       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
marci@448:       {
marci@448: 	pred.set(this->bNode(), this->actual_edge);
marci@448:       }
marci@448:       return *this;
marci@448:     }
marci@448:     const PredMap& getPredMap() const { return pred; }
marci@448:   };
marci@448: 
marci@448: 
marci@301: } // namespace hugo
marci@301: 
marci@301: #endif //HUGO_BFS_ITERATOR_H