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 <queue>
marci@602: #include <stack>
marci@602: #include <utility>
marci@602: 
alpar@921: #include <lemon/invalid.h>
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 <typename Graph, /*typename OutEdgeIt,*/ 
marci@944: 	    typename RM/*=typename Graph::NodeMap<bool>*/ >
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<Node> 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<Graph, RM>& 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<Graph, /*OutEdgeIt,*/ ReachedMap>& 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@986: 	  Node w=graph->target(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<Graph, ReachedMap> works as an edge-iterator, 
marci@602:     /// its \c operator++() iterates on the edges in a bfs order.
marci@602:     BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
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@986: 	  Node w=graph->target(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@986: 	    Node w=graph->target(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.
alpar@986:     Node source() const { return bfs_queue.front(); }
marci@646:     /// \pre The actual edge have to be valid.
alpar@986:     Node target() const { return graph->target(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 
alpar@987:     typename ReachedMap::Value 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<Node>& 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 <typename Graph, 
marci@944: 	    typename RM=typename Graph::template NodeMap<bool>, 
marci@944: 	    typename PM
marci@602: 	    =typename Graph::template NodeMap<typename Graph::Edge>, 
marci@944: 	    typename PNM
marci@944: 	    =typename Graph::template NodeMap<typename Graph::Node>, 
marci@944: 	    typename DM=typename Graph::template NodeMap<int> > 
marci@944:   class Bfs : public BfsIterator<Graph, RM> {
marci@944:     typedef BfsIterator<Graph, RM> 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<Graph, RM, PM, PNM, DM>
marci@944:     (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
marci@944:     /// PM have to be set before any bfs operation.
marci@944:     Bfs<Graph, RM, PM, PNM, DM>& 
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<Graph, RM, PM, PNM, DM>& 
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<Graph, RM, PM, PNM, DM>& 
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<Graph, RM, PM, PNM, DM>
marci@944:     (const Graph& _graph, ReachedMap& _reached_map, 
marci@944:      PredMap& _pred_map, PredNodeMap& _pred_node_map, 
marci@944:      DistMap& _dist_map) : BfsIterator<Graph, RM>(_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<Graph, RM, PM, PNM, DM>& 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<Graph, RM, PM, PNM, DM>& 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<Graph, RM, PM, PNM, DM>& operator++() {
marci@602:       Parent::operator++();
marci@944:       if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) 
marci@602:       {
alpar@986: 	pred_map->set(this->target(), this->actual_edge);
alpar@986: 	pred_node_map->set(this->target(), this->source());
alpar@986: 	dist_map->set(this->target(), (*dist_map)[this->source()]);
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 
alpar@987:     typename PredMap::Value 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 
alpar@987:     typename PredNodeMap::Value 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 
alpar@987:     typename DistMap::Value dist(const Node& n) const { 
marci@944:       return (*dist_map)[n]; 
marci@944:     }
marci@602:   };
marci@602: 
marci@944: //   template <typename Graph, 
marci@944: // 	    typename RM=typename Graph::template NodeMap<bool>, 
marci@944: // 	    typename PM
marci@944: // 	    =typename Graph::template NodeMap<typename Graph::Edge>, 
marci@944: // 	    typename PredNodeMap
marci@944: // 	    =typename Graph::template NodeMap<typename Graph::Node>, 
marci@944: // 	    typename DistMap=typename Graph::template NodeMap<int> > 
marci@944: //     class BfsWizard : public Bfs<Graph> {
marci@944: //     public:
marci@944: //       typedef Bfs<Graph, PM, PredNodeMap, DistMap> 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<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       makeRreached() { 
marci@944: // 	own_reached_map=true;
marci@944: // 	reached=new ReachedMap(*graph, false);
marci@944: //       }
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       deleteReachedMap() { 
marci@944: // 	own_reached_map=false;
marci@944: // 	delete reached;
marci@944: //       }
marci@944: 
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       makePM() { 
marci@944: // 	own_pred_map=true;
marci@944: // 	pred_map=new PM(*graph, INVALID);
marci@944: //       }
marci@944: //       BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>& 
marci@944: //       deletePM() { 
marci@944: // 	own_pred_map=false;
marci@944: // 	delete pred_map;
marci@944: //       }
marci@944: 
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       makePredNodeMap() { 
marci@944: // 	own_pred_node_map=true;
marci@944: // 	pred_node_map=new PredNodeMap(*graph, INVALID);
marci@944: //       }
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       deletePredNodeMap() { 
marci@944: // 	own_pred_node_map=false;
marci@944: // 	delete pred_node_map;
marci@944: //       }
marci@944: 
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
marci@944: //       makeDistMap() { 
marci@944: // 	own_dist_map=true;
marci@944: // 	dist_map=new DistMap(*graph, 0);
marci@944: //       }
marci@944: //       BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>
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<Graph, RM, PM, PredNodeMap, DistMap>() { 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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<Graph, RM, PM, PredNodeMap, DistMap>& 
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 <typename Graph, /*typename OutEdgeIt,*/ 
marci@602: 	    typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
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<OutEdgeIt> 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<Graph, /*OutEdgeIt,*/ ReachedMap>& 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<Graph, ReachedMap> works as an edge-iterator, 
marci@602:     /// its \c operator++() iterates on the edges in a dfs order.
marci@602:     DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& 
marci@602:     operator++() { 
marci@602:       actual_edge=dfs_stack.top();
alpar@774:       if (actual_edge!=INVALID/*.valid()*/) { 
alpar@986: 	Node w=graph->target(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@986: 	  actual_node=graph->source(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.
alpar@986:     Node source() const { return actual_node; /*FIXME*/}
marci@646:     /// Returns b-node of the actual edge. 
marci@646:     /// \pre The actual edge have to be valid.
alpar@986:     Node target() const { return graph->target(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<OutEdgeIt>& 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 <typename Graph, 
marci@602: 	    typename ReachedMap=typename Graph::template NodeMap<bool>, 
marci@602: 	    typename PredMap
marci@602: 	    =typename Graph::template NodeMap<typename Graph::Edge> > 
marci@602:   class Dfs : public DfsIterator<Graph, ReachedMap> {
marci@602:     typedef DfsIterator<Graph, ReachedMap> 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<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_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<Graph, ReachedMap, PredMap>& 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<Graph, ReachedMap, PredMap>& 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<Graph, ReachedMap, PredMap>& operator++() {
marci@602:       Parent::operator++();
marci@602:       if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) 
marci@602:       {
alpar@986: 	pred.set(this->target(), 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