COIN-OR::LEMON - Graph Library

Context Navigation

← Previous Changeset
Next Changeset →

Changeset 244:c30731a37f91 in lemon-main

Timestamp:

08/03/08 13:34:57 (16 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

Phase:

public

Message:

Many improvements in bfs.h, dfs.h and dijkstra.h

Add run() function to Bfs and run(s,t) function to DfsVisit?.
Add debug checking to addSource() function of Dfs and DfsVisit?.
Add a few missing named parameters (according to \todo notes).
Small fixes in the code (e.g. missing derivations).
Many doc improvements.
Remove \todo and \warning comments which are no longer valid.
Remove \author commands (see ticket #39).
Fixes in the the doc (e.g. wrong references).
Hide the doc of most of the private and protected members.
Use public typedefs instead of template parameters in public functions.
Use better parameter names for some functions.
Other small changes to make the doc more uniform.

Location:

Files:

: 3 edited

bfs.h (modified) (81 diffs)
dfs.h (modified) (74 diffs)
dijkstra.h (modified) (51 diffs)

Legend:

: Unmodified
: Added
: Removed

lemon/bfs.h

-                      r210
+                      r244
 ///\ingroup search
 ///\file
 ///\brief Bfs algorithm.
+///\brief BFS algorithm.
 #include <lemon/list_graph.h>
 …
 namespace lemon {
   ///Default traits class of Bfs class.
 …
   struct BfsDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
+    ///\brief The type of the map that stores the last
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
+    ///Instantiates a PredMap.
+    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
     ///This function instantiates a \ref PredMap.
+    ///\param G is the digraph, to which we would like to define the PredMap.
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
+    static PredMap *createPredMap(const GR &G)
+    {
+      return new PredMap(G);
+    }
+    static PredMap *createPredMap(const Digraph &g)
+    {
+      return new PredMap(g);
+    }
     ///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 concepts::WriteMap "WriteMap" concept.
     ///\todo named parameter to set this type, function to read and write.
+    ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
     ///This function instantiates a \ref ProcessedMap.
 …
     ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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 concepts::ReadWriteMap "ReadWriteMap" concept.
+    typedef typename Digraph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a \ref ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
+    ///\param g is the digraph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const Digraph &g)
+    {
+      return new ReachedMap(g);
+    }
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
-    typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-    ///This function instantiates a \ref ReachedMap.
-    ///\param G is the digraph, 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 concepts::WriteMap "WriteMap" concept.
-    ///
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
     ///\param G is the digraph, to which we would like to define
     ///the \ref DistMap
     static DistMap *createDistMap(const GR &G)
+    {
       return new DistMap(G);
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref DistMap.
+    static DistMap *createDistMap(const Digraph &g)
+    {
+      return new DistMap(g);
+    }
   };
 …
   ///This class provides an efficient implementation of the %BFS algorithm.
   ///
+  ///\tparam GR The digraph type the algorithm runs on. The default value is
+  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
+  ///is only passed to \ref BfsDefaultTraits.
+  ///There is also a \ref bfs() "function type interface" for the BFS
+  ///algorithm, which is convenient in the simplier cases and it can be
+  ///used easier.
+  ///
+  ///\tparam GR The type of the digraph the algorithm runs on.
+  ///The default value is \ref ListDigraph. The value of GR is not used
+  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
   ///\tparam TR Traits class to set various data types used by the algorithm.
   ///The default traits class is
 …
   ///See \ref BfsDefaultTraits for the documentation of
   ///a Bfs traits class.
 #ifdef DOXYGEN
   template <typename GR,
 …
   class Bfs {
   public:
+    /**
+     * \brief \ref Exception for uninitialized parameters.
+     *
+     * This error represents problems in the initialization
+     * of the parameters of the algorithms.
+     */
+    ///\ref Exception for uninitialized parameters.
+    ///This error represents problems in the initialization of the
+    ///parameters of the algorithm.
     class UninitializedParameter : public lemon::UninitializedParameter {
     public:
 …
     };
+    ///The type of the digraph the algorithm runs on.
+    typedef typename TR::Digraph Digraph;
+    ///\brief The type of the map that stores the predecessor arcs of the
+    ///shortest paths.
+    typedef typename TR::PredMap PredMap;
+    ///The type of the map that stores the distances of the nodes.
+    typedef typename TR::DistMap DistMap;
+    ///The type of the map that indicates which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///The type of the map that indicates which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///The type of the paths.
+    typedef PredMapPath<Digraph, PredMap> Path;
+    ///The traits class.
     typedef TR Traits;
+    ///The type of the underlying digraph.
+    typedef typename TR::Digraph Digraph;
+    ///\brief The type of the map that stores the last
+    ///arcs of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+    ///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:
 …
     typedef typename Digraph::OutArcIt OutArcIt;
     /// Pointer to the underlying digraph.
+    //Pointer to the underlying digraph.
     const Digraph *G;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessor arcs.
     PredMap *_pred;
     ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    //Indicates if _pred is locally allocated (true) or not.
     bool local_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     DistMap *_dist;
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    //Indicates if _dist is locally allocated (true) or not.
     bool local_dist;
     ///Pointer to the map of reached status of the nodes.
+    //Pointer to the map of reached status of the nodes.
     ReachedMap *_reached;
     ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    //Indicates if _reached is locally allocated (true) or not.
     bool local_reached;
     ///Pointer to the map of processed status of the nodes.
+    //Pointer to the map of processed status of the nodes.
     ProcessedMap *_processed;
     ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    //Indicates if _processed is locally allocated (true) or not.
     bool local_processed;
 …
     ///Creates the maps if necessary.
     ///\todo Better memory allocation (instead of new).
     void create_maps()
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///PredMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting PredMap type
     ///
+    ///\ref PredMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref PredMap type.
     template <class T>
     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///DistMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting DistMap type
     ///
+    ///\ref DistMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref DistMap type.
     template <class T>
     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ReachedMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     ///
+    ///\ref ReachedMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ReachedMap type.
     template <class T>
     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     ///
+    ///\ref ProcessedMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type.
     template <class T>
     struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
 …
     struct DefDigraphProcessedMapTraits : public Traits {
       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &G)
+      static ProcessedMap *createProcessedMap(const Digraph &g)
+      {
         return new ProcessedMap(G);
+      }
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     ///
     ///\ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
+        return new ProcessedMap(g);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
     ///If you don't set it explicitly, it will be automatically allocated.
     template <class T>
 …
     ///Constructor.
     ///\param _G the digraph the algorithm will run on.
     ///
     Bfs(const Digraph& _G) :
       G(&_G),
+    ///Constructor.
+    ///\param g The digraph the algorithm runs on.
+    Bfs(const Digraph &g) :
+      G(&g),
       _pred(NULL), local_pred(false),
       _dist(NULL), local_dist(false),
 …
+    }
     ///Sets the map storing the predecessor arcs.
     ///Sets the map storing the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destructor deallocates this
 …
+    }
     ///Sets the map indicating the reached nodes.
     ///Sets the map indicating the reached nodes.
+    ///Sets the map that indicates which nodes are reached.
+    ///Sets the map that indicates which nodes are reached.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destructor deallocates this
 …
+    }
     ///Sets the map indicating the processed nodes.
     ///Sets the map indicating the processed nodes.
+    ///Sets the map that indicates which nodes are processed.
+    ///Sets the map that indicates which nodes are processed.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destructor deallocates this
 …
+    }
+    ///Sets the map storing the distances calculated by the algorithm.
+    ///Sets the map storing the distances calculated by the algorithm.
+    ///Sets the map that stores the distances of the nodes.
+    ///Sets the map that stores the distances of the nodes calculated by
+    ///the algorithm.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destructor deallocates this
 …
   public:
     ///\name Execution control
     ///The simplest way to execute the algorithm is to use
     ///one of the member functions called \c run(...).
+    ///one of the member functions called \ref lemon::Bfs::run() "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.
+    ///If you need more control on the execution, first you must call
+    ///\ref lemon::Bfs::init() "init()", then you can add several source
+    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
+    ///Finally \ref lemon::Bfs::start() "start()" will perform the
+    ///actual path computation.
     ///@{
     ///\brief Initializes the internal data structures.
+    ///
+    ///Initializes the internal data structures.
     ///Initializes the internal data structures.
     ///
 …
     ///\return The processed node.
     ///
     ///\warning The queue must not be empty!
+    ///\pre The queue must not be empty.
     Node processNextNode()
