Index: src/hugo/bfs.h
===================================================================
--- src/hugo/bfs.h	(revision 774)
+++ src/hugo/bfs.h	(revision 780)
@@ -281,5 +281,5 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
+    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     
   };
Index: src/hugo/dfs.h
===================================================================
--- src/hugo/dfs.h	(revision 780)
+++ src/hugo/dfs.h	(revision 780)
@@ -0,0 +1,301 @@
+// -*- C++ -*-
+#ifndef HUGO_DFS_H
+#define HUGO_DFS_H
+
+///\ingroup flowalgs
+///\file
+///\brief Dfs algorithm.
+///
+///\todo Revise Manual.
+
+#include <hugo/bin_heap.h>
+#include <hugo/invalid.h>
+
+namespace hugo {
+
+/// \addtogroup flowalgs
+/// @{
+
+  ///%Dfs algorithm class.
+
+  ///This class provides an efficient implementation of %Dfs algorithm.
+  ///The edge lengths are passed to the algorithm using a
+  ///\ref ReadMapSkeleton "readable map",
+  ///so it is easy to change it to any kind of length.
+  ///
+  ///The type of the length is determined by the \c ValueType of the length map.
+  ///
+  ///It is also possible to change the underlying priority heap.
+  ///
+  ///\param GR The graph type the algorithm runs on.
+  ///\param LM This read-only
+  ///EdgeMap
+  ///determines the
+  ///lengths of the edges. It is read once for each edge, so the map
+  ///may involve in relatively time consuming process to compute the edge
+  ///length if it is necessary. The default map type is
+  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
+  ///\param Heap The heap type used by the %Dfs
+  ///algorithm. The default
+  ///is using \ref BinHeap "binary heap".
+  ///
+  ///\author Jacint Szabo and Alpar Juttner
+  ///\todo We need a typedef-names should be standardized. (-:
+  ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap
+  ///should not be fixed. (Problematic to solve).
+
+#ifdef DOXYGEN
+  template <typename GR>
+#else
+  template <typename GR>
+#endif
+  class Dfs{
+  public:
+    ///The type of the underlying graph.
+    typedef GR Graph;
+    typedef typename Graph::Node Node;
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::Edge Edge;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    typedef typename Graph::template NodeMap<Edge> PredMap;
+    ///\brief The type of the map that stores the last but one
+    ///nodes of the shortest paths.
+    typedef typename Graph::template NodeMap<Node> PredNodeMap;
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename Graph::template NodeMap<int> DistMap;
+
+  private:
+    const Graph *G;
+    PredMap *predecessor;
+    bool local_predecessor;
+    PredNodeMap *pred_node;
+    bool local_pred_node;
+    DistMap *distance;
+    bool local_distance;
+
+    //The source node of the last execution.
+    Node source;
+
+
+    ///Initialize maps.
+    
+    ///\todo Error if \c G or are \c NULL.
+    ///\todo Better memory allocation (instead of new).
+    void init_maps() 
+    {
+//       if(!length) {
+// 	local_length = true;
+// 	length = new LM(G);
+//       }
+      if(!predecessor) {
+	local_predecessor = true;
+	predecessor = new PredMap(*G);
+      }
+      if(!pred_node) {
+	local_pred_node = true;
+	pred_node = new PredNodeMap(*G);
+      }
+      if(!distance) {
+	local_distance = true;
+	distance = new DistMap(*G);
+      }
+    }
+    
+  public :    
+    Dfs(const Graph& _G) :
+      G(&_G),
+      predecessor(NULL), local_predecessor(false),
+      pred_node(NULL), local_pred_node(false),
+      distance(NULL), local_distance(false)
+    { }
+    
+    ~Dfs() 
+    {
+      //      if(local_length) delete length;
+      if(local_predecessor) delete predecessor;
+      if(local_pred_node) delete pred_node;
+      if(local_distance) delete distance;
+    }
+
+    ///Sets the graph the algorithm will run on.
+
+    ///Sets the graph the algorithm will run on.
+    ///\return <tt> (*this) </tt>
+    Dfs &setGraph(const Graph &_G) 
+    {
+      G = &_G;
+      return *this;
+    }
+    ///Sets the length map.
+
+    ///Sets the map storing the predecessor edges.
+
+    ///Sets the map storing the predecessor edges.
+    ///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 &setPredMap(PredMap &m) 
+    {
+      if(local_predecessor) {
+	delete predecessor;
+	local_predecessor=false;
+      }
+      predecessor = &m;
+      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 &setPredNodeMap(PredNodeMap &m) 
+    {
+      if(local_pred_node) {
+	delete pred_node;
+	local_pred_node=false;
+      }
+      pred_node = &m;
+      return *this;
+    }
+
+    ///Sets the map storing the distances calculated by the algorithm.
+
+    ///Sets the map storing the distances calculated by the algorithm.
+    ///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 &setDistMap(DistMap &m) 
+    {
+      if(local_distance) {
+	delete distance;
+	local_distance=false;
+      }
+      distance = &m;
+      return *this;
+    }
+    
+  ///Runs %DFS algorithm from node \c s.
+
+  ///This method runs the %DFS algorithm from a root node \c s
+  ///in order to
+  ///compute the
+  ///shortest path to each node. The algorithm computes
+  ///- The shortest path tree.
+  ///- The distance of each node from the root.
+ 
+    void run(Node s) {
+      
+      init_maps();
+      
+      source = s;
+      
+      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
+	predecessor->set(u,INVALID);
+	pred_node->set(u,INVALID);
+      }
+      
+      int N=G->nodeNum();
+      std::vector<typename Graph::OutEdgeIt> Q(N);
+
+      int Qh=0;
+      
+      G->first(Q[Qh],s);
+      distance->set(s, 0);
+
+      Node n=s;
+      Node m;
+      OutEdgeIt e;
+      do {
+	if((e=Q[Qh])!=INVALID)
+	  if((m=G->head(e))!=s && (*predecessor)[m=G->head(e)]==INVALID) {
+	    predecessor->set(m,e);
+	    pred_node->set(m,n);
+	    G->first(Q[++Qh],m);
+	    distance->set(m,Qh);
+	    n=m;
+	  }
+	  else ++Q[Qh];
+	else if(--Qh>=0) n=G->tail(Q[Qh]);
+      } while(Qh>=0);
+    }
+    
+    ///The distance of a node from the root.
+
+    ///Returns the distance of a node from the root.
+    ///\pre \ref run() must be called before using this function.
+    ///\warning If node \c v in unreachable from the root the return value
+    ///of this funcion is undefined.
+    int dist(Node v) const { return (*distance)[v]; }
+
+    ///Returns the 'previous edge' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
+    ///i.e. it returns the last edge from a shortest path from the root to \c
+    ///v. It is \ref INVALID
+    ///if \c v is unreachable from the root or if \c v=s. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///this function.
+    Edge pred(Node v) const { return (*predecessor)[v]; }
+
+    ///Returns the 'previous node' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous node' of the shortest path tree,
+    ///i.e. it returns the last but one node from a shortest path from the
+    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
+    ///\c v=s. The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
+    ///using this function.
+    Node predNode(Node v) const { return (*pred_node)[v]; }
+    
+    ///Returns a reference to the NodeMap of distances.
+    
+    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
+    ///be called before using this function.
+    const DistMap &distMap() const { return *distance;}
+ 
+    ///Returns a reference to the shortest path tree map.
+
+    ///Returns a reference to the NodeMap of the edges of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    const PredMap &predMap() const { return *predecessor;}
+ 
+    ///Returns a reference to the map of nodes of shortest paths.
+
+    ///Returns a reference to the NodeMap of the last but one nodes of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    const PredNodeMap &predNodeMap() const { return *pred_node;}
+
+    ///Checks if a node is reachable from the root.
+
+    ///Returns \c true if \c v is reachable from the root.
+    ///\warning The root node is reported to be reached!
+    ///
+    ///\pre \ref run() must be called before using this function.
+    ///
+    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
+    
+  };
+  
+
+  // **********************************************************************
+  //  IMPLEMENTATIONS
+  // **********************************************************************
+
+/// @}
+  
+} //END OF NAMESPACE HUGO
+
+#endif
+
+
Index: src/hugo/dijkstra.h
===================================================================
--- src/hugo/dijkstra.h	(revision 776)
+++ src/hugo/dijkstra.h	(revision 780)
@@ -280,4 +280,5 @@
     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     ///this function.
