#include <lemon/concept_check.h>

   /// \brief Visitor class for dfs.

   ///  

   /// It gives a simple interface for a functional interface for dfs 

   /// traversal. The traversal on a linear data structure. 

   template <typename _Graph>

   struct DfsVisitor {

     typedef _Graph Graph;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::Node Node;

     /// \brief Called when the edge reach a node.

     /// 

     /// It is called when the dfs find an edge which target is not

     /// reached yet.

     void discover(const Edge& edge) {}

     /// \brief Called when the node reached first time.

     /// 

     /// It is Called when the node reached first time.

     void reach(const Node& node) {}

     /// \brief Called when we step back on an edge.

     /// 

     /// It is called when the dfs should step back on the edge.

     void backtrack(const Edge& edge) {}

     /// \brief Called when we step back from the node.

     /// 

     /// It is called when we step back from the node.

     void leave(const Node& node) {}

     /// \brief Called when the edge examined but target of the edge 

     /// already discovered.

     /// 

     /// It called when the edge examined but the target of the edge 

     /// already discovered.

     void examine(const Edge& edge) {}

     /// \brief Called for the source node of the dfs.

     /// 

     /// It is called for the source node of the dfs.

     void start(const Node&) {}

     /// \brief Called when we leave the source node of the dfs.

     /// 

     /// It is called when we leave the source node of the dfs.

     void stop(const Node&) {}

     template <typename _Visitor>

     struct Constraints {

       void constraints() {

 	Edge edge;

 	Node node;

 	visitor.discover(edge);

 	visitor.reach(node);

 	visitor.backtrack(edge);

 	visitor.leave(node);

 	visitor.examine(edge);

 	visitor.start(node);

 	visitor.stop(edge);

       }

       _Visitor& visitor;

     };

   };

   /// \brief Default traits class of DfsVisit class.

   ///

   /// Default traits class of DfsVisit class.

   /// \param _Graph Graph type.

   template<class _Graph>

   struct DfsVisitDefaultTraits {

     /// \brief The graph type the algorithm runs on. 

     typedef _Graph Graph;

     /// \brief The type of the map that indicates which nodes are reached.

     /// 

     /// The type of the map that indicates which nodes are reached.

     /// It must meet the \ref concept::WriteMap "WriteMap" concept.

     /// \todo named parameter to set this type, function to read and write.

     typedef typename Graph::template NodeMap<bool> ReachedMap;

     /// \brief Instantiates a ReachedMap.

     ///

     /// This function instantiates a \ref ReachedMap. 

     /// \param G is the graph, to which

     /// we would like to define the \ref ReachedMap.

     static ReachedMap *createReachedMap(const Graph &graph) {

       return new ReachedMap(graph);

     }

   };

   /// %DFS Visit algorithm class.

   /// \ingroup flowalgs

   /// This class provides an efficient implementation of the %DFS algorithm

   /// with visitor interface.

   ///

   /// The %DfsVisit class provides an alternative interface to the Dfs

   /// class. It works with callback mechanism, the DfsVisit object calls

   /// on every dfs event the \c Visitor class member functions. 

   ///

   /// \param _Graph The graph type the algorithm runs on. The default value is

   /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it

   /// is only passed to \ref DfsDefaultTraits.

   /// \param _Visitor The Visitor object for the algorithm. The 

   /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which

   /// does not observe the Dfs events. If you want to observe the dfs

   /// events you should implement your own Visitor class.

   /// \param _Traits Traits class to set various data types used by the 

   /// algorithm. The default traits class is

   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".

   /// See \ref DfsVisitDefaultTraits for the documentation of

   /// a Dfs visit traits class.

   ///

   /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso

 #ifdef DOXYGEN

   template <typename _Graph, typename _Visitor, typename _Traits>

 #else

   template <typename _Graph = ListGraph,

 	    typename _Visitor = DfsVisitor<_Graph>,

 	    typename _Traits = DfsDefaultTraits<_Graph> >

 #endif

   class DfsVisit {

   public:

     /// \brief \ref Exception for uninitialized parameters.

     ///

     /// This error represents problems in the initialization

     /// of the parameters of the algorithms.

     class UninitializedParameter : public lemon::UninitializedParameter {

     public:

       virtual const char* exceptionName() const {

 	return "lemon::DfsVisit::UninitializedParameter";

       }

     };

     typedef _Traits Traits;

     typedef typename Traits::Graph Graph;

     typedef _Visitor Visitor;

     ///The type of the map indicating which nodes are reached.

     typedef typename Traits::ReachedMap ReachedMap;

   private:

     typedef typename Graph::Node Node;

     typedef typename Graph::NodeIt NodeIt;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::OutEdgeIt OutEdgeIt;

     /// Pointer to the underlying graph.

     const Graph *_graph;

     /// Pointer to the visitor object.

     Visitor *_visitor;

     ///Pointer to the map of reached status of the nodes.

     ReachedMap *_reached;

     ///Indicates if \ref _reached is locally allocated (\c true) or not.

     bool local_reached;

     std::vector<typename Graph::Edge> _stack;

     int _stack_head;

     /// \brief Creates the maps if necessary.

     ///

     /// Creates the maps if necessary.

     void create_maps() {

       if(!_reached) {

 	local_reached = true;

 	_reached = Traits::createReachedMap(*_graph);

       }

     }

   protected:

     DfsVisit() {}

   public:

     typedef DfsVisit Create;

     /// \name Named template parameters

     ///@{

     template <class T>

     struct DefReachedMapTraits : public Traits {

       typedef T ReachedMap;

       static ReachedMap *createReachedMap(const Graph &graph) {

 	throw UninitializedParameter();

       }

     };

     /// \brief \ref named-templ-param "Named parameter" for setting 

     /// ReachedMap type

     ///

     /// \ref named-templ-param "Named parameter" for setting ReachedMap type

     template <class T>

     struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {

       typedef Dfs< Graph, DefReachedMapTraits<T> > Create;

     };

     ///@}

   public:      

     /// \brief Constructor.

     ///

     /// Constructor.

     ///

     /// \param graph the graph the algorithm will run on.

     /// \param visitor The visitor of the algorithm.

     ///

     DfsVisit(const Graph& graph, Visitor& visitor) 

       : _graph(&graph), _visitor(&visitor),

 	_reached(0), local_reached(false) {}

     /// \brief Destructor.

     ///

     /// Destructor.

     ~DfsVisit() {

       if(local_reached) delete _reached;

     }

     /// \brief Sets the map indicating if a node is reached.

     ///

     /// Sets the map indicating if a node is reached.

     /// If you don't use this function before calling \ref run(),

     /// it will allocate one. The destuctor deallocates this

     /// automatically allocated map, of course.

     /// \return <tt> (*this) </tt>

     DfsVisit &reachedMap(ReachedMap &m) {

       if(local_reached) {

 	delete _reached;

 	local_reached=false;

       }

       _reached = &m;

       return *this;

     }

   public:

     /// \name Execution control

     /// The simplest way to execute the algorithm is to use

     /// one of the member functions called \c run(...).

     /// \n

     /// If you need more control on the execution,

     /// first you must call \ref init(), then you can add several source nodes

     /// with \ref addSource().

     /// Finally \ref start() will perform the actual path

     /// computation.

     /// @{

     /// \brief Initializes the internal data structures.

     ///

     /// Initializes the internal data structures.

     ///

     void init() {

       create_maps();

       _stack.resize(countNodes(*_graph));

       _stack_head = -1;

       for (NodeIt u(*_graph) ; u != INVALID ; ++u) {

 	_reached->set(u, false);

       }

     }

     /// \brief Adds a new source node.

     ///

     /// Adds a new source node to the set of nodes to be processed.

     void addSource(Node s) {

       if(!(*_reached)[s]) {

 	  _reached->set(s,true);

 	  _visitor->start(s);

 	  _visitor->reach(s);

 	  Edge e; 

 	  _graph->firstOut(e, s);

 	  if (e != INVALID) {

 	    _stack[++_stack_head] = e;

 	  } else {

 	    _visitor->leave(s);

 	  }

 	}

     }

     /// \brief Processes the next edge.

     ///

     /// Processes the next edge.

     ///

     /// \return The processed edge.

     ///

     /// \pre The stack must not be empty!

     Edge processNextEdge() { 

       Edge e = _stack[_stack_head];

       Node m = _graph->target(e);

       if(!(*_reached)[m]) {

 	_visitor->discover(e);

 	_visitor->reach(m);

 	_reached->set(m, true);

 	_graph->firstOut(_stack[++_stack_head], m);

       } else {

 	_visitor->examine(e);

 	m = _graph->source(e);

 	_graph->nextOut(_stack[_stack_head]);

       }

       while (_stack_head>=0 && _stack[_stack_head] == INVALID) {

 	_visitor->leave(m);

 	--_stack_head;

 	if (_stack_head >= 0) {

 	  _visitor->backtrack(_stack[_stack_head]);

 	  m = _graph->source(_stack[_stack_head]);

 	  _graph->nextOut(_stack[_stack_head]);

 	} else {

 	  _visitor->stop(m);	  

 	}

       }

       return e;

     }

     /// \brief Next edge to be processed.

     ///

     /// Next edge to be processed.

     ///

     /// \return The next edge to be processed or INVALID if the stack is

     /// empty.

     Edge nextEdge() { 

       return _stack_head >= 0 ? _stack[_stack_head] : INVALID;

     }

     /// \brief Returns \c false if there are nodes

     /// to be processed in the queue

     ///

     /// Returns \c false if there are nodes

     /// to be processed in the queue

     ///

     /// \todo This should be called emptyStack() or some "neutral" name.

     bool emptyQueue() { return _stack_head < 0; }

     /// \brief Returns the number of the nodes to be processed.

     ///

     /// Returns the number of the nodes to be processed in the queue.

     ///

     ///\todo This should be called stackSize() or some "neutral" name.

     int queueSize() { return _stack_head + 1; }

     /// \brief Executes the algorithm.

     ///

     /// Executes the algorithm.

     ///

     /// \pre init() must be called and at least one node should be added

     /// with addSource() before using this function.

     void start() {

       while ( !emptyQueue() ) processNextEdge();

     }

     /// \brief Executes the algorithm until \c dest is reached.

     ///

     /// Executes the algorithm until \c dest is reached.

     ///

     /// \pre init() must be called and at least one node should be added

     /// with addSource() before using this function.

     void start(Node dest) {

       while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) 

 	processNextEdge();

     }

     /// \brief Executes the algorithm until a condition is met.

     ///

     /// Executes the algorithm until a condition is met.

     ///

     /// \pre init() must be called and at least one node should be added

     /// with addSource() before using this function.

     ///

     /// \param nm must be a bool (or convertible) edge map. The algorithm

     /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.

     ///

     /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,

     /// not a node map.

     template <typename EM>

     void start(const EM &em) {

       while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();

     }

     /// \brief Runs %DFS algorithm from node \c s.

     ///

     /// This method runs the %DFS algorithm from a root node \c s.

     /// \note d.run(s) is just a shortcut of the following code.

     /// \code

     ///   d.init();

     ///   d.addSource(s);

     ///   d.start();

     /// \endcode

     void run(Node s) {

       init();

       addSource(s);

       start();

     }

     ///@}

     /// \name Query Functions

     /// The result of the %DFS algorithm can be obtained using these

     /// functions.\n

     /// Before the use of these functions,

     /// either run() or start() must be called.

     ///@{

     /// \brief Checks if a node is reachable from the root.

     ///

     /// Returns \c true if \c v is reachable from the root(s).

     /// \warning The source nodes are inditated as unreachable.

     /// \pre Either \ref run() or \ref start()

     /// must be called before using this function.

     ///

     bool reached(Node v) { return (*_reached)[v]; }

     ///@}

   };