+    {
 …
     ///Processes the next node.
     ///Processes the next node. And checks that the given target node
+    ///Processes the next node and checks if the given target node
     ///is reached. If the target node is reachable from the processed
+    ///node then the reached parameter will be set true. The reached
+    ///parameter should be initially false.
+    ///node, then the \c reach parameter will be set to \c true.
     ///
     ///\param target The target node.
+    ///\retval reach Indicates that the target node is reached.
+    ///\retval reach Indicates if the target node is reached.
+    ///It should be initially \c false.
+    ///
     ///\return The processed node.
     ///
     ///\warning The queue must not be empty!
+    ///\pre The queue must not be empty.
     Node processNextNode(Node target, bool& reach)
+    {
 …
     ///Processes the next node.
+    ///Processes the next node. And checks that at least one of
+    ///reached node has true value in the \c nm node map. If one node
+    ///with true value is reachable from the processed node then the
+    ///rnode parameter will be set to the first of such nodes.
+    ///
+    ///\param nm The node map of possible targets.
+    ///Processes the next node and checks if at least one of reached
+    ///nodes has \c true value in the \c nm node map. If one node
+    ///with \c true value is reachable from the processed node, then the
+    ///\c rnode parameter will be set to the first of such nodes.
+    ///
+    ///\param nm A \c bool (or convertible) node map that indicates the
+    ///possible targets.
     ///\retval rnode The reached target node.
+    ///It should be initially \c INVALID.
+    ///
     ///\return The processed node.
     ///
     ///\warning The queue must not be empty!
+    ///\pre The queue must not be empty.
     template<class NM>
     Node processNextNode(const NM& nm, Node& rnode)
 …
+    }
+    ///Next node to be processed.
+    ///Next node to be processed.
+    ///
+    ///\return The next node to be processed or INVALID if the queue is
+    /// empty.
+    Node nextNode()
+    ///The next node to be processed.
+    ///Returns the next node to be processed or \c INVALID if the queue
+    ///is empty.
+    Node nextNode() const
+    {
       return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
 …
     ///\brief Returns \c false if there are nodes
     ///to be processed in the queue
+    ///to be processed.
     ///
     ///Returns \c false if there are nodes
+    ///to be processed in the queue
+    bool emptyQueue() { return _queue_tail==_queue_head; }
+    ///to be processed in the queue.
+    bool emptyQueue() const { 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; }
+    int queueSize() const { 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).
+    ///in order to compute the shortest path to each node.
+    ///
+    ///The algorithm computes
+    ///- the shortest path tree (forest),
+    ///- the distance of each node from the root(s).
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
+    ///\code
+    ///  while ( !b.emptyQueue() ) {
+    ///    b.processNextNode();
+    ///  }
+    ///\endcode
     void start()
+    {
 …
+    }
+    ///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.
+    ///Executes the algorithm until the given target node is reached.
+    ///Executes the algorithm until the given target node is reached.
     ///
     ///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).
+    ///- the shortest path to \c dest,
+    ///- the distance of \c dest from the root(s).
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
+    ///\code
+    ///  bool reach = false;
+    ///  while ( !b.emptyQueue() && !reach ) {
+    ///    b.processNextNode(t, reach);
+    ///  }
+    ///\endcode
     void start(Node dest)
+    {
 …
     ///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]</tt> true.
+    ///This method runs the %BFS algorithm from the root node(s) in
+    ///order to compute the shortest path to a node \c v with
+    /// <tt>nm[v]</tt> true, if such a node can be found.
+    ///
+    ///\param nm A \c bool (or convertible) node map. The algorithm
+    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
     ///
     ///\return The reached node \c v with <tt>nm[v]</tt> true or
     ///\c INVALID if no such node was found.
+    template<class NM>
+    Node start(const NM &nm)
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
+    ///\code
+    ///  Node rnode = INVALID;
+    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
+    ///    b.processNextNode(nm, rnode);
+    ///  }
+    ///  return rnode;
+    ///\endcode
+    template<class NodeBoolMap>
+    Node start(const NodeBoolMap &nm)
+    {
       Node rnode = INVALID;
 …
+    }
     ///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 b.run(s) is just a shortcut of the following code.
+    ///Runs the algorithm from the given node.
+    ///This method runs the %BFS algorithm from 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 <tt>b.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///  b.init();
 …
     ///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, b.run(s) is
+    ///just a shortcut of the following code.
+    ///This method runs the %BFS algorithm from node \c s
+    ///in order to compute the shortest path to \c t.
+    ///
+    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
+    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///
+    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
+    ///shortcut of the following code.
     ///\code
     ///  b.init();
 …
+    }
+    ///Runs the algorithm to visit all nodes in the digraph.
+    ///This method runs the %BFS algorithm in order to
+    ///compute the shortest path to each node.
+    ///
+    ///The algorithm computes
+    ///- the shortest path tree (forest),
+    ///- the distance of each node from the root(s).
+    ///
+    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
+    ///\code
+    ///  b.init();
+    ///  for (NodeIt n(gr); n != INVALID; ++n) {
+    ///    if (!b.reached(n)) {
+    ///      b.addSource(n);
+    ///      b.start();
+    ///    }
+    ///  }
+    ///\endcode
+    void run() {
+      init();
+      for (NodeIt n(*G); n != INVALID; ++n) {
+        if (!reached(n)) {
+          addSource(n);
+          start();
+        }
+      }
+    }
     ///@}
 …
     ///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 calleb.
+    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
+    ///"start()" must be called before using them.
     ///@{
+    typedef PredMapPath<Digraph, PredMap> Path;
+    ///Gives back the shortest path.
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t)
+    {
+      return Path(*G, *_pred, t);
+    }
+    ///The shortest path to a node.
+    ///Returns the shortest path to a node.
+    ///
+    ///\warning \c t should be reachable from the root(s).
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
+    Path path(Node t) const { return Path(*G, *_pred, t); }
     ///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(s) the return value
+    ///of this function is undefined.
+    ///
+    ///\warning If node \c v is not reachable from the root(s), then
+    ///the return value of this function is undefined.
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     int dist(Node v) const { return (*_dist)[v]; }
+    ///Returns the 'previous arc' of the shortest path tree.
+    ///For a node \c v it returns the 'previous arc'
+    ///of the shortest path tree,
+    ///i.e. it returns the last arc of a shortest path from the root(s) to \c
+    ///v. It is \ref INVALID
+    ///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().
+    ///\pre Either \ref run() or \ref start() must be called before using
+    ///this function.
+    ///Returns the 'previous arc' of the shortest path tree for a node.
+    ///This function returns the 'previous arc' of the shortest path
+    ///tree for the node \c v, i.e. it returns the last arc of a
+    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+    ///is not reachable from the root(s) or if \c v is a root.
+    ///
+    ///The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref predNode().
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Arc predArc(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(a) to \c /v.
+    ///It is INVALID if \c v is unreachable from the root(s) or
+    ///if \c v itself a root.
+    ///Returns the 'previous node' of the shortest path tree for a node.
+    ///This function returns the 'previous node' of the shortest path
+    ///tree for the node \c v, i.e. it returns the last but one node
+    ///from a shortest path from the root(s) to \c v. It is \c INVALID
+    ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///
     ///The shortest path tree used here is equal to the shortest path
     ///tree used in \ref predArc().
+    ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
 …
                                   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.
+    ///\brief Returns a const reference to the node map that stores the
+    /// distances of the nodes.
+    ///
+    ///Returns a const reference to the node map that stores the distances
+    ///of the nodes calculated by the algorithm.
+    ///
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
+    ///Returns a reference to the shortest path tree map.
+    ///Returns a reference to the NodeMap of the arcs of the
+    ///shortest path tree.
+    ///\brief Returns a const reference to the node map that stores the
+    ///predecessor arcs.
+    ///
+    ///Returns a const reference to the node map that stores the predecessor
+    ///arcs, which form the shortest path tree.
+    ///
     ///\pre Either \ref run() or \ref init()
     ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
+    ///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 indicated as unreached.
+    ///Checks if a node is reachable from the root(s).
+    ///Returns \c true if \c v is reachable from the root(s).
     ///\pre Either \ref run() or \ref start()
     ///must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
     ///@}
   };
   ///Default traits class of Bfs function.
   ///Default traits class of Bfs function.
+  ///Default traits class of bfs() function.
+  ///Default traits class of bfs() function.
   ///\tparam GR Digraph type.
   template<class GR>
   struct BfsWizardDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
+    ///\brief The type of the map that stores the last
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
+    ///Instantiates a PredMap.
+    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
     ///This function instantiates a \ref PredMap.
+    ///\param g is the digraph, to which we would like to define the PredMap.
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
 #ifdef DOXYGEN
     static PredMap *createPredMap(const GR &g)
+    static PredMap *createPredMap(const Digraph &g)
 #else
     static PredMap *createPredMap(const GR &)
+    static PredMap *createPredMap(const Digraph &)
 #endif
+    {
 …
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
     ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \ref ProcessedMap
+    ///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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 concepts::ReadWriteMap "ReadWriteMap" concept.
+    typedef typename Digraph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a \ref ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
+    ///\param g is the digraph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const Digraph &g)
+    {
+      return new ReachedMap(g);
+    }
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
-    typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-    ///This function instantiates a \ref ReachedMap.
-    ///\param G is the digraph, 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 concepts::WriteMap "WriteMap" concept.
     ///
     typedef NullMap<typename Digraph::Node,int> DistMap;
     ///Instantiates a DistMap.
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
 …
     ///the \ref DistMap
 #ifdef DOXYGEN
     static DistMap *createDistMap(const GR &g)
+    static DistMap *createDistMap(const Digraph &g)
 #else
     static DistMap *createDistMap(const GR &)
+    static DistMap *createDistMap(const Digraph &)
 #endif
+    {
 …
   };
   /// Default traits used by \ref BfsWizard
+  /// Default traits class used by \ref BfsWizard
   /// To make it easier to use Bfs algorithm
   ///we have created a wizard class.
+  /// we have created a wizard class.
   /// This \ref BfsWizard class needs default traits,
   ///as well as the \ref Bfs class.
+  /// as well as the \ref Bfs class.
   /// The \ref BfsWizardBase is a class to be the default traits of the
   /// \ref BfsWizard class.
 …
     typedef BfsWizardDefaultTraits<GR> Base;
   protected:
     /// Type of the nodes in the digraph.
+    //The type of the nodes in the digraph.
     typedef typename Base::Digraph::Node Node;
     /// Pointer to the underlying digraph.
+    //Pointer to the digraph the algorithm runs on.
     void *_g;
     ///Pointer to the map of reached nodes.
+    //Pointer to the map of reached nodes.
     void *_reached;
     ///Pointer to the map of processed nodes.
+    //Pointer to the map of processed nodes.
     void *_processed;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessors arcs.
     void *_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     void *_dist;
     ///Pointer to the source node.
+    //Pointer to the source node.
     Node _source;
 …
     /// all of the attributes to default values (0, INVALID).
     BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
                            _dist(0), _source(INVALID) {}
+                      _dist(0), _source(INVALID) {}
     /// Constructor.
 …
     /// 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
+    /// \param g The digraph the algorithm runs on.
+    /// \param s The source node.
     BfsWizardBase(const GR &g, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 …
   };
+  /// 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.
+  /// Auxiliary class for the function type interface of BFS algorithm.
+  /// This auxiliary class is created to implement the function type
+  /// interface of \ref Bfs algorithm. It uses the functions and features
+  /// of the plain \ref Bfs, but it is much simpler to use it.
+  /// It should only be used through the \ref bfs() function, which makes
+  /// it easier to use the algorithm.
   ///
   /// Simplicity means that the way to change the types defined
 …
   /// the original class by using the ::
   /// operator. In the case of \ref BfsWizard only
   /// a function have to be called and it will
+  /// 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.
+  /// It does not have own \ref run() method. When its \ref run() method
+  /// is called, it initiates a plain \ref Bfs object, and calls the
+  /// \ref Bfs::run() method of it.
   template<class TR>
   class BfsWizard : public TR
 …
     typedef TR Base;
     ///The type of the underlying digraph.
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
+    //\e
     typedef typename Digraph::Node Node;
-    //\e
     typedef typename Digraph::NodeIt NodeIt;
-    //\e
     typedef typename Digraph::Arc Arc;
-    //\e
     typedef typename Digraph::OutArcIt OutArcIt;
+    ///\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
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     typedef typename TR::PredMap PredMap;
     ///The type of the map that stores the dists of the nodes.
+    ///\brief The type of the map that stores the distances of the nodes.
     typedef typename TR::DistMap DistMap;
+    ///\brief The type of the map that indicates which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///\brief The type of the map that indicates which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
   public:
     /// Constructor.
     BfsWizard() : TR() {}
 …
     ~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.
+    ///Runs BFS algorithm from a source node.
+    ///Runs BFS algorithm from a source node.
+    ///The node can be given with the \ref source() function.
     void run()
+    {
 …
+    }
     ///Runs Bfs algorithm from the given node.
     ///Runs Bfs algorithm from the given node.
+    ///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();
+    }
+    /// 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;
+    }
 …
       DefPredMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting PredMap
+    ///for setting \ref PredMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap
+    ///
+    ///for setting \ref PredMap object.
     template<class T>
     BfsWizard<DefPredMapBase<T> > predMap(const T &t)
 …
       return BfsWizard<DefPredMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefReachedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ReachedMap
+    ///for setting \ref ReachedMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    ///for setting \ref ReachedMap object.
     template<class T>
     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
 …
       return BfsWizard<DefReachedMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefProcessedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ProcessedMap
+    ///for setting \ref ProcessedMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    ///for setting \ref ProcessedMap object.
     template<class T>
     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
 …
       return BfsWizard<DefProcessedMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefDistMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting DistMap type
+    ///for setting \ref DistMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    ///for setting \ref DistMap object.
     template<class T>
     BfsWizard<DefDistMapBase<T> > distMap(const T &t)
 …
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&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;
+    }
 …
 #ifdef DOXYGEN
   /// \brief Visitor class for bfs.
+  /// \brief Visitor class for BFS.
   ///
   /// This class defines the interface of the BfsVisit events, and
   /// it could be the base of a real Visitor class.
+  /// it could be the base of a real visitor class.
   template <typename _Digraph>
   struct BfsVisitor {
 …
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
+    /// \brief Called when the arc reach a node.
+    ///
+    /// It is called when the bfs find an arc which target is not
+    /// reached yet.
+    /// \brief Called for the source node(s) of the BFS.
+    ///
+    /// This function is called for the source node(s) of the BFS.
+    void start(const Node& node) {}
+    /// \brief Called when a node is reached first time.
+    ///
+    /// This function is called when a node is reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when a node is processed.
+    ///
+    /// This function is called when a node is processed.
+    void process(const Node& node) {}
+    /// \brief Called when an arc reaches a new node.
+    ///
+    /// This function is called when the BFS finds an arc whose target node
+    /// is not reached yet.
     void discover(const Arc& arc) {}
+    /// \brief Called when the node reached first time.
+    ///
+    /// It is Called when the node reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when the arc examined but target of the arc
+    /// \brief Called when an arc is examined but its target node is
     /// already discovered.
     ///
     /// It called when the arc examined but the target of the arc
+    /// This function is called when an arc is examined but its target node is
     /// already discovered.
     void examine(const Arc& arc) {}
-    /// \brief Called for the source node of the bfs.
-    ///
-    /// It is called for the source node of the bfs.
-    void start(const Node& node) {}
-    /// \brief Called when the node processed.
-    ///
-    /// It is Called when the node processed.
-    void process(const Node& node) {}
   };
 #else
 …
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
+    void start(const Node&) {}
+    void reach(const Node&) {}
+    void process(const Node&) {}
     void discover(const Arc&) {}
-    void reach(const Node&) {}
     void examine(const Arc&) {}
-    void start(const Node&) {}
-    void process(const Node&) {}
     template <typename _Visitor>
 …
         Arc arc;
         Node node;
+        visitor.start(node);
+        visitor.reach(node);
+        visitor.process(node);
         visitor.discover(arc);
-        visitor.reach(node);
         visitor.examine(arc);
-        visitor.start(node);
-        visitor.process(node);
+      }
       _Visitor& visitor;
 …
   ///
   /// Default traits class of BfsVisit class.
   /// \tparam _Digraph Digraph type.
