Changeset 1218:5331168bbb18 in lemon-0.x

Timestamp:

03/16/05 08:56:25 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1638

Message:

• Several updates and clarifications on dijkstra.h
• bfs.h and dfs.h is synchronized with dijkstra.h

Location:

src

Files:

• lemon/bfs.h (modified) (6 diffs)
• lemon/dfs.h (modified) (6 diffs)
• lemon/dijkstra.h (modified) (26 diffs)
• test/bfs_test.cc (modified) (2 diffs)
• test/dfs_test.cc (modified) (2 diffs)
• test/dijkstra_test.cc (modified) (1 diff)

src/lemon/bfs.h

@@ -21 +21 @@
 ///\file
 ///\brief Bfs algorithm.
-///
-///\todo Revise Manual.
-
-#include <lemon/bin_heap.h>
+
+#include <lemon/list_graph.h>
+#include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
-#include <lemon/graph_utils.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
 
 namespace lemon {
 
-/// \addtogroup flowalgs
-/// @{
-
+
+  
+  ///Default traits class of Bfs class.
+
+  ///Default traits class of Bfs class.
+  ///\param GR Graph type.
+  template<class GR>
+  struct BfsDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the shortest paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap(G);
+    }
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///
+//     ///The type of the map that stores the last but one
+//     ///nodes of the shortest 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.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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;
+    ///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 GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap(G);
+    }
+  };
+  
   ///%BFS algorithm class.
-
-  ///This class provides an efficient implementation of %BFS algorithm.
-  ///\param GR The graph type the algorithm runs on.
-  ///This class does the same as Dijkstra does with constant 1 edge length,
-  ///but it is faster.
+  
+  ///\ingroup flowalgs
+  ///This class provides an efficient implementation of the %BFS algorithm.
   ///
-  ///\author Alpar Juttner
+  ///\param GR The graph type the algorithm runs on. The default value is
+  ///\ref ListGraph. The value of GR is not used directly by Bfs, it
+  ///is only passed to \ref BfsDefaultTraits.
+  ///\param TR Traits class to set various data types used by the algorithm.
+  ///The default traits class is
+  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
+  ///See \ref BfsDefaultTraits for the documentation of
+  ///a Bfs traits class.
+  ///
+  ///\author Jacint Szabo and Alpar Juttner
+  ///\todo A compare object would be nice.
 
 #ifdef DOXYGEN
-  template <typename GR>
+  template <typename GR,
+            typename TR>
 #else
-  template <typename GR>
+  template <typename GR=ListGraph,
+            typename TR=BfsDefaultTraits<GR> >
 #endif
-  class Bfs{
+  class Bfs {
   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::Bfs::UninitializedParameter";
+      }
+    };
+
+    typedef TR Traits;
     ///The type of the underlying graph.
-    typedef GR Graph;
+    typedef typename TR::Graph Graph;
     ///\e
     typedef typename Graph::Node Node;
@@ -62 +175 @@
     ///\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;
+    typedef typename TR::PredMap PredMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map indicating which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///The type of the map indicating which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
     ///The type of the map that stores the dists of the nodes.
-    typedef typename Graph::template NodeMap<int> DistMap;
-
+    typedef typename TR::DistMap DistMap;
   private:
     /// Pointer to the underlying graph.
     const Graph *G;
     ///Pointer to the map of predecessors edges.
-    PredMap *predecessor;
-    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
-    bool local_predecessor;
-    ///Pointer to the map of predecessors nodes.
-    PredNodeMap *pred_node;
-    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
-    bool local_pred_node;
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
+//     ///Pointer to the map of predecessors nodes.
+//     PredNodeMap *_predNode;
+//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
+//     bool local_predNode;
     ///Pointer to the map of distances.
-    DistMap *distance;
-    ///Indicates if \ref distance is locally allocated (\c true) or not.
-    bool local_distance;
-
-    ///The source node of the last execution.
-    Node source;
-
-
-    ///Initializes the maps.
-    void init_maps() 
-    {
-      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 :    
+    DistMap *_dist;
+    ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    bool local_dist;
+    ///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;
+    ///Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+
+    std::vector<typename Graph::Node> _queue;
+    int _queue_head,_queue_tail,_queue_next_dist;
+    int _curr_dist;
+//     ///The source node of the last execution.
+//     Node source;
+
+    ///Creates the maps if necessary.
+    
+    ///\todo Error if \c G are \c NULL.
+    ///\todo Better memory allocation (instead of new).
+    void create_maps() 
+    {
+      if(!_pred) {
+        local_pred = true;
+        _pred = Traits::createPredMap(*G);
+      }
+//       if(!_predNode) {
+//      local_predNode = true;
+//      _predNode = Traits::createPredNodeMap(*G);
+//       }
+      if(!_dist) {
+        local_dist = true;
+        _dist = Traits::createDistMap(*G);
+      }
+      if(!_reached) {
+        local_reached = true;
+        _reached = Traits::createReachedMap(*G);
+      }
+      if(!_processed) {
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*G);
+      }
+    }
+    
+  public :
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    class DefPredMap : public Bfs< Graph,
+                                        DefPredMapTraits<T> > { };
+    
+//     template <class T>
+//     struct DefPredNodeMapTraits : public Traits {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) 
+//       {
+//      throw UninitializedParameter();
+//       }
+//     };
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///
+//     template <class T>
+//     class DefPredNodeMap : public Bfs< Graph,
+//                                          LengthMap,
+//                                          DefPredNodeMapTraits<T> > { };
+    
+    template <class T>
+    struct DefDistMapTraits : public Traits {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    template <class T>
+    class DefDistMap : public Bfs< Graph,
+                                   DefDistMapTraits<T> > { };
+    
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+    ///
+    template <class T>
+    class DefReachedMap : public Bfs< Graph,
+                                      DefReachedMapTraits<T> > { };
+    
+    struct DefGraphReachedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        return new ReachedMap(G);
+      }
+    };
+    template <class T>
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///
+    template <class T>
+    class DefProcessedMap : public Bfs< Graph,
+                                        DefProcessedMapTraits<T> > { };
+    
+    struct DefGraphProcessedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        return new ProcessedMap(G);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///If you don't set it explicitely, it will be automatically allocated.
+    template <class T>
+    class DefProcessedMapToBeDefaultMap :
+      public Bfs< Graph,
+                  DefGraphProcessedMapTraits> { };
+    
+    ///@}
+
+  public:      
+    
     ///Constructor.
     
@@ -113 +365 @@
     Bfs(const Graph& _G) :
       G(&_G),
-      predecessor(NULL), local_predecessor(false),
-      pred_node(NULL), local_pred_node(false),
-      distance(NULL), local_distance(false)
+      _pred(NULL), local_pred(false),
+//       _predNode(NULL), local_predNode(false),
+      _dist(NULL), local_dist(false),
+      _reached(NULL), local_reached(false),
+      _processed(NULL), local_processed(false)
     { }
     
@@ -121 +375 @@
     ~Bfs() 
     {
-      if(local_predecessor) delete predecessor;
-      if(local_pred_node) delete pred_node;
-      if(local_distance) delete distance;
+      if(local_pred) delete _pred;
+//       if(local_predNode) delete _predNode;
+      if(local_dist) delete _dist;
+      if(local_reached) delete _reached;
+      if(local_processed) delete _processed;
     }
 