+    ///\todo predEdge could be a better name.
     Edge pred(Node v) const { return (*predecessor)[v]; }
 
@@ -318,5 +319,5 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
+    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     
   };
Index: src/test/Makefile.am
===================================================================
--- src/test/Makefile.am	(revision 774)
+++ src/test/Makefile.am	(revision 780)
@@ -3,5 +3,5 @@
 noinst_HEADERS = test_tools.h
 
-check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
+check_PROGRAMS = graph_test dijkstra_test bfs_test dfs_test time_measure_test \
 	error_test xy_test \
 	unionfind_test test_tools_pass test_tools_fail
@@ -13,4 +13,5 @@
 dijkstra_test_SOURCES = dijkstra_test.cc
 bfs_test_SOURCES = bfs_test.cc
+dfs_test_SOURCES = dfs_test.cc
 unionfind_test_SOURCES = unionfind_test.cc
 time_measure_test_SOURCES = time_measure_test.cc
Index: src/test/bfs_test.cc
===================================================================
--- src/test/bfs_test.cc	(revision 774)
+++ src/test/bfs_test.cc	(revision 780)
@@ -77,13 +77,16 @@
   }
 
-  ///\bug This works only for integer lengths
-  for(NodeIt v(G); v==INVALID; ++v)
-    if ( bfs_test.reached(v) ) {
+  for(NodeIt v(G); v==INVALID; ++v) {
+    check(bfs_test.reached(v),"Each node should be reached.");
+    if ( bfs_test.pred(v)!=INVALID ) {
       Edge e=bfs_test.pred(v);
       Node u=G.tail(e);
+      check(u==bfs_test.predNode(v),"Wrong tree.");
       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
-	    "Bad shortest path tree edge! Difference: " 
+	    "Wrong distance. Difference: " 
 	    << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
 			- 1));
     }
