Index: lemon/dfs.h
===================================================================
--- lemon/dfs.h	(revision 1710)
+++ lemon/dfs.h	(revision 1749)
@@ -28,6 +28,7 @@
 #include <lemon/maps.h>
 
+#include <lemon/concept_check.h>
+
 namespace lemon {
-
 
   
@@ -124,6 +125,4 @@
   ///
   ///\author Jacint Szabo and Alpar Juttner
-  ///\todo A compare object would be nice.
-
 #ifdef DOXYGEN
   template <typename GR,
@@ -276,5 +275,5 @@
     ///
     template <class T>
-    struct DefReachedMap {
+    struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
       typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
     };
@@ -327,5 +326,4 @@
       G(&_G),
       _pred(NULL), local_pred(false),
-//       _predNode(NULL), local_predNode(false),
       _dist(NULL), local_dist(false),
       _reached(NULL), local_reached(false),
@@ -337,5 +335,4 @@
     {
       if(local_pred) delete _pred;
-//       if(local_predNode) delete _predNode;
       if(local_dist) delete _dist;
       if(local_reached) delete _reached;
@@ -359,21 +356,4 @@
       return *this;
     }
-
-//     ///Sets the map storing the predecessor nodes.
-
-//     ///Sets the map storing the predecessor nodes.
-//     ///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>
-//     Dfs &predNodeMap(PredNodeMap &m) 
-//     {
-//       if(local_predNode) {
-// 	delete _predNode;
-// 	local_predNode=false;
-//       }
-//       _predNode = &m;
-//       return *this;
-//     }
 
     ///Sets the map storing the distances calculated by the algorithm.
@@ -469,5 +449,4 @@
 	  _reached->set(s,true);
 	  _pred->set(s,INVALID);
-	  // _predNode->set(u,INVALID);
 	  OutEdgeIt e(*G,s);
 	  if(e!=INVALID) {
@@ -496,5 +475,4 @@
 	_pred->set(m,e);
 	_reached->set(m,true);
-	//	  _pred_node->set(m,G->source(e));
 	++_stack_head;
 	_stack[_stack_head] = OutEdgeIt(*G, m);
@@ -505,5 +483,4 @@
 	++_stack[_stack_head];
       }
-      //'m' is now the (original) source of the _stack[_stack_head] 
       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
 	_processed->set(m,true);
@@ -591,12 +568,12 @@
     ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
     ///
-    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
+    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
     ///not a node map.
-    template<class NM>
-      void start(const NM &nm)
-      {
-	while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
-      }
-    
+    template<class EM>
+    void start(const EM &em)
+    {
+      while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
+    }
+
     ///Runs %DFS algorithm from node \c s.
     
@@ -726,11 +703,4 @@
     const PredMap &predMap() const { return *_pred;}
  
-//     ///Returns a reference to the map of nodes of %DFS paths.
-
-//     ///Returns a reference to the NodeMap of the last but one nodes of the
-//     ///%DFS tree.
-//     ///\pre \ref run() must be called before using this function.
-//     const PredNodeMap &predNodeMap() const { return *_predNode;}
-
     ///Checks if a node is reachable from the root.
 
@@ -775,21 +745,4 @@
       return new PredMap();
     }
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the %DFS paths.
-//     ///
-//     ///The type of the map that stores the last but one
-//     ///nodes of the %DFS paths.
-//     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
-//     ///
-//     typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
-//     ///Instantiates a PredNodeMap.
-    
-//     ///This function instantiates a \ref PredNodeMap. 
-//     ///\param G is the graph, to which
-//     ///we would like to define the \ref PredNodeMap
-//     static PredNodeMap *createPredNodeMap(const GR &G)
-//     {
-//       return new PredNodeMap();
-//     }
 
     ///The type of the map that indicates which nodes are processed.
@@ -872,6 +825,4 @@
     ///Pointer to the map of predecessors edges.
     void *_pred;
-//     ///Pointer to the map of predecessors nodes.
-//     void *_predNode;
     ///Pointer to the map of distances.
     void *_dist;
@@ -885,5 +836,4 @@
     /// all of the attributes to default values (0, INVALID).
     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
-// 			   _predNode(0),
 			   _dist(0), _source(INVALID) {}
 
@@ -897,5 +847,4 @@
     DfsWizardBase(const GR &g, Node s=INVALID) :
       _g((void *)&g), _reached(0), _processed(0), _pred(0),
-//       _predNode(0),
       _dist(0), _source(s) {}
 
@@ -946,7 +895,4 @@
     ///edges of the %DFS paths.
     typedef typename TR::PredMap PredMap;
-//     ///\brief The type of the map that stores the last but one
-//     ///nodes of the %DFS paths.
-//     typedef typename TR::PredNodeMap PredNodeMap;
     ///The type of the map that stores the distances of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -979,5 +925,4 @@
       if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
       if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
-//       if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
       if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
       alg.run(Base::_source);
@@ -1056,25 +1001,4 @@
     }
     
-
-//     template<class T>
-//     struct DefPredNodeMapBase : public Base {
-//       typedef T PredNodeMap;
-//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
-//       DefPredNodeMapBase(const TR &b) : TR(b) {}
-//     };
-    
-//     ///\brief \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     /// \ref named-templ-param "Named parameter"
-//     ///function for setting PredNodeMap type
-//     ///
-//     template<class T>
-//     DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
-//     {
-//       Base::_predNode=(void *)&t;
-//       return DfsWizard<DefPredNodeMapBase<T> >(*this);
-//     }
-   
     template<class T>
     struct DefDistMapBase : public Base {
@@ -1133,4 +1057,412 @@
   }
 
+  /// \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]; }
+    ///@}
+  };
+
+
 } //END OF NAMESPACE LEMON
 