@@ -133 +389 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Bfs &setPredMap(PredMap &m) 
-    {
-      if(local_predecessor) {
-        delete predecessor;
-        local_predecessor=false;
-      }
-      predecessor = &m;
+    Bfs &predMap(PredMap &m) 
+    {
+      if(local_pred) {
+        delete _pred;
+        local_pred=false;
+      }
+      _pred = &m;
       return *this;
     }
 
-    ///Sets the map storing the predecessor nodes.
-
-    ///Sets the map storing the predecessor nodes.
+    ///Sets the map indicating the reached nodes.
+
+    ///Sets the map indicating the reached 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>
-    Bfs &setPredNodeMap(PredNodeMap &m) 
-    {
-      if(local_pred_node) {
-        delete pred_node;
-        local_pred_node=false;
-      }
-      pred_node = &m;
+    Bfs &reachedMap(ReachedMap &m) 
+    {
+      if(local_reached) {
+        delete _reached;
+        local_reached=false;
+      }
+      _reached = &m;
       return *this;
     }
+
+    ///Sets the map indicating the processed nodes.
+
+    ///Sets the map indicating the processed 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>
+    Bfs &processedMap(ProcessedMap &m) 
+    {
+      if(local_processed) {
+        delete _processed;
+        local_processed=false;
+      }
+      _processed = &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>
+//     Bfs &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.
@@ -167 +457 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Bfs &setDistMap(DistMap &m) 
-    {
-      if(local_distance) {
-        delete distance;
-        local_distance=false;
-      }
-      distance = &m;
+    Bfs &distMap(DistMap &m) 
+    {
+      if(local_dist) {
+        delete _dist;
+        local_dist=false;
+      }
+      _dist = &m;
       return *this;
     }
-    
-  ///Runs %BFS algorithm from node \c s.
-
-  ///This method runs the %BFS algorithm from a root node \c s
-  ///in order to
-  ///compute a
-  ///shortest path to each node. The algorithm computes
-  ///- The %BFS tree.
-  ///- The distance of each node from the root.
- 
+
+  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.
+
+    ///@{
+
+    ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    void init()
+    {
+      create_maps();
+      _queue.resize(countNodes(*G));
+      _queue_head=_queue_tail=0;
+      _curr_dist=1;
+      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
+        _pred->set(u,INVALID);
+//      _predNode->set(u,INVALID);
+        _reached->set(u,false);
+        _processed->set(u,false);
+      }
+    }
+    
+    ///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);
+          _pred->set(s,INVALID);
+          _dist->set(s,0);
+          _queue[_queue_head++]=s;
+          _queue_next_dist=_queue_head;
+        }
+    }
+    
+    ///Processes the next node.
+
+    ///Processes the next node.
+    ///
+    ///\warning The queue must not be empty!
+    void processNextNode()
+    {
+      if(_queue_tail==_queue_next_dist) {
+        _curr_dist++;
+        _queue_next_dist=_queue_head;
+      }
+      Node n=_queue[_queue_tail++];
+      _processed->set(n,true);
+      Node m;
+      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
+        if(!(*_reached)[m=G->target(e)]) {
+          _queue[_queue_head++]=m;
+          _reached->set(m,true);
+          _pred->set(m,e);
+//        _pred_node->set(m,n);
+          _dist->set(m,_curr_dist);
+        }
+    }
+      
+    ///\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
+    bool emptyQueue() { return _queue_tail==_queue_head; }
+    ///Returns the number of the nodes to be processed.
+    
+    ///Returns the number of the nodes to be processed in the queue.
+    ///
+    int queueSize() { return _queue_head-_queue_tail; }
+    
+    ///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.
+    ///
+    ///This method runs the %BFS algorithm from the root node(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(s).
+    ///
+    void start()
+    {
+      while ( !emptyQueue() ) processNextNode();
+    }
+    
+    ///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.
+    ///
+    ///This method runs the %BFS algorithm from the root node(s)
+    ///in order to
+    ///compute the
+    ///shortest path to \c dest. The algorithm computes
+    ///- The shortest path to \c  dest.
+    ///- The distance of \c dest from the root(s).
+    ///
+    void start(Node dest)
+    {
+      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
+    }
+    
+    ///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) node map. The algorithm
+    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    template<class NM>
+      void start(const NM &nm)
+      {
+        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
+      }
+    
+    ///Runs %BFS algorithm from node \c s.
+    
+    ///This method runs the %BFS 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.
+    ///
+    ///\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_maps();
-      
-      source = s;
-      
-      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-        predecessor->set(u,INVALID);
-        pred_node->set(u,INVALID);
-      }
-      
-      int N = countNodes(*G);
-      std::vector<typename Graph::Node> Q(N);
-      int Qh=0;
-      int Qt=0;
-      
-      Q[Qh++]=source;
-      distance->set(s, 0);
-      do {
-        Node m;
-        Node n=Q[Qt++];
-        int d= (*distance)[n]+1;
-        
-        for(OutEdgeIt e(*G,n);e!=INVALID;++e)
-          if((m=G->target(e))!=s && (*predecessor)[m]==INVALID) {
-            Q[Qh++]=m;
-            predecessor->set(m,e);
-            pred_node->set(m,n);
-            distance->set(m,d);
-          }
-      } while(Qt!=Qh);
-    }
-    
-    ///The distance of a node from the root.
-
-    ///Returns the distance of a node from the root.
+      init();
+      addSource(s);
+      start();
+    }
+    
+    ///Finds the shortest path between \c s and \c t.
+    
+    ///Finds the shortest path between \c s and \c t.
+    ///
+    ///\return The length of the shortest s---t path if there exists one,
+    ///0 otherwise.
+    ///\note Apart from the return value, d.run(s) is
+    ///just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start(t);
+    ///\endcode
+    int run(Node s,Node t) {
+      init();
+      addSource(s);
+      start(t);
+      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
+    }
+    
+    ///@}
+
+    ///\name Query Functions
+    ///The result of the %BFS algorithm can be obtained using these
+    ///functions.\n
+    ///Before the use of these functions,
+    ///either run() or start() must be called.
+    
+    ///@{
+
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///\pre \ref run() must be called before using this function.
-    ///\warning If node \c v in unreachable from the root the return value
+    ///\warning If node \c v in unreachable from the root(s) the return value
     ///of this funcion is undefined.
-    int dist(Node v) const { return (*distance)[v]; }
-
-    ///Returns the 'previous edge' of the %BFS path tree.
-
-    ///For a node \c v it returns the 'previous edge' of the %BFS tree,
-    ///i.e. it returns the last edge of a shortest path from the root to \c
+    int dist(Node v) const { return (*_dist)[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 of a shortest path from the root(s) to \c
     ///v. It is \ref INVALID
-    ///if \c v is unreachable from the root or if \c v=s. The
-    ///%BFS tree used here is equal to the %BFS tree used in
-    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///if \c v is unreachable from the root(s) or \c v is a root. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before using
     ///this function.
-    Edge pred(Node v) const { return (*predecessor)[v]; }
-
-    ///Returns the 'previous node' of the %BFS tree.
-
-    ///For a node \c v it returns the 'previous node' on the %BFS tree,
+    ///\todo predEdge could be a better name.
+    Edge pred(Node v) const { return (*_pred)[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 %BFS
-    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
+    ///root(a) to \c /v.
+    ///It is INVALID if \c v is unreachable from the root(s) or
+    ///if \c v itself a root.
+    ///The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref pred(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
-    Node predNode(Node v) const { return (*pred_node)[v]; }
+    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
+                                  G->source((*_pred)[v]); }
     
     ///Returns a reference to the NodeMap of distances.
-    
-    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
+
+    ///Returns a reference to the NodeMap of distances.
+    ///\pre Either \ref run() or \ref init() must
     ///be called before using this function.
-    const DistMap &distMap() const { return *distance;}
- 
-    ///Returns a reference to the %BFS tree map.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    ///Returns a reference to the shortest path tree map.
 
     ///Returns a reference to the NodeMap of the edges of the
-    ///%BFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return *predecessor;}
- 
-    ///Returns a reference to the map of last but one nodes of shortest paths.
-
-    ///Returns a reference to the NodeMap of the last but one nodes on the
-    ///%BFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return *pred_node;}
+    ///shortest path tree.
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
+    const PredMap &predMap() const { return *_pred;}
+ 
+//     ///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 *_predNode;}
 
     ///Checks if a node is reachable from the root.
 
     ///Returns \c true if \c v is reachable from the root.
-    ///\note 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; }
-    
+    ///\warning The source nodes are inditated as unreached.
+    ///\pre Either \ref run() or \ref start()
+    ///must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    
+    ///@}
+  };
+
+  ///Default traits class of Bfs function.
+
+  ///Default traits class of Bfs function.
+  ///\param GR Graph type.
+  template<class GR>
+  struct BfsWizardDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the shortest paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap();
+    }
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///
+//     ///The type of the map that stores the last but one
+//     ///nodes of the shortest 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.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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;
+    ///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 GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap();
+    }
   };
   