+  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   template<class _Digraph>
   struct BfsVisitDefaultTraits {
     /// \brief The digraph type the algorithm runs on.
+    /// \brief The type of the digraph the algorithm runs on.
     typedef _Digraph Digraph;
 …
     ///
     /// The type of the map that indicates which nodes are reached.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    /// \todo named parameter to set this type, function to read and write.
+    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     /// \brief Instantiates a ReachedMap.
+    /// \brief Instantiates a \ref ReachedMap.
     ///
     /// This function instantiates a \ref ReachedMap.
 …
   /// \ingroup search
   ///
   /// \brief %BFS Visit algorithm class.
+  /// \brief %BFS algorithm class with visitor interface.
   ///
   /// This class provides an efficient implementation of the %BFS algorithm
 …
   /// The %BfsVisit class provides an alternative interface to the Bfs
   /// class. It works with callback mechanism, the BfsVisit object calls
   /// on every bfs event the \c Visitor class member functions.
+  /// the member functions of the \c Visitor class on every BFS event.
   ///
   /// \tparam _Digraph The digraph type the algorithm runs on.
+  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   /// The default value is
   /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
   /// is only passed to \ref BfsDefaultTraits.
   /// \tparam _Visitor The Visitor object for the algorithm. The
   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
   /// does not observe the Bfs events. If you want to observe the bfs
   /// events you should implement your own Visitor class.
+  /// \ref ListDigraph. The value of _Digraph is not used directly by
+  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
+  /// \tparam _Visitor The Visitor type that is used by the algorithm.
+  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
+  /// does not observe the BFS events. If you want to observe the BFS
+  /// events, you should implement your own visitor class.
   /// \tparam _Traits Traits class to set various data types used by the
   /// algorithm. The default traits class is
   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
   /// See \ref BfsVisitDefaultTraits for the documentation of
   /// a Bfs visit traits class.
+  /// a BFS visit traits class.
 #ifdef DOXYGEN
   template <typename _Digraph, typename _Visitor, typename _Traits>
 …
     ///
     /// This error represents problems in the initialization
     /// of the parameters of the algorithms.
+    /// of the parameters of the algorithm.
     class UninitializedParameter : public lemon::UninitializedParameter {
     public:
 …
     };
+    ///The traits class.
     typedef _Traits Traits;
+    ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
+    ///The visitor type used by the algorithm.
     typedef _Visitor Visitor;
     ///The type of the map indicating which nodes are reached.
+    ///The type of the map that indicates which nodes are reached.
     typedef typename Traits::ReachedMap ReachedMap;
 …
     typedef typename Digraph::OutArcIt OutArcIt;
     /// Pointer to the underlying digraph.
+    //Pointer to the underlying digraph.
     const Digraph *_digraph;
     /// Pointer to the visitor object.
+    //Pointer to the visitor object.
     Visitor *_visitor;
     ///Pointer to the map of reached status of the nodes.
+    //Pointer to the map of reached status of the nodes.
     ReachedMap *_reached;
     ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    //Indicates if _reached is locally allocated (true) or not.
     bool local_reached;
 …
     int _list_front, _list_back;
+    /// \brief Creates the maps if necessary.
+    ///
+    /// Creates the maps if necessary.
+    ///Creates the maps if necessary.
+    ///\todo Better memory allocation (instead of new).
     void create_maps() {
       if(!_reached) {
 …
     };
     /// \brief \ref named-templ-param "Named parameter" for setting
     /// ReachedMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
+    /// ReachedMap type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
     template <class T>
     struct DefReachedMap : public BfsVisit< Digraph, Visitor,
 …
     /// Constructor.
     ///
+    /// \param digraph the digraph the algorithm will run on.
+    /// \param visitor The visitor of the algorithm.
+    ///
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param visitor The visitor object of the algorithm.
     BfsVisit(const Digraph& digraph, Visitor& visitor)
       : _digraph(&digraph), _visitor(&visitor),
 …
     /// \brief Destructor.
-    ///
-    /// Destructor.
     ~BfsVisit() {
       if(local_reached) delete _reached;
+    }
     /// \brief Sets the map indicating if a node is reached.
     ///
     /// Sets the map indicating if a node is reached.
+    /// \brief Sets the map that indicates which nodes are reached.
+    ///
+    /// Sets the map that indicates which nodes are reached.
     /// If you don't use this function before calling \ref run(),
     /// it will allocate one. The destuctor deallocates this
+    /// it will allocate one. The destructor deallocates this
     /// automatically allocated map, of course.
     /// \return <tt> (*this) </tt>
 …
   public:
     /// \name Execution control
     /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// one of the member functions called \ref lemon::BfsVisit::run()
+    /// "run()".
     /// \n
     /// If you need more control on the execution,
     /// first you must call \ref init(), then you can adda source node
     /// with \ref addSource().
     /// Finally \ref start() will perform the actual path
     /// computation.
+    /// If you need more control on the execution, first you must call
+    /// \ref lemon::BfsVisit::init() "init()", then you can add several
+    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
+    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
+    /// actual path computation.
     /// @{
     /// \brief Initializes the internal data structures.
     ///
     /// Initializes the internal data structures.
-    ///
     void init() {
       create_maps();
 …
     /// \return The processed node.
     ///
     /// \pre The queue must not be empty!
+    /// \pre The queue must not be empty.
     Node processNextNode() {
       Node n = _list[++_list_front];
 …
     /// \brief Processes the next node.
     ///
     /// Processes the next node. And checks that the given target node
+    /// Processes the next node and checks if the given target node
     /// is reached. If the target node is reachable from the processed
+    /// node then the reached parameter will be set true. The reached
+    /// parameter should be initially false.
+    /// node, then the \c reach parameter will be set to \c true.
     ///
     /// \param target The target node.
+    /// \retval reach Indicates that the target node is reached.
+    /// \retval reach Indicates if the target node is reached.
+    /// It should be initially \c false.
+    ///
     /// \return The processed node.
     ///
     /// \warning The queue must not be empty!
+    /// \pre The queue must not be empty.
     Node processNextNode(Node target, bool& reach) {
       Node n = _list[++_list_front];
 …
     /// \brief Processes the next node.
     ///
+    /// Processes the next node. And checks that at least one of
+    /// reached node has true value in the \c nm node map. If one node
+    /// with true value is reachable from the processed node then the
+    /// rnode parameter will be set to the first of such nodes.
+    ///
+    /// \param nm The node map of possible targets.
+    /// Processes the next node and checks if at least one of reached
+    /// nodes has \c true value in the \c nm node map. If one node
+    /// with \c true value is reachable from the processed node, then the
+    /// \c rnode parameter will be set to the first of such nodes.
+    ///
+    /// \param nm A \c bool (or convertible) node map that indicates the
+    /// possible targets.
     /// \retval rnode The reached target node.
+    /// It should be initially \c INVALID.
+    ///
     /// \return The processed node.
     ///
     /// \warning The queue must not be empty!
+    /// \pre The queue must not be empty.
     template <typename NM>
     Node processNextNode(const NM& nm, Node& rnode) {
 …
+    }
+    /// \brief Next node to be processed.
+    ///
+    /// Next node to be processed.
+    ///
+    /// \return The next node to be processed or INVALID if the stack is
+    /// empty.
+    Node nextNode() {
+    /// \brief The next node to be processed.
+    ///
+    /// Returns the next node to be processed or \c INVALID if the queue
+    /// is empty.
+    Node nextNode() const {
       return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
+    }
     /// \brief Returns \c false if there are nodes
     /// to be processed in the queue
+    /// to be processed.
     ///
     /// Returns \c false if there are nodes
     /// to be processed in the queue
     bool emptyQueue() { return _list_front == _list_back; }
+    /// to be processed in the queue.
+    bool emptyQueue() const { return _list_front == _list_back; }
     /// \brief Returns the number of the nodes to be processed.
     ///
     /// Returns the number of the nodes to be processed in the queue.
     int queueSize() { return _list_back - _list_front; }
+    int queueSize() const { return _list_back - _list_front; }
     /// \brief Executes the algorithm.
 …
     /// Executes the algorithm.
     ///
+    /// \pre init() must be called and at least one node should be added
+    /// 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 (forest),
+    /// - the distance of each node from the root(s).
+    ///
+    /// \pre init() must be called and at least one root node should be added
     /// with addSource() before using this function.
+    ///
+    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
+    /// \code
+    ///   while ( !b.emptyQueue() ) {
+    ///     b.processNextNode();
+    ///   }
+    /// \endcode
     void start() {
       while ( !emptyQueue() ) processNextNode();
+    }
+    /// \brief Executes the algorithm until \c dest is reached.
+    ///
+    /// Executes the algorithm until \c dest is reached.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    /// \brief Executes the algorithm until the given target node is reached.
+    ///
+    /// Executes the algorithm until the given target node is reached.
+    ///
+    /// 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).
+    ///
+    /// \pre init() must be called and at least one root node should be
+    /// added with addSource() before using this function.
+    ///
+    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
+    /// \code
+    ///   bool reach = false;
+    ///   while ( !b.emptyQueue() && !reach ) {
+    ///     b.processNextNode(t, reach);
+    ///   }
+    /// \endcode
     void start(Node dest) {
       bool reach = false;
 …
     /// 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
+    /// This method runs the %BFS algorithm from the root node(s) in
+    /// order to compute the shortest path to a node \c v with
+    /// <tt>nm[v]</tt> true, if such a node can be found.
+    ///
+    /// \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]</tt> true.
     ///
+    ///\return The reached node \c v with <tt>nm[v]</tt> true or
+    ///\c INVALID if no such node was found.
+    /// \return The reached node \c v with <tt>nm[v]</tt> true or
+    /// \c INVALID if no such node was found.
+    ///
+    /// \pre init() must be called and at least one root node should be
+    /// added with addSource() before using this function.
+    ///
+    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
+    /// \code
+    ///   Node rnode = INVALID;
+    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
+    ///     b.processNextNode(nm, rnode);
+    ///   }
+    ///   return rnode;
+    /// \endcode
     template <typename NM>
     Node start(const NM &nm) {
 …
+    }
+    /// \brief Runs %BFSVisit algorithm from node \c s.
+    ///
+    /// This method runs the %BFS algorithm from a root node \c s.
+    /// \note b.run(s) is just a shortcut of the following code.
+    /// \brief Runs the algorithm from the given node.
+    ///
+    /// This method runs the %BFS algorithm from 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 <tt>b.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///   b.init();
 …
+    }
     /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
+    /// \brief Runs the algorithm to visit all nodes in the digraph.
     ///
     /// This method runs the %BFS algorithm in order to
+    /// compute the %BFS path to each node. The algorithm computes
+    /// - The %BFS tree.
+    /// - The distance of each node from the root in the %BFS tree.
+    ///
+    ///\note b.run() is just a shortcut of the following code.
+    /// compute the shortest path to each node.
+    ///
+    /// The algorithm computes
+    /// - the shortest path tree (forest),
+    /// - the distance of each node from the root(s).
+    ///
+    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///  b.init();
     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
     ///    if (!b.reached(it)) {
     ///      b.addSource(it);
+    ///  for (NodeIt n(gr); n != INVALID; ++n) {
+    ///    if (!b.reached(n)) {
+    ///      b.addSource(n);
     ///      b.start();
     ///    }
 …
+      }
+    }
     ///@}
 …
     /// 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.
+    /// Either \ref lemon::BfsVisit::run() "run()" or
+    /// \ref lemon::BfsVisit::start() "start()" must be called before
+    /// using them.
     ///@{
     /// \brief Checks if a node is reachable from the root.
+    /// \brief Checks if a node is reachable from the root(s).
     ///
     /// Returns \c true if \c v is reachable from the root(s).
-    /// \warning The source nodes are inditated as unreachable.
     /// \pre Either \ref run() or \ref start()
     /// must be called before using this function.
-    ///
     bool reached(Node v) { return (*_reached)[v]; }
     ///@}
   };
 …
 #endif

lemon/dfs.h

-                      r210
+                      r244
 ///\ingroup search
 ///\file
 ///\brief Dfs algorithm.
+///\brief DFS algorithm.
 #include <lemon/list_graph.h>
 …
 #include <lemon/bits/invalid.h>
 #include <lemon/error.h>
+#include <lemon/assert.h>
 #include <lemon/maps.h>
-#include <lemon/concept_check.h>
 namespace lemon {
   ///Default traits class of Dfs class.
 …
   struct DfsDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
+    ///\brief The type of the map that stores the last
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
+    ///Instantiates a PredMap.
+    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
     ///This function instantiates a \ref PredMap.
+    ///\param G is the digraph, to which we would like to define the PredMap.
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
     static PredMap *createPredMap(const GR &G)
+    {
       return new PredMap(G);
+    static PredMap *createPredMap(const Digraph &g)
+    {
+      return new PredMap(g);
+    }
 …
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///\todo named parameter to set this type, function to read and write.
+    ///By default it is a NullMap.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
     ///This function instantiates a \ref ProcessedMap.
 …
     ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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 concepts::ReadWriteMap "ReadWriteMap" concept.
+    typedef typename Digraph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a \ref ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
+    ///\param g is the digraph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const Digraph &g)
+    {
+      return new ReachedMap(g);
+    }
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
-    typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-    ///This function instantiates a \ref ReachedMap.
-    ///\param G is the digraph, 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 concepts::WriteMap "WriteMap" concept.
-    ///
     typedef typename Digraph::template NodeMap<int> DistMap;
     ///Instantiates a DistMap.
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
     ///\param G is the digraph, to which we would like to define
     ///the \ref DistMap
     static DistMap *createDistMap(const GR &G)
+    {
       return new DistMap(G);
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref DistMap.
+    static DistMap *createDistMap(const Digraph &g)
+    {
+      return new DistMap(g);
+    }
   };
 …
   ///This class provides an efficient implementation of the %DFS algorithm.
   ///
+  ///\tparam GR The digraph type the algorithm runs on. The default value is
+  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
+  ///is only passed to \ref DfsDefaultTraits.
+  ///There is also a \ref dfs() "function type interface" for the DFS
+  ///algorithm, which is convenient in the simplier cases and it can be
+  ///used easier.
+  ///
+  ///\tparam GR The type of the digraph the algorithm runs on.
+  ///The default value is \ref ListDigraph. The value of GR is not used
+  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
   ///\tparam TR Traits class to set various data types used by the algorithm.
   ///The default traits class is
 …
   class Dfs {
   public:
+    /**
+     * \brief \ref Exception for uninitialized parameters.
+     *
+     * This error represents problems in the initialization
+     * of the parameters of the algorithms.
+     */
+    ///\ref Exception for uninitialized parameters.
+    ///This error represents problems in the initialization of the
+    ///parameters of the algorithm.
     class UninitializedParameter : public lemon::UninitializedParameter {
     public:
 …
     };
+    ///The type of the digraph the algorithm runs on.
+    typedef typename TR::Digraph Digraph;
+    ///\brief The type of the map that stores the predecessor arcs of the
+    ///DFS paths.
+    typedef typename TR::PredMap PredMap;
+    ///The type of the map that stores the distances of the nodes.
+    typedef typename TR::DistMap DistMap;
+    ///The type of the map that indicates which nodes are reached.
+    typedef typename TR::ReachedMap ReachedMap;
+    ///The type of the map that indicates which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
+    ///The type of the paths.
+    typedef PredMapPath<Digraph, PredMap> Path;
+    ///The traits class.
     typedef TR Traits;
+    ///The type of the underlying digraph.
     typedef typename TR::Digraph Digraph;
+    ///\e
+  private:
     typedef typename Digraph::Node Node;
-    ///\e
     typedef typename Digraph::NodeIt NodeIt;
-    ///\e
     typedef typename Digraph::Arc Arc;
-    ///\e
     typedef typename Digraph::OutArcIt OutArcIt;
+    ///\brief The type of the map that stores the last
+    ///arcs of the %DFS paths.
+    typedef typename TR::PredMap PredMap;
+    ///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 digraph.
+    //Pointer to the underlying digraph.
     const Digraph *G;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessor arcs.
     PredMap *_pred;
     ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    //Indicates if _pred is locally allocated (true) or not.
     bool local_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     DistMap *_dist;
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    //Indicates if _dist is locally allocated (true) or not.
     bool local_dist;
     ///Pointer to the map of reached status of the nodes.
+    //Pointer to the map of reached status of the nodes.
     ReachedMap *_reached;
     ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    //Indicates if _reached is locally allocated (true) or not.
     bool local_reached;
     ///Pointer to the map of processed status of the nodes.
+    //Pointer to the map of processed status of the nodes.
     ProcessedMap *_processed;
     ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    //Indicates if _processed is locally allocated (true) or not.
     bool local_processed;
 …
     ///Creates the maps if necessary.
     ///\todo Better memory allocation (instead of new).
     void create_maps()
 …
     struct DefPredMapTraits : public Traits {
       typedef T PredMap;
       static PredMap *createPredMap(const Digraph &G)
+      static PredMap *createPredMap(const Digraph &)
+      {
         throw UninitializedParameter();
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///PredMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting PredMap type
     ///
+    ///\ref PredMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref PredMap type.
     template <class T>
     struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
       typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
     };
     template <class T>
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///DistMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting DistMap
     ///type
+    ///\ref DistMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref DistMap type.
     template <class T>
     struct DefDistMap {
+    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
       typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
     };
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ReachedMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     ///
+    ///\ref ReachedMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ReachedMap type.
     template <class T>
     struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
 …
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type
     ///
     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
     ///
+    ///\ref ProcessedMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type.
     template <class T>
     struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
 …
     struct DefDigraphProcessedMapTraits : public Traits {
       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &G)
+      static ProcessedMap *createProcessedMap(const Digraph &g)
+      {
         return new ProcessedMap(G);
+      }
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     ///
     ///\ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     ///If you don't set it explicitely, it will be automatically allocated.
+        return new ProcessedMap(g);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///If you don't set it explicitly, it will be automatically allocated.
     template <class T>
     class DefProcessedMapToBeDefaultMap :
+    struct DefProcessedMapToBeDefaultMap :
       public Dfs< Digraph, DefDigraphProcessedMapTraits> {
       typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
 …
     ///Constructor.
     ///\param _G the digraph the algorithm will run on.
     ///
     Dfs(const Digraph& _G) :
       G(&_G),
+    ///Constructor.
+    ///\param g The digraph the algorithm runs on.
+    Dfs(const Digraph &g) :
+      G(&g),
       _pred(NULL), local_pred(false),
       _dist(NULL), local_dist(false),
 …
+    }
     ///Sets the map storing the predecessor arcs.
     ///Sets the map storing the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destuctor deallocates this
+    ///it will allocate one. The destructor deallocates this
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
 …
+    }
     ///Sets the map storing the distances calculated by the algorithm.
     ///Sets the map storing the distances calculated by the algorithm.
+    ///Sets the map that indicates which nodes are reached.
+    ///Sets the map that indicates which nodes are reached.
     ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dfs &reachedMap(ReachedMap &m)
+    {
+      if(local_reached) {
+        delete _reached;
+        local_reached=false;
+      }
+      _reached = &m;
+      return *this;
+    }
+    ///Sets the map that indicates which nodes are processed.
+    ///Sets the map that indicates which nodes are processed.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dfs &processedMap(ProcessedMap &m)
+    {
+      if(local_processed) {
+        delete _processed;
+        local_processed=false;
+      }
+      _processed = &m;
+      return *this;
+    }
+    ///Sets the map that stores the distances of the nodes.
+    ///Sets the map that stores the distances of the nodes calculated by
+    ///the algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
 …
+    }
-    ///Sets the map indicating if a node is reached.
-    ///Sets the map indicating if a node is reached.
-    ///If you don't use this function before calling \ref run(),
-    ///it will allocate one. The destuctor deallocates this
-    ///automatically allocated map, of course.
-    ///\return <tt> (*this) </tt>
-    Dfs &reachedMap(ReachedMap &m)
+    {
-      if(local_reached) {
-        delete _reached;
-        local_reached=false;
+      }
-      _reached = &m;
-      return *this;
+    }
-    ///Sets the map indicating if a node is processed.
-    ///Sets the map indicating if a node is processed.
-    ///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 &processedMap(ProcessedMap &m)
+    {
-      if(local_processed) {
-        delete _processed;
-        local_processed=false;
+      }
-      _processed = &m;
-      return *this;
+    }
   public:
     ///\name Execution control
     ///The simplest way to execute the algorithm is to use
     ///one of the member functions called \c run(...).
+    ///one of the member functions called \ref lemon::Dfs::run() "run()".
     ///\n
     ///If you need more control on the execution,
     ///first you must call \ref init(), then you can add a source node
     ///with \ref addSource().
     ///Finally \ref start() will perform the actual path
     ///computation.
+    ///If you need more control on the execution, first you must call
+    ///\ref lemon::Dfs::init() "init()", then you can add a source node
+    ///with \ref lemon::Dfs::addSource() "addSource()".
+    ///Finally \ref lemon::Dfs::start() "start()" will perform the
+    ///actual path computation.
     ///@{
 …
       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 to the set of nodes to be processed.
     ///
+    ///\warning dists are wrong (or at least strange)
+    ///in case of multiple sources.
+    ///\pre The stack must be empty. (Otherwise the algorithm gives
+    ///false results.)
+    ///
+    ///\warning Distances will be wrong (or at least strange) in case of
+    ///multiple sources.
     void addSource(Node s)
+    {
+      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
       if(!(*_reached)[s])
+        {
 …
     ///\return The processed arc.
     ///
     ///\pre The stack must not be empty!
+    ///\pre The stack must not be empty.
     Arc processNextArc()
+    {
 …
       return e;
+    }
     ///Next arc to be processed.
     ///Next arc to be processed.
     ///
     ///\return The next arc to be processed or INVALID if the stack is
     /// empty.
     OutArcIt nextArc()
+    ///\return The next arc to be processed or \c INVALID if the stack
+    ///is empty.
+    OutArcIt nextArc() const
+    {
       return _stack_head>=0?_stack[_stack_head]:INVALID;
 …
     ///\brief Returns \c false if there are nodes
     ///to be processed in the queue
+    ///to be processed.
     ///
     ///Returns \c false if there are nodes
+    ///to be processed in the queue
+    bool emptyQueue() { return _stack_head<0; }
+    ///to be processed in the queue (stack).
+    bool emptyQueue() const { 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; }
+    ///Returns the number of the nodes to be processed in the queue (stack).
+    int queueSize() const { 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) in the %DFS tree.
+    ///
+    ///This method runs the %DFS algorithm from the root node
+    ///in order to compute the DFS path to each node.
+    ///
+    /// The algorithm computes
+    ///- the %DFS tree,
+    ///- the distance of each node from the root in the %DFS tree.
+    ///
+    ///\pre init() must be called and a root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
+    ///\code
+    ///  while ( !d.emptyQueue() ) {
+    ///    d.processNextArc();
+    ///  }
+    ///\endcode
     void start()
+    {
 …
+    }
+    ///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) in the %DFS tree.
+    ///
+    ///Executes the algorithm until the given target node is reached.
+    ///Executes the algorithm until the given target node is reached.
+    ///
+    ///This method runs the %DFS algorithm from the root node
+    ///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 in the %DFS tree.
+    ///
+    ///\pre init() must be called and a root node should be
+    ///added with addSource() before using this function.
     void start(Node dest)
+    {
 …
     ///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 em must be a bool (or convertible) arc map. The algorithm
     ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
     ///
     ///\return The reached arc \c e with <tt>em[e]</tt> true or
+    ///This method runs the %DFS algorithm from the root node
+    ///until an arc \c a with <tt>am[a]</tt> true is found.
+    ///
+    ///\param am A \c bool (or convertible) arc map. The algorithm
+    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
+    ///
+    ///\return The reached arc \c a with <tt>am[a]</tt> true or
     ///\c INVALID if no such arc was found.
     ///
+    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
+    ///\pre init() must be called and a root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
     ///not a node map.
     template<class EM>
     Arc start(const EM &em)
+    {
       while ( !emptyQueue() && !em[_stack[_stack_head]] )
+    template<class ArcBoolMap>
+    Arc start(const ArcBoolMap &am)
+    {
+      while ( !emptyQueue() && !am[_stack[_stack_head]] )
         processNextArc();
       return emptyQueue() ? INVALID : _stack[_stack_head];
+    }
+    ///Runs %DFS algorithm to visit all nodes in the digraph.
+    ///This method runs the %DFS algorithm in order to
+    ///compute the
+    ///%DFS path to each node. The algorithm computes
+    ///- The %DFS tree.
+    ///- The distance of each node from the root in the %DFS tree.
+    ///
+    ///\note d.run() is just a shortcut of the following code.
+    ///Runs the algorithm from the given node.
+    ///This method runs the %DFS algorithm from 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 in the %DFS tree.
+    ///
+    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///  d.init();
+    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
+    ///    if (!d.reached(it)) {
+    ///      d.addSource(it);
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+    ///Finds the %DFS path between \c s and \c t.
+    ///This method runs the %DFS algorithm from node \c s
+    ///in order to compute the DFS path to \c t.
+    ///
+    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
+    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///
+    ///\note Apart from the return value, <tt>d.run(s,t)</tt> 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)?_stack_head+1:0;
+    }
+    ///Runs the algorithm to visit all nodes in the digraph.
+    ///This method runs the %DFS algorithm in order to compute the
+    ///%DFS path to each node.
+    ///
+    ///The algorithm computes
+    ///- the %DFS tree,
+    ///- the distance of each node from the root in the %DFS tree.
+    ///
+    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
+    ///    if (!d.reached(n)) {
+    ///      d.addSource(n);
     ///      d.start();
     ///    }
 …
+    }
-    ///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 in the %DFS tree.
-    ///
-    ///\note d.run(s) is just a shortcut of the following code.
-    ///\code
-    ///  d.init();
-    ///  d.addSource(s);
-    ///  d.start();
-    ///\endcode
-    void run(Node s) {
-      init();
-      addSource(s);
-      start();
+    }
-    ///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,t) 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)?_stack_head+1:0;
+    }
     ///@}
 …
     ///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.
+    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
+    ///"start()" must be called before using them.
     ///@{
+    typedef PredMapPath<Digraph, PredMap> Path;
+    ///Gives back the shortest path.
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t)
+    {
+      return Path(*G, *_pred, t);
+    }
+    ///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 is unreachable from the root(s) then the return
+    ///value of this funcion is undefined.
+    ///The DFS path to a node.
+    ///Returns the DFS path to a node.
+    ///
+    ///\warning \c t should be reachable from the root.
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
+    Path path(Node t) const { return Path(*G, *_pred, t); }
+    ///The distance of a node from the root.
+    ///Returns the distance of a node from the root.
+    ///
+    ///\warning If node \c v is not reachable from the root, then
+    ///the return value of this function is undefined.
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     int dist(Node v) const { return (*_dist)[v]; }
     ///Returns the 'previous arc' of the %DFS tree.
     ///For a node \c v it returns the 'previous arc'
     ///of the %DFS path,
     ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
     ///v. It is \ref INVALID
     ///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
+    ///Returns the 'previous arc' of the %DFS tree for a node.
+    ///This function returns the 'previous arc' of the %DFS tree for the
+    ///node \c v, i.e. it returns the last arc of a %DFS path from the
+    ///root to \c v. It is \c INVALID
+    ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///
+    ///The %DFS tree used here is equal to the %DFS tree used in
     ///\ref predNode().
+    ///
     ///\pre Either \ref run() or \ref start() must be called before using
     ///this function.
 …
     ///Returns the 'previous node' of the %DFS tree.
     ///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(s) 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 predArc().
+    ///This function returns the 'previous node' of the %DFS
+    ///tree for the node \c v, i.e. it returns the last but one node
+    ///from a %DFS path from the root to \c v. It is \c INVALID
+    ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///
+    ///The %DFS tree used here is equal to the %DFS tree used in
+    ///\ref predArc().
+    ///
     ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
 …
                                   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.
+    ///\brief Returns a const reference to the node map that stores the
+    ///distances of the nodes.
+    ///
+    ///Returns a const reference to the node map that stores the
+    ///distances of the nodes calculated by the algorithm.
+    ///
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
+    ///Returns a reference to the %DFS arc-tree map.
+    ///Returns a reference to the NodeMap of the arcs of the
+    ///%DFS tree.
+    ///\brief Returns a const reference to the node map that stores the
+    ///predecessor arcs.
+    ///
+    ///Returns a const reference to the node map that stores the predecessor
+    ///arcs, which form the DFS tree.
+    ///
     ///\pre Either \ref run() or \ref init()
     ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
     ///Checks if a node is reachable from the root.
+    ///Checks if a node is reachable from the root(s).
     ///Returns \c true if \c v is reachable from the root(s).
-    ///\warning The source nodes are inditated as unreachable.
     ///\pre Either \ref run() or \ref start()
     ///must be called before using this function.
+    ///
+    bool reached(Node v) { return (*_reached)[v]; }
+    bool reached(Node v) const { return (*_reached)[v]; }
     ///@}
   };
   ///Default traits class of Dfs function.
   ///Default traits class of Dfs function.
+  ///Default traits class of dfs() function.
+  ///Default traits class of dfs() function.
   ///\tparam GR Digraph type.
   template<class GR>
   struct DfsWizardDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
+    ///\brief The type of the map that stores the last
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the %DFS paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///
     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
     ///Instantiates a PredMap.
+    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
     ///This function instantiates a \ref PredMap.
+    ///\param g is the digraph, to which we would like to define the PredMap.
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
     ///\todo The digraph alone may be insufficient to initialize
 #ifdef DOXYGEN
     static PredMap *createPredMap(const GR &g)
+    static PredMap *createPredMap(const Digraph &g)
 #else
     static PredMap *createPredMap(const GR &)
+    static PredMap *createPredMap(const Digraph &)
 #endif
+    {
 …
     ///The type of the map that indicates which nodes are processed.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
     ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \ref ProcessedMap
+    ///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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 concepts::ReadWriteMap "ReadWriteMap" concept.
+    typedef typename Digraph::template NodeMap<bool> ReachedMap;
+    ///Instantiates a \ref ReachedMap.
+    ///This function instantiates a \ref ReachedMap.
+    ///\param g is the digraph, to which
+    ///we would like to define the \ref ReachedMap.
+    static ReachedMap *createReachedMap(const Digraph &g)
+    {
+      return new ReachedMap(g);
+    }
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///\todo named parameter to set this type, function to read and write.
-    typedef typename Digraph::template NodeMap<bool> ReachedMap;
-    ///Instantiates a ReachedMap.
-    ///This function instantiates a \ref ReachedMap.
-    ///\param G is the digraph, 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 concepts::WriteMap "WriteMap" concept.
     ///
     typedef NullMap<typename Digraph::Node,int> DistMap;
     ///Instantiates a DistMap.
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
 …
     ///the \ref DistMap
 #ifdef DOXYGEN
     static DistMap *createDistMap(const GR &g)
+    static DistMap *createDistMap(const Digraph &g)
 #else
     static DistMap *createDistMap(const GR &)
+    static DistMap *createDistMap(const Digraph &)
 #endif
+    {
 …
   };
   /// Default traits used by \ref DfsWizard
+  /// Default traits class used by \ref DfsWizard
   /// To make it easier to use Dfs algorithm
   ///we have created a wizard class.
+  /// we have created a wizard class.
   /// This \ref DfsWizard class needs default traits,
   ///as well as the \ref Dfs class.
+  /// as well as the \ref Dfs class.
   /// The \ref DfsWizardBase is a class to be the default traits of the
   /// \ref DfsWizard class.
 …
     typedef DfsWizardDefaultTraits<GR> Base;
   protected:
     /// Type of the nodes in the digraph.
+    //The type of the nodes in the digraph.
     typedef typename Base::Digraph::Node Node;
     /// Pointer to the underlying digraph.
+    //Pointer to the digraph the algorithm runs on.
     void *_g;
     ///Pointer to the map of reached nodes.
+    //Pointer to the map of reached nodes.
     void *_reached;
     ///Pointer to the map of processed nodes.
+    //Pointer to the map of processed nodes.
     void *_processed;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessors arcs.
     void *_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     void *_dist;
     ///Pointer to the source node.
+    //Pointer to the source node.
     Node _source;
 …
     /// all of the attributes to default values (0, INVALID).
     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
                            _dist(0), _source(INVALID) {}
+                      _dist(0), _source(INVALID) {}
     /// Constructor.
 …
     /// 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
+    /// \param g The digraph the algorithm runs on.
+    /// \param s The source node.
     DfsWizardBase(const GR &g, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 …
   };
+  /// A class to make the usage of the Dfs algorithm easier
+  /// This class is created to make it easier to use the Dfs algorithm.
+  /// It uses the functions and features of the plain \ref Dfs,
+  /// but it is much simpler to use it.
+  /// Auxiliary class for the function type interface of DFS algorithm.
+  /// This auxiliary class is created to implement the function type
+  /// interface of \ref Dfs algorithm. It uses the functions and features
+  /// of the plain \ref Dfs, but it is much simpler to use it.
+  /// It should only be used through the \ref dfs() function, which makes
+  /// it easier to use the algorithm.
   ///
   /// Simplicity means that the way to change the types defined
 …
   /// the original class by using the ::
   /// operator. In the case of \ref DfsWizard only
   /// a function have to be called and it will
+  /// 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 object, and calls the \ref Dfs::run
   /// method of it.
+  /// It does not have own \ref run() method. When its \ref run() method
+  /// is called, it initiates a plain \ref Dfs object, and calls the
+  /// \ref Dfs::run() method of it.
   template<class TR>
   class DfsWizard : public TR
 …
     typedef TR Base;
     ///The type of the underlying digraph.
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
+    //\e
     typedef typename Digraph::Node Node;
-    //\e
     typedef typename Digraph::NodeIt NodeIt;
-    //\e
     typedef typename Digraph::Arc Arc;
-    //\e
     typedef typename Digraph::OutArcIt OutArcIt;
+    ///\brief The type of the map that stores
+    ///the reached nodes
+    ///\brief The type of the map that stores the predecessor
+    ///arcs of the shortest paths.
+    typedef typename TR::PredMap PredMap;
+    ///\brief The type of the map that stores the distances of the nodes.
+    typedef typename TR::DistMap DistMap;
+    ///\brief The type of the map that indicates which nodes are reached.
     typedef typename TR::ReachedMap ReachedMap;
+    ///\brief The type of the map that stores
+    ///the processed nodes
+    ///\brief The type of the map that indicates which nodes are processed.
     typedef typename TR::ProcessedMap ProcessedMap;
-    ///\brief The type of the map that stores the last
-    ///arcs of the %DFS paths.
-    typedef typename TR::PredMap PredMap;
-    ///The type of the map that stores the distances of the nodes.
-    typedef typename TR::DistMap DistMap;
   public:
     /// Constructor.
     DfsWizard() : TR() {}
 …
     ~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.
+    ///Runs DFS algorithm from a source node.
+    ///Runs DFS algorithm from a source node.
+    ///The node can be given with the \ref source() function.
     void run()
+    {
 …
+    }
     ///Runs Dfs algorithm from the given node.
     ///Runs Dfs algorithm from the given node.
+    ///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();
+    }
+    /// 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;
+    }
 …
       DefPredMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    ///for setting \ref PredMap object.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting \ref PredMap object.
     template<class T>
     DfsWizard<DefPredMapBase<T> > predMap(const T &t)
 …
       return DfsWizard<DefPredMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefReachedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ReachedMap
+    ///for setting \ref ReachedMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting ReachedMap
+    ///
+    ///for setting \ref ReachedMap object.
     template<class T>
     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
 …
       return DfsWizard<DefReachedMapBase<T> >(*this);
+    }
     template<class T>
 …
       DefProcessedMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///function for setting ProcessedMap
+    ///for setting \ref ProcessedMap object.
     ///
     /// \ref named-templ-param "Named parameter"
+    ///function for setting ProcessedMap
+    ///
+    ///for setting \ref ProcessedMap object.
     template<class T>
     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
 …
       DefDistMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    ///for setting \ref DistMap object.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting \ref DistMap object.
     template<class T>
     DfsWizard<DefDistMapBase<T> > distMap(const T &t)
 …
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&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;
+    }
 …
 #ifdef DOXYGEN
   /// \brief Visitor class for dfs.
+  /// \brief Visitor class for DFS.
   ///
   /// It gives a simple interface for a functional interface for dfs
   /// traversal. The traversal on a linear data structure.
+  /// This class defines the interface of the DfsVisit events, and
+  /// it could be the base of a real visitor class.
   template <typename _Digraph>
   struct DfsVisitor {
 …
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
+    /// \brief Called when the arc reach a node.
+    ///
+    /// It is called when the dfs find an arc which target is not
+    /// reached yet.
+    /// \brief Called for the source node of the DFS.
+    ///
+    /// This function is called for the source node of the DFS.
+    void start(const Node& node) {}
+    /// \brief Called when the source node is leaved.
+    ///
+    /// This function is called when the source node is leaved.
+    void stop(const Node& node) {}
+    /// \brief Called when a node is reached first time.
+    ///
+    /// This function is called when a node is reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when an arc reaches a new node.
+    ///
+    /// This function is called when the DFS finds an arc whose target node
+    /// is not reached yet.
     void discover(const Arc& arc) {}
+    /// \brief Called when the node reached first time.
+    ///
+    /// It is Called when the node reached first time.
+    void reach(const Node& node) {}
+    /// \brief Called when we step back on an arc.
+    ///
+    /// It is called when the dfs should step back on the arc.
+    void backtrack(const Arc& arc) {}
+    /// \brief Called when we step back from the node.
+    ///
+    /// It is called when we step back from the node.
+    void leave(const Node& node) {}
+    /// \brief Called when the arc examined but target of the arc
+    /// \brief Called when an arc is examined but its target node is
     /// already discovered.
     ///
     /// It called when the arc examined but the target of the arc
+    /// This function is called when an arc is examined but its target node is
     /// already discovered.
     void examine(const Arc& arc) {}
+    /// \brief Called for the source node of the dfs.
+    ///
+    /// It is called for the source node of the dfs.
+    void start(const Node& node) {}
+    /// \brief Called when we leave the source node of the dfs.
+    ///
+    /// It is called when we leave the source node of the dfs.
+    void stop(const Node& node) {}
+    /// \brief Called when the DFS steps back from a node.
+    ///
+    /// This function is called when the DFS steps back from a node.
+    void leave(const Node& node) {}
+    /// \brief Called when the DFS steps back on an arc.
+    ///
+    /// This function is called when the DFS steps back on an arc.
+    void backtrack(const Arc& arc) {}
   };
 #else
 …
     typedef typename Digraph::Arc Arc;
     typedef typename Digraph::Node Node;
-    void discover(const Arc&) {}
-    void reach(const Node&) {}
-    void backtrack(const Arc&) {}
-    void leave(const Node&) {}
-    void examine(const Arc&) {}
     void start(const Node&) {}
     void stop(const Node&) {}
+    void reach(const Node&) {}
+    void discover(const Arc&) {}
+    void examine(const Arc&) {}
+    void leave(const Node&) {}
+    void backtrack(const Arc&) {}
     template <typename _Visitor>
 …
         Arc arc;
         Node node;
-        visitor.discover(arc);
-        visitor.reach(node);
-        visitor.backtrack(arc);
-        visitor.leave(node);
-        visitor.examine(arc);
         visitor.start(node);
         visitor.stop(arc);
+        visitor.reach(node);
+        visitor.discover(arc);
+        visitor.examine(arc);
+        visitor.leave(node);
+        visitor.backtrack(arc);
+      }
       _Visitor& visitor;
 …
   ///
   /// Default traits class of DfsVisit class.
   /// \tparam _Digraph Digraph type.
+  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   template<class _Digraph>
   struct DfsVisitDefaultTraits {
     /// \brief The digraph type the algorithm runs on.
+    /// \brief The type of the digraph the algorithm runs on.
     typedef _Digraph Digraph;
 …
     ///
     /// The type of the map that indicates which nodes are reached.
+    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    /// \todo named parameter to set this type, function to read and write.
+    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     typedef typename Digraph::template NodeMap<bool> ReachedMap;
     /// \brief Instantiates a ReachedMap.
+    /// \brief Instantiates a \ref ReachedMap.
     ///
     /// This function instantiates a \ref ReachedMap.
 …
   };
-  /// %DFS Visit algorithm class.
   /// \ingroup search
+  ///
+  /// \brief %DFS algorithm class with visitor interface.
+  ///
   /// This class provides an efficient implementation of the %DFS algorithm
   /// with visitor interface.
 …
   /// The %DfsVisit class provides an alternative interface to the Dfs
   /// class. It works with callback mechanism, the DfsVisit object calls
   /// on every dfs event the \c Visitor class member functions.
+  /// the member functions of the \c Visitor class on every DFS event.
   ///
   /// \tparam _Digraph The digraph type the algorithm runs on.
+  /// \tparam _Digraph The type of the digraph the algorithm runs on.
   /// The default value is
   /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
   /// is only passed to \ref DfsDefaultTraits.
   /// \tparam _Visitor The Visitor object for the algorithm. The
   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
   /// does not observe the Dfs events. If you want to observe the dfs
   /// events you should implement your own Visitor class.
+  /// \ref ListDigraph. The value of _Digraph is not used directly by
+  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
+  /// \tparam _Visitor The Visitor type that is used by the algorithm.
+  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
+  /// does not observe the DFS events. If you want to observe the DFS
+  /// events, you should implement your own visitor class.
   /// \tparam _Traits Traits class to set various data types used by the
   /// algorithm. The default traits class is
   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
   /// See \ref DfsVisitDefaultTraits for the documentation of
+  /// a Dfs visit traits class.
+  ///
+  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
+  /// a DFS visit traits class.
 #ifdef DOXYGEN
   template <typename _Digraph, typename _Visitor, typename _Traits>
 …
     ///
     /// This error represents problems in the initialization
     /// of the parameters of the algorithms.
+    /// of the parameters of the algorithm.
     class UninitializedParameter : public lemon::UninitializedParameter {
     public:
 …
     };
+    ///The traits class.
     typedef _Traits Traits;
+    ///The type of the digraph the algorithm runs on.
     typedef typename Traits::Digraph Digraph;
+    ///The visitor type used by the algorithm.
     typedef _Visitor Visitor;
     ///The type of the map indicating which nodes are reached.
+    ///The type of the map that indicates which nodes are reached.
     typedef typename Traits::ReachedMap ReachedMap;
 …
     typedef typename Digraph::OutArcIt OutArcIt;
     /// Pointer to the underlying digraph.
+    //Pointer to the underlying digraph.
     const Digraph *_digraph;
     /// Pointer to the visitor object.
+    //Pointer to the visitor object.
     Visitor *_visitor;
     ///Pointer to the map of reached status of the nodes.
+    //Pointer to the map of reached status of the nodes.
     ReachedMap *_reached;
     ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    //Indicates if _reached is locally allocated (true) or not.
     bool local_reached;
 …
     int _stack_head;
+    /// \brief Creates the maps if necessary.
+    ///
+    /// Creates the maps if necessary.
+    ///Creates the maps if necessary.
+    ///\todo Better memory allocation (instead of new).
     void create_maps() {
       if(!_reached) {
 …
     };
     /// \brief \ref named-templ-param "Named parameter" for setting
     /// ReachedMap type
     ///
     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
+    /// ReachedMap type.
+    ///
+    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
     template <class T>
     struct DefReachedMap : public DfsVisit< Digraph, Visitor,
 …
     /// Constructor.
     ///
+    /// \param digraph the digraph the algorithm will run on.
+    /// \param visitor The visitor of the algorithm.
+    ///
+    /// \param digraph The digraph the algorithm runs on.
+    /// \param visitor The visitor object of the algorithm.
     DfsVisit(const Digraph& digraph, Visitor& visitor)
       : _digraph(&digraph), _visitor(&visitor),
 …
     /// \brief Destructor.
-    ///
-    /// Destructor.
     ~DfsVisit() {
       if(local_reached) delete _reached;
+    }
     /// \brief Sets the map indicating if a node is reached.
     ///
     /// Sets the map indicating if a node is reached.
+    /// \brief Sets the map that indicates which nodes are reached.
+    ///
+    /// Sets the map that indicates which nodes are reached.
     /// If you don't use this function before calling \ref run(),
     /// it will allocate one. The destuctor deallocates this
+    /// it will allocate one. The destructor deallocates this
     /// automatically allocated map, of course.
     /// \return <tt> (*this) </tt>
 …
   public:
     /// \name Execution control
     /// The simplest way to execute the algorithm is to use
+    /// one of the member functions called \c run(...).
+    /// one of the member functions called \ref lemon::DfsVisit::run()
+    /// "run()".
     /// \n
     /// If you need more control on the execution,
     /// first you must call \ref init(), then you can adda source node
     /// with \ref addSource().
     /// Finally \ref start() will perform the actual path
     /// computation.
+    /// If you need more control on the execution, first you must call
+    /// \ref lemon::DfsVisit::init() "init()", then you can add several
+    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
+    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
+    /// actual path computation.
     /// @{
     /// \brief Initializes the internal data structures.
     ///
     /// Initializes the internal data structures.
-    ///
     void init() {
       create_maps();
 …
+    }
+    /// \brief Adds a new source node.
+    ///
+    /// Adds a new source node to the set of nodes to be processed.
+    void addSource(Node s) {
+    ///Adds a new source node.
+    ///Adds a new source node to the set of nodes to be processed.
+    ///
+    ///\pre The stack must be empty. (Otherwise the algorithm gives
+    ///false results.)
+    ///
+    ///\warning Distances will be wrong (or at least strange) in case of
+    ///multiple sources.
+    void addSource(Node s)
+    {
+      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
       if(!(*_reached)[s]) {
           _reached->set(s,true);
 …
     /// \return The processed arc.
     ///
     /// \pre The stack must not be empty!
+    /// \pre The stack must not be empty.
     Arc processNextArc() {
       Arc e = _stack[_stack_head];
 …
     /// \return The next arc to be processed or INVALID if the stack is
     /// empty.
     Arc nextArc() {
+    Arc nextArc() const {
       return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
+    }
     /// \brief Returns \c false if there are nodes
     /// to be processed in the queue
+    /// to be processed.
     ///
     /// Returns \c false if there are nodes
     /// to be processed in the queue
     bool emptyQueue() { return _stack_head < 0; }
+    /// to be processed in the queue (stack).
+    bool emptyQueue() const { return _stack_head < 0; }
     /// \brief Returns the number of the nodes to be processed.
     ///
     /// Returns the number of the nodes to be processed in the queue.
     int queueSize() { return _stack_head + 1; }
+    /// Returns the number of the nodes to be processed in the queue (stack).
+    int queueSize() const { return _stack_head + 1; }
     /// \brief Executes the algorithm.
 …
     /// Executes the algorithm.
     ///
+    /// \pre init() must be called and at least one node should be added
+    /// with addSource() before using this function.
+    /// This method runs the %DFS algorithm from the root node
+    /// in order to compute the %DFS path to each node.
+    ///
+    /// The algorithm computes
+    /// - the %DFS tree,
+    /// - the distance of each node from the root in the %DFS tree.
+    ///
+    /// \pre init() must be called and a root node should be
+    /// added with addSource() before using this function.
+    ///
+    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
+    /// \code
+    ///   while ( !d.emptyQueue() ) {
+    ///     d.processNextArc();
+    ///   }
+    /// \endcode
     void start() {
       while ( !emptyQueue() ) processNextArc();
+    }
+    /// \brief Executes the algorithm until \c dest is reached.
+    ///
+    /// Executes the algorithm until \c dest is reached.
+    ///
+    /// \pre init() must be called and at least one node should be added
+    /// \brief Executes the algorithm until the given target node is reached.
+    ///
+    /// Executes the algorithm until the given target node is reached.
+    ///
+    /// This method runs the %DFS algorithm from the root node
+    /// 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 in the %DFS tree.
+    ///
+    /// \pre init() must be called and a root node should be added
     /// with addSource() before using this function.
     void start(Node dest) {
 …
     /// Executes the algorithm until a condition is met.
     ///
+    /// \pre init() must be called and at least one node should be added
+    /// This method runs the %DFS algorithm from the root node
+    /// until an arc \c a with <tt>am[a]</tt> true is found.
+    ///
+    /// \param am A \c bool (or convertible) arc map. The algorithm
+    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
+    ///
+    /// \return The reached arc \c a with <tt>am[a]</tt> true or
+    /// \c INVALID if no such arc was found.
+    ///
+    /// \pre init() must be called and a root node should be added
     /// with addSource() before using this function.
     ///
+    /// \param em must be a bool (or convertible) arc map. The algorithm
+    /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
+    ///
+    ///\return The reached arc \c e with <tt>em[e]</tt> true or
+    ///\c INVALID if no such arc was found.
+    ///
+    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
+    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
     /// not a node map.
     template <typename EM>
     Arc start(const EM &em) {
       while ( !emptyQueue() && !em[_stack[_stack_head]] )
+    template <typename AM>
+    Arc start(const AM &am) {
+      while ( !emptyQueue() && !am[_stack[_stack_head]] )
         processNextArc();
       return emptyQueue() ? INVALID : _stack[_stack_head];
+    }
+    /// \brief Runs %DFSVisit algorithm from node \c s.
+    ///
+    /// This method runs the %DFS algorithm from a root node \c s.
+    /// \note d.run(s) is just a shortcut of the following code.
+    /// \brief Runs the algorithm from the given node.
+    ///
+    /// This method runs the %DFS algorithm from 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 in the %DFS tree.
+    ///
+    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///   d.init();
 …
+    }
+    /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
+    /// \brief Finds the %DFS path between \c s and \c t.
+    /// This method runs the %DFS algorithm from node \c s
+    /// in order to compute the DFS path to \c t.
+    ///
+    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
+    /// if \c t is reachable form \c s, \c 0 otherwise.
+    ///
+    /// \note Apart from the return value, <tt>d.run(s,t)</tt> 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)?_stack_head+1:0;
+    }
+    /// \brief Runs the algorithm to visit all nodes in the digraph.
     /// This method runs the %DFS algorithm in order to
+    /// compute the %DFS path to each node. The algorithm computes
+    /// - The %DFS tree.
+    /// - The distance of each node from the root in the %DFS tree.
+    ///
+    ///\note d.run() is just a shortcut of the following code.
+    /// compute the %DFS path to each node.
+    ///
+    /// The algorithm computes
+    /// - the %DFS tree,
+    /// - the distance of each node from the root in the %DFS tree.
+    ///
+    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
     ///\code
     ///  d.init();
     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
     ///    if (!d.reached(it)) {
     ///      d.addSource(it);
     ///      d.start();
     ///    }
     ///  }
+    ///   d.init();
+    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
+    ///     if (!d.reached(n)) {
+    ///       d.addSource(n);
+    ///       d.start();
+    ///     }
+    ///   }
     ///\endcode
     void run() {
 …
+      }
+    }
     ///@}
 …
     /// 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.
+    /// Either \ref lemon::DfsVisit::run() "run()" or
+    /// \ref lemon::DfsVisit::start() "start()" must be called before
+    /// using them.
     ///@{
+    /// \brief Checks if a node is reachable from the root.
+    /// \brief Checks if a node is reachable from the root(s).
     ///
     /// Returns \c true if \c v is reachable from the root(s).
-    /// \warning The source nodes are inditated as unreachable.
     /// \pre Either \ref run() or \ref start()
     /// must be called before using this function.
-    ///
     bool reached(Node v) { return (*_reached)[v]; }
     ///@}
   };
 } //END OF NAMESPACE LEMON
 #endif

lemon/dijkstra.h

-                      r210
+                      r244
 namespace lemon {
   /// \brief Default OperationTraits for the Dijkstra algorithm class.
+  /// \brief Default operation traits for the Dijkstra algorithm class.
   ///
   /// It defines all computational operations and constants which are
   /// used in the Dijkstra algorithm.
+  /// This operation traits class defines all computational operations and
+  /// constants which are used in the Dijkstra algorithm.
   template <typename Value>
   struct DijkstraDefaultOperationTraits {
 …
       return left + right;
+    }
     /// \brief Gives back true only if the first value less than the second.
+    /// \brief Gives back true only if the first value is less than the second.
     static bool less(const Value& left, const Value& right) {
       return left < right;
 …
   };
   /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
+  /// \brief Widest path operation traits for the Dijkstra algorithm class.
   ///
+  /// It defines all computational operations and constants which are
+  /// used in the Dijkstra algorithm for widest path computation.
+  /// This operation traits class defines all computational operations and
+  /// constants which are used in the Dijkstra algorithm for widest path
+  /// computation.
+  ///
+  /// \see DijkstraDefaultOperationTraits
   template <typename Value>
   struct DijkstraWidestPathOperationTraits {
 …
       return std::min(left, right);
+    }
     /// \brief Gives back true only if the first value less than the second.
+    /// \brief Gives back true only if the first value is less than the second.
     static bool less(const Value& left, const Value& right) {
       return left < right;
 …
   ///Default traits class of Dijkstra class.
   ///\tparam GR Digraph type.
   ///\tparam LM Type of length map.
+  ///\tparam GR The type of the digraph.
+  ///\tparam LM The type of the length map.
   template<class GR, class LM>
   struct DijkstraDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
     ///The type of the map that stores the arc lengths.
 …
     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     typedef LM LengthMap;
     //The type of the length of the arcs.
+    ///The type of the length of the arcs.
     typedef typename LM::Value Value;
     /// Operation traits for Dijkstra algorithm.
     /// It defines the used operation by the algorithm.
+    /// This class defines the operations that are used in the algorithm.
     /// \see DijkstraDefaultOperationTraits
     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
+    /// The cross reference type used by heap.
     /// The cross reference type used by heap.
+    /// The cross reference type used by the heap.
+    /// The cross reference type used by the heap.
     /// Usually it is \c Digraph::NodeMap<int>.
     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
     ///Instantiates a HeapCrossRef.
     ///This function instantiates a \c HeapCrossRef.
     /// \param G is the digraph, to which we would like to define the
     /// HeapCrossRef.
     static HeapCrossRef *createHeapCrossRef(const GR &G)
+    {
       return new HeapCrossRef(G);
+    }
     ///The heap type used by Dijkstra algorithm.
     ///The heap type used by Dijkstra algorithm.
+    ///Instantiates a \ref HeapCrossRef.
+    ///This function instantiates a \ref HeapCrossRef.
+    /// \param g is the digraph, to which we would like to define the
+    /// \ref HeapCrossRef.
+    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
+    {
+      return new HeapCrossRef(g);
+    }
+    ///The heap type used by the Dijkstra algorithm.
+    ///The heap type used by the Dijkstra algorithm.
     ///
     ///\sa BinHeap
     ///\sa Dijkstra
     typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
+    static Heap *createHeap(HeapCrossRef& R)
+    {
+      return new Heap(R);
+    }
+    ///\brief The type of the map that stores the last
+    ///Instantiates a \ref Heap.
+    ///This function instantiates a \ref Heap.
+    static Heap *createHeap(HeapCrossRef& r)
+    {
+      return new Heap(r);
+    }
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///
     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
+    ///Instantiates a PredMap.
     ///This function instantiates a \c PredMap.
     ///\param G is the digraph, to which we would like to define the PredMap.
+    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
+    ///This function instantiates a \ref PredMap.
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
     ///\todo The digraph alone may be insufficient for the initialization
     static PredMap *createPredMap(const GR &G)
+    {
       return new PredMap(G);
+    }
     ///The type of the map that stores whether a nodes is processed.
     ///The type of the map that stores whether a nodes is processed.
+    static PredMap *createPredMap(const Digraph &g)
+    {
+      return new PredMap(g);
+    }
+    ///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 concepts::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 Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
     ///This function instantiates a \c ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
+    ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \c ProcessedMap
+    ///we would like to define the \ref ProcessedMap
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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.
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
-    ///
     typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
     ///Instantiates a DistMap.
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
     ///\param G is the digraph, to which we would like to define
+    ///\param g is the digraph, to which we would like to define
     ///the \ref DistMap
     static DistMap *createDistMap(const GR &G)
+    {
       return new DistMap(G);
+    static DistMap *createDistMap(const Digraph &g)
+    {
+      return new DistMap(g);
+    }
   };
 …
   /// \ingroup shortest_path
+  ///This class provides an efficient implementation of %Dijkstra algorithm.
+  ///This class provides an efficient implementation of the %Dijkstra algorithm.
+  ///
   ///The arc lengths are passed to the algorithm using a
   ///\ref concepts::ReadMap "ReadMap",
   ///so it is easy to change it to any kind of length.
-  ///
   ///The type of the length is determined by the
   ///\ref concepts::ReadMap::Value "Value" of the length map.
-  ///
   ///It is also possible to change the underlying priority heap.
   ///
+  ///\tparam GR The digraph type the algorithm runs on. The default value
+  ///is \ref ListDigraph. The value of GR is not used directly by
+  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
+  ///\tparam LM This read-only ArcMap determines the lengths of the
+  ///There is also a \ref dijkstra() "function type interface" for the
+  ///%Dijkstra algorithm, which is convenient in the simplier cases and
+  ///it can be used easier.
+  ///
+  ///\tparam GR The type of the digraph the algorithm runs on.
+  ///The default value is \ref ListDigraph.
+  ///The value of GR is not used directly by \ref Dijkstra, it is only
+  ///passed to \ref DijkstraDefaultTraits.
+  ///\tparam LM A readable arc map that determines the lengths of the
   ///arcs. It is read once for each arc, so the map may involve in
   ///relatively time consuming process to compute the arc length if
+  ///relatively time consuming process to compute the arc lengths if
   ///it is necessary. The default map type is \ref
+  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
+  ///of LM is not used directly by Dijkstra, it is only passed to \ref
+  ///DijkstraDefaultTraits.
+  ///\tparam 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.
+  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
+  ///The value of LM is not used directly by \ref Dijkstra, it is only
+  ///passed to \ref DijkstraDefaultTraits.
+  ///\tparam 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.
 #ifdef DOXYGEN
   template <typename GR, typename LM, typename TR>
 …
   class Dijkstra {
   public:
+    /**
+     * \brief \ref Exception for uninitialized parameters.
+     *
+     * This error represents problems in the initialization
+     * of the parameters of the algorithms.
+     */
+    ///\ref Exception for uninitialized parameters.
+    ///This error represents problems in the initialization of the
+    ///parameters of the algorithm.
     class UninitializedParameter : public lemon::UninitializedParameter {
     public:
 …
     };
+    typedef TR Traits;
+    ///The type of the underlying digraph.
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
-    ///\e
-    typedef typename Digraph::Node Node;
-    ///\e
-    typedef typename Digraph::NodeIt NodeIt;
-    ///\e
-    typedef typename Digraph::Arc Arc;
-    ///\e
-    typedef typename Digraph::OutArcIt OutArcIt;
     ///The type of the length of the arcs.
 …
     ///The type of the map that stores the arc lengths.
     typedef typename TR::LengthMap LengthMap;
     ///\brief The type of the map that stores the last
     ///arcs of the shortest paths.
+    ///\brief The type of the map that stores the predecessor arcs of the
+    ///shortest paths.
     typedef typename TR::PredMap PredMap;
+    ///The type of the map indicating if a node is processed.
+    ///The type of the map that stores the distances of the nodes.
+    typedef typename TR::DistMap DistMap;
+    ///The type of the map that indicates 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;
+    ///The type of the paths.
+    typedef PredMapPath<Digraph, PredMap> Path;
     ///The cross reference type used for the current heap.
     typedef typename TR::HeapCrossRef HeapCrossRef;
     ///The heap type used by the dijkstra algorithm.
+    ///The heap type used by the algorithm.
     typedef typename TR::Heap Heap;
     ///The operation traits.
+    ///The operation traits class.
     typedef typename TR::OperationTraits OperationTraits;
+    ///The traits class.
+    typedef TR Traits;
   private:
+    /// Pointer to the underlying digraph.
+    typedef typename Digraph::Node Node;
+    typedef typename Digraph::NodeIt NodeIt;
+    typedef typename Digraph::Arc Arc;
+    typedef typename Digraph::OutArcIt OutArcIt;
+    //Pointer to the underlying digraph.
     const Digraph *G;
     /// Pointer to the length map
+    //Pointer to the length map.
     const LengthMap *length;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessors arcs.
     PredMap *_pred;
     ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    //Indicates if _pred is locally allocated (true) or not.
     bool local_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     DistMap *_dist;
     ///Indicates if \ref _dist is locally allocated (\c true) or not.
+    //Indicates if _dist is locally allocated (true) or not.
     bool local_dist;
     ///Pointer to the map of processed status of the nodes.
+    //Pointer to the map of processed status of the nodes.
     ProcessedMap *_processed;
     ///Indicates if \ref _processed is locally allocated (\c true) or not.
+    //Indicates if _processed is locally allocated (true) or not.
     bool local_processed;
     ///Pointer to the heap cross references.
+    //Pointer to the heap cross references.
     HeapCrossRef *_heap_cross_ref;
     ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
+    //Indicates if _heap_cross_ref is locally allocated (true) or not.
     bool local_heap_cross_ref;
     ///Pointer to the heap.
+    //Pointer to the heap.
     Heap *_heap;
     ///Indicates if \ref _heap is locally allocated (\c true) or not.
+    //Indicates if _heap is locally allocated (true) or not.
     bool local_heap;
     ///Creates the maps if necessary.
     ///\todo Better memory allocation (instead of new).
     void create_maps()
 …
+    }
   public :
+  public:
     typedef Dijkstra Create;
 …
+      }
     };
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///\ref named-templ-param "Named parameter" for setting PredMap type
+    ///
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref PredMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref PredMap type.
     template <class T>
     struct DefPredMap
 …
+      }
     };
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+    ///\ref named-templ-param "Named parameter" for setting DistMap type
+    ///
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref DistMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref DistMap type.
     template <class T>
     struct DefDistMap
 …
     struct DefProcessedMapTraits : public Traits {
       typedef T ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &G)
+      static ProcessedMap *createProcessedMap(const Digraph &)
+      {
         throw UninitializedParameter();
+      }
     };
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
+    ///
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type.
     template <class T>
     struct DefProcessedMap
 …
     struct DefDigraphProcessedMapTraits : public Traits {
       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       static ProcessedMap *createProcessedMap(const Digraph &G)
+      static ProcessedMap *createProcessedMap(const Digraph &g)
+      {
         return new ProcessedMap(G);
+      }
     };
     ///\brief \ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     ///
     ///\ref named-templ-param "Named parameter"
     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
     ///If you don't set it explicitely, it will be automatically allocated.
+        return new ProcessedMap(g);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
+    ///If you don't set it explicitly, it will be automatically allocated.
     template <class T>
     struct DefProcessedMapToBeDefaultMap
 …
     ///
     ///\ref named-templ-param "Named parameter" for setting heap and cross
+    ///reference type
+    ///
+    ///reference type.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct DefHeap
 …
     /// \brief \ref named-templ-param "Named parameter" for setting
     /// OperationTraits type
     ///
     /// \ref named-templ-param "Named parameter" for setting OperationTraits
     /// type
+    ///\ref OperationTraits type
+    ///
+    ///\ref named-templ-param "Named parameter" for setting
+    ///\ref OperationTraits type.
     template <class T>
     struct DefOperationTraits
 …
     ///@}
   protected:
 …
     ///Constructor.
+    ///\param _G the digraph the algorithm will run on.
+    ///\param _length the length map used by the algorithm.
+    Dijkstra(const Digraph& _G, const LengthMap& _length) :
+      G(&_G), length(&_length),
+    ///Constructor.
+    ///\param _g The digraph the algorithm runs on.
+    ///\param _length The length map used by the algorithm.
+    Dijkstra(const Digraph& _g, const LengthMap& _length) :
+      G(&_g), length(&_length),
       _pred(NULL), local_pred(false),
       _dist(NULL), local_dist(false),
 …
+    }
     ///Sets the map storing the predecessor arcs.
     ///Sets the map storing the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