+  }
 }
+
Index: src/test/dfs_test.cc
===================================================================
--- src/test/dfs_test.cc	(revision 780)
+++ src/test/dfs_test.cc	(revision 780)
@@ -0,0 +1,79 @@
+#include "test_tools.h"
+#include <hugo/smart_graph.h>
+#include <hugo/dfs.h>
+
+using namespace hugo;
+
+const int PET_SIZE =5;
+
+
+void check_Dfs_SmartGraph_Compile() 
+{
+  typedef int VType;
+  typedef SmartGraph Graph;
+
+  typedef Graph::Edge Edge;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::EdgeMap<VType> LengthMap;
+ 
+  typedef Dfs<Graph> BType;
+  
+  Graph G;
+  Node n;
+  Edge e;
+  VType l;
+  bool b;
+  BType::DistMap d(G);
+  BType::PredMap p(G);
+  BType::PredNodeMap pn(G);
+  LengthMap cap(G);
+  
+  BType dfs_test(G);
+  
+  dfs_test.run(n);
+  
+  l  = dfs_test.dist(n);
+  e  = dfs_test.pred(n);
+  n  = dfs_test.predNode(n);
+  d  = dfs_test.distMap();
+  p  = dfs_test.predMap();
+  pn = dfs_test.predNodeMap();
+  b  = dfs_test.reached(n);
+
+}
+
+int main()
+{
+    
+  typedef SmartGraph Graph;
+
+  typedef Graph::Edge Edge;
+  typedef Graph::Node Node;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::EdgeMap<int> LengthMap;
+
+  Graph G;
+  Node s, t;
+  PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
+   
+  s=ps.outer[2];
+  t=ps.inner[0];
+  
+  Dfs<Graph> dfs_test(G);
+  dfs_test.run(s);  
+  
+  for(NodeIt v(G); v!=INVALID; ++v) {
+    check(dfs_test.reached(v),"Each node should be reached.");
+    if ( dfs_test.pred(v)!=INVALID ) {
+      Edge e=dfs_test.pred(v);
+      Node u=G.tail(e);
+      check(u==dfs_test.predNode(v),"Wrong tree.");
+      check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
+	    "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
+    }
+  }
+}
+
Index: src/test/dijkstra_test.cc
===================================================================
--- src/test/dijkstra_test.cc	(revision 776)
+++ src/test/dijkstra_test.cc	(revision 780)
@@ -87,12 +87,16 @@
 
   ///\bug This works only for integer lengths
-  for(NodeIt v(G); v!=INVALID; ++v)
-    if ( dijkstra_test.reached(v) ) {
+  for(NodeIt v(G); v!=INVALID; ++v){
+    check(dijkstra_test.reached(v),"Each node should be reached.");
+    if ( dijkstra_test.pred(v)!=INVALID ) {
       Edge e=dijkstra_test.pred(v);
       Node u=G.tail(e);
+      check(u==dijkstra_test.predNode(v),"Wrong tree.");
       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
-	    "Bad shortest path tree edge! Difference: " 
+	    "Wrong distance! Difference: " 
 	    << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
 			    - cap[e]));
     }
+  }
 }
+