-/// @}
+  /// Default traits used by \ref BfsWizard
+
+  /// To make it easier to use Bfs algorithm
+  ///we have created a wizard class.
+  /// This \ref BfsWizard class needs default traits,
+  ///as well as the \ref Bfs class.
+  /// The \ref BfsWizardBase is a class to be the default traits of the
+  /// \ref BfsWizard class.
+  template<class GR>
+  class BfsWizardBase : public BfsWizardDefaultTraits<GR>
+  {
+
+    typedef BfsWizardDefaultTraits<GR> Base;
+  protected:
+    /// Type of the nodes in the graph.
+    typedef typename Base::Graph::Node Node;
+
+    /// Pointer to the underlying graph.
+    void *_g;
+    ///Pointer to the map of reached nodes.
+    void *_reached;
+    ///Pointer to the map of processed nodes.
+    void *_processed;
+    ///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;
+    ///Pointer to the source node.
+    Node _source;
+    
+    public:
+    /// Constructor.
+    
+    /// This constructor does not require parameters, therefore it initiates
+    /// all of the attributes to default values (0, INVALID).
+    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
+//                         _predNode(0),
+                           _dist(0), _source(INVALID) {}
+
+    /// Constructor.
+    
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
+    /// \param g is the initial value of  \ref _g
+    /// \param s is the initial value of  \ref _source
+    BfsWizardBase(const GR &g, Node s=INVALID) :
+      _g((void *)&g), _reached(0), _processed(0), _pred(0),
+//       _predNode(0),
+      _dist(0), _source(s) {}
+
+  };
   
+  /// A class to make the usage of Bfs algorithm easier
+
+  /// This class is created to make it easier to use Bfs algorithm.
+  /// It uses the functions and features of the plain \ref Bfs,
+  /// but it is much simpler to use it.
+  ///
+  /// Simplicity means that the way to change the types defined
+  /// in the traits class is based on functions that returns the new class
+  /// and not on templatable built-in classes.
+  /// When using the plain \ref Bfs
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref BfsWizard only
+  /// a function have to be called and it will
+  /// return the needed class.
+  ///
+  /// It does not have own \ref run method. When its \ref run method is called
+  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
+  /// method of it.
+  template<class TR>
+  class BfsWizard : public TR
+  {
+    typedef TR Base;
+
+    ///The type of the underlying graph.
+    typedef typename TR::Graph Graph;
+    //\e
+    typedef typename Graph::Node Node;
+    //\e
+    typedef typename Graph::NodeIt NodeIt;
+    //\e
+    typedef typename Graph::Edge Edge;
+    //\e
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    ///\brief The type of the map that stores
+    ///the reached nodes
+    typedef typename TR::ReachedMap ReachedMap;
+    ///\brief The type of the map that stores
+    ///the processed nodes
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename TR::DistMap DistMap;
+
+public:
+    /// Constructor.
+    BfsWizard() : TR() {}
+
+    /// Constructor that requires parameters.
+
+    /// Constructor that requires parameters.
+    /// These parameters will be the default values for the traits class.
+    BfsWizard(const Graph &g, Node s=INVALID) :
+      TR(g,s) {}
+
+    ///Copy constructor
+    BfsWizard(const TR &b) : TR(b) {}
+
+    ~BfsWizard() {}
+
+    ///Runs Bfs algorithm from a given node.
+    
+    ///Runs Bfs algorithm from a given node.
+    ///The node can be given by the \ref source function.
+    void run()
+    {
+      if(Base::_source==INVALID) throw UninitializedParameter();
+      Bfs<Graph,TR> alg(*(Graph*)Base::_g);
+      if(Base::_reached)
+        alg.reachedMap(*(ReachedMap*)Base::_reached);
+      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);
+    }
+
+    ///Runs Bfs algorithm from the given node.
+
+    ///Runs Bfs algorithm from the given node.
+    ///\param s is the given source.
+    void run(Node s)
+    {
+      Base::_source=s;
+      run();
+    }
+
+    template<class T>
+    struct DefPredMapBase : public Base {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) { return 0; };
+      DefPredMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap
+    ///
+    template<class T>
+    BfsWizard<DefPredMapBase<T> > predMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefPredMapBase<T> >(*this);
+    }
+    
+ 
+    template<class T>
+    struct DefReachedMapBase : public Base {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
+      DefReachedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    template<class T>
+    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefReachedMapBase<T> >(*this);
+    }
+    
+
+    template<class T>
+    struct DefProcessedMapBase : public Base {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
+      DefProcessedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    template<class T>
+    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return BfsWizard<DefProcessedMapBase<T> >(*this);
+    }
+    
+
+//     template<class T>
+//     struct DefPredNodeMapBase : public Base {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
+//       DefPredNodeMapBase(const Base &b) : Base(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>
+//     BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
+//     {
+//       Base::_predNode=(void *)&t;
+//       return BfsWizard<DefPredNodeMapBase<T> >(*this);
+//     }
+   
+    template<class T>
+    struct DefDistMapBase : public Base {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) { return 0; };
+      DefDistMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    template<class T>
+    BfsWizard<DefDistMapBase<T> > distMap(const T &t) 
+    {
+      Base::_dist=(void *)&t;
+      return BfsWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// Sets the source node, from which the Bfs algorithm runs.
+
+    /// Sets the source node, from which the Bfs algorithm runs.
+    /// \param s is the source node.
+    BfsWizard<TR> &source(Node s) 
+    {
+      Base::_source=s;
+      return *this;
+    }
+    
+  };
+  
+  ///Function type interface for Bfs algorithm.
+
+  /// \ingroup flowalgs
+  ///Function type interface for Bfs algorithm.
+  ///
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
+  ///they are declared as the members of class \ref BfsWizard.
+  ///The following
+  ///example shows how to use these parameters.
+  ///\code
+  ///  bfs(g,source).predMap(preds).run();
+  ///\endcode
+  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+  ///to the end of the parameter list.
+  ///\sa BfsWizard
+  ///\sa Bfs
+  template<class GR>
+  BfsWizard<BfsWizardBase<GR> >
+  bfs(const GR &g,typename GR::Node s=INVALID)
+  {
+    return BfsWizard<BfsWizardBase<GR> >(g,s);
+  }
+
 } //END OF NAMESPACE LEMON
 
 #endif
 
-

src/lemon/dfs.h

@@ -20 +20 @@
 ///\ingroup flowalgs
 ///\file
-///\brief %DFS algorithm.
-///
-///\todo Revise Manual.
-
+///\brief Dfs algorithm.
+
+#include <lemon/list_graph.h>
 #include <lemon/graph_utils.h>
 #include <lemon/invalid.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
 
 namespace lemon {
 
-/// \addtogroup flowalgs
-/// @{
-
+
+  
+  ///Default traits class of Dfs class.
+
+  ///Default traits class of Dfs class.
+  ///\param GR Graph type.
+  template<class GR>
+  struct DfsDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the %DFS paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the %DFS paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap(G);
+    }
+//     ///\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.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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;
+    ///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 GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Graph::template NodeMap<int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap(G);
+    }
+  };
+  
   ///%DFS algorithm class.
-
-  ///This class provides an efficient implementation of %DFS algorithm.
+  
+  ///\ingroup flowalgs
+  ///This class provides an efficient implementation of the %DFS algorithm.
   ///
-  ///\param GR The graph type the algorithm runs on.
+  ///\param GR The graph type the algorithm runs on. The default value is
+  ///\ref ListGraph. The value of GR is not used directly by Dfs, it
+  ///is only passed to \ref DfsDefaultTraits.
+  ///\param TR Traits class to set various data types used by the algorithm.
+  ///The default traits class is
+  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
+  ///See \ref DfsDefaultTraits for the documentation of
+  ///a Dfs traits class.
   ///
-  ///\author Alpar Juttner
+  ///\author Jacint Szabo and Alpar Juttner
+  ///\todo A compare object would be nice.
 
 #ifdef DOXYGEN
-  template <typename GR>
+  template <typename GR,
+            typename TR>
 #else
-  template <typename GR>
+  template <typename GR=ListGraph,
+            typename TR=DfsDefaultTraits<GR> >
 #endif
-  class Dfs{
+  class Dfs {
   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::Dfs::UninitializedParameter";
+      }
+    };
+
+    typedef TR Traits;
     ///The type of the underlying graph.
-    typedef GR Graph;
+    typedef typename TR::Graph Graph;
     ///\e
     typedef typename Graph::Node Node;
@@ -59 +174 @@
     
     ///\brief The type of the map that stores the last
-    ///edges of the paths on the %DFS tree.
-    typedef typename Graph::template NodeMap<Edge> PredMap;
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the paths on the %DFS tree.
-    typedef typename Graph::template NodeMap<Node> PredNodeMap;
-    ///The type of the map that stores the dists of the nodes on the %DFS tree.
-    typedef typename Graph::template NodeMap<int> DistMap;
-
+    ///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 indicating which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///The type of the map indicating which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///The type of the map that stores the dists of the nodes.
+    typedef typename TR::DistMap DistMap;
   private:
     /// Pointer to the underlying graph.
     const Graph *G;
     ///Pointer to the map of predecessors edges.
-    PredMap *predecessor;
-    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
-    bool local_predecessor;
-    ///Pointer to the map of predecessors nodes.
-    PredNodeMap *pred_node;
-    ///Indicates if \ref pred_node is locally allocated (\c true) or not.
-    bool local_pred_node;
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
+//     ///Pointer to the map of predecessors nodes.
+//     PredNodeMap *_predNode;
+//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
+//     bool local_predNode;
     ///Pointer to the map of distances.
-    DistMap *distance;
-    ///Indicates if \ref distance is locally allocated (\c true) or not.
-    bool local_distance;
-
-    ///The source node of the last execution.
-    Node source;
-
-
-    ///Initializes the maps.
-    void init_maps() 
-    {
-      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 :    
+    DistMap *_dist;
+    ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    bool local_dist;
+    ///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;
+    ///Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+
+    std::vector<typename Graph::OutEdgeIt> _stack;
+    int _stack_head;
+//     ///The source node of the last execution.
+//     Node source;
+
+    ///Creates the maps if necessary.
+    
+    ///\todo Error if \c G are \c NULL.
+    ///\todo Better memory allocation (instead of new).
+    void create_maps() 
+    {
+      if(!_pred) {
+        local_pred = true;
+        _pred = Traits::createPredMap(*G);
+      }
+//       if(!_predNode) {
+//      local_predNode = true;
+//      _predNode = Traits::createPredNodeMap(*G);
+//       }
+      if(!_dist) {
+        local_dist = true;
+        _dist = Traits::createDistMap(*G);
+      }
+      if(!_reached) {
+        local_reached = true;
+        _reached = Traits::createReachedMap(*G);
+      }
+      if(!_processed) {
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*G);
+      }
+    }
+    
+  public :
+ 
+    ///\name Named template parameters
+
+    ///@{
+
+    template <class T>
+    struct DefPredMapTraits : public Traits {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    template <class T>
+    class DefPredMap : public Dfs< Graph,
+                                        DefPredMapTraits<T> > { };
+    
+//     template <class T>
+//     struct DefPredNodeMapTraits : public Traits {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) 
+//       {
+//      throw UninitializedParameter();
+//       }
+//     };
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///
+//     template <class T>
+//     class DefPredNodeMap : public Dfs< Graph,
+//                                          LengthMap,
+//                                          DefPredNodeMapTraits<T> > { };
+    
+    template <class T>
+    struct DefDistMapTraits : public Traits {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    template <class T>
+    class DefDistMap : public Dfs< Graph,
+                                   DefDistMapTraits<T> > { };
+    
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+    ///
+    template <class T>
+    class DefReachedMap : public Dfs< Graph,
+                                      DefReachedMapTraits<T> > { };
+    
+    struct DefGraphReachedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        return new ReachedMap(G);
+      }
+    };
+    template <class T>
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///
+    template <class T>
+    class DefProcessedMap : public Dfs< Graph,
+                                        DefProcessedMapTraits<T> > { };
+    
+    struct DefGraphProcessedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
+      {
+        return new ProcessedMap(G);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
+    ///If you don't set it explicitely, it will be automatically allocated.
+    template <class T>
+    class DefProcessedMapToBeDefaultMap :
+      public Dfs< Graph,
+                  DefGraphProcessedMapTraits> { };
+    
+    ///@}
+
+  public:      
+    
     ///Constructor.
     
@@ -111 +364 @@
     Dfs(const Graph& _G) :
       G(&_G),
-      predecessor(NULL), local_predecessor(false),
-      pred_node(NULL), local_pred_node(false),
-      distance(NULL), local_distance(false)
+      _pred(NULL), local_pred(false),
+//       _predNode(NULL), local_predNode(false),
+      _dist(NULL), local_dist(false),
+      _reached(NULL), local_reached(false),
+      _processed(NULL), local_processed(false)
     { }
     
@@ -119 +374 @@
     ~Dfs() 
     {
-      if(local_predecessor) delete predecessor;
-      if(local_pred_node) delete pred_node;
-      if(local_distance) delete distance;
+      if(local_pred) delete _pred;
+//       if(local_predNode) delete _predNode;
+      if(local_dist) delete _dist;
+      if(local_reached) delete _reached;
+      if(local_processed) delete _processed;
     }
 
@@ -131 +388 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Dfs &setPredMap(PredMap &m) 
-    {
-      if(local_predecessor) {
-        delete predecessor;
-        local_predecessor=false;
-      }
-      predecessor = &m;
+    Dfs &predMap(PredMap &m) 
+    {
+      if(local_pred) {
+        delete _pred;
+        local_pred=false;
+      }
+      _pred = &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 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.
@@ -165 +422 @@
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
-    Dfs &setDistMap(DistMap &m) 
-    {
-      if(local_distance) {
-        delete distance;
-        local_distance=false;
-      }
-      distance = &m;
+    Dfs &distMap(DistMap &m) 
+    {
+      if(local_dist) {
+        delete _dist;
+        local_dist=false;
+      }
+      _dist = &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 
-  ///- a %DFS tree and
-  ///- the distance of each node from the root on this tree.
- 
+
+  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.
+
+    ///@{
+
+    ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    void init()
+    {
+      create_maps();
+      _stack.resize(countNodes(*G));
+      _stack_head=-1;
+      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
+        _pred->set(u,INVALID);
+        // _predNode->set(u,INVALID);
+        _reached->set(u,false);
+        _processed->set(u,false);
+      }
+    }
+    
+    ///Adds a new source node.
+
+    ///Adds a new source node to the set of nodes to be processed.
+    ///
+    ///\bug dist's are wrong (or at least strange) in case of multiple sources.
+    void addSource(Node s)
+    {
+      if(!(*_reached)[s])
+        {
+          _reached->set(s,true);
+          _pred->set(s,INVALID);
+          // _predNode->set(u,INVALID);
+          _stack[++_stack_head]=OutEdgeIt(*G,s);
+          _dist->set(s,_stack_head);
+        }
+    }
+    
+    ///Processes the next node.
+
+    ///Processes the next node.
+    ///
+    ///\warning The stack must not be empty!
+    void processNextEdge()
+    { 
+      Node m;
+      Edge e=_stack[_stack_head];
+      if(!(*_reached)[m=G->target(e)]) {
+        _pred->set(m,e);
+        _reached->set(m,true);
+        //        _pred_node->set(m,G->source(e));
+        _stack[++_stack_head] = OutEdgeIt(*G, m);
+        _dist->set(m,_stack_head);
+      }
+      else {
+        Node n;
+        while(_stack_head>=0 &&
+              (n=G->source(_stack[_stack_head]),
+               ++_stack[_stack_head]==INVALID))
+          {
+            _processed->set(n,true);
+            --_stack_head;
+          }
+      }
+    }
+      
+    ///\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
+    bool emptyQueue() { return _stack_head<0; }
+    ///Returns the number of the nodes to be processed.
+    
+    ///Returns the number of the nodes to be processed in the queue.
+    ///
+    int queueSize() { return _stack_head+1; }
+    
+    ///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.
+    ///
+    ///This method runs the %DFS algorithm from the root node(s)
+    ///in order to
+    ///compute the
+    ///%DFS path to each node. The algorithm computes
+    ///- The %DFS tree.
+    ///- The distance of each node from the root(s).
+    ///
+    void start()
+    {
+      while ( !emptyQueue() ) processNextEdge();
+    }
+    
+    ///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.
+    ///
+    ///This method runs the %DFS algorithm from the root node(s)
+    ///in order to
+    ///compute the
+    ///%DFS path to \c dest. The algorithm computes
+    ///- The %DFS path to \c  dest.
+    ///- The distance of \c dest from the root(s).
+    ///
+    void start(Node dest)
+    {
+      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
+    }
+    
+    ///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) node map. The algorithm
+    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    template<class NM>
+      void start(const NM &nm)
+      {
+        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
+      }
+    
+    ///Runs %DFS algorithm from node \c s.
+    
+    ///This method runs the %DFS algorithm from a root node \c s
+    ///in order to
+    ///compute the
+    ///%DFS path to each node. The algorithm computes
+    ///- The %DFS tree.
+    ///- The distance of each node from the root.
+    ///
+    ///\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_maps();
-      
-      source = s;
-      
-      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-        predecessor->set(u,INVALID);
-        pred_node->set(u,INVALID);
-      }
-      
-      int N = countNodes(*G);
-      std::vector<typename Graph::OutEdgeIt> Q(N);
-
-      int Qh=0;
-      
-      Q[Qh] = OutEdgeIt(*G, s);
-      distance->set(s, 0);
-
-      Node n=s;
-      Node m;
-      OutEdgeIt e;
-      do {
-        if((e=Q[Qh])!=INVALID)
-          if((m=G->target(e))!=s && (*predecessor)[m=G->target(e)]==INVALID) {
-            predecessor->set(m,e);
-            pred_node->set(m,n);
-            Q[++Qh] = OutEdgeIt(*G, m);
-            distance->set(m,Qh);
-            n=m;
-          }
-          else ++Q[Qh];
-        else if(--Qh>=0) n=G->source(Q[Qh]);
-      } while(Qh>=0);
-    }
-    
-    ///The distance of a node from the root on the %DFS tree.
-
-    ///Returns the distance of a node from the root on the %DFS tree.
+      init();
+      addSource(s);
+      start();
+    }
+    
+    ///Finds the %DFS path between \c s and \c t.
+    
+    ///Finds the %DFS path between \c s and \c t.
+    ///
+    ///\return The length of the %DFS s---t path if there exists one,
+    ///0 otherwise.
+    ///\note Apart from the return value, d.run(s) is
+    ///just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start(t);
+    ///\endcode
+    int run(Node s,Node t) {
+      init();
+      addSource(s);
+      start(t);
+      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
+    }
+    
+    ///@}
+
+    ///\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.
+    
+    ///@{
+
+    ///The distance of a node from the root(s).
+
+    ///Returns the distance of a node from the root(s).
     ///\pre \ref run() must be called before using this function.
-    ///\warning If node \c v in unreachable from the root the return value
+    ///\warning If node \c v in unreachable from the root(s) the return value
     ///of this funcion is undefined.
-    int dist(Node v) const { return (*distance)[v]; }
-
-    ///Returns the 'previous edge' of the %DFS path tree.
-
-    ///For a node \c v it returns the last edge of the path on the %DFS tree
-    ///from the root to \c
+    int dist(Node v) const { return (*_dist)[v]; }
+
+    ///Returns the 'previous edge' of the %DFS tree.
+
+    ///For a node \c v it returns the 'previous edge'
+    ///of the %DFS path,
+    ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
     ///v. It is \ref INVALID
-    ///if \c v is unreachable from the root or if \c v=s. The
+    ///if \c v is unreachable from the root(s) or \c v is a root. The
     ///%DFS tree used here is equal to the %DFS tree used in
-    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///\ref predNode(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before using
     ///this function.
-    Edge pred(Node v) const { return (*predecessor)[v]; }
+    ///\todo predEdge could be a better name.
+    Edge pred(Node v) const { return (*_pred)[v];}
 
     ///Returns the 'previous node' of the %DFS tree.
 
-    ///For a node \c v it returns the 'previous node' on the %DFS tree,
-    ///i.e. it returns the last but one node of the path from the
-    ///root to \c /v on the %DFS tree.
-    ///It is INVALID if \c v is unreachable from the root or if
-    ///\c v=s.
-    ///\pre \ref run() must be called before
+    ///For a node \c v it returns the 'previous node'
+    ///of the %DFS tree,
+    ///i.e. it returns the last but one node from a %DFS path from the
+    ///root(a) to \c /v.
+    ///It is INVALID if \c v is unreachable from the root(s) or
+    ///if \c v itself a root.
+    ///The %DFS tree used here is equal to the %DFS
+    ///tree used in \ref pred(Node v).
+    ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
-    Node predNode(Node v) const { return (*pred_node)[v]; }
-    
-    ///Returns a reference to the NodeMap of distances on the %DFS tree.
-    
-    ///Returns a reference to the NodeMap of distances on the %DFS tree.
-    ///\pre \ref run() must
+    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
+                                  G->source((*_pred)[v]); }
+    
+    ///Returns a reference to the NodeMap of distances.
+
+    ///Returns a reference to the NodeMap of distances.
+    ///\pre Either \ref run() or \ref init() must
     ///be called before using this function.
-    const DistMap &distMap() const { return *distance;}
- 
-    ///Returns a reference to the %DFS tree map.
+    const DistMap &distMap() const { return *_dist;}
+ 
+    ///Returns a reference to the %DFS edge-tree map.
 
     ///Returns a reference to the NodeMap of the edges of the
     ///%DFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return *predecessor;}
- 
-    ///Returns a reference to the map of last but one nodes of the %DFS tree.
-
-    ///Returns a reference to the NodeMap of the last but one nodes of the paths
-    ///on the
-    ///%DFS tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return *pred_node;}
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
+    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.
 
     ///Returns \c true if \c v is reachable from the root.
-    ///\note 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; }
-    
+    ///\warning The source nodes are inditated as unreached.
+    ///\pre Either \ref run() or \ref start()
+    ///must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    
+    ///@}
+  };
+
+  ///Default traits class of Dfs function.
+
+  ///Default traits class of Dfs function.
+  ///\param GR Graph type.
+  template<class GR>
+  struct DfsWizardDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///\brief The type of the map that stores the last
+    ///edges of the %DFS paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the %DFS paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G) 
+    {
+      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.
+ 
+    ///The type of the map that indicates which nodes are processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///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;
+    ///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 GR &G)
+    {
+      return new ReachedMap(G);
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,int> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap();
+    }
   };
   
-/// @}
+  /// Default traits used by \ref DfsWizard
+
+  /// To make it easier to use Dfs algorithm
+  ///we have created a wizard class.
+  /// This \ref DfsWizard class needs default traits,
+  ///as well as the \ref Dfs class.
+  /// The \ref DfsWizardBase is a class to be the default traits of the
+  /// \ref DfsWizard class.
+  template<class GR>
+  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
+  {
+
+    typedef DfsWizardDefaultTraits<GR> Base;
+  protected:
+    /// Type of the nodes in the graph.
+    typedef typename Base::Graph::Node Node;
+
+    /// Pointer to the underlying graph.
+    void *_g;
+    ///Pointer to the map of reached nodes.
+    void *_reached;
+    ///Pointer to the map of processed nodes.
+    void *_processed;
+    ///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;
+    ///Pointer to the source node.
+    Node _source;
+    
+    public:
+    /// Constructor.
+    
+    /// This constructor does not require parameters, therefore it initiates
+    /// all of the attributes to default values (0, INVALID).
+    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
+//                         _predNode(0),
+                           _dist(0), _source(INVALID) {}
+
+    /// Constructor.
+    
+    /// This constructor requires some parameters,
+    /// listed in the parameters list.
+    /// Others are initiated to 0.
+    /// \param g is the initial value of  \ref _g
+    /// \param s is the initial value of  \ref _source
+    DfsWizardBase(const GR &g, Node s=INVALID) :
+      _g((void *)&g), _reached(0), _processed(0), _pred(0),
+//       _predNode(0),
+      _dist(0), _source(s) {}
+
+  };
   
+  /// A class to make the usage of Dfs algorithm easier
+
+  /// This class is created to make it easier to use Dfs algorithm.
+  /// It uses the functions and features of the plain \ref Dfs,
+  /// but it is much simpler to use it.
+  ///
+  /// Simplicity means that the way to change the types defined
+  /// in the traits class is based on functions that returns the new class
+  /// and not on templatable built-in classes.
+  /// When using the plain \ref Dfs
+  /// the new class with the modified type comes from
+  /// the original class by using the ::
+  /// operator. In the case of \ref DfsWizard only
+  /// a function have to be called and it will
+  /// return the needed class.
+  ///
+  /// It does not have own \ref run method. When its \ref run method is called
+  /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run
+  /// method of it.
+  template<class TR>
+  class DfsWizard : public TR
+  {
+    typedef TR Base;
+
+    ///The type of the underlying graph.
+    typedef typename TR::Graph Graph;
+    //\e
+    typedef typename Graph::Node Node;
+    //\e
+    typedef typename Graph::NodeIt NodeIt;
+    //\e
+    typedef typename Graph::Edge Edge;
+    //\e
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    
+    ///\brief The type of the map that stores
+    ///the reached nodes
+    typedef typename TR::ReachedMap ReachedMap;
+    ///\brief The type of the map that stores
+    ///the processed nodes
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///\brief The type of the map that stores the last
+    ///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 dists of the nodes.
+    typedef typename TR::DistMap DistMap;
+
+public:
+    /// Constructor.
+    DfsWizard() : TR() {}
+
+    /// Constructor that requires parameters.
+
+    /// Constructor that requires parameters.
+    /// These parameters will be the default values for the traits class.
+    DfsWizard(const Graph &g, Node s=INVALID) :
+      TR(g,s) {}
+
+    ///Copy constructor
+    DfsWizard(const TR &b) : TR(b) {}
+
+    ~DfsWizard() {}
+
+    ///Runs Dfs algorithm from a given node.
+    
+    ///Runs Dfs algorithm from a given node.
+    ///The node can be given by the \ref source function.
+    void run()
+    {
+      if(Base::_source==INVALID) throw UninitializedParameter();
+      Dfs<Graph,TR> alg(*(Graph*)Base::_g);
+      if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
+      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);
+    }
+
+    ///Runs Dfs algorithm from the given node.
+
+    ///Runs Dfs algorithm from the given node.
+    ///\param s is the given source.
+    void run(Node s)
+    {
+      Base::_source=s;
+      run();
+    }
+
+    template<class T>
+    struct DefPredMapBase : public Base {
+      typedef T PredMap;
+      static PredMap *createPredMap(const Graph &G) { return 0; };
+      DefPredMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    template<class T>
+    DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return DfsWizard<DefPredMapBase<T> >(*this);
+    }
+    
+ 
+    template<class T>
+    struct DefReachedMapBase : public Base {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) { return 0; };
+      DefReachedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    template<class T>
+    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return DfsWizard<DefReachedMapBase<T> >(*this);
+    }
+    
+
+    template<class T>
+    struct DefProcessedMapBase : public Base {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) { return 0; };
+      DefProcessedMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    template<class T>
+    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
+    {
+      Base::_pred=(void *)&t;
+      return DfsWizard<DefProcessedMapBase<T> >(*this);
+    }
+    
+
+//     template<class T>
+//     struct DefPredNodeMapBase : public Base {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
+//       DefPredNodeMapBase(const Base &b) : Base(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 {
+      typedef T DistMap;
+      static DistMap *createDistMap(const Graph &G) { return 0; };
+      DefDistMapBase(const Base &b) : Base(b) {}
+    };
+    
+    ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    template<class T>
+    DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
+    {
+      Base::_dist=(void *)&t;
+      return DfsWizard<DefDistMapBase<T> >(*this);
+    }
+    
+    /// Sets the source node, from which the Dfs algorithm runs.
+
+    /// Sets the source node, from which the Dfs algorithm runs.
+    /// \param s is the source node.
+    DfsWizard<TR> &source(Node s) 
+    {
+      Base::_source=s;
+      return *this;
+    }
+    
+  };
+  
+  ///Function type interface for Dfs algorithm.
+
+  /// \ingroup flowalgs
+  ///Function type interface for Dfs algorithm.
+  ///
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
+  ///they are declared as the members of class \ref DfsWizard.
+  ///The following
+  ///example shows how to use these parameters.
+  ///\code
+  ///  dfs(g,source).predMap(preds).run();
+  ///\endcode
+  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
+  ///to the end of the parameter list.
+  ///\sa DfsWizard
+  ///\sa Dfs
+  template<class GR>
+  DfsWizard<DfsWizardBase<GR> >
+  dfs(const GR &g,typename GR::Node s=INVALID)
+  {
+    return DfsWizard<DfsWizardBase<GR> >(g,s);
+  }
+
 } //END OF NAMESPACE LEMON
 
 #endif
 
-

src/lemon/dijkstra.h

@@ -77 +77 @@
       return new PredMap(G);
     }
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the shortest paths.
-    ///
-    ///The type of the map that stores the last but one
-    ///nodes of the shortest 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 stores whether a nodes is reached.
- 
-    ///The type of the map that stores whether a nodes is reached.
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     ///
+//     ///The type of the map that stores the last but one
+//     ///nodes of the shortest 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 stores whether a nodes is processed.
+ 
+    ///The type of the map that stores whether a nodes is processed.
     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
-    ///\todo If it is set to a real map, Dijkstra::reached() should read this.
+    ///\todo If it is set to a real map,
+    ///Dijkstra::processed() should read this.
     ///\todo named parameter to set this type, function to read and write.
-    typedef NullMap<typename Graph::Node,bool> ReachedMap;
-    ///Instantiates a ReachedMap.
- 
-    ///This function instantiates a \ref ReachedMap. 
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
     ///\param G is the graph, to which
-    ///we would like to define the \ref ReachedMap
-    static ReachedMap *createReachedMap(const GR &G)
-    {
-      return new ReachedMap();
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
     }
     ///The type of the map that stores the dists of the nodes.
@@ -141 +142 @@
   ///It is also possible to change the underlying priority heap.
   ///
-  ///\param GR The graph type the algorithm runs on. The default value is
-  ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
-  ///is only passed to \ref DijkstraDefaultTraits.
-  ///\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 concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
-  ///The value of LM is not used directly by Dijkstra, it
-  ///is only passed to \ref DijkstraDefaultTraits.
-  ///\param TR Traits class to set various data types used by the algorithm.
-  ///The default traits class is
-  ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
-  ///See \ref DijkstraDefaultTraits for the documentation of
-  ///a Dijkstra traits class.
+  ///\param GR The graph type the algorithm runs on. The default value
+  ///is \ref ListGraph. The value of GR is not used directly by
+  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
+  ///\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
+  ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".  The value
+  ///of LM is not used directly by Dijkstra, it is only passed to \ref
+  ///DijkstraDefaultTraits.  \param TR Traits class to set
+  ///various data types used by the algorithm.  The default traits
+  ///class is \ref DijkstraDefaultTraits
+  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
+  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
+  ///class.
   ///
   ///\author Jacint Szabo and Alpar Juttner
@@ -182 +181 @@
     public:
       virtual const char* exceptionName() const {
-        return "lemon::Dijsktra::UninitializedParameter";
+        return "lemon::Dijkstra::UninitializedParameter";
       }
     };
@@ -205 +204 @@
     ///edges of the shortest paths.
     typedef typename TR::PredMap PredMap;
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the shortest paths.
-    typedef typename TR::PredNodeMap PredNodeMap;
-    ///The type of the map indicating if a node is reached.
-    typedef typename TR::ReachedMap ReachedMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map indicating if a node is processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
     ///The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -223 +222 @@
     ///Indicates if \ref _pred is locally allocated (\c true) or not.
     bool local_pred;
-    ///Pointer to the map of predecessors nodes.
-    PredNodeMap *_predNode;
-    ///Indicates if \ref _predNode is locally allocated (\c true) or not.
-    bool local_predNode;
+//     ///Pointer to the map of predecessors nodes.
+//     PredNodeMap *_predNode;
+//     ///Indicates if \ref _predNode is locally allocated (\c true) or not.
+//     bool local_predNode;
     ///Pointer to the map of distances.
     DistMap *_dist;
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
     bool local_dist;
-    ///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;
-
-    ///The source node of the last execution.
-    Node source;
+    ///Pointer to the map of processed status of the nodes.
+    ProcessedMap *_processed;
+    ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    bool local_processed;
+
+//     ///The source node of the last execution.
+//     Node source;
 
     ///Creates the maps if necessary.
@@ -249 +248 @@
         _pred = Traits::createPredMap(*G);
       }
-      if(!_predNode) {
-        local_predNode = true;
-        _predNode = Traits::createPredNodeMap(*G);
-      }
+//       if(!_predNode) {
+//      local_predNode = true;
+//      _predNode = Traits::createPredNodeMap(*G);
+//       }
       if(!_dist) {
         local_dist = true;
         _dist = Traits::createDistMap(*G);
       }
-      if(!_reached) {
-        local_reached = true;
-        _reached = Traits::createReachedMap(*G);
+      if(!_processed) {
+        local_processed = true;
+        _processed = Traits::createProcessedMap(*G);
       }
     }
@@ -286 +285 @@
                                         DefPredMapTraits<T> > { };
     
-    template <class T>
-    struct DefPredNodeMapTraits : public Traits {
-      typedef T PredNodeMap;
-      static PredNodeMap *createPredNodeMap(const Graph &G) 
-      {
-        throw UninitializedParameter();
-      }
-    };
-    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-
-    ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
-    ///
-    template <class T>
-    class DefPredNodeMap : public Dijkstra< Graph,
-                                            LengthMap,
-                                            DefPredNodeMapTraits<T> > { };
+//     template <class T>
+//     struct DefPredNodeMapTraits : public Traits {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) 
+//       {
+//      throw UninitializedParameter();
+//       }
+//     };
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+
+//     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
+//     ///
+//     template <class T>
+//     class DefPredNodeMap : public Dijkstra< Graph,
+//                                          LengthMap,
+//                                          DefPredNodeMapTraits<T> > { };
     
     template <class T>
@@ -321 +320 @@
     
     template <class T>
-    struct DefReachedMapTraits : public Traits {
-      typedef T ReachedMap;
-      static ReachedMap *createReachedMap(const Graph &G) 
+    struct DefProcessedMapTraits : public Traits {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
       {
         throw UninitializedParameter();
       }
     };
-    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
-
-    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     ///
     template <class T>
-    class DefReachedMap : public Dijkstra< Graph,
+    class DefProcessedMap : public Dijkstra< Graph,
                                         LengthMap,
-                                        DefReachedMapTraits<T> > { };
-    
-    struct DefGraphReachedMapTraits : public Traits {
-      typedef typename Graph::template NodeMap<bool> ReachedMap;
-      static ReachedMap *createReachedMap(const Graph &G) 
+                                        DefProcessedMapTraits<T> > { };
+    
+    struct DefGraphProcessedMapTraits : public Traits {
+      typedef typename Graph::template NodeMap<bool> ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Graph &G) 
       {
-        return new ReachedMap(G);
+        return new ProcessedMap(G);
       }
     };
     ///\brief \ref named-templ-param "Named parameter"
-    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     ///
     ///\ref named-templ-param "Named parameter"
-    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+    ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
     ///If you don't set it explicitely, it will be automatically allocated.
     template <class T>
-    class DefReachedMapToBeDefaultMap :
+    class DefProcessedMapToBeDefaultMap :
       public Dijkstra< Graph,
                        LengthMap,
-                       DefGraphReachedMapTraits> { };
+                       DefGraphProcessedMapTraits> { };
     
     ///@}
@@ -371 +370 @@
       G(&_G), length(&_length),
       _pred(NULL), local_pred(false),
-      _predNode(NULL), local_predNode(false),
+//       _predNode(NULL), local_predNode(false),
       _dist(NULL), local_dist(false),
-      _reached(NULL), local_reached(false),
+      _processed(NULL), local_processed(false),
       _heap_map(*G,-1),_heap(_heap_map)
     { }
@@ -381 +380 @@
     {
       if(local_pred) delete _pred;
-      if(local_predNode) delete _predNode;
+//       if(local_predNode) delete _predNode;
       if(local_dist) delete _dist;
-      if(local_reached) delete _reached;
+      if(local_processed) delete _processed;
     }
 
@@ -413 +412 @@
     }
 
-    ///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>
-    Dijkstra &predNodeMap(PredNodeMap &m) 
-    {
-      if(local_predNode) {
-        delete _predNode;
-        local_predNode=false;
-      }
-      _predNode = &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>
+//     Dijkstra &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.
@@ -450 +449 @@
     void finalizeNodeData(Node v,Value dst)
     {
-      _reached->set(v,true);
+      _processed->set(v,true);
       _dist->set(v, dst);
-      if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
+//       if((*_pred)[v]!=INVALID)
+//       _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
     }
 
   public:
-    ///\name Excetution control
+    ///\name Execution control
     ///The simplest way to execute the algorithm is to use
     ///one of the member functions called \c run(...).
     ///\n
-    ///It you need more control on the execution,
+    ///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
+    ///with \ref addSource().
+    ///Finally \ref start() will perform the actual path
     ///computation.
 
@@ -478 +479 @@
       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
         _pred->set(u,INVALID);
-        _predNode->set(u,INVALID);
-        ///\todo *_reached is not set to false.
+//      _predNode->set(u,INVALID);
+        _processed->set(u,false);
         _heap_map.set(u,Heap::PRE_HEAP);
       }
@@ -495 +496 @@
     void addSource(Node s,Value dst=0)
     {
-      source = s;
+//       source = s;
       if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
       else if(_heap[s]<dst) {
@@ -536 +537 @@
     }
 
-    ///Returns \c false if there are nodes to be processed in the priority heap
-
-    ///Returns \c false if there are nodes to be processed in the priority heap
-    ///
-    bool emptyHeap() { return _heap.empty(); }
+    ///\brief Returns \c false if there are nodes
+    ///to be processed in the priority heap
+    ///
+    ///Returns \c false if there are nodes
+    ///to be processed in the priority heap
+    bool emptyQueue() { return _heap.empty(); }
     ///Returns the number of the nodes to be processed in the priority heap
 
     ///Returns the number of the nodes to be processed in the priority heap
     ///
-    int heapSize() { return _heap.size(); }
+    int queueSize() { return _heap.size(); }
     
     ///Executes the algorithm.
@@ -697 +699 @@
     const PredMap &predMap() const { return *_pred;}
  
-    ///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.
+//     ///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 *_predNode;}
+
+    ///Checks if a node is reachable from the root.
+
+    ///Returns \c true if \c v is reachable from the root.
+    ///\warning The source nodes are inditated as unreached.
     ///\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.
-
-    ///Returns \c true if \c v is reachable from the root.
-    ///\warning If the algorithm is started from multiple nodes,
-    ///this function may give false result for the source nodes.
-    ///\pre \ref run() must be called before using this function.
-    ///
-    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
+    ///
+    bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
     
     ///@}
   };
 
+
+
+
+ 
+  ///Default traits class of Dijkstra function.
+
+  ///Default traits class of Dijkstra function.
+  ///\param GR Graph type.
+  ///\param LM Type of length map.
+  template<class GR, class LM>
+  struct DijkstraWizardDefaultTraits
+  {
+    ///The graph type the algorithm runs on. 
+    typedef GR Graph;
+    ///The type of the map that stores the edge lengths.
+
+    ///The type of the map that stores the edge lengths.
+    ///It must meet the \ref concept::ReadMap "ReadMap" concept.
+    typedef LM LengthMap;
+    //The type of the length of the edges.
+    typedef typename LM::Value Value;
+    ///The heap type used by Dijkstra algorithm.
+
+    ///The heap type used by Dijkstra algorithm.
+    ///
+    ///\sa BinHeap
+    ///\sa Dijkstra
+    typedef BinHeap<typename Graph::Node,
+                    typename LM::Value,
+                    typename GR::template NodeMap<int>,
+                    std::less<Value> > Heap;
+
+    ///\brief The type of the map that stores the last
+    ///edges of the shortest paths.
+    /// 
+    ///The type of the map that stores the last
+    ///edges of the shortest paths.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
+    ///Instantiates a PredMap.
+ 
+    ///This function instantiates a \ref PredMap. 
+    ///\param G is the graph, to which we would like to define the PredMap.
+    ///\todo The graph alone may be insufficient for the initialization
+    static PredMap *createPredMap(const GR &G) 
+    {
+      return new PredMap();
+    }
+    ///The type of the map that stores whether a nodes is processed.
+ 
+    ///The type of the map that stores whether a nodes is processed.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///By default it is a NullMap.
+    ///\todo If it is set to a real map,
+    ///Dijkstra::processed() should read this.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ProcessedMap;
+    ///Instantiates a ProcessedMap.
+ 
+    ///This function instantiates a \ref ProcessedMap. 
+    ///\param G is the graph, to which
+    ///we would like to define the \ref ProcessedMap
+    static ProcessedMap *createProcessedMap(const GR &G)
+    {
+      return new ProcessedMap();
+    }
+    ///The type of the map that stores the dists of the nodes.
+ 
+    ///The type of the map that stores the dists of the nodes.
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
+    ///Instantiates a DistMap.
+ 
+    ///This function instantiates a \ref DistMap. 
+    ///\param G is the graph, to which we would like to define the \ref DistMap
+    static DistMap *createDistMap(const GR &G)
+    {
+      return new DistMap();
+    }
+  };
+  
   /// Default traits used by \ref DijkstraWizard
 
@@ -725 +809 @@
   /// \ref DijkstraWizard class.
   template<class GR,class LM>
-  class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
+  class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
   {
 
-    typedef DijkstraDefaultTraits<GR,LM> Base;
+    typedef DijkstraWizardDefaultTraits<GR,LM> Base;
   protected:
     /// Type of the nodes in the graph.
@@ -739 +823 @@
     ///Pointer to the map of predecessors edges.
     void *_pred;
-    ///Pointer to the map of predecessors nodes.
-    void *_predNode;
+//     ///Pointer to the map of predecessors nodes.
+//     void *_predNode;
     ///Pointer to the map of distances.
     void *_dist;
@@ -751 +835 @@
     /// This constructor does not require parameters, therefore it initiates
     /// all of the attributes to default values (0, INVALID).
-    DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
-                       _dist(0), _source(INVALID) {}
+    DijkstraWizardBase() : _g(0), _length(0), _pred(0),
+//                         _predNode(0),
+                           _dist(0), _source(INVALID) {}
 
     /// Constructor.
@@ -763 +848 @@
     /// \param s is the initial value of  \ref _source
     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
-      _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
-                  _dist(0), _source(s) {}
+      _g((void *)&g), _length((void *)&l), _pred(0),
+//       _predNode(0),
+      _dist(0), _source(s) {}
 
   };
@@ -770 +856 @@
   /// A class to make easier the usage of Dijkstra algorithm
 
-  /// \ingroup flowalgs
   /// This class is created to make it easier to use Dijkstra algorithm.
   /// It uses the functions and features of the plain \ref Dijkstra,
@@ -811 +896 @@
     ///edges of the shortest paths.
     typedef typename TR::PredMap PredMap;
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the shortest paths.
-    typedef typename TR::PredNodeMap PredNodeMap;
+//     ///\brief The type of the map that stores the last but one
+//     ///nodes of the shortest paths.
+//     typedef typename TR::PredNodeMap PredNodeMap;
     ///The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -845 +930 @@
         Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
       if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
-      if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
+//       if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
       if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
       Dij.run(Base::_source);
@@ -881 +966 @@
     
 
-    template<class T>
-    struct DefPredNodeMapBase : public Base {
-      typedef T PredNodeMap;
-      static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
-      DefPredNodeMapBase(const Base &b) : Base(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>
-    DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
-    {
-      Base::_predNode=(void *)&t;
-      return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
-    }
+//     template<class T>
+//     struct DefPredNodeMapBase : public Base {
+//       typedef T PredNodeMap;
+//       static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
+//       DefPredNodeMapBase(const Base &b) : Base(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>
+//     DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) 
+//     {
+//       Base::_predNode=(void *)&t;
+//       return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
+//     }
    
     template<class T>
@@ -933 +1018 @@
   };
   
-  ///\e
+  ///Function type interface for Dijkstra algorithm.
 
   /// \ingroup flowalgs
-  ///\todo Please document...
+  ///Function type interface for Dijkstra algorithm.
   ///
+  ///This function also has several
+  ///\ref named-templ-func-param "named parameters",
+  ///they are declared as the members of class \ref DijkstraWizard.
+  ///The following
+  ///example shows how to use these parameters.
+  ///\code
+  ///  dijkstra(g,length,source).predMap(preds).run();
+  ///\endcode
+  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
+  ///to the end of the parameter list.
+  ///\sa DijkstraWizard
+  ///\sa Dijkstra
   template<class GR, class LM>
   DijkstraWizard<DijkstraWizardBase<GR,LM> >
@@ -945 +1042 @@
   }
 
-/// @}
-  
 } //END OF NAMESPACE LEMON
 

src/test/bfs_test.cc

@@ -43 +43 @@
   BType::DistMap d(G);
   BType::PredMap p(G);
-  BType::PredNodeMap pn(G);
+  //  BType::PredNodeMap pn(G);
   
   BType bfs_test(G);
@@ -54 +54 @@
   d  = bfs_test.distMap();
   p  = bfs_test.predMap();
-  pn = bfs_test.predNodeMap();
+  //  pn = bfs_test.predNodeMap();
   b  = bfs_test.reached(n);
 

src/test/dfs_test.cc

@@ -43 +43 @@
   DType::DistMap d(G);
   DType::PredMap p(G);
-  DType::PredNodeMap pn(G);
+  //  DType::PredNodeMap pn(G);
   
   DType dfs_test(G);
@@ -54 +54 @@
   d  = dfs_test.distMap();
   p  = dfs_test.predMap();
-  pn = dfs_test.predNodeMap();
+  //  pn = dfs_test.predNodeMap();
   b  = dfs_test.reached(n);
 

src/test/dijkstra_test.cc

@@ -120 +120 @@
   
   {
-    NullMap<Node,Node> myPredNodeMap;
-    dijkstra(G,cap).predNodeMap(myPredNodeMap).run(s);
+    NullMap<Node,Edge> myPredMap;
+    dijkstra(G,cap).predMap(myPredMap).run(s);
   }
   return 0;