+    ///Sets the map that stores the predecessor arcs.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destuctor deallocates this
+    ///it will allocate one. The destructor deallocates this
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
 …
+    }
     ///Sets the map storing the distances calculated by the algorithm.
     ///Sets the map storing the distances calculated by the algorithm.
+    ///Sets the map that indicates which nodes are processed.
+    ///Sets the map that indicates which nodes are processed.
     ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &processedMap(ProcessedMap &m)
+    {
+      if(local_processed) {
+        delete _processed;
+        local_processed=false;
+      }
+      _processed = &m;
+      return *this;
+    }
+    ///Sets the map that stores the distances of the nodes.
+    ///Sets the map that stores the distances of the nodes calculated by the
+    ///algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
     ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
 …
     ///Sets the heap and the cross reference used by algorithm.
     ///If you don't use this function before calling \ref run(),
     ///it will allocate one. The destuctor deallocates this
+    ///it will allocate one. The destructor deallocates this
     ///automatically allocated heap and cross reference, of course.
     ///\return <tt> (*this) </tt>
 …
   private:
     void finalizeNodeData(Node v,Value dst)
+    {
 …
   public:
-    typedef PredMapPath<Digraph, PredMap> Path;
     ///\name Execution control
     ///The simplest way to execute the algorithm is to use
     ///one of the member functions called \c run(...).
+    ///The simplest way to execute the algorithm is to use one of the
+    ///member functions called \ref lemon::Dijkstra::run() "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.
+    ///If you need more control on the execution, first you must call
+    ///\ref lemon::Dijkstra::init() "init()", then you can add several
+    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
+    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
+    ///actual path computation.
     ///@{
 …
     ///Adds a new source node to the priority heap.
-    ///
     ///The optional second parameter is the initial distance of the node.
     ///
     ///It checks if the node has already been added to the heap and
+    ///The function checks if the node has already been added to the heap and
     ///it is pushed to the heap only if either it was not in the heap
     ///or the shortest path found till then is shorter than \c dst.
 …
     ///\return The processed node.
     ///
     ///\warning The priority heap must not be empty!
+    ///\warning The priority heap must not be empty.
     Node processNextNode()
+    {
 …
+    }
+    ///Next node to be processed.
+    ///Next node to be processed.
+    ///
+    ///\return The next node to be processed or INVALID if the priority heap
+    /// is empty.
+    Node nextNode()
+    ///The next node to be processed.
+    ///Returns the next node to be processed or \c INVALID if the
+    ///priority heap is empty.
+    Node nextNode() const
+    {
       return !_heap->empty()?_heap->top():INVALID;
 …
     ///\brief Returns \c false if there are nodes
     ///to be processed in the priority heap
+    ///to be processed.
     ///
     ///Returns \c false if there are nodes
+    ///to be processed in the priority heap
+    bool emptyQueue() { return _heap->empty(); }
+    ///to be processed in the priority heap.
+    bool emptyQueue() const { 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 queueSize() { return _heap->size(); }
+    ///Returns the number of the nodes to be processed in the priority heap.
+    ///
+    int queueSize() const { return _heap->size(); }
     ///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 %Dijkstra 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).
+    ///
+    ///in order to compute the shortest path to each node.
+    ///
+    ///The algorithm computes
+    ///- the shortest path tree (forest),
+    ///- the distance of each node from the root(s).
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
+    ///
+    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
+    ///\code
+    ///  while ( !d.emptyQueue() ) {
+    ///    d.processNextNode();
+    ///  }
+    ///\endcode
     void start()
+    {
+      while ( !_heap->empty() ) 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.
+      while ( !emptyQueue() ) processNextNode();
+    }
+    ///Executes the algorithm until the given target node is reached.
+    ///Executes the algorithm until the given target node is reached.
     ///
     ///This method runs the %Dijkstra 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).
+    ///
+    ///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).
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
     void start(Node dest)
+    {
 …
     ///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
+    ///This method runs the %Dijkstra algorithm from the root node(s) in
+    ///order to compute the shortest path to a node \c v with
+    /// <tt>nm[v]</tt> true, if such a node can be found.
+    ///
+    ///\param nm A \c bool (or convertible) node map. The algorithm
     ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
     ///
     ///\return The reached node \c v with <tt>nm[v]</tt> true or
     ///\c INVALID if no such node was found.
+    ///
+    ///\pre init() must be called and at least one root node should be
+    ///added with addSource() before using this function.
     template<class NodeBoolMap>
     Node start(const NodeBoolMap &nm)
 …
+    }
     ///Runs %Dijkstra algorithm from node \c s.
     ///This method runs the %Dijkstra 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.
+    ///Runs the algorithm from the given node.
+    ///This method runs the %Dijkstra algorithm from 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 <tt>d.run(s)</tt> is just a shortcut of the following code.
     ///\code
     ///  d.init();
 …
     ///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.
+    ///This method runs the %Dijkstra algorithm from node \c s
+    ///in order to compute the shortest path to \c t.
+    ///
+    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
+    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///
+    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
+    ///shortcut of the following code.
     ///\code
     ///  d.init();
 …
     ///The result of the %Dijkstra algorithm can be obtained using these
     ///functions.\n
+    ///Before the use of these functions,
+    ///either run() or start() must be called.
+    ///Either \ref lemon::Dijkstra::run() "run()" or
+    ///\ref lemon::Dijkstra::start() "start()" must be called before
+    ///using them.
     ///@{
+    ///Gives back the shortest path.
+    ///Gives back the shortest path.
+    ///\pre The \c t should be reachable from the source.
+    Path path(Node t)
+    {
+      return Path(*G, *_pred, t);
+    }
+    ///The distance of a node from the root.
+    ///Returns the distance of a node from the root.
+    ///\pre \ref run() must be called before using this function.
+    ///\warning If node \c v in unreachable from the root the return value
+    ///of this funcion is undefined.
+    ///The shortest path to a node.
+    ///Returns the shortest path to a node.
+    ///
+    ///\warning \c t should be reachable from the root(s).
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
+    Path path(Node t) const { return Path(*G, *_pred, t); }
+    ///The distance of a node from the root(s).
+    ///Returns the distance of a node from the root(s).
+    ///
+    ///\warning If node \c v is not reachable from the root(s), then
+    ///the return value of this function is undefined.
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Value dist(Node v) const { return (*_dist)[v]; }
+    ///The current distance of a node from the root.
+    ///Returns the current distance of a node from the root.
+    ///It may be decreased in the following processes.
+    ///\pre \c node should be reached but not processed
+    Value currentDist(Node v) const { return (*_heap)[v]; }
+    ///Returns the 'previous arc' of the shortest path tree.
+    ///For a node \c v it returns the 'previous arc' of the shortest path tree,
+    ///i.e. it returns the last arc of a shortest path from the root to \c
+    ///v. It is \ref INVALID
+    ///if \c v is unreachable from the root or if \c v=s. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode().  \pre \ref run() must be called before using
+    ///this function.
+    ///Returns the 'previous arc' of the shortest path tree for a node.
+    ///This function returns the 'previous arc' of the shortest path
+    ///tree for the node \c v, i.e. it returns the last arc of a
+    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+    ///is not reachable from the root(s) or if \c v is a root.
+    ///
+    ///The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref predNode().
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Arc predArc(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 shortest path
+    ///tree used in \ref predArc().  \pre \ref run() must be called before
+    ///Returns the 'previous node' of the shortest path tree for a node.
+    ///This function returns the 'previous node' of the shortest path
+    ///tree for the node \c v, i.e. it returns the last but one node
+    ///from a shortest path from the root(s) to \c v. It is \c INVALID
+    ///if \c v is not reachable from the root(s) or if \c v is a root.
+    ///
+    ///The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref predArc().
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
     ///using this function.
     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
+    ///be called before using this function.
+    ///\brief Returns a const reference to the node map that stores the
+    ///distances of the nodes.
+    ///
+    ///Returns a const reference to the node map that stores the distances
+    ///of the nodes calculated by the algorithm.
+    ///
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
+    ///Returns a reference to the shortest path tree map.
+    ///Returns a reference to the NodeMap of the arcs of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    ///\brief Returns a const reference to the node map that stores the
+    ///predecessor arcs.
+    ///
+    ///Returns a const reference to the node map that stores the predecessor
+    ///arcs, which form the shortest path tree.
+    ///
+    ///\pre Either \ref run() or \ref init()
+    ///must be called before using this function.
     const PredMap &predMap() const { return *_pred;}
     ///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.
     ///
     bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
+    ///Checks if a node is reachable from the root(s).
+    ///Returns \c true if \c v is reachable from the root(s).
+    ///\pre Either \ref run() or \ref start()
+    ///must be called before using this function.
+    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
+                                        Heap::PRE_HEAP; }
     ///Checks if a node is processed.
 …
     ///Returns \c true if \c v is processed, i.e. the shortest
     ///path to \c v has already found.
+    ///\pre \ref run() must be called before using this function.
+    ///
+    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
+    ///\pre Either \ref run() or \ref start()
+    ///must be called before using this function.
+    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
+                                          Heap::POST_HEAP; }
+    ///The current distance of a node from the root(s).
+    ///Returns the current distance of a node from the root(s).
+    ///It may be decreased in the following processes.
+    ///\pre \c v should be reached but not processed.
+    Value currentDist(Node v) const { return (*_heap)[v]; }
     ///@}
 …
+  ///Default traits class of Dijkstra function.
+  ///Default traits class of Dijkstra function.
+  ///\tparam GR Digraph type.
+  ///\tparam LM Type of length map.
+  ///Default traits class of dijkstra() function.
+  ///Default traits class of dijkstra() function.
+  ///\tparam GR The type of the digraph.
+  ///\tparam LM The type of the length map.
   template<class GR, class LM>
   struct DijkstraWizardDefaultTraits
+  {
     ///The digraph type the algorithm runs on.
+    ///The type of the digraph the algorithm runs on.
     typedef GR Digraph;
     ///The type of the map that stores the arc lengths.
 …
     ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     typedef LM LengthMap;
     //The type of the length of the arcs.
+    ///The type of the length of the arcs.
     typedef typename LM::Value Value;
     /// Operation traits for Dijkstra algorithm.
     /// It defines the used operation by the algorithm.
+    /// This class defines the operations that are used in the algorithm.
     /// \see DijkstraDefaultOperationTraits
     typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
+    ///The heap type used by Dijkstra algorithm.
+    /// The cross reference type used by heap.
+    /// The cross reference type used by heap.
+    /// The cross reference type used by the heap.
+    /// The cross reference type used by the heap.
     /// Usually it is \c Digraph::NodeMap<int>.
     typedef typename Digraph::template NodeMap<int> HeapCrossRef;
     ///Instantiates a HeapCrossRef.
+    ///Instantiates a \ref HeapCrossRef.
     ///This function instantiates a \ref HeapCrossRef.
     /// \param G is the digraph, to which we would like to define the
+    /// \param g is the digraph, to which we would like to define the
     /// HeapCrossRef.
     /// \todo The digraph alone may be insufficient for the initialization
     static HeapCrossRef *createHeapCrossRef(const GR &G)
+    {
       return new HeapCrossRef(G);
+    }
     ///The heap type used by Dijkstra algorithm.
     ///The heap type used by Dijkstra algorithm.
+    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
+    {
+      return new HeapCrossRef(g);
+    }
+    ///The heap type used by the Dijkstra algorithm.
+    ///The heap type used by the Dijkstra algorithm.
     ///
     ///\sa BinHeap
     ///\sa Dijkstra
     typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
+    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
                     std::less<Value> > Heap;
+    static Heap *createHeap(HeapCrossRef& R)
+    {
+      return new Heap(R);
+    }
+    ///\brief The type of the map that stores the last
+    ///Instantiates a \ref Heap.
+    ///This function instantiates a \ref Heap.
+    /// \param r is the HeapCrossRef which is used.
+    static Heap *createHeap(HeapCrossRef& r)
+    {
+      return new Heap(r);
+    }
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///
     ///The type of the map that stores the last
+    ///The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
+    ///Instantiates a PredMap.
+    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
+    ///Instantiates a \ref PredMap.
     ///This function instantiates a \ref PredMap.
+    ///\param g is the digraph, to which we would like to define the PredMap.
+    ///\todo The digraph alone may be insufficient for the initialization
+    ///\param g is the digraph, to which we would like to define the
+    ///\ref PredMap.
+    ///\todo The digraph alone may be insufficient to initialize
 #ifdef DOXYGEN
     static PredMap *createPredMap(const GR &g)
+    static PredMap *createPredMap(const Digraph &g)
 #else
     static PredMap *createPredMap(const GR &)
+    static PredMap *createPredMap(const Digraph &)
 #endif
+    {
       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.
+    ///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 concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
 …
     ///\todo named parameter to set this type, function to read and write.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a ProcessedMap.
+    ///Instantiates a \ref ProcessedMap.
     ///This function instantiates a \ref ProcessedMap.
     ///\param g is the digraph, to which
     ///we would like to define the \ref ProcessedMap
+    ///we would like to define the \ref ProcessedMap.
 #ifdef DOXYGEN
     static ProcessedMap *createProcessedMap(const GR &g)
+    static ProcessedMap *createProcessedMap(const Digraph &g)
 #else
     static ProcessedMap *createProcessedMap(const GR &)
+    static ProcessedMap *createProcessedMap(const Digraph &)
 #endif
+    {
       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.
+    ///The type of the map that stores the distances of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+    ///
+    typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
+    ///Instantiates a DistMap.
+    typedef NullMap<typename Digraph::Node,Value> DistMap;
+    ///Instantiates a \ref DistMap.
     ///This function instantiates a \ref DistMap.
 …
     ///the \ref DistMap
 #ifdef DOXYGEN
     static DistMap *createDistMap(const GR &g)
+    static DistMap *createDistMap(const Digraph &g)
 #else
     static DistMap *createDistMap(const GR &)
+    static DistMap *createDistMap(const Digraph &)
 #endif
+    {
 …
   };
   /// Default traits used by \ref DijkstraWizard
+  /// Default traits class used by \ref DijkstraWizard
   /// To make it easier to use Dijkstra algorithm
   ///we have created a wizard class.
+  /// we have created a wizard class.
   /// This \ref DijkstraWizard class needs default traits,
   ///as well as the \ref Dijkstra class.
+  /// as well as the \ref Dijkstra class.
   /// The \ref DijkstraWizardBase is a class to be the default traits of the
   /// \ref DijkstraWizard class.
 …
   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
+  {
     typedef DijkstraWizardDefaultTraits<GR,LM> Base;
   protected:
     /// Type of the nodes in the digraph.
+    //The type of the nodes in the digraph.
     typedef typename Base::Digraph::Node Node;
     /// Pointer to the underlying digraph.
+    //Pointer to the digraph the algorithm runs on.
     void *_g;
     /// Pointer to the length map
+    //Pointer to the length map
     void *_length;
     ///Pointer to the map of predecessors arcs.
+    //Pointer to the map of predecessors arcs.
     void *_pred;
     ///Pointer to the map of distances.
+    //Pointer to the map of distances.
     void *_dist;
     ///Pointer to the source node.
+    //Pointer to the source node.
     Node _source;
     public:
+  public:
     /// Constructor.
 …
     /// listed in the parameters list.
     /// Others are initiated to 0.
     /// \param g is the initial value of  \ref _g
     /// \param l is the initial value of  \ref _length
     /// \param s is the initial value of  \ref _source
+    /// \param g The digraph the algorithm runs on.
+    /// \param l The length map.
+    /// \param s The source node.
     DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
 …
   };
+  /// A class to make the usage of Dijkstra algorithm easier
+  /// This class is created to make it easier to use Dijkstra algorithm.
+  /// It uses the functions and features of the plain \ref Dijkstra,
+  /// but it is much simpler to use it.
+  /// Auxiliary class for the function type interface of Dijkstra algorithm.
+  /// This auxiliary class is created to implement the function type
+  /// interface of \ref Dijkstra algorithm. It uses the functions and features
+  /// of the plain \ref Dijkstra, but it is much simpler to use it.
+  /// It should only be used through the \ref dijkstra() function, which makes
+  /// it easier to use the algorithm.
   ///
   /// Simplicity means that the way to change the types defined
 …
   /// the original class by using the ::
   /// operator. In the case of \ref DijkstraWizard only
   /// a function have to be called and it will
+  /// 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 Dijkstra class, and calls the \ref
   /// Dijkstra::run method of it.
+  /// It does not have own \ref run() method. When its \ref run() method
+  /// is called, it initiates a plain \ref Dijkstra object, and calls the
+  /// \ref Dijkstra::run() method of it.
   template<class TR>
   class DijkstraWizard : public TR
 …
     typedef TR Base;
     ///The type of the underlying digraph.
+    ///The type of the digraph the algorithm runs on.
     typedef typename TR::Digraph Digraph;
+    //\e
     typedef typename Digraph::Node Node;
-    //\e
     typedef typename Digraph::NodeIt NodeIt;
-    //\e
     typedef typename Digraph::Arc Arc;
-    //\e
     typedef typename Digraph::OutArcIt OutArcIt;
 …
     ///The type of the length of the arcs.
     typedef typename LengthMap::Value Value;
     ///\brief The type of the map that stores the last
+    ///\brief The type of the map that stores the predecessor
     ///arcs of the shortest paths.
     typedef typename TR::PredMap PredMap;
     ///The type of the map that stores the dists of the nodes.
+    ///The type of the map that stores the distances of the nodes.
     typedef typename TR::DistMap DistMap;
+    ///The type of the map that indicates which nodes are processed.
+    typedef typename TR::ProcessedMap ProcessedMap;
     ///The heap type used by the dijkstra algorithm.
     typedef typename TR::Heap Heap;
   public:
     /// Constructor.
     DijkstraWizard() : TR() {}
 …
     ~DijkstraWizard() {}
     ///Runs Dijkstra algorithm from a given node.
     ///Runs Dijkstra algorithm from a given node.
     ///The node can be given by the \ref source function.
+    ///Runs Dijkstra algorithm from a source node.
+    ///Runs Dijkstra algorithm from a source node.
+    ///The node can be given with the \ref source() function.
     void run()
+    {
 …
+    }
+    /// Sets the source node, from which the Dijkstra algorithm runs.
+    /// Sets the source node, from which the Dijkstra algorithm runs.
+    /// \param s is the source node.
+    DijkstraWizard<TR> &source(Node s)
+    {
+      Base::_source=s;
+      return *this;
+    }
     template<class T>
     struct DefPredMapBase : public Base {
 …
       DefPredMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting PredMap type
+    ///
+    ///for setting \ref PredMap object.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting \ref PredMap object.
     template<class T>
     DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
 …
       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DijkstraWizard<DefPredMapBase<T> >(*this);
+    }
+    template<class T>
+    struct DefProcessedMapBase : public Base {
+      typedef T ProcessedMap;
+      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
+      DefProcessedMapBase(const TR &b) : TR(b) {}
+    };
+    ///\brief \ref named-templ-param "Named parameter"
+    ///for setting \ref ProcessedMap object.
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///for setting \ref ProcessedMap object.
+    template<class T>
+    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
+    {
+      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
+      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
+    }
 …
       DefDistMapBase(const TR &b) : TR(b) {}
     };
     ///\brief \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    /// \ref named-templ-param "Named parameter"
+    ///function for setting DistMap type
+    ///
+    ///for setting \ref DistMap object.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting \ref DistMap object.
     template<class T>
     DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
 …
       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
       return DijkstraWizard<DefDistMapBase<T> >(*this);
+    }
-    /// Sets the source node, from which the Dijkstra algorithm runs.
-    /// Sets the source node, from which the Dijkstra algorithm runs.
-    /// \param s is the source node.
-    DijkstraWizard<TR> &source(Node s)
+    {
-      Base::_source=s;
-      return *this;
+    }

Note: See TracChangeset for help on using the changeset viewer.

Download in other formats: