Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Mon, 04 Aug 2008 22:00:36 +0200
changeset 247f1158744a112
parent 246 7c67988fca07
parent 244 c30731a37f91
child 248 8fada33fc60a
child 365 37557a46e298
Merge
lemon/bfs.h
lemon/dfs.h
lemon/dijkstra.h
     1.1 --- a/lemon/bfs.h	Wed Jul 30 12:07:48 2008 +0100
     1.2 +++ b/lemon/bfs.h	Mon Aug 04 22:00:36 2008 +0200
     1.3 @@ -21,7 +21,7 @@
     1.4  
     1.5  ///\ingroup search
     1.6  ///\file
     1.7 -///\brief Bfs algorithm.
     1.8 +///\brief BFS algorithm.
     1.9  
    1.10  #include <lemon/list_graph.h>
    1.11  #include <lemon/bits/path_dump.h>
    1.12 @@ -31,8 +31,6 @@
    1.13  
    1.14  namespace lemon {
    1.15  
    1.16 -
    1.17 -
    1.18    ///Default traits class of Bfs class.
    1.19  
    1.20    ///Default traits class of Bfs class.
    1.21 @@ -40,73 +38,75 @@
    1.22    template<class GR>
    1.23    struct BfsDefaultTraits
    1.24    {
    1.25 -    ///The digraph type the algorithm runs on.
    1.26 +    ///The type of the digraph the algorithm runs on.
    1.27      typedef GR Digraph;
    1.28 -    ///\brief The type of the map that stores the last
    1.29 +
    1.30 +    ///\brief The type of the map that stores the predecessor
    1.31      ///arcs of the shortest paths.
    1.32      ///
    1.33 -    ///The type of the map that stores the last
    1.34 +    ///The type of the map that stores the predecessor
    1.35      ///arcs of the shortest paths.
    1.36      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.37 -    ///
    1.38 -    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    1.39 -    ///Instantiates a PredMap.
    1.40 +    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    1.41 +    ///Instantiates a \ref PredMap.
    1.42  
    1.43      ///This function instantiates a \ref PredMap.
    1.44 -    ///\param G is the digraph, to which we would like to define the PredMap.
    1.45 +    ///\param g is the digraph, to which we would like to define the
    1.46 +    ///\ref PredMap.
    1.47      ///\todo The digraph alone may be insufficient to initialize
    1.48 -    static PredMap *createPredMap(const GR &G)
    1.49 +    static PredMap *createPredMap(const Digraph &g)
    1.50      {
    1.51 -      return new PredMap(G);
    1.52 +      return new PredMap(g);
    1.53      }
    1.54 +
    1.55      ///The type of the map that indicates which nodes are processed.
    1.56  
    1.57      ///The type of the map that indicates which nodes are processed.
    1.58      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.59 -    ///\todo named parameter to set this type, function to read and write.
    1.60 +    ///By default it is a NullMap.
    1.61      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    1.62 -    ///Instantiates a ProcessedMap.
    1.63 +    ///Instantiates a \ref ProcessedMap.
    1.64  
    1.65      ///This function instantiates a \ref ProcessedMap.
    1.66      ///\param g is the digraph, to which
    1.67      ///we would like to define the \ref ProcessedMap
    1.68  #ifdef DOXYGEN
    1.69 -    static ProcessedMap *createProcessedMap(const GR &g)
    1.70 +    static ProcessedMap *createProcessedMap(const Digraph &g)
    1.71  #else
    1.72 -    static ProcessedMap *createProcessedMap(const GR &)
    1.73 +    static ProcessedMap *createProcessedMap(const Digraph &)
    1.74  #endif
    1.75      {
    1.76        return new ProcessedMap();
    1.77      }
    1.78 +
    1.79      ///The type of the map that indicates which nodes are reached.
    1.80  
    1.81      ///The type of the map that indicates which nodes are reached.
    1.82 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.83 -    ///\todo named parameter to set this type, function to read and write.
    1.84 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.85      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    1.86 -    ///Instantiates a ReachedMap.
    1.87 +    ///Instantiates a \ref ReachedMap.
    1.88  
    1.89      ///This function instantiates a \ref ReachedMap.
    1.90 -    ///\param G is the digraph, to which
    1.91 +    ///\param g is the digraph, to which
    1.92      ///we would like to define the \ref ReachedMap.
    1.93 -    static ReachedMap *createReachedMap(const GR &G)
    1.94 +    static ReachedMap *createReachedMap(const Digraph &g)
    1.95      {
    1.96 -      return new ReachedMap(G);
    1.97 +      return new ReachedMap(g);
    1.98      }
    1.99 -    ///The type of the map that stores the dists of the nodes.
   1.100  
   1.101 -    ///The type of the map that stores the dists of the nodes.
   1.102 +    ///The type of the map that stores the distances of the nodes.
   1.103 +
   1.104 +    ///The type of the map that stores the distances of the nodes.
   1.105      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.106 -    ///
   1.107      typedef typename Digraph::template NodeMap<int> DistMap;
   1.108 -    ///Instantiates a DistMap.
   1.109 +    ///Instantiates a \ref DistMap.
   1.110  
   1.111      ///This function instantiates a \ref DistMap.
   1.112 -    ///\param G is the digraph, to which we would like to define
   1.113 -    ///the \ref DistMap
   1.114 -    static DistMap *createDistMap(const GR &G)
   1.115 +    ///\param g is the digraph, to which we would like to define the
   1.116 +    ///\ref DistMap.
   1.117 +    static DistMap *createDistMap(const Digraph &g)
   1.118      {
   1.119 -      return new DistMap(G);
   1.120 +      return new DistMap(g);
   1.121      }
   1.122    };
   1.123  
   1.124 @@ -115,15 +115,18 @@
   1.125    ///\ingroup search
   1.126    ///This class provides an efficient implementation of the %BFS algorithm.
   1.127    ///
   1.128 -  ///\tparam GR The digraph type the algorithm runs on. The default value is
   1.129 -  ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
   1.130 -  ///is only passed to \ref BfsDefaultTraits.
   1.131 +  ///There is also a \ref bfs() "function type interface" for the BFS
   1.132 +  ///algorithm, which is convenient in the simplier cases and it can be
   1.133 +  ///used easier.
   1.134 +  ///
   1.135 +  ///\tparam GR The type of the digraph the algorithm runs on.
   1.136 +  ///The default value is \ref ListDigraph. The value of GR is not used
   1.137 +  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
   1.138    ///\tparam TR Traits class to set various data types used by the algorithm.
   1.139    ///The default traits class is
   1.140    ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
   1.141    ///See \ref BfsDefaultTraits for the documentation of
   1.142    ///a Bfs traits class.
   1.143 -
   1.144  #ifdef DOXYGEN
   1.145    template <typename GR,
   1.146              typename TR>
   1.147 @@ -133,12 +136,10 @@
   1.148  #endif
   1.149    class Bfs {
   1.150    public:
   1.151 -    /**
   1.152 -     * \brief \ref Exception for uninitialized parameters.
   1.153 -     *
   1.154 -     * This error represents problems in the initialization
   1.155 -     * of the parameters of the algorithms.
   1.156 -     */
   1.157 +    ///\ref Exception for uninitialized parameters.
   1.158 +
   1.159 +    ///This error represents problems in the initialization of the
   1.160 +    ///parameters of the algorithm.
   1.161      class UninitializedParameter : public lemon::UninitializedParameter {
   1.162      public:
   1.163        virtual const char* what() const throw() {
   1.164 @@ -146,19 +147,24 @@
   1.165        }
   1.166      };
   1.167  
   1.168 -    typedef TR Traits;
   1.169 -    ///The type of the underlying digraph.
   1.170 +    ///The type of the digraph the algorithm runs on.
   1.171      typedef typename TR::Digraph Digraph;
   1.172  
   1.173 -    ///\brief The type of the map that stores the last
   1.174 -    ///arcs of the shortest paths.
   1.175 +    ///\brief The type of the map that stores the predecessor arcs of the
   1.176 +    ///shortest paths.
   1.177      typedef typename TR::PredMap PredMap;
   1.178 -    ///The type of the map indicating which nodes are reached.
   1.179 +    ///The type of the map that stores the distances of the nodes.
   1.180 +    typedef typename TR::DistMap DistMap;
   1.181 +    ///The type of the map that indicates which nodes are reached.
   1.182      typedef typename TR::ReachedMap ReachedMap;
   1.183 -    ///The type of the map indicating which nodes are processed.
   1.184 +    ///The type of the map that indicates which nodes are processed.
   1.185      typedef typename TR::ProcessedMap ProcessedMap;
   1.186 -    ///The type of the map that stores the dists of the nodes.
   1.187 -    typedef typename TR::DistMap DistMap;
   1.188 +    ///The type of the paths.
   1.189 +    typedef PredMapPath<Digraph, PredMap> Path;
   1.190 +
   1.191 +    ///The traits class.
   1.192 +    typedef TR Traits;
   1.193 +
   1.194    private:
   1.195  
   1.196      typedef typename Digraph::Node Node;
   1.197 @@ -166,23 +172,23 @@
   1.198      typedef typename Digraph::Arc Arc;
   1.199      typedef typename Digraph::OutArcIt OutArcIt;
   1.200  
   1.201 -    /// Pointer to the underlying digraph.
   1.202 +    //Pointer to the underlying digraph.
   1.203      const Digraph *G;
   1.204 -    ///Pointer to the map of predecessors arcs.
   1.205 +    //Pointer to the map of predecessor arcs.
   1.206      PredMap *_pred;
   1.207 -    ///Indicates if \ref _pred is locally allocated (\c true) or not.
   1.208 +    //Indicates if _pred is locally allocated (true) or not.
   1.209      bool local_pred;
   1.210 -    ///Pointer to the map of distances.
   1.211 +    //Pointer to the map of distances.
   1.212      DistMap *_dist;
   1.213 -    ///Indicates if \ref _dist is locally allocated (\c true) or not.
   1.214 +    //Indicates if _dist is locally allocated (true) or not.
   1.215      bool local_dist;
   1.216 -    ///Pointer to the map of reached status of the nodes.
   1.217 +    //Pointer to the map of reached status of the nodes.
   1.218      ReachedMap *_reached;
   1.219 -    ///Indicates if \ref _reached is locally allocated (\c true) or not.
   1.220 +    //Indicates if _reached is locally allocated (true) or not.
   1.221      bool local_reached;
   1.222 -    ///Pointer to the map of processed status of the nodes.
   1.223 +    //Pointer to the map of processed status of the nodes.
   1.224      ProcessedMap *_processed;
   1.225 -    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   1.226 +    //Indicates if _processed is locally allocated (true) or not.
   1.227      bool local_processed;
   1.228  
   1.229      std::vector<typename Digraph::Node> _queue;
   1.230 @@ -190,7 +196,6 @@
   1.231      int _curr_dist;
   1.232  
   1.233      ///Creates the maps if necessary.
   1.234 -
   1.235      ///\todo Better memory allocation (instead of new).
   1.236      void create_maps()
   1.237      {
   1.238 @@ -233,10 +238,10 @@
   1.239        }
   1.240      };
   1.241      ///\brief \ref named-templ-param "Named parameter" for setting
   1.242 -    ///PredMap type
   1.243 +    ///\ref PredMap type.
   1.244      ///
   1.245 -    ///\ref named-templ-param "Named parameter" for setting PredMap type
   1.246 -    ///
   1.247 +    ///\ref named-templ-param "Named parameter" for setting
   1.248 +    ///\ref PredMap type.
   1.249      template <class T>
   1.250      struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
   1.251        typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
   1.252 @@ -251,10 +256,10 @@
   1.253        }
   1.254      };
   1.255      ///\brief \ref named-templ-param "Named parameter" for setting
   1.256 -    ///DistMap type
   1.257 +    ///\ref DistMap type.
   1.258      ///
   1.259 -    ///\ref named-templ-param "Named parameter" for setting DistMap type
   1.260 -    ///
   1.261 +    ///\ref named-templ-param "Named parameter" for setting
   1.262 +    ///\ref DistMap type.
   1.263      template <class T>
   1.264      struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
   1.265        typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
   1.266 @@ -269,10 +274,10 @@
   1.267        }
   1.268      };
   1.269      ///\brief \ref named-templ-param "Named parameter" for setting
   1.270 -    ///ReachedMap type
   1.271 +    ///\ref ReachedMap type.
   1.272      ///
   1.273 -    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   1.274 -    ///
   1.275 +    ///\ref named-templ-param "Named parameter" for setting
   1.276 +    ///\ref ReachedMap type.
   1.277      template <class T>
   1.278      struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
   1.279        typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
   1.280 @@ -287,10 +292,10 @@
   1.281        }
   1.282      };
   1.283      ///\brief \ref named-templ-param "Named parameter" for setting
   1.284 -    ///ProcessedMap type
   1.285 +    ///\ref ProcessedMap type.
   1.286      ///
   1.287 -    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   1.288 -    ///
   1.289 +    ///\ref named-templ-param "Named parameter" for setting
   1.290 +    ///\ref ProcessedMap type.
   1.291      template <class T>
   1.292      struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
   1.293        typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
   1.294 @@ -298,16 +303,16 @@
   1.295  
   1.296      struct DefDigraphProcessedMapTraits : public Traits {
   1.297        typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   1.298 -      static ProcessedMap *createProcessedMap(const Digraph &G)
   1.299 +      static ProcessedMap *createProcessedMap(const Digraph &g)
   1.300        {
   1.301 -        return new ProcessedMap(G);
   1.302 +        return new ProcessedMap(g);
   1.303        }
   1.304      };
   1.305 -    ///\brief \ref named-templ-param "Named parameter"
   1.306 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   1.307 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.308 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.309      ///
   1.310 -    ///\ref named-templ-param "Named parameter"
   1.311 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   1.312 +    ///\ref named-templ-param "Named parameter" for setting
   1.313 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   1.314      ///If you don't set it explicitly, it will be automatically allocated.
   1.315      template <class T>
   1.316      struct DefProcessedMapToBeDefaultMap :
   1.317 @@ -321,10 +326,10 @@
   1.318  
   1.319      ///Constructor.
   1.320  
   1.321 -    ///\param _G the digraph the algorithm will run on.
   1.322 -    ///
   1.323 -    Bfs(const Digraph& _G) :
   1.324 -      G(&_G),
   1.325 +    ///Constructor.
   1.326 +    ///\param g The digraph the algorithm runs on.
   1.327 +    Bfs(const Digraph &g) :
   1.328 +      G(&g),
   1.329        _pred(NULL), local_pred(false),
   1.330        _dist(NULL), local_dist(false),
   1.331        _reached(NULL), local_reached(false),
   1.332 @@ -340,9 +345,9 @@
   1.333        if(local_processed) delete _processed;
   1.334      }
   1.335  
   1.336 -    ///Sets the map storing the predecessor arcs.
   1.337 +    ///Sets the map that stores the predecessor arcs.
   1.338  
   1.339 -    ///Sets the map storing the predecessor arcs.
   1.340 +    ///Sets the map that stores the predecessor arcs.
   1.341      ///If you don't use this function before calling \ref run(),
   1.342      ///it will allocate one. The destructor deallocates this
   1.343      ///automatically allocated map, of course.
   1.344 @@ -357,9 +362,9 @@
   1.345        return *this;
   1.346      }
   1.347  
   1.348 -    ///Sets the map indicating the reached nodes.
   1.349 +    ///Sets the map that indicates which nodes are reached.
   1.350  
   1.351 -    ///Sets the map indicating the reached nodes.
   1.352 +    ///Sets the map that indicates which nodes are reached.
   1.353      ///If you don't use this function before calling \ref run(),
   1.354      ///it will allocate one. The destructor deallocates this
   1.355      ///automatically allocated map, of course.
   1.356 @@ -374,9 +379,9 @@
   1.357        return *this;
   1.358      }
   1.359  
   1.360 -    ///Sets the map indicating the processed nodes.
   1.361 +    ///Sets the map that indicates which nodes are processed.
   1.362  
   1.363 -    ///Sets the map indicating the processed nodes.
   1.364 +    ///Sets the map that indicates which nodes are processed.
   1.365      ///If you don't use this function before calling \ref run(),
   1.366      ///it will allocate one. The destructor deallocates this
   1.367      ///automatically allocated map, of course.
   1.368 @@ -391,9 +396,10 @@
   1.369        return *this;
   1.370      }
   1.371  
   1.372 -    ///Sets the map storing the distances calculated by the algorithm.
   1.373 +    ///Sets the map that stores the distances of the nodes.
   1.374  
   1.375 -    ///Sets the map storing the distances calculated by the algorithm.
   1.376 +    ///Sets the map that stores the distances of the nodes calculated by
   1.377 +    ///the algorithm.
   1.378      ///If you don't use this function before calling \ref run(),
   1.379      ///it will allocate one. The destructor deallocates this
   1.380      ///automatically allocated map, of course.
   1.381 @@ -409,20 +415,21 @@
   1.382      }
   1.383  
   1.384    public:
   1.385 +
   1.386      ///\name Execution control
   1.387      ///The simplest way to execute the algorithm is to use
   1.388 -    ///one of the member functions called \c run(...).
   1.389 +    ///one of the member functions called \ref lemon::Bfs::run() "run()".
   1.390      ///\n
   1.391 -    ///If you need more control on the execution,
   1.392 -    ///first you must call \ref init(), then you can add several source nodes
   1.393 -    ///with \ref addSource().
   1.394 -    ///Finally \ref start() will perform the actual path
   1.395 -    ///computation.
   1.396 +    ///If you need more control on the execution, first you must call
   1.397 +    ///\ref lemon::Bfs::init() "init()", then you can add several source
   1.398 +    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
   1.399 +    ///Finally \ref lemon::Bfs::start() "start()" will perform the
   1.400 +    ///actual path computation.
   1.401  
   1.402      ///@{
   1.403  
   1.404 -    ///\brief Initializes the internal data structures.
   1.405 -    ///
   1.406 +    ///Initializes the internal data structures.
   1.407 +
   1.408      ///Initializes the internal data structures.
   1.409      ///
   1.410      void init()
   1.411 @@ -460,7 +467,7 @@
   1.412      ///
   1.413      ///\return The processed node.
   1.414      ///
   1.415 -    ///\warning The queue must not be empty!
   1.416 +    ///\pre The queue must not be empty.
   1.417      Node processNextNode()
   1.418      {
   1.419        if(_queue_tail==_queue_next_dist) {
   1.420 @@ -482,16 +489,17 @@
   1.421  
   1.422      ///Processes the next node.
   1.423  
   1.424 -    ///Processes the next node. And checks that the given target node
   1.425 +    ///Processes the next node and checks if the given target node
   1.426      ///is reached. If the target node is reachable from the processed
   1.427 -    ///node then the reached parameter will be set true. The reached
   1.428 -    ///parameter should be initially false.
   1.429 +    ///node, then the \c reach parameter will be set to \c true.
   1.430      ///
   1.431      ///\param target The target node.
   1.432 -    ///\retval reach Indicates that the target node is reached.
   1.433 +    ///\retval reach Indicates if the target node is reached.
   1.434 +    ///It should be initially \c false.
   1.435 +    ///
   1.436      ///\return The processed node.
   1.437      ///
   1.438 -    ///\warning The queue must not be empty!
   1.439 +    ///\pre The queue must not be empty.
   1.440      Node processNextNode(Node target, bool& reach)
   1.441      {
   1.442        if(_queue_tail==_queue_next_dist) {
   1.443 @@ -514,16 +522,19 @@
   1.444  
   1.445      ///Processes the next node.
   1.446  
   1.447 -    ///Processes the next node. And checks that at least one of
   1.448 -    ///reached node has true value in the \c nm node map. If one node
   1.449 -    ///with true value is reachable from the processed node then the
   1.450 -    ///rnode parameter will be set to the first of such nodes.
   1.451 +    ///Processes the next node and checks if at least one of reached
   1.452 +    ///nodes has \c true value in the \c nm node map. If one node
   1.453 +    ///with \c true value is reachable from the processed node, then the
   1.454 +    ///\c rnode parameter will be set to the first of such nodes.
   1.455      ///
   1.456 -    ///\param nm The node map of possible targets.
   1.457 +    ///\param nm A \c bool (or convertible) node map that indicates the
   1.458 +    ///possible targets.
   1.459      ///\retval rnode The reached target node.
   1.460 +    ///It should be initially \c INVALID.
   1.461 +    ///
   1.462      ///\return The processed node.
   1.463      ///
   1.464 -    ///\warning The queue must not be empty!
   1.465 +    ///\pre The queue must not be empty.
   1.466      template<class NM>
   1.467      Node processNextNode(const NM& nm, Node& rnode)
   1.468      {
   1.469 @@ -545,58 +556,73 @@
   1.470        return n;
   1.471      }
   1.472  
   1.473 -    ///Next node to be processed.
   1.474 +    ///The next node to be processed.
   1.475  
   1.476 -    ///Next node to be processed.
   1.477 -    ///
   1.478 -    ///\return The next node to be processed or INVALID if the queue is
   1.479 -    /// empty.
   1.480 -    Node nextNode()
   1.481 +    ///Returns the next node to be processed or \c INVALID if the queue
   1.482 +    ///is empty.
   1.483 +    Node nextNode() const
   1.484      {
   1.485        return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   1.486      }
   1.487  
   1.488      ///\brief Returns \c false if there are nodes
   1.489 -    ///to be processed in the queue
   1.490 +    ///to be processed.
   1.491      ///
   1.492      ///Returns \c false if there are nodes
   1.493 -    ///to be processed in the queue
   1.494 -    bool emptyQueue() { return _queue_tail==_queue_head; }
   1.495 +    ///to be processed in the queue.
   1.496 +    bool emptyQueue() const { return _queue_tail==_queue_head; }
   1.497 +
   1.498      ///Returns the number of the nodes to be processed.
   1.499  
   1.500      ///Returns the number of the nodes to be processed in the queue.
   1.501 -    int queueSize() { return _queue_head-_queue_tail; }
   1.502 +    int queueSize() const { return _queue_head-_queue_tail; }
   1.503  
   1.504      ///Executes the algorithm.
   1.505  
   1.506      ///Executes the algorithm.
   1.507      ///
   1.508 -    ///\pre init() must be called and at least one node should be added
   1.509 -    ///with addSource() before using this function.
   1.510 +    ///This method runs the %BFS algorithm from the root node(s)
   1.511 +    ///in order to compute the shortest path to each node.
   1.512      ///
   1.513 -    ///This method runs the %BFS algorithm from the root node(s)
   1.514 -    ///in order to
   1.515 -    ///compute the
   1.516 -    ///shortest path to each node. The algorithm computes
   1.517 -    ///- The shortest path tree.
   1.518 -    ///- The distance of each node from the root(s).
   1.519 +    ///The algorithm computes
   1.520 +    ///- the shortest path tree (forest),
   1.521 +    ///- the distance of each node from the root(s).
   1.522 +    ///
   1.523 +    ///\pre init() must be called and at least one root node should be
   1.524 +    ///added with addSource() before using this function.
   1.525 +    ///
   1.526 +    ///\note <tt>b.start()</tt> is just a shortcut of the following code.
   1.527 +    ///\code
   1.528 +    ///  while ( !b.emptyQueue() ) {
   1.529 +    ///    b.processNextNode();
   1.530 +    ///  }
   1.531 +    ///\endcode
   1.532      void start()
   1.533      {
   1.534        while ( !emptyQueue() ) processNextNode();
   1.535      }
   1.536  
   1.537 -    ///Executes the algorithm until \c dest is reached.
   1.538 +    ///Executes the algorithm until the given target node is reached.
   1.539  
   1.540 -    ///Executes the algorithm until \c dest is reached.
   1.541 -    ///
   1.542 -    ///\pre init() must be called and at least one node should be added
   1.543 -    ///with addSource() before using this function.
   1.544 +    ///Executes the algorithm until the given target node is reached.
   1.545      ///
   1.546      ///This method runs the %BFS algorithm from the root node(s)
   1.547      ///in order to compute the shortest path to \c dest.
   1.548 +    ///
   1.549      ///The algorithm computes
   1.550 -    ///- The shortest path to \c  dest.
   1.551 -    ///- The distance of \c dest from the root(s).
   1.552 +    ///- the shortest path to \c dest,
   1.553 +    ///- the distance of \c dest from the root(s).
   1.554 +    ///
   1.555 +    ///\pre init() must be called and at least one root node should be
   1.556 +    ///added with addSource() before using this function.
   1.557 +    ///
   1.558 +    ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
   1.559 +    ///\code
   1.560 +    ///  bool reach = false;
   1.561 +    ///  while ( !b.emptyQueue() && !reach ) {
   1.562 +    ///    b.processNextNode(t, reach);
   1.563 +    ///  }
   1.564 +    ///\endcode
   1.565      void start(Node dest)
   1.566      {
   1.567        bool reach = false;
   1.568 @@ -607,17 +633,29 @@
   1.569  
   1.570      ///Executes the algorithm until a condition is met.
   1.571      ///
   1.572 -    ///\pre init() must be called and at least one node should be added
   1.573 -    ///with addSource() before using this function.
   1.574 +    ///This method runs the %BFS algorithm from the root node(s) in
   1.575 +    ///order to compute the shortest path to a node \c v with
   1.576 +    /// <tt>nm[v]</tt> true, if such a node can be found.
   1.577      ///
   1.578 -    ///\param nm must be a bool (or convertible) node map. The
   1.579 -    ///algorithm will stop when it reaches a node \c v with
   1.580 -    /// <tt>nm[v]</tt> true.
   1.581 +    ///\param nm A \c bool (or convertible) node map. The algorithm
   1.582 +    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   1.583      ///
   1.584      ///\return The reached node \c v with <tt>nm[v]</tt> true or
   1.585      ///\c INVALID if no such node was found.
   1.586 -    template<class NM>
   1.587 -    Node start(const NM &nm)
   1.588 +    ///
   1.589 +    ///\pre init() must be called and at least one root node should be
   1.590 +    ///added with addSource() before using this function.
   1.591 +    ///
   1.592 +    ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
   1.593 +    ///\code
   1.594 +    ///  Node rnode = INVALID;
   1.595 +    ///  while ( !b.emptyQueue() && rnode == INVALID ) {
   1.596 +    ///    b.processNextNode(nm, rnode);
   1.597 +    ///  }
   1.598 +    ///  return rnode;
   1.599 +    ///\endcode
   1.600 +    template<class NodeBoolMap>
   1.601 +    Node start(const NodeBoolMap &nm)
   1.602      {
   1.603        Node rnode = INVALID;
   1.604        while ( !emptyQueue() && rnode == INVALID ) {
   1.605 @@ -626,16 +664,16 @@
   1.606        return rnode;
   1.607      }
   1.608  
   1.609 -    ///Runs %BFS algorithm from node \c s.
   1.610 +    ///Runs the algorithm from the given node.
   1.611  
   1.612 -    ///This method runs the %BFS algorithm from a root node \c s
   1.613 -    ///in order to
   1.614 -    ///compute the
   1.615 -    ///shortest path to each node. The algorithm computes
   1.616 -    ///- The shortest path tree.
   1.617 -    ///- The distance of each node from the root.
   1.618 +    ///This method runs the %BFS algorithm from node \c s
   1.619 +    ///in order to compute the shortest path to each node.
   1.620      ///
   1.621 -    ///\note b.run(s) is just a shortcut of the following code.
   1.622 +    ///The algorithm computes
   1.623 +    ///- the shortest path tree,
   1.624 +    ///- the distance of each node from the root.
   1.625 +    ///
   1.626 +    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
   1.627      ///\code
   1.628      ///  b.init();
   1.629      ///  b.addSource(s);
   1.630 @@ -649,12 +687,14 @@
   1.631  
   1.632      ///Finds the shortest path between \c s and \c t.
   1.633  
   1.634 -    ///Finds the shortest path between \c s and \c t.
   1.635 +    ///This method runs the %BFS algorithm from node \c s
   1.636 +    ///in order to compute the shortest path to \c t.
   1.637      ///
   1.638 -    ///\return The length of the shortest s---t path if there exists one,
   1.639 -    ///0 otherwise.
   1.640 -    ///\note Apart from the return value, b.run(s) is
   1.641 -    ///just a shortcut of the following code.
   1.642 +    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
   1.643 +    ///if \c t is reachable form \c s, \c 0 otherwise.
   1.644 +    ///
   1.645 +    ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
   1.646 +    ///shortcut of the following code.
   1.647      ///\code
   1.648      ///  b.init();
   1.649      ///  b.addSource(s);
   1.650 @@ -667,116 +707,152 @@
   1.651        return reached(t) ? _curr_dist : 0;
   1.652      }
   1.653  
   1.654 +    ///Runs the algorithm to visit all nodes in the digraph.
   1.655 +
   1.656 +    ///This method runs the %BFS algorithm in order to
   1.657 +    ///compute the shortest path to each node.
   1.658 +    ///
   1.659 +    ///The algorithm computes
   1.660 +    ///- the shortest path tree (forest),
   1.661 +    ///- the distance of each node from the root(s).
   1.662 +    ///
   1.663 +    ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
   1.664 +    ///\code
   1.665 +    ///  b.init();
   1.666 +    ///  for (NodeIt n(gr); n != INVALID; ++n) {
   1.667 +    ///    if (!b.reached(n)) {
   1.668 +    ///      b.addSource(n);
   1.669 +    ///      b.start();
   1.670 +    ///    }
   1.671 +    ///  }
   1.672 +    ///\endcode
   1.673 +    void run() {
   1.674 +      init();
   1.675 +      for (NodeIt n(*G); n != INVALID; ++n) {
   1.676 +        if (!reached(n)) {
   1.677 +          addSource(n);
   1.678 +          start();
   1.679 +        }
   1.680 +      }
   1.681 +    }
   1.682 +
   1.683      ///@}
   1.684  
   1.685      ///\name Query Functions
   1.686      ///The result of the %BFS algorithm can be obtained using these
   1.687      ///functions.\n
   1.688 -    ///Before the use of these functions,
   1.689 -    ///either run() or start() must be calleb.
   1.690 +    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
   1.691 +    ///"start()" must be called before using them.
   1.692  
   1.693      ///@{
   1.694  
   1.695 -    typedef PredMapPath<Digraph, PredMap> Path;
   1.696 +    ///The shortest path to a node.
   1.697  
   1.698 -    ///Gives back the shortest path.
   1.699 -
   1.700 -    ///Gives back the shortest path.
   1.701 -    ///\pre The \c t should be reachable from the source.
   1.702 -    Path path(Node t)
   1.703 -    {
   1.704 -      return Path(*G, *_pred, t);
   1.705 -    }
   1.706 +    ///Returns the shortest path to a node.
   1.707 +    ///
   1.708 +    ///\warning \c t should be reachable from the root(s).
   1.709 +    ///
   1.710 +    ///\pre Either \ref run() or \ref start() must be called before
   1.711 +    ///using this function.
   1.712 +    Path path(Node t) const { return Path(*G, *_pred, t); }
   1.713  
   1.714      ///The distance of a node from the root(s).
   1.715  
   1.716      ///Returns the distance of a node from the root(s).
   1.717 -    ///\pre \ref run() must be called before using this function.
   1.718 -    ///\warning If node \c v in unreachable from the root(s) the return value
   1.719 -    ///of this function is undefined.
   1.720 +    ///
   1.721 +    ///\warning If node \c v is not reachable from the root(s), then
   1.722 +    ///the return value of this function is undefined.
   1.723 +    ///
   1.724 +    ///\pre Either \ref run() or \ref start() must be called before
   1.725 +    ///using this function.
   1.726      int dist(Node v) const { return (*_dist)[v]; }
   1.727  
   1.728 -    ///Returns the 'previous arc' of the shortest path tree.
   1.729 +    ///Returns the 'previous arc' of the shortest path tree for a node.
   1.730  
   1.731 -    ///For a node \c v it returns the 'previous arc'
   1.732 -    ///of the shortest path tree,
   1.733 -    ///i.e. it returns the last arc of a shortest path from the root(s) to \c
   1.734 -    ///v. It is \ref INVALID
   1.735 -    ///if \c v is unreachable from the root(s) or \c v is a root. The
   1.736 -    ///shortest path tree used here is equal to the shortest path tree used in
   1.737 -    ///\ref predNode().
   1.738 -    ///\pre Either \ref run() or \ref start() must be called before using
   1.739 -    ///this function.
   1.740 +    ///This function returns the 'previous arc' of the shortest path
   1.741 +    ///tree for the node \c v, i.e. it returns the last arc of a
   1.742 +    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   1.743 +    ///is not reachable from the root(s) or if \c v is a root.
   1.744 +    ///
   1.745 +    ///The shortest path tree used here is equal to the shortest path
   1.746 +    ///tree used in \ref predNode().
   1.747 +    ///
   1.748 +    ///\pre Either \ref run() or \ref start() must be called before
   1.749 +    ///using this function.
   1.750      Arc predArc(Node v) const { return (*_pred)[v];}
   1.751  
   1.752 -    ///Returns the 'previous node' of the shortest path tree.
   1.753 +    ///Returns the 'previous node' of the shortest path tree for a node.
   1.754  
   1.755 -    ///For a node \c v it returns the 'previous node'
   1.756 -    ///of the shortest path tree,
   1.757 -    ///i.e. it returns the last but one node from a shortest path from the
   1.758 -    ///root(a) to \c /v.
   1.759 -    ///It is INVALID if \c v is unreachable from the root(s) or
   1.760 -    ///if \c v itself a root.
   1.761 +    ///This function returns the 'previous node' of the shortest path
   1.762 +    ///tree for the node \c v, i.e. it returns the last but one node
   1.763 +    ///from a shortest path from the root(s) to \c v. It is \c INVALID
   1.764 +    ///if \c v is not reachable from the root(s) or if \c v is a root.
   1.765 +    ///
   1.766      ///The shortest path tree used here is equal to the shortest path
   1.767      ///tree used in \ref predArc().
   1.768 +    ///
   1.769      ///\pre Either \ref run() or \ref start() must be called before
   1.770      ///using this function.
   1.771      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   1.772                                    G->source((*_pred)[v]); }
   1.773  
   1.774 -    ///Returns a reference to the NodeMap of distances.
   1.775 -
   1.776 -    ///Returns a reference to the NodeMap of distances.
   1.777 -    ///\pre Either \ref run() or \ref init() must
   1.778 -    ///be called before using this function.
   1.779 +    ///\brief Returns a const reference to the node map that stores the
   1.780 +    /// distances of the nodes.
   1.781 +    ///
   1.782 +    ///Returns a const reference to the node map that stores the distances
   1.783 +    ///of the nodes calculated by the algorithm.
   1.784 +    ///
   1.785 +    ///\pre Either \ref run() or \ref init()
   1.786 +    ///must be called before using this function.
   1.787      const DistMap &distMap() const { return *_dist;}
   1.788  
   1.789 -    ///Returns a reference to the shortest path tree map.
   1.790 -
   1.791 -    ///Returns a reference to the NodeMap of the arcs of the
   1.792 -    ///shortest path tree.
   1.793 +    ///\brief Returns a const reference to the node map that stores the
   1.794 +    ///predecessor arcs.
   1.795 +    ///
   1.796 +    ///Returns a const reference to the node map that stores the predecessor
   1.797 +    ///arcs, which form the shortest path tree.
   1.798 +    ///
   1.799      ///\pre Either \ref run() or \ref init()
   1.800      ///must be called before using this function.
   1.801      const PredMap &predMap() const { return *_pred;}
   1.802  
   1.803 -    ///Checks if a node is reachable from the root.
   1.804 +    ///Checks if a node is reachable from the root(s).
   1.805  
   1.806 -    ///Returns \c true if \c v is reachable from the root.
   1.807 -    ///\warning The source nodes are indicated as unreached.
   1.808 +    ///Returns \c true if \c v is reachable from the root(s).
   1.809      ///\pre Either \ref run() or \ref start()
   1.810      ///must be called before using this function.
   1.811 -    ///
   1.812 -    bool reached(Node v) { return (*_reached)[v]; }
   1.813 +    bool reached(Node v) const { return (*_reached)[v]; }
   1.814  
   1.815      ///@}
   1.816    };
   1.817  
   1.818 -  ///Default traits class of Bfs function.
   1.819 +  ///Default traits class of bfs() function.
   1.820  
   1.821 -  ///Default traits class of Bfs function.
   1.822 +  ///Default traits class of bfs() function.
   1.823    ///\tparam GR Digraph type.
   1.824    template<class GR>
   1.825    struct BfsWizardDefaultTraits
   1.826    {
   1.827 -    ///The digraph type the algorithm runs on.
   1.828 +    ///The type of the digraph the algorithm runs on.
   1.829      typedef GR Digraph;
   1.830 -    ///\brief The type of the map that stores the last
   1.831 +
   1.832 +    ///\brief The type of the map that stores the predecessor
   1.833      ///arcs of the shortest paths.
   1.834      ///
   1.835 -    ///The type of the map that stores the last
   1.836 +    ///The type of the map that stores the predecessor
   1.837      ///arcs of the shortest paths.
   1.838      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.839 -    ///
   1.840 -    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
   1.841 -    ///Instantiates a PredMap.
   1.842 +    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
   1.843 +    ///Instantiates a \ref PredMap.
   1.844  
   1.845      ///This function instantiates a \ref PredMap.
   1.846 -    ///\param g is the digraph, to which we would like to define the PredMap.
   1.847 +    ///\param g is the digraph, to which we would like to define the
   1.848 +    ///\ref PredMap.
   1.849      ///\todo The digraph alone may be insufficient to initialize
   1.850  #ifdef DOXYGEN
   1.851 -    static PredMap *createPredMap(const GR &g)
   1.852 +    static PredMap *createPredMap(const Digraph &g)
   1.853  #else
   1.854 -    static PredMap *createPredMap(const GR &)
   1.855 +    static PredMap *createPredMap(const Digraph &)
   1.856  #endif
   1.857      {
   1.858        return new PredMap();
   1.859 @@ -786,63 +862,63 @@
   1.860  
   1.861      ///The type of the map that indicates which nodes are processed.
   1.862      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.863 -    ///\todo named parameter to set this type, function to read and write.
   1.864      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   1.865 -    ///Instantiates a ProcessedMap.
   1.866 +    ///Instantiates a \ref ProcessedMap.
   1.867  
   1.868      ///This function instantiates a \ref ProcessedMap.
   1.869      ///\param g is the digraph, to which
   1.870 -    ///we would like to define the \ref ProcessedMap
   1.871 +    ///we would like to define the \ref ProcessedMap.
   1.872  #ifdef DOXYGEN
   1.873 -    static ProcessedMap *createProcessedMap(const GR &g)
   1.874 +    static ProcessedMap *createProcessedMap(const Digraph &g)
   1.875  #else
   1.876 -    static ProcessedMap *createProcessedMap(const GR &)
   1.877 +    static ProcessedMap *createProcessedMap(const Digraph &)
   1.878  #endif
   1.879      {
   1.880        return new ProcessedMap();
   1.881      }
   1.882 +
   1.883      ///The type of the map that indicates which nodes are reached.
   1.884  
   1.885      ///The type of the map that indicates which nodes are reached.
   1.886 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.887 -    ///\todo named parameter to set this type, function to read and write.
   1.888 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   1.889      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   1.890 -    ///Instantiates a ReachedMap.
   1.891 +    ///Instantiates a \ref ReachedMap.
   1.892  
   1.893      ///This function instantiates a \ref ReachedMap.
   1.894 -    ///\param G is the digraph, to which
   1.895 +    ///\param g is the digraph, to which
   1.896      ///we would like to define the \ref ReachedMap.
   1.897 -    static ReachedMap *createReachedMap(const GR &G)
   1.898 +    static ReachedMap *createReachedMap(const Digraph &g)
   1.899      {
   1.900 -      return new ReachedMap(G);
   1.901 +      return new ReachedMap(g);
   1.902      }
   1.903 -    ///The type of the map that stores the dists of the nodes.
   1.904  
   1.905 -    ///The type of the map that stores the dists of the nodes.
   1.906 +    ///The type of the map that stores the distances of the nodes.
   1.907 +
   1.908 +    ///The type of the map that stores the distances of the nodes.
   1.909      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.910      ///
   1.911      typedef NullMap<typename Digraph::Node,int> DistMap;
   1.912 -    ///Instantiates a DistMap.
   1.913 +    ///Instantiates a \ref DistMap.
   1.914  
   1.915      ///This function instantiates a \ref DistMap.
   1.916      ///\param g is the digraph, to which we would like to define
   1.917      ///the \ref DistMap
   1.918  #ifdef DOXYGEN
   1.919 -    static DistMap *createDistMap(const GR &g)
   1.920 +    static DistMap *createDistMap(const Digraph &g)
   1.921  #else
   1.922 -    static DistMap *createDistMap(const GR &)
   1.923 +    static DistMap *createDistMap(const Digraph &)
   1.924  #endif
   1.925      {
   1.926        return new DistMap();
   1.927      }
   1.928    };
   1.929  
   1.930 -  /// Default traits used by \ref BfsWizard
   1.931 +  /// Default traits class used by \ref BfsWizard
   1.932  
   1.933    /// To make it easier to use Bfs algorithm
   1.934 -  ///we have created a wizard class.
   1.935 +  /// we have created a wizard class.
   1.936    /// This \ref BfsWizard class needs default traits,
   1.937 -  ///as well as the \ref Bfs class.
   1.938 +  /// as well as the \ref Bfs class.
   1.939    /// The \ref BfsWizardBase is a class to be the default traits of the
   1.940    /// \ref BfsWizard class.
   1.941    template<class GR>
   1.942 @@ -851,20 +927,20 @@
   1.943  
   1.944      typedef BfsWizardDefaultTraits<GR> Base;
   1.945    protected:
   1.946 -    /// Type of the nodes in the digraph.
   1.947 +    //The type of the nodes in the digraph.
   1.948      typedef typename Base::Digraph::Node Node;
   1.949  
   1.950 -    /// Pointer to the underlying digraph.
   1.951 +    //Pointer to the digraph the algorithm runs on.
   1.952      void *_g;
   1.953 -    ///Pointer to the map of reached nodes.
   1.954 +    //Pointer to the map of reached nodes.
   1.955      void *_reached;
   1.956 -    ///Pointer to the map of processed nodes.
   1.957 +    //Pointer to the map of processed nodes.
   1.958      void *_processed;
   1.959 -    ///Pointer to the map of predecessors arcs.
   1.960 +    //Pointer to the map of predecessors arcs.
   1.961      void *_pred;
   1.962 -    ///Pointer to the map of distances.
   1.963 +    //Pointer to the map of distances.
   1.964      void *_dist;
   1.965 -    ///Pointer to the source node.
   1.966 +    //Pointer to the source node.
   1.967      Node _source;
   1.968  
   1.969      public:
   1.970 @@ -873,26 +949,28 @@
   1.971      /// This constructor does not require parameters, therefore it initiates
   1.972      /// all of the attributes to default values (0, INVALID).
   1.973      BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   1.974 -                           _dist(0), _source(INVALID) {}
   1.975 +                      _dist(0), _source(INVALID) {}
   1.976  
   1.977      /// Constructor.
   1.978  
   1.979      /// This constructor requires some parameters,
   1.980      /// listed in the parameters list.
   1.981      /// Others are initiated to 0.
   1.982 -    /// \param g is the initial value of  \ref _g
   1.983 -    /// \param s is the initial value of  \ref _source
   1.984 +    /// \param g The digraph the algorithm runs on.
   1.985 +    /// \param s The source node.
   1.986      BfsWizardBase(const GR &g, Node s=INVALID) :
   1.987        _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   1.988        _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   1.989  
   1.990    };
   1.991  
   1.992 -  /// A class to make the usage of Bfs algorithm easier
   1.993 +  /// Auxiliary class for the function type interface of BFS algorithm.
   1.994  
   1.995 -  /// This class is created to make it easier to use Bfs algorithm.
   1.996 -  /// It uses the functions and features of the plain \ref Bfs,
   1.997 -  /// but it is much simpler to use it.
   1.998 +  /// This auxiliary class is created to implement the function type
   1.999 +  /// interface of \ref Bfs algorithm. It uses the functions and features
  1.1000 +  /// of the plain \ref Bfs, but it is much simpler to use it.
  1.1001 +  /// It should only be used through the \ref bfs() function, which makes
  1.1002 +  /// it easier to use the algorithm.
  1.1003    ///
  1.1004    /// Simplicity means that the way to change the types defined
  1.1005    /// in the traits class is based on functions that returns the new class
  1.1006 @@ -901,41 +979,37 @@
  1.1007    /// the new class with the modified type comes from
  1.1008    /// the original class by using the ::
  1.1009    /// operator. In the case of \ref BfsWizard only
  1.1010 -  /// a function have to be called and it will
  1.1011 +  /// a function have to be called, and it will
  1.1012    /// return the needed class.
  1.1013    ///
  1.1014 -  /// It does not have own \ref run method. When its \ref run method is called
  1.1015 -  /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
  1.1016 -  /// method of it.
  1.1017 +  /// It does not have own \ref run() method. When its \ref run() method
  1.1018 +  /// is called, it initiates a plain \ref Bfs object, and calls the
  1.1019 +  /// \ref Bfs::run() method of it.
  1.1020    template<class TR>
  1.1021    class BfsWizard : public TR
  1.1022    {
  1.1023      typedef TR Base;
  1.1024  
  1.1025 -    ///The type of the underlying digraph.
  1.1026 +    ///The type of the digraph the algorithm runs on.
  1.1027      typedef typename TR::Digraph Digraph;
  1.1028 -    //\e
  1.1029 +
  1.1030      typedef typename Digraph::Node Node;
  1.1031 -    //\e
  1.1032      typedef typename Digraph::NodeIt NodeIt;
  1.1033 -    //\e
  1.1034      typedef typename Digraph::Arc Arc;
  1.1035 -    //\e
  1.1036      typedef typename Digraph::OutArcIt OutArcIt;
  1.1037  
  1.1038 -    ///\brief The type of the map that stores
  1.1039 -    ///the reached nodes
  1.1040 -    typedef typename TR::ReachedMap ReachedMap;
  1.1041 -    ///\brief The type of the map that stores
  1.1042 -    ///the processed nodes
  1.1043 -    typedef typename TR::ProcessedMap ProcessedMap;
  1.1044 -    ///\brief The type of the map that stores the last
  1.1045 +    ///\brief The type of the map that stores the predecessor
  1.1046      ///arcs of the shortest paths.
  1.1047      typedef typename TR::PredMap PredMap;
  1.1048 -    ///The type of the map that stores the dists of the nodes.
  1.1049 +    ///\brief The type of the map that stores the distances of the nodes.
  1.1050      typedef typename TR::DistMap DistMap;
  1.1051 +    ///\brief The type of the map that indicates which nodes are reached.
  1.1052 +    typedef typename TR::ReachedMap ReachedMap;
  1.1053 +    ///\brief The type of the map that indicates which nodes are processed.
  1.1054 +    typedef typename TR::ProcessedMap ProcessedMap;
  1.1055  
  1.1056    public:
  1.1057 +
  1.1058      /// Constructor.
  1.1059      BfsWizard() : TR() {}
  1.1060  
  1.1061 @@ -951,10 +1025,10 @@
  1.1062  
  1.1063      ~BfsWizard() {}
  1.1064  
  1.1065 -    ///Runs Bfs algorithm from a given node.
  1.1066 +    ///Runs BFS algorithm from a source node.
  1.1067  
  1.1068 -    ///Runs Bfs algorithm from a given node.
  1.1069 -    ///The node can be given by the \ref source function.
  1.1070 +    ///Runs BFS algorithm from a source node.
  1.1071 +    ///The node can be given with the \ref source() function.
  1.1072      void run()
  1.1073      {
  1.1074        if(Base::_source==INVALID) throw UninitializedParameter();
  1.1075 @@ -970,9 +1044,9 @@
  1.1076        alg.run(Base::_source);
  1.1077      }
  1.1078  
  1.1079 -    ///Runs Bfs algorithm from the given node.
  1.1080 +    ///Runs BFS algorithm from the given node.
  1.1081  
  1.1082 -    ///Runs Bfs algorithm from the given node.
  1.1083 +    ///Runs BFS algorithm from the given node.
  1.1084      ///\param s is the given source.
  1.1085      void run(Node s)
  1.1086      {
  1.1087 @@ -980,89 +1054,6 @@
  1.1088        run();
  1.1089      }
  1.1090  
  1.1091 -    template<class T>
  1.1092 -    struct DefPredMapBase : public Base {
  1.1093 -      typedef T PredMap;
  1.1094 -      static PredMap *createPredMap(const Digraph &) { return 0; };
  1.1095 -      DefPredMapBase(const TR &b) : TR(b) {}
  1.1096 -    };
  1.1097 -
  1.1098 -    ///\brief \ref named-templ-param "Named parameter"
  1.1099 -    ///function for setting PredMap
  1.1100 -    ///
  1.1101 -    /// \ref named-templ-param "Named parameter"
  1.1102 -    ///function for setting PredMap
  1.1103 -    ///
  1.1104 -    template<class T>
  1.1105 -    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
  1.1106 -    {
  1.1107 -      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1108 -      return BfsWizard<DefPredMapBase<T> >(*this);
  1.1109 -    }
  1.1110 -
  1.1111 -
  1.1112 -    template<class T>
  1.1113 -    struct DefReachedMapBase : public Base {
  1.1114 -      typedef T ReachedMap;
  1.1115 -      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1.1116 -      DefReachedMapBase(const TR &b) : TR(b) {}
  1.1117 -    };
  1.1118 -
  1.1119 -    ///\brief \ref named-templ-param "Named parameter"
  1.1120 -    ///function for setting ReachedMap
  1.1121 -    ///
  1.1122 -    /// \ref named-templ-param "Named parameter"
  1.1123 -    ///function for setting ReachedMap
  1.1124 -    ///
  1.1125 -    template<class T>
  1.1126 -    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  1.1127 -    {
  1.1128 -      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1129 -      return BfsWizard<DefReachedMapBase<T> >(*this);
  1.1130 -    }
  1.1131 -
  1.1132 -
  1.1133 -    template<class T>
  1.1134 -    struct DefProcessedMapBase : public Base {
  1.1135 -      typedef T ProcessedMap;
  1.1136 -      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1.1137 -      DefProcessedMapBase(const TR &b) : TR(b) {}
  1.1138 -    };
  1.1139 -
  1.1140 -    ///\brief \ref named-templ-param "Named parameter"
  1.1141 -    ///function for setting ProcessedMap
  1.1142 -    ///
  1.1143 -    /// \ref named-templ-param "Named parameter"
  1.1144 -    ///function for setting ProcessedMap
  1.1145 -    ///
  1.1146 -    template<class T>
  1.1147 -    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  1.1148 -    {
  1.1149 -      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1150 -      return BfsWizard<DefProcessedMapBase<T> >(*this);
  1.1151 -    }
  1.1152 -
  1.1153 -
  1.1154 -    template<class T>
  1.1155 -    struct DefDistMapBase : public Base {
  1.1156 -      typedef T DistMap;
  1.1157 -      static DistMap *createDistMap(const Digraph &) { return 0; };
  1.1158 -      DefDistMapBase(const TR &b) : TR(b) {}
  1.1159 -    };
  1.1160 -
  1.1161 -    ///\brief \ref named-templ-param "Named parameter"
  1.1162 -    ///function for setting DistMap type
  1.1163 -    ///
  1.1164 -    /// \ref named-templ-param "Named parameter"
  1.1165 -    ///function for setting DistMap type
  1.1166 -    ///
  1.1167 -    template<class T>
  1.1168 -    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
  1.1169 -    {
  1.1170 -      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1171 -      return BfsWizard<DefDistMapBase<T> >(*this);
  1.1172 -    }
  1.1173 -
  1.1174      /// Sets the source node, from which the Bfs algorithm runs.
  1.1175  
  1.1176      /// Sets the source node, from which the Bfs algorithm runs.
  1.1177 @@ -1073,6 +1064,78 @@
  1.1178        return *this;
  1.1179      }
  1.1180  
  1.1181 +    template<class T>
  1.1182 +    struct DefPredMapBase : public Base {
  1.1183 +      typedef T PredMap;
  1.1184 +      static PredMap *createPredMap(const Digraph &) { return 0; };
  1.1185 +      DefPredMapBase(const TR &b) : TR(b) {}
  1.1186 +    };
  1.1187 +    ///\brief \ref named-templ-param "Named parameter"
  1.1188 +    ///for setting \ref PredMap object.
  1.1189 +    ///
  1.1190 +    /// \ref named-templ-param "Named parameter"
  1.1191 +    ///for setting \ref PredMap object.
  1.1192 +    template<class T>
  1.1193 +    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
  1.1194 +    {
  1.1195 +      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1196 +      return BfsWizard<DefPredMapBase<T> >(*this);
  1.1197 +    }
  1.1198 +
  1.1199 +    template<class T>
  1.1200 +    struct DefReachedMapBase : public Base {
  1.1201 +      typedef T ReachedMap;
  1.1202 +      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1.1203 +      DefReachedMapBase(const TR &b) : TR(b) {}
  1.1204 +    };
  1.1205 +    ///\brief \ref named-templ-param "Named parameter"
  1.1206 +    ///for setting \ref ReachedMap object.
  1.1207 +    ///
  1.1208 +    /// \ref named-templ-param "Named parameter"
  1.1209 +    ///for setting \ref ReachedMap object.
  1.1210 +    template<class T>
  1.1211 +    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  1.1212 +    {
  1.1213 +      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1214 +      return BfsWizard<DefReachedMapBase<T> >(*this);
  1.1215 +    }
  1.1216 +
  1.1217 +    template<class T>
  1.1218 +    struct DefProcessedMapBase : public Base {
  1.1219 +      typedef T ProcessedMap;
  1.1220 +      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1.1221 +      DefProcessedMapBase(const TR &b) : TR(b) {}
  1.1222 +    };
  1.1223 +    ///\brief \ref named-templ-param "Named parameter"
  1.1224 +    ///for setting \ref ProcessedMap object.
  1.1225 +    ///
  1.1226 +    /// \ref named-templ-param "Named parameter"
  1.1227 +    ///for setting \ref ProcessedMap object.
  1.1228 +    template<class T>
  1.1229 +    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  1.1230 +    {
  1.1231 +      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1232 +      return BfsWizard<DefProcessedMapBase<T> >(*this);
  1.1233 +    }
  1.1234 +
  1.1235 +    template<class T>
  1.1236 +    struct DefDistMapBase : public Base {
  1.1237 +      typedef T DistMap;
  1.1238 +      static DistMap *createDistMap(const Digraph &) { return 0; };
  1.1239 +      DefDistMapBase(const TR &b) : TR(b) {}
  1.1240 +    };
  1.1241 +    ///\brief \ref named-templ-param "Named parameter"
  1.1242 +    ///for setting \ref DistMap object.
  1.1243 +    ///
  1.1244 +    /// \ref named-templ-param "Named parameter"
  1.1245 +    ///for setting \ref DistMap object.
  1.1246 +    template<class T>
  1.1247 +    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
  1.1248 +    {
  1.1249 +      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1250 +      return BfsWizard<DefDistMapBase<T> >(*this);
  1.1251 +    }
  1.1252 +
  1.1253    };
  1.1254  
  1.1255    ///Function type interface for Bfs algorithm.
  1.1256 @@ -1100,38 +1163,38 @@
  1.1257    }
  1.1258  
  1.1259  #ifdef DOXYGEN
  1.1260 -  /// \brief Visitor class for bfs.
  1.1261 +  /// \brief Visitor class for BFS.
  1.1262    ///
  1.1263    /// This class defines the interface of the BfsVisit events, and
  1.1264 -  /// it could be the base of a real Visitor class.
  1.1265 +  /// it could be the base of a real visitor class.
  1.1266    template <typename _Digraph>
  1.1267    struct BfsVisitor {
  1.1268      typedef _Digraph Digraph;
  1.1269      typedef typename Digraph::Arc Arc;
  1.1270      typedef typename Digraph::Node Node;
  1.1271 -    /// \brief Called when the arc reach a node.
  1.1272 +    /// \brief Called for the source node(s) of the BFS.
  1.1273      ///
  1.1274 -    /// It is called when the bfs find an arc which target is not
  1.1275 -    /// reached yet.
  1.1276 +    /// This function is called for the source node(s) of the BFS.
  1.1277 +    void start(const Node& node) {}
  1.1278 +    /// \brief Called when a node is reached first time.
  1.1279 +    ///
  1.1280 +    /// This function is called when a node is reached first time.
  1.1281 +    void reach(const Node& node) {}
  1.1282 +    /// \brief Called when a node is processed.
  1.1283 +    ///
  1.1284 +    /// This function is called when a node is processed.
  1.1285 +    void process(const Node& node) {}
  1.1286 +    /// \brief Called when an arc reaches a new node.
  1.1287 +    ///
  1.1288 +    /// This function is called when the BFS finds an arc whose target node
  1.1289 +    /// is not reached yet.
  1.1290      void discover(const Arc& arc) {}
  1.1291 -    /// \brief Called when the node reached first time.
  1.1292 -    ///
  1.1293 -    /// It is Called when the node reached first time.
  1.1294 -    void reach(const Node& node) {}
  1.1295 -    /// \brief Called when the arc examined but target of the arc
  1.1296 +    /// \brief Called when an arc is examined but its target node is
  1.1297      /// already discovered.
  1.1298      ///
  1.1299 -    /// It called when the arc examined but the target of the arc
  1.1300 +    /// This function is called when an arc is examined but its target node is
  1.1301      /// already discovered.
  1.1302      void examine(const Arc& arc) {}
  1.1303 -    /// \brief Called for the source node of the bfs.
  1.1304 -    ///
  1.1305 -    /// It is called for the source node of the bfs.
  1.1306 -    void start(const Node& node) {}
  1.1307 -    /// \brief Called when the node processed.
  1.1308 -    ///
  1.1309 -    /// It is Called when the node processed.
  1.1310 -    void process(const Node& node) {}
  1.1311    };
  1.1312  #else
  1.1313    template <typename _Digraph>
  1.1314 @@ -1139,22 +1202,22 @@
  1.1315      typedef _Digraph Digraph;
  1.1316      typedef typename Digraph::Arc Arc;
  1.1317      typedef typename Digraph::Node Node;
  1.1318 +    void start(const Node&) {}
  1.1319 +    void reach(const Node&) {}
  1.1320 +    void process(const Node&) {}
  1.1321      void discover(const Arc&) {}
  1.1322 -    void reach(const Node&) {}
  1.1323      void examine(const Arc&) {}
  1.1324 -    void start(const Node&) {}
  1.1325 -    void process(const Node&) {}
  1.1326  
  1.1327      template <typename _Visitor>
  1.1328      struct Constraints {
  1.1329        void constraints() {
  1.1330          Arc arc;
  1.1331          Node node;
  1.1332 +        visitor.start(node);
  1.1333 +        visitor.reach(node);
  1.1334 +        visitor.process(node);
  1.1335          visitor.discover(arc);
  1.1336 -        visitor.reach(node);
  1.1337          visitor.examine(arc);
  1.1338 -        visitor.start(node);
  1.1339 -        visitor.process(node);
  1.1340        }
  1.1341        _Visitor& visitor;
  1.1342      };
  1.1343 @@ -1164,21 +1227,20 @@
  1.1344    /// \brief Default traits class of BfsVisit class.
  1.1345    ///
  1.1346    /// Default traits class of BfsVisit class.
  1.1347 -  /// \tparam _Digraph Digraph type.
  1.1348 +  /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1.1349    template<class _Digraph>
  1.1350    struct BfsVisitDefaultTraits {
  1.1351  
  1.1352 -    /// \brief The digraph type the algorithm runs on.
  1.1353 +    /// \brief The type of the digraph the algorithm runs on.
  1.1354      typedef _Digraph Digraph;
  1.1355  
  1.1356      /// \brief The type of the map that indicates which nodes are reached.
  1.1357      ///
  1.1358      /// The type of the map that indicates which nodes are reached.
  1.1359 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1.1360 -    /// \todo named parameter to set this type, function to read and write.
  1.1361 +    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1.1362      typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1.1363  
  1.1364 -    /// \brief Instantiates a ReachedMap.
  1.1365 +    /// \brief Instantiates a \ref ReachedMap.
  1.1366      ///
  1.1367      /// This function instantiates a \ref ReachedMap.
  1.1368      /// \param digraph is the digraph, to which
  1.1369 @@ -1191,28 +1253,28 @@
  1.1370  
  1.1371    /// \ingroup search
  1.1372    ///
  1.1373 -  /// \brief %BFS Visit algorithm class.
  1.1374 +  /// \brief %BFS algorithm class with visitor interface.
  1.1375    ///
  1.1376    /// This class provides an efficient implementation of the %BFS algorithm
  1.1377    /// with visitor interface.
  1.1378    ///
  1.1379    /// The %BfsVisit class provides an alternative interface to the Bfs
  1.1380    /// class. It works with callback mechanism, the BfsVisit object calls
  1.1381 -  /// on every bfs event the \c Visitor class member functions.
  1.1382 +  /// the member functions of the \c Visitor class on every BFS event.
  1.1383    ///
  1.1384 -  /// \tparam _Digraph The digraph type the algorithm runs on.
  1.1385 +  /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1.1386    /// The default value is
  1.1387 -  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
  1.1388 -  /// is only passed to \ref BfsDefaultTraits.
  1.1389 -  /// \tparam _Visitor The Visitor object for the algorithm. The
  1.1390 -  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
  1.1391 -  /// does not observe the Bfs events. If you want to observe the bfs
  1.1392 -  /// events you should implement your own Visitor class.
  1.1393 +  /// \ref ListDigraph. The value of _Digraph is not used directly by
  1.1394 +  /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
  1.1395 +  /// \tparam _Visitor The Visitor type that is used by the algorithm.
  1.1396 +  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
  1.1397 +  /// does not observe the BFS events. If you want to observe the BFS
  1.1398 +  /// events, you should implement your own visitor class.
  1.1399    /// \tparam _Traits Traits class to set various data types used by the
  1.1400    /// algorithm. The default traits class is
  1.1401    /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
  1.1402    /// See \ref BfsVisitDefaultTraits for the documentation of
  1.1403 -  /// a Bfs visit traits class.
  1.1404 +  /// a BFS visit traits class.
  1.1405  #ifdef DOXYGEN
  1.1406    template <typename _Digraph, typename _Visitor, typename _Traits>
  1.1407  #else
  1.1408 @@ -1226,7 +1288,7 @@
  1.1409      /// \brief \ref Exception for uninitialized parameters.
  1.1410      ///
  1.1411      /// This error represents problems in the initialization
  1.1412 -    /// of the parameters of the algorithms.
  1.1413 +    /// of the parameters of the algorithm.
  1.1414      class UninitializedParameter : public lemon::UninitializedParameter {
  1.1415      public:
  1.1416        virtual const char* what() const throw()
  1.1417 @@ -1235,13 +1297,16 @@
  1.1418        }
  1.1419      };
  1.1420  
  1.1421 +    ///The traits class.
  1.1422      typedef _Traits Traits;
  1.1423  
  1.1424 +    ///The type of the digraph the algorithm runs on.
  1.1425      typedef typename Traits::Digraph Digraph;
  1.1426  
  1.1427 +    ///The visitor type used by the algorithm.
  1.1428      typedef _Visitor Visitor;
  1.1429  
  1.1430 -    ///The type of the map indicating which nodes are reached.
  1.1431 +    ///The type of the map that indicates which nodes are reached.
  1.1432      typedef typename Traits::ReachedMap ReachedMap;
  1.1433  
  1.1434    private:
  1.1435 @@ -1251,21 +1316,20 @@
  1.1436      typedef typename Digraph::Arc Arc;
  1.1437      typedef typename Digraph::OutArcIt OutArcIt;
  1.1438  
  1.1439 -    /// Pointer to the underlying digraph.
  1.1440 +    //Pointer to the underlying digraph.
  1.1441      const Digraph *_digraph;
  1.1442 -    /// Pointer to the visitor object.
  1.1443 +    //Pointer to the visitor object.
  1.1444      Visitor *_visitor;
  1.1445 -    ///Pointer to the map of reached status of the nodes.
  1.1446 +    //Pointer to the map of reached status of the nodes.
  1.1447      ReachedMap *_reached;
  1.1448 -    ///Indicates if \ref _reached is locally allocated (\c true) or not.
  1.1449 +    //Indicates if _reached is locally allocated (true) or not.
  1.1450      bool local_reached;
  1.1451  
  1.1452      std::vector<typename Digraph::Node> _list;
  1.1453      int _list_front, _list_back;
  1.1454  
  1.1455 -    /// \brief Creates the maps if necessary.
  1.1456 -    ///
  1.1457 -    /// Creates the maps if necessary.
  1.1458 +    ///Creates the maps if necessary.
  1.1459 +    ///\todo Better memory allocation (instead of new).
  1.1460      void create_maps() {
  1.1461        if(!_reached) {
  1.1462          local_reached = true;
  1.1463 @@ -1292,9 +1356,9 @@
  1.1464        }
  1.1465      };
  1.1466      /// \brief \ref named-templ-param "Named parameter" for setting
  1.1467 -    /// ReachedMap type
  1.1468 +    /// ReachedMap type.
  1.1469      ///
  1.1470 -    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  1.1471 +    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
  1.1472      template <class T>
  1.1473      struct DefReachedMap : public BfsVisit< Digraph, Visitor,
  1.1474                                              DefReachedMapTraits<T> > {
  1.1475 @@ -1308,25 +1372,22 @@
  1.1476      ///
  1.1477      /// Constructor.
  1.1478      ///
  1.1479 -    /// \param digraph the digraph the algorithm will run on.
  1.1480 -    /// \param visitor The visitor of the algorithm.
  1.1481 -    ///
  1.1482 +    /// \param digraph The digraph the algorithm runs on.
  1.1483 +    /// \param visitor The visitor object of the algorithm.
  1.1484      BfsVisit(const Digraph& digraph, Visitor& visitor)
  1.1485        : _digraph(&digraph), _visitor(&visitor),
  1.1486          _reached(0), local_reached(false) {}
  1.1487  
  1.1488      /// \brief Destructor.
  1.1489 -    ///
  1.1490 -    /// Destructor.
  1.1491      ~BfsVisit() {
  1.1492        if(local_reached) delete _reached;
  1.1493      }
  1.1494  
  1.1495 -    /// \brief Sets the map indicating if a node is reached.
  1.1496 +    /// \brief Sets the map that indicates which nodes are reached.
  1.1497      ///
  1.1498 -    /// Sets the map indicating if a node is reached.
  1.1499 +    /// Sets the map that indicates which nodes are reached.
  1.1500      /// If you don't use this function before calling \ref run(),
  1.1501 -    /// it will allocate one. The destuctor deallocates this
  1.1502 +    /// it will allocate one. The destructor deallocates this
  1.1503      /// automatically allocated map, of course.
  1.1504      /// \return <tt> (*this) </tt>
  1.1505      BfsVisit &reachedMap(ReachedMap &m) {
  1.1506 @@ -1339,21 +1400,23 @@
  1.1507      }
  1.1508  
  1.1509    public:
  1.1510 +
  1.1511      /// \name Execution control
  1.1512      /// The simplest way to execute the algorithm is to use
  1.1513 -    /// one of the member functions called \c run(...).
  1.1514 +    /// one of the member functions called \ref lemon::BfsVisit::run()
  1.1515 +    /// "run()".
  1.1516      /// \n
  1.1517 -    /// If you need more control on the execution,
  1.1518 -    /// first you must call \ref init(), then you can adda source node
  1.1519 -    /// with \ref addSource().
  1.1520 -    /// Finally \ref start() will perform the actual path
  1.1521 -    /// computation.
  1.1522 +    /// If you need more control on the execution, first you must call
  1.1523 +    /// \ref lemon::BfsVisit::init() "init()", then you can add several
  1.1524 +    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
  1.1525 +    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
  1.1526 +    /// actual path computation.
  1.1527  
  1.1528      /// @{
  1.1529 +
  1.1530      /// \brief Initializes the internal data structures.
  1.1531      ///
  1.1532      /// Initializes the internal data structures.
  1.1533 -    ///
  1.1534      void init() {
  1.1535        create_maps();
  1.1536        _list.resize(countNodes(*_digraph));
  1.1537 @@ -1381,7 +1444,7 @@
  1.1538      ///
  1.1539      /// \return The processed node.
  1.1540      ///
  1.1541 -    /// \pre The queue must not be empty!
  1.1542 +    /// \pre The queue must not be empty.
  1.1543      Node processNextNode() {
  1.1544        Node n = _list[++_list_front];
  1.1545        _visitor->process(n);
  1.1546 @@ -1402,16 +1465,17 @@
  1.1547  
  1.1548      /// \brief Processes the next node.
  1.1549      ///
  1.1550 -    /// Processes the next node. And checks that the given target node
  1.1551 +    /// Processes the next node and checks if the given target node
  1.1552      /// is reached. If the target node is reachable from the processed
  1.1553 -    /// node then the reached parameter will be set true. The reached
  1.1554 -    /// parameter should be initially false.
  1.1555 +    /// node, then the \c reach parameter will be set to \c true.
  1.1556      ///
  1.1557      /// \param target The target node.
  1.1558 -    /// \retval reach Indicates that the target node is reached.
  1.1559 +    /// \retval reach Indicates if the target node is reached.
  1.1560 +    /// It should be initially \c false.
  1.1561 +    ///
  1.1562      /// \return The processed node.
  1.1563      ///
  1.1564 -    /// \warning The queue must not be empty!
  1.1565 +    /// \pre The queue must not be empty.
  1.1566      Node processNextNode(Node target, bool& reach) {
  1.1567        Node n = _list[++_list_front];
  1.1568        _visitor->process(n);
  1.1569 @@ -1433,16 +1497,19 @@
  1.1570  
  1.1571      /// \brief Processes the next node.
  1.1572      ///
  1.1573 -    /// Processes the next node. And checks that at least one of
  1.1574 -    /// reached node has true value in the \c nm node map. If one node
  1.1575 -    /// with true value is reachable from the processed node then the
  1.1576 -    /// rnode parameter will be set to the first of such nodes.
  1.1577 +    /// Processes the next node and checks if at least one of reached
  1.1578 +    /// nodes has \c true value in the \c nm node map. If one node
  1.1579 +    /// with \c true value is reachable from the processed node, then the
  1.1580 +    /// \c rnode parameter will be set to the first of such nodes.
  1.1581      ///
  1.1582 -    /// \param nm The node map of possible targets.
  1.1583 +    /// \param nm A \c bool (or convertible) node map that indicates the
  1.1584 +    /// possible targets.
  1.1585      /// \retval rnode The reached target node.
  1.1586 +    /// It should be initially \c INVALID.
  1.1587 +    ///
  1.1588      /// \return The processed node.
  1.1589      ///
  1.1590 -    /// \warning The queue must not be empty!
  1.1591 +    /// \pre The queue must not be empty.
  1.1592      template <typename NM>
  1.1593      Node processNextNode(const NM& nm, Node& rnode) {
  1.1594        Node n = _list[++_list_front];
  1.1595 @@ -1463,44 +1530,71 @@
  1.1596        return n;
  1.1597      }
  1.1598  
  1.1599 -    /// \brief Next node to be processed.
  1.1600 +    /// \brief The next node to be processed.
  1.1601      ///
  1.1602 -    /// Next node to be processed.
  1.1603 -    ///
  1.1604 -    /// \return The next node to be processed or INVALID if the stack is
  1.1605 -    /// empty.
  1.1606 -    Node nextNode() {
  1.1607 +    /// Returns the next node to be processed or \c INVALID if the queue
  1.1608 +    /// is empty.
  1.1609 +    Node nextNode() const {
  1.1610        return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
  1.1611      }
  1.1612  
  1.1613      /// \brief Returns \c false if there are nodes
  1.1614 -    /// to be processed in the queue
  1.1615 +    /// to be processed.
  1.1616      ///
  1.1617      /// Returns \c false if there are nodes
  1.1618 -    /// to be processed in the queue
  1.1619 -    bool emptyQueue() { return _list_front == _list_back; }
  1.1620 +    /// to be processed in the queue.
  1.1621 +    bool emptyQueue() const { return _list_front == _list_back; }
  1.1622  
  1.1623      /// \brief Returns the number of the nodes to be processed.
  1.1624      ///
  1.1625      /// Returns the number of the nodes to be processed in the queue.
  1.1626 -    int queueSize() { return _list_back - _list_front; }
  1.1627 +    int queueSize() const { return _list_back - _list_front; }
  1.1628  
  1.1629      /// \brief Executes the algorithm.
  1.1630      ///
  1.1631      /// Executes the algorithm.
  1.1632      ///
  1.1633 -    /// \pre init() must be called and at least one node should be added
  1.1634 +    /// This method runs the %BFS algorithm from the root node(s)
  1.1635 +    /// in order to compute the shortest path to each node.
  1.1636 +    ///
  1.1637 +    /// The algorithm computes
  1.1638 +    /// - the shortest path tree (forest),
  1.1639 +    /// - the distance of each node from the root(s).
  1.1640 +    ///
  1.1641 +    /// \pre init() must be called and at least one root node should be added
  1.1642      /// with addSource() before using this function.
  1.1643 +    ///
  1.1644 +    /// \note <tt>b.start()</tt> is just a shortcut of the following code.
  1.1645 +    /// \code
  1.1646 +    ///   while ( !b.emptyQueue() ) {
  1.1647 +    ///     b.processNextNode();
  1.1648 +    ///   }
  1.1649 +    /// \endcode
  1.1650      void start() {
  1.1651        while ( !emptyQueue() ) processNextNode();
  1.1652      }
  1.1653  
  1.1654 -    /// \brief Executes the algorithm until \c dest is reached.
  1.1655 +    /// \brief Executes the algorithm until the given target node is reached.
  1.1656      ///
  1.1657 -    /// Executes the algorithm until \c dest is reached.
  1.1658 +    /// Executes the algorithm until the given target node is reached.
  1.1659      ///
  1.1660 -    /// \pre init() must be called and at least one node should be added
  1.1661 -    /// with addSource() before using this function.
  1.1662 +    /// This method runs the %BFS algorithm from the root node(s)
  1.1663 +    /// in order to compute the shortest path to \c dest.
  1.1664 +    ///
  1.1665 +    /// The algorithm computes
  1.1666 +    /// - the shortest path to \c dest,
  1.1667 +    /// - the distance of \c dest from the root(s).
  1.1668 +    ///
  1.1669 +    /// \pre init() must be called and at least one root node should be
  1.1670 +    /// added with addSource() before using this function.
  1.1671 +    ///
  1.1672 +    /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
  1.1673 +    /// \code
  1.1674 +    ///   bool reach = false;
  1.1675 +    ///   while ( !b.emptyQueue() && !reach ) {
  1.1676 +    ///     b.processNextNode(t, reach);
  1.1677 +    ///   }
  1.1678 +    /// \endcode
  1.1679      void start(Node dest) {
  1.1680        bool reach = false;
  1.1681        while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
  1.1682 @@ -1510,15 +1604,28 @@
  1.1683      ///
  1.1684      /// Executes the algorithm until a condition is met.
  1.1685      ///
  1.1686 -    /// \pre init() must be called and at least one node should be added
  1.1687 -    /// with addSource() before using this function.
  1.1688 +    /// This method runs the %BFS algorithm from the root node(s) in
  1.1689 +    /// order to compute the shortest path to a node \c v with
  1.1690 +    /// <tt>nm[v]</tt> true, if such a node can be found.
  1.1691      ///
  1.1692 -    ///\param nm must be a bool (or convertible) node map. The
  1.1693 -    ///algorithm will stop when it reaches a node \c v with
  1.1694 +    /// \param nm must be a bool (or convertible) node map. The
  1.1695 +    /// algorithm will stop when it reaches a node \c v with
  1.1696      /// <tt>nm[v]</tt> true.
  1.1697      ///
  1.1698 -    ///\return The reached node \c v with <tt>nm[v]</tt> true or
  1.1699 -    ///\c INVALID if no such node was found.
  1.1700 +    /// \return The reached node \c v with <tt>nm[v]</tt> true or
  1.1701 +    /// \c INVALID if no such node was found.
  1.1702 +    ///
  1.1703 +    /// \pre init() must be called and at least one root node should be
  1.1704 +    /// added with addSource() before using this function.
  1.1705 +    ///
  1.1706 +    /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
  1.1707 +    /// \code
  1.1708 +    ///   Node rnode = INVALID;
  1.1709 +    ///   while ( !b.emptyQueue() && rnode == INVALID ) {
  1.1710 +    ///     b.processNextNode(nm, rnode);
  1.1711 +    ///   }
  1.1712 +    ///   return rnode;
  1.1713 +    /// \endcode
  1.1714      template <typename NM>
  1.1715      Node start(const NM &nm) {
  1.1716        Node rnode = INVALID;
  1.1717 @@ -1528,10 +1635,16 @@
  1.1718        return rnode;
  1.1719      }
  1.1720  
  1.1721 -    /// \brief Runs %BFSVisit algorithm from node \c s.
  1.1722 +    /// \brief Runs the algorithm from the given node.
  1.1723      ///
  1.1724 -    /// This method runs the %BFS algorithm from a root node \c s.
  1.1725 -    /// \note b.run(s) is just a shortcut of the following code.
  1.1726 +    /// This method runs the %BFS algorithm from node \c s
  1.1727 +    /// in order to compute the shortest path to each node.
  1.1728 +    ///
  1.1729 +    /// The algorithm computes
  1.1730 +    /// - the shortest path tree,
  1.1731 +    /// - the distance of each node from the root.
  1.1732 +    ///
  1.1733 +    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1.1734      ///\code
  1.1735      ///   b.init();
  1.1736      ///   b.addSource(s);
  1.1737 @@ -1543,19 +1656,21 @@
  1.1738        start();
  1.1739      }
  1.1740  
  1.1741 -    /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
  1.1742 +    /// \brief Runs the algorithm to visit all nodes in the digraph.
  1.1743      ///
  1.1744      /// This method runs the %BFS algorithm in order to
  1.1745 -    /// compute the %BFS path to each node. The algorithm computes
  1.1746 -    /// - The %BFS tree.
  1.1747 -    /// - The distance of each node from the root in the %BFS tree.
  1.1748 +    /// compute the shortest path to each node.
  1.1749      ///
  1.1750 -    ///\note b.run() is just a shortcut of the following code.
  1.1751 +    /// The algorithm computes
  1.1752 +    /// - the shortest path tree (forest),
  1.1753 +    /// - the distance of each node from the root(s).
  1.1754 +    ///
  1.1755 +    /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
  1.1756      ///\code
  1.1757      ///  b.init();
  1.1758 -    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
  1.1759 -    ///    if (!b.reached(it)) {
  1.1760 -    ///      b.addSource(it);
  1.1761 +    ///  for (NodeIt n(gr); n != INVALID; ++n) {
  1.1762 +    ///    if (!b.reached(n)) {
  1.1763 +    ///      b.addSource(n);
  1.1764      ///      b.start();
  1.1765      ///    }
  1.1766      ///  }
  1.1767 @@ -1569,27 +1684,28 @@
  1.1768          }
  1.1769        }
  1.1770      }
  1.1771 +
  1.1772      ///@}
  1.1773  
  1.1774      /// \name Query Functions
  1.1775      /// The result of the %BFS algorithm can be obtained using these
  1.1776      /// functions.\n
  1.1777 -    /// Before the use of these functions,
  1.1778 -    /// either run() or start() must be called.
  1.1779 +    /// Either \ref lemon::BfsVisit::run() "run()" or
  1.1780 +    /// \ref lemon::BfsVisit::start() "start()" must be called before
  1.1781 +    /// using them.
  1.1782      ///@{
  1.1783  
  1.1784 -    /// \brief Checks if a node is reachable from the root.
  1.1785 +    /// \brief Checks if a node is reachable from the root(s).
  1.1786      ///
  1.1787      /// Returns \c true if \c v is reachable from the root(s).
  1.1788 -    /// \warning The source nodes are inditated as unreachable.
  1.1789      /// \pre Either \ref run() or \ref start()
  1.1790      /// must be called before using this function.
  1.1791 -    ///
  1.1792      bool reached(Node v) { return (*_reached)[v]; }
  1.1793 +
  1.1794      ///@}
  1.1795 +
  1.1796    };
  1.1797  
  1.1798  } //END OF NAMESPACE LEMON
  1.1799  
  1.1800  #endif
  1.1801 -
     2.1 --- a/lemon/dfs.h	Wed Jul 30 12:07:48 2008 +0100
     2.2 +++ b/lemon/dfs.h	Mon Aug 04 22:00:36 2008 +0200
     2.3 @@ -21,19 +21,17 @@
     2.4  
     2.5  ///\ingroup search
     2.6  ///\file
     2.7 -///\brief Dfs algorithm.
     2.8 +///\brief DFS algorithm.
     2.9  
    2.10  #include <lemon/list_graph.h>
    2.11  #include <lemon/bits/path_dump.h>
    2.12  #include <lemon/core.h>
    2.13  #include <lemon/error.h>
    2.14 +#include <lemon/assert.h>
    2.15  #include <lemon/maps.h>
    2.16  
    2.17 -#include <lemon/concept_check.h>
    2.18 -
    2.19  namespace lemon {
    2.20  
    2.21 -
    2.22    ///Default traits class of Dfs class.
    2.23  
    2.24    ///Default traits class of Dfs class.
    2.25 @@ -41,74 +39,75 @@
    2.26    template<class GR>
    2.27    struct DfsDefaultTraits
    2.28    {
    2.29 -    ///The digraph type the algorithm runs on.
    2.30 +    ///The type of the digraph the algorithm runs on.
    2.31      typedef GR Digraph;
    2.32 -    ///\brief The type of the map that stores the last
    2.33 +
    2.34 +    ///\brief The type of the map that stores the predecessor
    2.35      ///arcs of the %DFS paths.
    2.36      ///
    2.37 -    ///The type of the map that stores the last
    2.38 +    ///The type of the map that stores the predecessor
    2.39      ///arcs of the %DFS paths.
    2.40      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.41 -    ///
    2.42 -    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    2.43 -    ///Instantiates a PredMap.
    2.44 +    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    2.45 +    ///Instantiates a \ref PredMap.
    2.46  
    2.47      ///This function instantiates a \ref PredMap.
    2.48 -    ///\param G is the digraph, to which we would like to define the PredMap.
    2.49 +    ///\param g is the digraph, to which we would like to define the
    2.50 +    ///\ref PredMap.
    2.51      ///\todo The digraph alone may be insufficient to initialize
    2.52 -    static PredMap *createPredMap(const GR &G)
    2.53 +    static PredMap *createPredMap(const Digraph &g)
    2.54      {
    2.55 -      return new PredMap(G);
    2.56 +      return new PredMap(g);
    2.57      }
    2.58  
    2.59      ///The type of the map that indicates which nodes are processed.
    2.60  
    2.61      ///The type of the map that indicates which nodes are processed.
    2.62      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.63 -    ///\todo named parameter to set this type, function to read and write.
    2.64 +    ///By default it is a NullMap.
    2.65      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    2.66 -    ///Instantiates a ProcessedMap.
    2.67 +    ///Instantiates a \ref ProcessedMap.
    2.68  
    2.69      ///This function instantiates a \ref ProcessedMap.
    2.70      ///\param g is the digraph, to which
    2.71      ///we would like to define the \ref ProcessedMap
    2.72  #ifdef DOXYGEN
    2.73 -    static ProcessedMap *createProcessedMap(const GR &g)
    2.74 +    static ProcessedMap *createProcessedMap(const Digraph &g)
    2.75  #else
    2.76 -    static ProcessedMap *createProcessedMap(const GR &)
    2.77 +    static ProcessedMap *createProcessedMap(const Digraph &)
    2.78  #endif
    2.79      {
    2.80        return new ProcessedMap();
    2.81      }
    2.82 +
    2.83      ///The type of the map that indicates which nodes are reached.
    2.84  
    2.85      ///The type of the map that indicates which nodes are reached.
    2.86 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.87 -    ///\todo named parameter to set this type, function to read and write.
    2.88 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.89      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    2.90 -    ///Instantiates a ReachedMap.
    2.91 +    ///Instantiates a \ref ReachedMap.
    2.92  
    2.93      ///This function instantiates a \ref ReachedMap.
    2.94 -    ///\param G is the digraph, to which
    2.95 +    ///\param g is the digraph, to which
    2.96      ///we would like to define the \ref ReachedMap.
    2.97 -    static ReachedMap *createReachedMap(const GR &G)
    2.98 +    static ReachedMap *createReachedMap(const Digraph &g)
    2.99      {
   2.100 -      return new ReachedMap(G);
   2.101 +      return new ReachedMap(g);
   2.102      }
   2.103 -    ///The type of the map that stores the dists of the nodes.
   2.104  
   2.105 -    ///The type of the map that stores the dists of the nodes.
   2.106 +    ///The type of the map that stores the distances of the nodes.
   2.107 +
   2.108 +    ///The type of the map that stores the distances of the nodes.
   2.109      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.110 -    ///
   2.111      typedef typename Digraph::template NodeMap<int> DistMap;
   2.112 -    ///Instantiates a DistMap.
   2.113 +    ///Instantiates a \ref DistMap.
   2.114  
   2.115      ///This function instantiates a \ref DistMap.
   2.116 -    ///\param G is the digraph, to which we would like to define
   2.117 -    ///the \ref DistMap
   2.118 -    static DistMap *createDistMap(const GR &G)
   2.119 +    ///\param g is the digraph, to which we would like to define the
   2.120 +    ///\ref DistMap.
   2.121 +    static DistMap *createDistMap(const Digraph &g)
   2.122      {
   2.123 -      return new DistMap(G);
   2.124 +      return new DistMap(g);
   2.125      }
   2.126    };
   2.127  
   2.128 @@ -117,9 +116,13 @@
   2.129    ///\ingroup search
   2.130    ///This class provides an efficient implementation of the %DFS algorithm.
   2.131    ///
   2.132 -  ///\tparam GR The digraph type the algorithm runs on. The default value is
   2.133 -  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
   2.134 -  ///is only passed to \ref DfsDefaultTraits.
   2.135 +  ///There is also a \ref dfs() "function type interface" for the DFS
   2.136 +  ///algorithm, which is convenient in the simplier cases and it can be
   2.137 +  ///used easier.
   2.138 +  ///
   2.139 +  ///\tparam GR The type of the digraph the algorithm runs on.
   2.140 +  ///The default value is \ref ListDigraph. The value of GR is not used
   2.141 +  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
   2.142    ///\tparam TR Traits class to set various data types used by the algorithm.
   2.143    ///The default traits class is
   2.144    ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
   2.145 @@ -134,12 +137,10 @@
   2.146  #endif
   2.147    class Dfs {
   2.148    public:
   2.149 -    /**
   2.150 -     * \brief \ref Exception for uninitialized parameters.
   2.151 -     *
   2.152 -     * This error represents problems in the initialization
   2.153 -     * of the parameters of the algorithms.
   2.154 -     */
   2.155 +    ///\ref Exception for uninitialized parameters.
   2.156 +
   2.157 +    ///This error represents problems in the initialization of the
   2.158 +    ///parameters of the algorithm.
   2.159      class UninitializedParameter : public lemon::UninitializedParameter {
   2.160      public:
   2.161        virtual const char* what() const throw() {
   2.162 @@ -147,52 +148,54 @@
   2.163        }
   2.164      };
   2.165  
   2.166 +    ///The type of the digraph the algorithm runs on.
   2.167 +    typedef typename TR::Digraph Digraph;
   2.168 +
   2.169 +    ///\brief The type of the map that stores the predecessor arcs of the
   2.170 +    ///DFS paths.
   2.171 +    typedef typename TR::PredMap PredMap;
   2.172 +    ///The type of the map that stores the distances of the nodes.
   2.173 +    typedef typename TR::DistMap DistMap;
   2.174 +    ///The type of the map that indicates which nodes are reached.
   2.175 +    typedef typename TR::ReachedMap ReachedMap;
   2.176 +    ///The type of the map that indicates which nodes are processed.
   2.177 +    typedef typename TR::ProcessedMap ProcessedMap;
   2.178 +    ///The type of the paths.
   2.179 +    typedef PredMapPath<Digraph, PredMap> Path;
   2.180 +
   2.181 +    ///The traits class.
   2.182      typedef TR Traits;
   2.183 -    ///The type of the underlying digraph.
   2.184 -    typedef typename TR::Digraph Digraph;
   2.185 -    ///\e
   2.186 +
   2.187 +  private:
   2.188 +
   2.189      typedef typename Digraph::Node Node;
   2.190 -    ///\e
   2.191      typedef typename Digraph::NodeIt NodeIt;
   2.192 -    ///\e
   2.193      typedef typename Digraph::Arc Arc;
   2.194 -    ///\e
   2.195      typedef typename Digraph::OutArcIt OutArcIt;
   2.196  
   2.197 -    ///\brief The type of the map that stores the last
   2.198 -    ///arcs of the %DFS paths.
   2.199 -    typedef typename TR::PredMap PredMap;
   2.200 -    ///The type of the map indicating which nodes are reached.
   2.201 -    typedef typename TR::ReachedMap ReachedMap;
   2.202 -    ///The type of the map indicating which nodes are processed.
   2.203 -    typedef typename TR::ProcessedMap ProcessedMap;
   2.204 -    ///The type of the map that stores the dists of the nodes.
   2.205 -    typedef typename TR::DistMap DistMap;
   2.206 -  private:
   2.207 -    /// Pointer to the underlying digraph.
   2.208 +    //Pointer to the underlying digraph.
   2.209      const Digraph *G;
   2.210 -    ///Pointer to the map of predecessors arcs.
   2.211 +    //Pointer to the map of predecessor arcs.
   2.212      PredMap *_pred;
   2.213 -    ///Indicates if \ref _pred is locally allocated (\c true) or not.
   2.214 +    //Indicates if _pred is locally allocated (true) or not.
   2.215      bool local_pred;
   2.216 -    ///Pointer to the map of distances.
   2.217 +    //Pointer to the map of distances.
   2.218      DistMap *_dist;
   2.219 -    ///Indicates if \ref _dist is locally allocated (\c true) or not.
   2.220 +    //Indicates if _dist is locally allocated (true) or not.
   2.221      bool local_dist;
   2.222 -    ///Pointer to the map of reached status of the nodes.
   2.223 +    //Pointer to the map of reached status of the nodes.
   2.224      ReachedMap *_reached;
   2.225 -    ///Indicates if \ref _reached is locally allocated (\c true) or not.
   2.226 +    //Indicates if _reached is locally allocated (true) or not.
   2.227      bool local_reached;
   2.228 -    ///Pointer to the map of processed status of the nodes.
   2.229 +    //Pointer to the map of processed status of the nodes.
   2.230      ProcessedMap *_processed;
   2.231 -    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   2.232 +    //Indicates if _processed is locally allocated (true) or not.
   2.233      bool local_processed;
   2.234  
   2.235      std::vector<typename Digraph::OutArcIt> _stack;
   2.236      int _stack_head;
   2.237  
   2.238      ///Creates the maps if necessary.
   2.239 -
   2.240      ///\todo Better memory allocation (instead of new).
   2.241      void create_maps()
   2.242      {
   2.243 @@ -229,22 +232,21 @@
   2.244      template <class T>
   2.245      struct DefPredMapTraits : public Traits {
   2.246        typedef T PredMap;
   2.247 -      static PredMap *createPredMap(const Digraph &G)
   2.248 +      static PredMap *createPredMap(const Digraph &)
   2.249        {
   2.250          throw UninitializedParameter();
   2.251        }
   2.252      };
   2.253      ///\brief \ref named-templ-param "Named parameter" for setting
   2.254 -    ///PredMap type
   2.255 +    ///\ref PredMap type.
   2.256      ///
   2.257 -    ///\ref named-templ-param "Named parameter" for setting PredMap type
   2.258 -    ///
   2.259 +    ///\ref named-templ-param "Named parameter" for setting
   2.260 +    ///\ref PredMap type.
   2.261      template <class T>
   2.262      struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
   2.263        typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
   2.264      };
   2.265  
   2.266 -
   2.267      template <class T>
   2.268      struct DefDistMapTraits : public Traits {
   2.269        typedef T DistMap;
   2.270 @@ -254,12 +256,12 @@
   2.271        }
   2.272      };
   2.273      ///\brief \ref named-templ-param "Named parameter" for setting
   2.274 -    ///DistMap type
   2.275 +    ///\ref DistMap type.
   2.276      ///
   2.277 -    ///\ref named-templ-param "Named parameter" for setting DistMap
   2.278 -    ///type
   2.279 +    ///\ref named-templ-param "Named parameter" for setting
   2.280 +    ///\ref DistMap type.
   2.281      template <class T>
   2.282 -    struct DefDistMap {
   2.283 +    struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
   2.284        typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
   2.285      };
   2.286  
   2.287 @@ -272,10 +274,10 @@
   2.288        }
   2.289      };
   2.290      ///\brief \ref named-templ-param "Named parameter" for setting
   2.291 -    ///ReachedMap type
   2.292 +    ///\ref ReachedMap type.
   2.293      ///
   2.294 -    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   2.295 -    ///
   2.296 +    ///\ref named-templ-param "Named parameter" for setting
   2.297 +    ///\ref ReachedMap type.
   2.298      template <class T>
   2.299      struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
   2.300        typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
   2.301 @@ -290,10 +292,10 @@
   2.302        }
   2.303      };
   2.304      ///\brief \ref named-templ-param "Named parameter" for setting
   2.305 -    ///ProcessedMap type
   2.306 +    ///\ref ProcessedMap type.
   2.307      ///
   2.308 -    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   2.309 -    ///
   2.310 +    ///\ref named-templ-param "Named parameter" for setting
   2.311 +    ///\ref ProcessedMap type.
   2.312      template <class T>
   2.313      struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
   2.314        typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
   2.315 @@ -301,19 +303,19 @@
   2.316  
   2.317      struct DefDigraphProcessedMapTraits : public Traits {
   2.318        typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   2.319 -      static ProcessedMap *createProcessedMap(const Digraph &G)
   2.320 +      static ProcessedMap *createProcessedMap(const Digraph &g)
   2.321        {
   2.322 -        return new ProcessedMap(G);
   2.323 +        return new ProcessedMap(g);
   2.324        }
   2.325      };
   2.326 -    ///\brief \ref named-templ-param "Named parameter"
   2.327 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   2.328 +    ///\brief \ref named-templ-param "Named parameter" for setting
   2.329 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   2.330      ///
   2.331 -    ///\ref named-templ-param "Named parameter"
   2.332 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   2.333 -    ///If you don't set it explicitely, it will be automatically allocated.
   2.334 +    ///\ref named-templ-param "Named parameter" for setting
   2.335 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   2.336 +    ///If you don't set it explicitly, it will be automatically allocated.
   2.337      template <class T>
   2.338 -    class DefProcessedMapToBeDefaultMap :
   2.339 +    struct DefProcessedMapToBeDefaultMap :
   2.340        public Dfs< Digraph, DefDigraphProcessedMapTraits> {
   2.341        typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
   2.342      };
   2.343 @@ -324,10 +326,10 @@
   2.344  
   2.345      ///Constructor.
   2.346  
   2.347 -    ///\param _G the digraph the algorithm will run on.
   2.348 -    ///
   2.349 -    Dfs(const Digraph& _G) :
   2.350 -      G(&_G),
   2.351 +    ///Constructor.
   2.352 +    ///\param g The digraph the algorithm runs on.
   2.353 +    Dfs(const Digraph &g) :
   2.354 +      G(&g),
   2.355        _pred(NULL), local_pred(false),
   2.356        _dist(NULL), local_dist(false),
   2.357        _reached(NULL), local_reached(false),
   2.358 @@ -343,11 +345,11 @@
   2.359        if(local_processed) delete _processed;
   2.360      }
   2.361  
   2.362 -    ///Sets the map storing the predecessor arcs.
   2.363 +    ///Sets the map that stores the predecessor arcs.
   2.364  
   2.365 -    ///Sets the map storing the predecessor arcs.
   2.366 +    ///Sets the map that stores the predecessor arcs.
   2.367      ///If you don't use this function before calling \ref run(),
   2.368 -    ///it will allocate one. The destuctor deallocates this
   2.369 +    ///it will allocate one. The destructor deallocates this
   2.370      ///automatically allocated map, of course.
   2.371      ///\return <tt> (*this) </tt>
   2.372      Dfs &predMap(PredMap &m)
   2.373 @@ -360,11 +362,46 @@
   2.374        return *this;
   2.375      }
   2.376  
   2.377 -    ///Sets the map storing the distances calculated by the algorithm.
   2.378 +    ///Sets the map that indicates which nodes are reached.
   2.379  
   2.380 -    ///Sets the map storing the distances calculated by the algorithm.
   2.381 +    ///Sets the map that indicates which nodes are reached.
   2.382      ///If you don't use this function before calling \ref run(),
   2.383 -    ///it will allocate one. The destuctor deallocates this
   2.384 +    ///it will allocate one. The destructor deallocates this
   2.385 +    ///automatically allocated map, of course.
   2.386 +    ///\return <tt> (*this) </tt>
   2.387 +    Dfs &reachedMap(ReachedMap &m)
   2.388 +    {
   2.389 +      if(local_reached) {
   2.390 +        delete _reached;
   2.391 +        local_reached=false;
   2.392 +      }
   2.393 +      _reached = &m;
   2.394 +      return *this;
   2.395 +    }
   2.396 +
   2.397 +    ///Sets the map that indicates which nodes are processed.
   2.398 +
   2.399 +    ///Sets the map that indicates which nodes are processed.
   2.400 +    ///If you don't use this function before calling \ref run(),
   2.401 +    ///it will allocate one. The destructor deallocates this
   2.402 +    ///automatically allocated map, of course.
   2.403 +    ///\return <tt> (*this) </tt>
   2.404 +    Dfs &processedMap(ProcessedMap &m)
   2.405 +    {
   2.406 +      if(local_processed) {
   2.407 +        delete _processed;
   2.408 +        local_processed=false;
   2.409 +      }
   2.410 +      _processed = &m;
   2.411 +      return *this;
   2.412 +    }
   2.413 +
   2.414 +    ///Sets the map that stores the distances of the nodes.
   2.415 +
   2.416 +    ///Sets the map that stores the distances of the nodes calculated by
   2.417 +    ///the algorithm.
   2.418 +    ///If you don't use this function before calling \ref run(),
   2.419 +    ///it will allocate one. The destructor deallocates this
   2.420      ///automatically allocated map, of course.
   2.421      ///\return <tt> (*this) </tt>
   2.422      Dfs &distMap(DistMap &m)
   2.423 @@ -377,50 +414,17 @@
   2.424        return *this;
   2.425      }
   2.426  
   2.427 -    ///Sets the map indicating if a node is reached.
   2.428 +  public:
   2.429  
   2.430 -    ///Sets the map indicating if a node is reached.
   2.431 -    ///If you don't use this function before calling \ref run(),
   2.432 -    ///it will allocate one. The destuctor deallocates this
   2.433 -    ///automatically allocated map, of course.
   2.434 -    ///\return <tt> (*this) </tt>
   2.435 -    Dfs &reachedMap(ReachedMap &m)
   2.436 -    {
   2.437 -      if(local_reached) {
   2.438 -        delete _reached;
   2.439 -        local_reached=false;
   2.440 -      }
   2.441 -      _reached = &m;
   2.442 -      return *this;
   2.443 -    }
   2.444 -
   2.445 -    ///Sets the map indicating if a node is processed.
   2.446 -
   2.447 -    ///Sets the map indicating if a node is processed.
   2.448 -    ///If you don't use this function before calling \ref run(),
   2.449 -    ///it will allocate one. The destuctor deallocates this
   2.450 -    ///automatically allocated map, of course.
   2.451 -    ///\return <tt> (*this) </tt>
   2.452 -    Dfs &processedMap(ProcessedMap &m)
   2.453 -    {
   2.454 -      if(local_processed) {
   2.455 -        delete _processed;
   2.456 -        local_processed=false;
   2.457 -      }
   2.458 -      _processed = &m;
   2.459 -      return *this;
   2.460 -    }
   2.461 -
   2.462 -  public:
   2.463      ///\name Execution control
   2.464      ///The simplest way to execute the algorithm is to use
   2.465 -    ///one of the member functions called \c run(...).
   2.466 +    ///one of the member functions called \ref lemon::Dfs::run() "run()".
   2.467      ///\n
   2.468 -    ///If you need more control on the execution,
   2.469 -    ///first you must call \ref init(), then you can add a source node
   2.470 -    ///with \ref addSource().
   2.471 -    ///Finally \ref start() will perform the actual path
   2.472 -    ///computation.
   2.473 +    ///If you need more control on the execution, first you must call
   2.474 +    ///\ref lemon::Dfs::init() "init()", then you can add a source node
   2.475 +    ///with \ref lemon::Dfs::addSource() "addSource()".
   2.476 +    ///Finally \ref lemon::Dfs::start() "start()" will perform the
   2.477 +    ///actual path computation.
   2.478  
   2.479      ///@{
   2.480  
   2.481 @@ -435,7 +439,6 @@
   2.482        _stack_head=-1;
   2.483        for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   2.484          _pred->set(u,INVALID);
   2.485 -        // _predNode->set(u,INVALID);
   2.486          _reached->set(u,false);
   2.487          _processed->set(u,false);
   2.488        }
   2.489 @@ -445,10 +448,14 @@
   2.490  
   2.491      ///Adds a new source node to the set of nodes to be processed.
   2.492      ///
   2.493 -    ///\warning dists are wrong (or at least strange)
   2.494 -    ///in case of multiple sources.
   2.495 +    ///\pre The stack must be empty. (Otherwise the algorithm gives
   2.496 +    ///false results.)
   2.497 +    ///
   2.498 +    ///\warning Distances will be wrong (or at least strange) in case of
   2.499 +    ///multiple sources.
   2.500      void addSource(Node s)
   2.501      {
   2.502 +      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   2.503        if(!(*_reached)[s])
   2.504          {
   2.505            _reached->set(s,true);
   2.506 @@ -471,7 +478,7 @@
   2.507      ///
   2.508      ///\return The processed arc.
   2.509      ///
   2.510 -    ///\pre The stack must not be empty!
   2.511 +    ///\pre The stack must not be empty.
   2.512      Arc processNextArc()
   2.513      {
   2.514        Node m;
   2.515 @@ -497,61 +504,68 @@
   2.516        }
   2.517        return e;
   2.518      }
   2.519 +
   2.520      ///Next arc to be processed.
   2.521  
   2.522      ///Next arc to be processed.
   2.523      ///
   2.524 -    ///\return The next arc to be processed or INVALID if the stack is
   2.525 -    /// empty.
   2.526 -    OutArcIt nextArc()
   2.527 +    ///\return The next arc to be processed or \c INVALID if the stack
   2.528 +    ///is empty.
   2.529 +    OutArcIt nextArc() const
   2.530      {
   2.531        return _stack_head>=0?_stack[_stack_head]:INVALID;
   2.532      }
   2.533  
   2.534      ///\brief Returns \c false if there are nodes
   2.535 -    ///to be processed in the queue
   2.536 +    ///to be processed.
   2.537      ///
   2.538      ///Returns \c false if there are nodes
   2.539 -    ///to be processed in the queue
   2.540 -    bool emptyQueue() { return _stack_head<0; }
   2.541 +    ///to be processed in the queue (stack).
   2.542 +    bool emptyQueue() const { return _stack_head<0; }
   2.543 +
   2.544      ///Returns the number of the nodes to be processed.
   2.545  
   2.546 -    ///Returns the number of the nodes to be processed in the queue.
   2.547 -    int queueSize() { return _stack_head+1; }
   2.548 +    ///Returns the number of the nodes to be processed in the queue (stack).
   2.549 +    int queueSize() const { return _stack_head+1; }
   2.550  
   2.551      ///Executes the algorithm.
   2.552  
   2.553      ///Executes the algorithm.
   2.554      ///
   2.555 -    ///\pre init() must be called and at least one node should be added
   2.556 -    ///with addSource() before using this function.
   2.557 +    ///This method runs the %DFS algorithm from the root node
   2.558 +    ///in order to compute the DFS path to each node.
   2.559      ///
   2.560 -    ///This method runs the %DFS algorithm from the root node(s)
   2.561 -    ///in order to
   2.562 -    ///compute the
   2.563 -    ///%DFS path to each node. The algorithm computes
   2.564 -    ///- The %DFS tree.
   2.565 -    ///- The distance of each node from the root(s) in the %DFS tree.
   2.566 +    /// The algorithm computes
   2.567 +    ///- the %DFS tree,
   2.568 +    ///- the distance of each node from the root in the %DFS tree.
   2.569      ///
   2.570 +    ///\pre init() must be called and a root node should be
   2.571 +    ///added with addSource() before using this function.
   2.572 +    ///
   2.573 +    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
   2.574 +    ///\code
   2.575 +    ///  while ( !d.emptyQueue() ) {
   2.576 +    ///    d.processNextArc();
   2.577 +    ///  }
   2.578 +    ///\endcode
   2.579      void start()
   2.580      {
   2.581        while ( !emptyQueue() ) processNextArc();
   2.582      }
   2.583  
   2.584 -    ///Executes the algorithm until \c dest is reached.
   2.585 +    ///Executes the algorithm until the given target node is reached.
   2.586  
   2.587 -    ///Executes the algorithm until \c dest is reached.
   2.588 +    ///Executes the algorithm until the given target node is reached.
   2.589      ///
   2.590 -    ///\pre init() must be called and at least one node should be added
   2.591 -    ///with addSource() before using this function.
   2.592 +    ///This method runs the %DFS algorithm from the root node
   2.593 +    ///in order to compute the DFS path to \c dest.
   2.594      ///
   2.595 -    ///This method runs the %DFS algorithm from the root node(s)
   2.596 -    ///in order to
   2.597 -    ///compute the
   2.598 -    ///%DFS path to \c dest. The algorithm computes
   2.599 -    ///- The %DFS path to \c  dest.
   2.600 -    ///- The distance of \c dest from the root(s) in the %DFS tree.
   2.601 +    ///The algorithm computes
   2.602 +    ///- the %DFS path to \c dest,
   2.603 +    ///- the distance of \c dest from the root in the %DFS tree.
   2.604      ///
   2.605 +    ///\pre init() must be called and a root node should be
   2.606 +    ///added with addSource() before using this function.
   2.607      void start(Node dest)
   2.608      {
   2.609        while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
   2.610 @@ -562,39 +576,86 @@
   2.611  
   2.612      ///Executes the algorithm until a condition is met.
   2.613      ///
   2.614 -    ///\pre init() must be called and at least one node should be added
   2.615 -    ///with addSource() before using this function.
   2.616 +    ///This method runs the %DFS algorithm from the root node
   2.617 +    ///until an arc \c a with <tt>am[a]</tt> true is found.
   2.618      ///
   2.619 -    ///\param em must be a bool (or convertible) arc map. The algorithm
   2.620 -    ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
   2.621 +    ///\param am A \c bool (or convertible) arc map. The algorithm
   2.622 +    ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
   2.623      ///
   2.624 -    ///\return The reached arc \c e with <tt>em[e]</tt> true or
   2.625 +    ///\return The reached arc \c a with <tt>am[a]</tt> true or
   2.626      ///\c INVALID if no such arc was found.
   2.627      ///
   2.628 -    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
   2.629 +    ///\pre init() must be called and a root node should be
   2.630 +    ///added with addSource() before using this function.
   2.631 +    ///
   2.632 +    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
   2.633      ///not a node map.
   2.634 -    template<class EM>
   2.635 -    Arc start(const EM &em)
   2.636 +    template<class ArcBoolMap>
   2.637 +    Arc start(const ArcBoolMap &am)
   2.638      {
   2.639 -      while ( !emptyQueue() && !em[_stack[_stack_head]] )
   2.640 +      while ( !emptyQueue() && !am[_stack[_stack_head]] )
   2.641          processNextArc();
   2.642        return emptyQueue() ? INVALID : _stack[_stack_head];
   2.643      }
   2.644  
   2.645 -    ///Runs %DFS algorithm to visit all nodes in the digraph.
   2.646 +    ///Runs the algorithm from the given node.
   2.647  
   2.648 -    ///This method runs the %DFS algorithm in order to
   2.649 -    ///compute the
   2.650 -    ///%DFS path to each node. The algorithm computes
   2.651 -    ///- The %DFS tree.
   2.652 -    ///- The distance of each node from the root in the %DFS tree.
   2.653 +    ///This method runs the %DFS algorithm from node \c s
   2.654 +    ///in order to compute the DFS path to each node.
   2.655      ///
   2.656 -    ///\note d.run() is just a shortcut of the following code.
   2.657 +    ///The algorithm computes
   2.658 +    ///- the %DFS tree,
   2.659 +    ///- the distance of each node from the root in the %DFS tree.
   2.660 +    ///
   2.661 +    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
   2.662      ///\code
   2.663      ///  d.init();
   2.664 -    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
   2.665 -    ///    if (!d.reached(it)) {
   2.666 -    ///      d.addSource(it);
   2.667 +    ///  d.addSource(s);
   2.668 +    ///  d.start();
   2.669 +    ///\endcode
   2.670 +    void run(Node s) {
   2.671 +      init();
   2.672 +      addSource(s);
   2.673 +      start();
   2.674 +    }
   2.675 +
   2.676 +    ///Finds the %DFS path between \c s and \c t.
   2.677 +
   2.678 +    ///This method runs the %DFS algorithm from node \c s
   2.679 +    ///in order to compute the DFS path to \c t.
   2.680 +    ///
   2.681 +    ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
   2.682 +    ///if \c t is reachable form \c s, \c 0 otherwise.
   2.683 +    ///
   2.684 +    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
   2.685 +    ///just a shortcut of the following code.
   2.686 +    ///\code
   2.687 +    ///  d.init();
   2.688 +    ///  d.addSource(s);
   2.689 +    ///  d.start(t);
   2.690 +    ///\endcode
   2.691 +    int run(Node s,Node t) {
   2.692 +      init();
   2.693 +      addSource(s);
   2.694 +      start(t);
   2.695 +      return reached(t)?_stack_head+1:0;
   2.696 +    }
   2.697 +
   2.698 +    ///Runs the algorithm to visit all nodes in the digraph.
   2.699 +
   2.700 +    ///This method runs the %DFS algorithm in order to compute the
   2.701 +    ///%DFS path to each node.
   2.702 +    ///
   2.703 +    ///The algorithm computes
   2.704 +    ///- the %DFS tree,
   2.705 +    ///- the distance of each node from the root in the %DFS tree.
   2.706 +    ///
   2.707 +    ///\note <tt>d.run()</tt> is just a shortcut of the following code.
   2.708 +    ///\code
   2.709 +    ///  d.init();
   2.710 +    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
   2.711 +    ///    if (!d.reached(n)) {
   2.712 +    ///      d.addSource(n);
   2.713      ///      d.start();
   2.714      ///    }
   2.715      ///  }
   2.716 @@ -609,157 +670,124 @@
   2.717        }
   2.718      }
   2.719  
   2.720 -    ///Runs %DFS algorithm from node \c s.
   2.721 -
   2.722 -    ///This method runs the %DFS algorithm from a root node \c s
   2.723 -    ///in order to
   2.724 -    ///compute the
   2.725 -    ///%DFS path to each node. The algorithm computes
   2.726 -    ///- The %DFS tree.
   2.727 -    ///- The distance of each node from the root in the %DFS tree.
   2.728 -    ///
   2.729 -    ///\note d.run(s) is just a shortcut of the following code.
   2.730 -    ///\code
   2.731 -    ///  d.init();
   2.732 -    ///  d.addSource(s);
   2.733 -    ///  d.start();
   2.734 -    ///\endcode
   2.735 -    void run(Node s) {
   2.736 -      init();
   2.737 -      addSource(s);
   2.738 -      start();
   2.739 -    }
   2.740 -
   2.741 -    ///Finds the %DFS path between \c s and \c t.
   2.742 -
   2.743 -    ///Finds the %DFS path between \c s and \c t.
   2.744 -    ///
   2.745 -    ///\return The length of the %DFS s---t path if there exists one,
   2.746 -    ///0 otherwise.
   2.747 -    ///\note Apart from the return value, d.run(s,t) is
   2.748 -    ///just a shortcut of the following code.
   2.749 -    ///\code
   2.750 -    ///  d.init();
   2.751 -    ///  d.addSource(s);
   2.752 -    ///  d.start(t);
   2.753 -    ///\endcode
   2.754 -    int run(Node s,Node t) {
   2.755 -      init();
   2.756 -      addSource(s);
   2.757 -      start(t);
   2.758 -      return reached(t)?_stack_head+1:0;
   2.759 -    }
   2.760 -
   2.761      ///@}
   2.762  
   2.763      ///\name Query Functions
   2.764      ///The result of the %DFS algorithm can be obtained using these
   2.765      ///functions.\n
   2.766 -    ///Before the use of these functions,
   2.767 -    ///either run() or start() must be called.
   2.768 +    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
   2.769 +    ///"start()" must be called before using them.
   2.770  
   2.771      ///@{
   2.772  
   2.773 -    typedef PredMapPath<Digraph, PredMap> Path;
   2.774 +    ///The DFS path to a node.
   2.775  
   2.776 -    ///Gives back the shortest path.
   2.777 +    ///Returns the DFS path to a node.
   2.778 +    ///
   2.779 +    ///\warning \c t should be reachable from the root.
   2.780 +    ///
   2.781 +    ///\pre Either \ref run() or \ref start() must be called before
   2.782 +    ///using this function.
   2.783 +    Path path(Node t) const { return Path(*G, *_pred, t); }
   2.784  
   2.785 -    ///Gives back the shortest path.
   2.786 -    ///\pre The \c t should be reachable from the source.
   2.787 -    Path path(Node t)
   2.788 -    {
   2.789 -      return Path(*G, *_pred, t);
   2.790 -    }
   2.791 +    ///The distance of a node from the root.
   2.792  
   2.793 -    ///The distance of a node from the root(s).
   2.794 -
   2.795 -    ///Returns the distance of a node from the root(s).
   2.796 -    ///\pre \ref run() must be called before using this function.
   2.797 -    ///\warning If node \c v is unreachable from the root(s) then the return
   2.798 -    ///value of this funcion is undefined.
   2.799 +    ///Returns the distance of a node from the root.
   2.800 +    ///
   2.801 +    ///\warning If node \c v is not reachable from the root, then
   2.802 +    ///the return value of this function is undefined.
   2.803 +    ///
   2.804 +    ///\pre Either \ref run() or \ref start() must be called before
   2.805 +    ///using this function.
   2.806      int dist(Node v) const { return (*_dist)[v]; }
   2.807  
   2.808 -    ///Returns the 'previous arc' of the %DFS tree.
   2.809 +    ///Returns the 'previous arc' of the %DFS tree for a node.
   2.810  
   2.811 -    ///For a node \c v it returns the 'previous arc'
   2.812 -    ///of the %DFS path,
   2.813 -    ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
   2.814 -    ///v. It is \ref INVALID
   2.815 -    ///if \c v is unreachable from the root(s) or \c v is a root. The
   2.816 -    ///%DFS tree used here is equal to the %DFS tree used in
   2.817 +    ///This function returns the 'previous arc' of the %DFS tree for the
   2.818 +    ///node \c v, i.e. it returns the last arc of a %DFS path from the
   2.819 +    ///root to \c v. It is \c INVALID
   2.820 +    ///if \c v is not reachable from the root(s) or if \c v is a root.
   2.821 +    ///
   2.822 +    ///The %DFS tree used here is equal to the %DFS tree used in
   2.823      ///\ref predNode().
   2.824 +    ///
   2.825      ///\pre Either \ref run() or \ref start() must be called before using
   2.826      ///this function.
   2.827      Arc predArc(Node v) const { return (*_pred)[v];}
   2.828  
   2.829      ///Returns the 'previous node' of the %DFS tree.
   2.830  
   2.831 -    ///For a node \c v it returns the 'previous node'
   2.832 -    ///of the %DFS tree,
   2.833 -    ///i.e. it returns the last but one node from a %DFS path from the
   2.834 -    ///root(s) to \c v.
   2.835 -    ///It is INVALID if \c v is unreachable from the root(s) or
   2.836 -    ///if \c v itself a root.
   2.837 -    ///The %DFS tree used here is equal to the %DFS
   2.838 -    ///tree used in \ref predArc().
   2.839 +    ///This function returns the 'previous node' of the %DFS
   2.840 +    ///tree for the node \c v, i.e. it returns the last but one node
   2.841 +    ///from a %DFS path from the root to \c v. It is \c INVALID
   2.842 +    ///if \c v is not reachable from the root(s) or if \c v is a root.
   2.843 +    ///
   2.844 +    ///The %DFS tree used here is equal to the %DFS tree used in
   2.845 +    ///\ref predArc().
   2.846 +    ///
   2.847      ///\pre Either \ref run() or \ref start() must be called before
   2.848      ///using this function.
   2.849      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   2.850                                    G->source((*_pred)[v]); }
   2.851  
   2.852 -    ///Returns a reference to the NodeMap of distances.
   2.853 -
   2.854 -    ///Returns a reference to the NodeMap of distances.
   2.855 -    ///\pre Either \ref run() or \ref init() must
   2.856 -    ///be called before using this function.
   2.857 +    ///\brief Returns a const reference to the node map that stores the
   2.858 +    ///distances of the nodes.
   2.859 +    ///
   2.860 +    ///Returns a const reference to the node map that stores the
   2.861 +    ///distances of the nodes calculated by the algorithm.
   2.862 +    ///
   2.863 +    ///\pre Either \ref run() or \ref init()
   2.864 +    ///must be called before using this function.
   2.865      const DistMap &distMap() const { return *_dist;}
   2.866  
   2.867 -    ///Returns a reference to the %DFS arc-tree map.
   2.868 -
   2.869 -    ///Returns a reference to the NodeMap of the arcs of the
   2.870 -    ///%DFS tree.
   2.871 +    ///\brief Returns a const reference to the node map that stores the
   2.872 +    ///predecessor arcs.
   2.873 +    ///
   2.874 +    ///Returns a const reference to the node map that stores the predecessor
   2.875 +    ///arcs, which form the DFS tree.
   2.876 +    ///
   2.877      ///\pre Either \ref run() or \ref init()
   2.878      ///must be called before using this function.
   2.879      const PredMap &predMap() const { return *_pred;}
   2.880  
   2.881 -    ///Checks if a node is reachable from the root.
   2.882 +    ///Checks if a node is reachable from the root(s).
   2.883  
   2.884      ///Returns \c true if \c v is reachable from the root(s).
   2.885 -    ///\warning The source nodes are inditated as unreachable.
   2.886      ///\pre Either \ref run() or \ref start()
   2.887      ///must be called before using this function.
   2.888 -    ///
   2.889 -    bool reached(Node v) { return (*_reached)[v]; }
   2.890 +    bool reached(Node v) const { return (*_reached)[v]; }
   2.891  
   2.892      ///@}
   2.893    };
   2.894  
   2.895 -  ///Default traits class of Dfs function.
   2.896 +  ///Default traits class of dfs() function.
   2.897  
   2.898 -  ///Default traits class of Dfs function.
   2.899 +  ///Default traits class of dfs() function.
   2.900    ///\tparam GR Digraph type.
   2.901    template<class GR>
   2.902    struct DfsWizardDefaultTraits
   2.903    {
   2.904 -    ///The digraph type the algorithm runs on.
   2.905 +    ///The type of the digraph the algorithm runs on.
   2.906      typedef GR Digraph;
   2.907 -    ///\brief The type of the map that stores the last
   2.908 +
   2.909 +    ///\brief The type of the map that stores the predecessor
   2.910      ///arcs of the %DFS paths.
   2.911      ///
   2.912 -    ///The type of the map that stores the last
   2.913 +    ///The type of the map that stores the predecessor
   2.914      ///arcs of the %DFS paths.
   2.915      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.916      ///
   2.917 -    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
   2.918 -    ///Instantiates a PredMap.
   2.919 +    typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
   2.920 +    ///Instantiates a \ref PredMap.
   2.921  
   2.922      ///This function instantiates a \ref PredMap.
   2.923 -    ///\param g is the digraph, to which we would like to define the PredMap.
   2.924 +    ///\param g is the digraph, to which we would like to define the
   2.925 +    ///\ref PredMap.
   2.926      ///\todo The digraph alone may be insufficient to initialize
   2.927  #ifdef DOXYGEN
   2.928 -    static PredMap *createPredMap(const GR &g)
   2.929 +    static PredMap *createPredMap(const Digraph &g)
   2.930  #else
   2.931 -    static PredMap *createPredMap(const GR &)
   2.932 +    static PredMap *createPredMap(const Digraph &)
   2.933  #endif
   2.934      {
   2.935        return new PredMap();
   2.936 @@ -769,63 +797,63 @@
   2.937  
   2.938      ///The type of the map that indicates which nodes are processed.
   2.939      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.940 -    ///\todo named parameter to set this type, function to read and write.
   2.941      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   2.942 -    ///Instantiates a ProcessedMap.
   2.943 +    ///Instantiates a \ref ProcessedMap.
   2.944  
   2.945      ///This function instantiates a \ref ProcessedMap.
   2.946      ///\param g is the digraph, to which
   2.947 -    ///we would like to define the \ref ProcessedMap
   2.948 +    ///we would like to define the \ref ProcessedMap.
   2.949  #ifdef DOXYGEN
   2.950 -    static ProcessedMap *createProcessedMap(const GR &g)
   2.951 +    static ProcessedMap *createProcessedMap(const Digraph &g)
   2.952  #else
   2.953 -    static ProcessedMap *createProcessedMap(const GR &)
   2.954 +    static ProcessedMap *createProcessedMap(const Digraph &)
   2.955  #endif
   2.956      {
   2.957        return new ProcessedMap();
   2.958      }
   2.959 +
   2.960      ///The type of the map that indicates which nodes are reached.
   2.961  
   2.962      ///The type of the map that indicates which nodes are reached.
   2.963 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.964 -    ///\todo named parameter to set this type, function to read and write.
   2.965 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   2.966      typedef typename Digraph::template NodeMap<bool> ReachedMap;
   2.967 -    ///Instantiates a ReachedMap.
   2.968 +    ///Instantiates a \ref ReachedMap.
   2.969  
   2.970      ///This function instantiates a \ref ReachedMap.
   2.971 -    ///\param G is the digraph, to which
   2.972 +    ///\param g is the digraph, to which
   2.973      ///we would like to define the \ref ReachedMap.
   2.974 -    static ReachedMap *createReachedMap(const GR &G)
   2.975 +    static ReachedMap *createReachedMap(const Digraph &g)
   2.976      {
   2.977 -      return new ReachedMap(G);
   2.978 +      return new ReachedMap(g);
   2.979      }
   2.980 -    ///The type of the map that stores the dists of the nodes.
   2.981  
   2.982 -    ///The type of the map that stores the dists of the nodes.
   2.983 +    ///The type of the map that stores the distances of the nodes.
   2.984 +
   2.985 +    ///The type of the map that stores the distances of the nodes.
   2.986      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   2.987      ///
   2.988      typedef NullMap<typename Digraph::Node,int> DistMap;
   2.989 -    ///Instantiates a DistMap.
   2.990 +    ///Instantiates a \ref DistMap.
   2.991  
   2.992      ///This function instantiates a \ref DistMap.
   2.993      ///\param g is the digraph, to which we would like to define
   2.994      ///the \ref DistMap
   2.995  #ifdef DOXYGEN
   2.996 -    static DistMap *createDistMap(const GR &g)
   2.997 +    static DistMap *createDistMap(const Digraph &g)
   2.998  #else
   2.999 -    static DistMap *createDistMap(const GR &)
  2.1000 +    static DistMap *createDistMap(const Digraph &)
  2.1001  #endif
  2.1002      {
  2.1003        return new DistMap();
  2.1004      }
  2.1005    };
  2.1006  
  2.1007 -  /// Default traits used by \ref DfsWizard
  2.1008 +  /// Default traits class used by \ref DfsWizard
  2.1009  
  2.1010    /// To make it easier to use Dfs algorithm
  2.1011 -  ///we have created a wizard class.
  2.1012 +  /// we have created a wizard class.
  2.1013    /// This \ref DfsWizard class needs default traits,
  2.1014 -  ///as well as the \ref Dfs class.
  2.1015 +  /// as well as the \ref Dfs class.
  2.1016    /// The \ref DfsWizardBase is a class to be the default traits of the
  2.1017    /// \ref DfsWizard class.
  2.1018    template<class GR>
  2.1019 @@ -834,20 +862,20 @@
  2.1020  
  2.1021      typedef DfsWizardDefaultTraits<GR> Base;
  2.1022    protected:
  2.1023 -    /// Type of the nodes in the digraph.
  2.1024 +    //The type of the nodes in the digraph.
  2.1025      typedef typename Base::Digraph::Node Node;
  2.1026  
  2.1027 -    /// Pointer to the underlying digraph.
  2.1028 +    //Pointer to the digraph the algorithm runs on.
  2.1029      void *_g;
  2.1030 -    ///Pointer to the map of reached nodes.
  2.1031 +    //Pointer to the map of reached nodes.
  2.1032      void *_reached;
  2.1033 -    ///Pointer to the map of processed nodes.
  2.1034 +    //Pointer to the map of processed nodes.
  2.1035      void *_processed;
  2.1036 -    ///Pointer to the map of predecessors arcs.
  2.1037 +    //Pointer to the map of predecessors arcs.
  2.1038      void *_pred;
  2.1039 -    ///Pointer to the map of distances.
  2.1040 +    //Pointer to the map of distances.
  2.1041      void *_dist;
  2.1042 -    ///Pointer to the source node.
  2.1043 +    //Pointer to the source node.
  2.1044      Node _source;
  2.1045  
  2.1046      public:
  2.1047 @@ -856,26 +884,28 @@
  2.1048      /// This constructor does not require parameters, therefore it initiates
  2.1049      /// all of the attributes to default values (0, INVALID).
  2.1050      DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
  2.1051 -                           _dist(0), _source(INVALID) {}
  2.1052 +                      _dist(0), _source(INVALID) {}
  2.1053  
  2.1054      /// Constructor.
  2.1055  
  2.1056      /// This constructor requires some parameters,
  2.1057      /// listed in the parameters list.
  2.1058      /// Others are initiated to 0.
  2.1059 -    /// \param g is the initial value of  \ref _g
  2.1060 -    /// \param s is the initial value of  \ref _source
  2.1061 +    /// \param g The digraph the algorithm runs on.
  2.1062 +    /// \param s The source node.
  2.1063      DfsWizardBase(const GR &g, Node s=INVALID) :
  2.1064        _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  2.1065        _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
  2.1066  
  2.1067    };
  2.1068  
  2.1069 -  /// A class to make the usage of the Dfs algorithm easier
  2.1070 +  /// Auxiliary class for the function type interface of DFS algorithm.
  2.1071  
  2.1072 -  /// This class is created to make it easier to use the Dfs algorithm.
  2.1073 -  /// It uses the functions and features of the plain \ref Dfs,
  2.1074 -  /// but it is much simpler to use it.
  2.1075 +  /// This auxiliary class is created to implement the function type
  2.1076 +  /// interface of \ref Dfs algorithm. It uses the functions and features
  2.1077 +  /// of the plain \ref Dfs, but it is much simpler to use it.
  2.1078 +  /// It should only be used through the \ref dfs() function, which makes
  2.1079 +  /// it easier to use the algorithm.
  2.1080    ///
  2.1081    /// Simplicity means that the way to change the types defined
  2.1082    /// in the traits class is based on functions that returns the new class
  2.1083 @@ -884,41 +914,37 @@
  2.1084    /// the new class with the modified type comes from
  2.1085    /// the original class by using the ::
  2.1086    /// operator. In the case of \ref DfsWizard only
  2.1087 -  /// a function have to be called and it will
  2.1088 +  /// a function have to be called, and it will
  2.1089    /// return the needed class.
  2.1090    ///
  2.1091 -  /// It does not have own \ref run method. When its \ref run method is called
  2.1092 -  /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
  2.1093 -  /// method of it.
  2.1094 +  /// It does not have own \ref run() method. When its \ref run() method
  2.1095 +  /// is called, it initiates a plain \ref Dfs object, and calls the
  2.1096 +  /// \ref Dfs::run() method of it.
  2.1097    template<class TR>
  2.1098    class DfsWizard : public TR
  2.1099    {
  2.1100      typedef TR Base;
  2.1101  
  2.1102 -    ///The type of the underlying digraph.
  2.1103 +    ///The type of the digraph the algorithm runs on.
  2.1104      typedef typename TR::Digraph Digraph;
  2.1105 -    //\e
  2.1106 +
  2.1107      typedef typename Digraph::Node Node;
  2.1108 -    //\e
  2.1109      typedef typename Digraph::NodeIt NodeIt;
  2.1110 -    //\e
  2.1111      typedef typename Digraph::Arc Arc;
  2.1112 -    //\e
  2.1113      typedef typename Digraph::OutArcIt OutArcIt;
  2.1114  
  2.1115 -    ///\brief The type of the map that stores
  2.1116 -    ///the reached nodes
  2.1117 +    ///\brief The type of the map that stores the predecessor
  2.1118 +    ///arcs of the shortest paths.
  2.1119 +    typedef typename TR::PredMap PredMap;
  2.1120 +    ///\brief The type of the map that stores the distances of the nodes.
  2.1121 +    typedef typename TR::DistMap DistMap;
  2.1122 +    ///\brief The type of the map that indicates which nodes are reached.
  2.1123      typedef typename TR::ReachedMap ReachedMap;
  2.1124 -    ///\brief The type of the map that stores
  2.1125 -    ///the processed nodes
  2.1126 +    ///\brief The type of the map that indicates which nodes are processed.
  2.1127      typedef typename TR::ProcessedMap ProcessedMap;
  2.1128 -    ///\brief The type of the map that stores the last
  2.1129 -    ///arcs of the %DFS paths.
  2.1130 -    typedef typename TR::PredMap PredMap;
  2.1131 -    ///The type of the map that stores the distances of the nodes.
  2.1132 -    typedef typename TR::DistMap DistMap;
  2.1133  
  2.1134    public:
  2.1135 +
  2.1136      /// Constructor.
  2.1137      DfsWizard() : TR() {}
  2.1138  
  2.1139 @@ -934,10 +960,10 @@
  2.1140  
  2.1141      ~DfsWizard() {}
  2.1142  
  2.1143 -    ///Runs Dfs algorithm from a given node.
  2.1144 +    ///Runs DFS algorithm from a source node.
  2.1145  
  2.1146 -    ///Runs Dfs algorithm from a given node.
  2.1147 -    ///The node can be given by the \ref source function.
  2.1148 +    ///Runs DFS algorithm from a source node.
  2.1149 +    ///The node can be given with the \ref source() function.
  2.1150      void run()
  2.1151      {
  2.1152        if(Base::_source==INVALID) throw UninitializedParameter();
  2.1153 @@ -953,9 +979,9 @@
  2.1154        alg.run(Base::_source);
  2.1155      }
  2.1156  
  2.1157 -    ///Runs Dfs algorithm from the given node.
  2.1158 +    ///Runs DFS algorithm from the given node.
  2.1159  
  2.1160 -    ///Runs Dfs algorithm from the given node.
  2.1161 +    ///Runs DFS algorithm from the given node.
  2.1162      ///\param s is the given source.
  2.1163      void run(Node s)
  2.1164      {
  2.1165 @@ -963,19 +989,27 @@
  2.1166        run();
  2.1167      }
  2.1168  
  2.1169 +    /// Sets the source node, from which the Dfs algorithm runs.
  2.1170 +
  2.1171 +    /// Sets the source node, from which the Dfs algorithm runs.
  2.1172 +    /// \param s is the source node.
  2.1173 +    DfsWizard<TR> &source(Node s)
  2.1174 +    {
  2.1175 +      Base::_source=s;
  2.1176 +      return *this;
  2.1177 +    }
  2.1178 +
  2.1179      template<class T>
  2.1180      struct DefPredMapBase : public Base {
  2.1181        typedef T PredMap;
  2.1182        static PredMap *createPredMap(const Digraph &) { return 0; };
  2.1183        DefPredMapBase(const TR &b) : TR(b) {}
  2.1184      };
  2.1185 -
  2.1186      ///\brief \ref named-templ-param "Named parameter"
  2.1187 -    ///function for setting PredMap type
  2.1188 +    ///for setting \ref PredMap object.
  2.1189      ///
  2.1190 -    /// \ref named-templ-param "Named parameter"
  2.1191 -    ///function for setting PredMap type
  2.1192 -    ///
  2.1193 +    ///\ref named-templ-param "Named parameter"
  2.1194 +    ///for setting \ref PredMap object.
  2.1195      template<class T>
  2.1196      DfsWizard<DefPredMapBase<T> > predMap(const T &t)
  2.1197      {
  2.1198 @@ -983,20 +1017,17 @@
  2.1199        return DfsWizard<DefPredMapBase<T> >(*this);
  2.1200      }
  2.1201  
  2.1202 -
  2.1203      template<class T>
  2.1204      struct DefReachedMapBase : public Base {
  2.1205        typedef T ReachedMap;
  2.1206        static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  2.1207        DefReachedMapBase(const TR &b) : TR(b) {}
  2.1208      };
  2.1209 -
  2.1210      ///\brief \ref named-templ-param "Named parameter"
  2.1211 -    ///function for setting ReachedMap
  2.1212 +    ///for setting \ref ReachedMap object.
  2.1213      ///
  2.1214      /// \ref named-templ-param "Named parameter"
  2.1215 -    ///function for setting ReachedMap
  2.1216 -    ///
  2.1217 +    ///for setting \ref ReachedMap object.
  2.1218      template<class T>
  2.1219      DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  2.1220      {
  2.1221 @@ -1004,20 +1035,17 @@
  2.1222        return DfsWizard<DefReachedMapBase<T> >(*this);
  2.1223      }
  2.1224  
  2.1225 -
  2.1226      template<class T>
  2.1227      struct DefProcessedMapBase : public Base {
  2.1228        typedef T ProcessedMap;
  2.1229        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  2.1230        DefProcessedMapBase(const TR &b) : TR(b) {}
  2.1231      };
  2.1232 -
  2.1233      ///\brief \ref named-templ-param "Named parameter"
  2.1234 -    ///function for setting ProcessedMap
  2.1235 +    ///for setting \ref ProcessedMap object.
  2.1236      ///
  2.1237      /// \ref named-templ-param "Named parameter"
  2.1238 -    ///function for setting ProcessedMap
  2.1239 -    ///
  2.1240 +    ///for setting \ref ProcessedMap object.
  2.1241      template<class T>
  2.1242      DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  2.1243      {
  2.1244 @@ -1031,13 +1059,11 @@
  2.1245        static DistMap *createDistMap(const Digraph &) { return 0; };
  2.1246        DefDistMapBase(const TR &b) : TR(b) {}
  2.1247      };
  2.1248 -
  2.1249      ///\brief \ref named-templ-param "Named parameter"
  2.1250 -    ///function for setting DistMap type
  2.1251 +    ///for setting \ref DistMap object.
  2.1252      ///
  2.1253 -    /// \ref named-templ-param "Named parameter"
  2.1254 -    ///function for setting DistMap type
  2.1255 -    ///
  2.1256 +    ///\ref named-templ-param "Named parameter"
  2.1257 +    ///for setting \ref DistMap object.
  2.1258      template<class T>
  2.1259      DfsWizard<DefDistMapBase<T> > distMap(const T &t)
  2.1260      {
  2.1261 @@ -1045,16 +1071,6 @@
  2.1262        return DfsWizard<DefDistMapBase<T> >(*this);
  2.1263      }
  2.1264  
  2.1265 -    /// Sets the source node, from which the Dfs algorithm runs.
  2.1266 -
  2.1267 -    /// Sets the source node, from which the Dfs algorithm runs.
  2.1268 -    /// \param s is the source node.
  2.1269 -    DfsWizard<TR> &source(Node s)
  2.1270 -    {
  2.1271 -      Base::_source=s;
  2.1272 -      return *this;
  2.1273 -    }
  2.1274 -
  2.1275    };
  2.1276  
  2.1277    ///Function type interface for Dfs algorithm.
  2.1278 @@ -1082,47 +1098,46 @@
  2.1279    }
  2.1280  
  2.1281  #ifdef DOXYGEN
  2.1282 -  /// \brief Visitor class for dfs.
  2.1283 +  /// \brief Visitor class for DFS.
  2.1284    ///
  2.1285 -  /// It gives a simple interface for a functional interface for dfs
  2.1286 -  /// traversal. The traversal on a linear data structure.
  2.1287 +  /// This class defines the interface of the DfsVisit events, and
  2.1288 +  /// it could be the base of a real visitor class.
  2.1289    template <typename _Digraph>
  2.1290    struct DfsVisitor {
  2.1291      typedef _Digraph Digraph;
  2.1292      typedef typename Digraph::Arc Arc;
  2.1293      typedef typename Digraph::Node Node;
  2.1294 -    /// \brief Called when the arc reach a node.
  2.1295 +    /// \brief Called for the source node of the DFS.
  2.1296      ///
  2.1297 -    /// It is called when the dfs find an arc which target is not
  2.1298 -    /// reached yet.
  2.1299 +    /// This function is called for the source node of the DFS.
  2.1300 +    void start(const Node& node) {}
  2.1301 +    /// \brief Called when the source node is leaved.
  2.1302 +    ///
  2.1303 +    /// This function is called when the source node is leaved.
  2.1304 +    void stop(const Node& node) {}
  2.1305 +    /// \brief Called when a node is reached first time.
  2.1306 +    ///
  2.1307 +    /// This function is called when a node is reached first time.
  2.1308 +    void reach(const Node& node) {}
  2.1309 +    /// \brief Called when an arc reaches a new node.
  2.1310 +    ///
  2.1311 +    /// This function is called when the DFS finds an arc whose target node
  2.1312 +    /// is not reached yet.
  2.1313      void discover(const Arc& arc) {}
  2.1314 -    /// \brief Called when the node reached first time.
  2.1315 -    ///
  2.1316 -    /// It is Called when the node reached first time.
  2.1317 -    void reach(const Node& node) {}
  2.1318 -    /// \brief Called when we step back on an arc.
  2.1319 -    ///
  2.1320 -    /// It is called when the dfs should step back on the arc.
  2.1321 -    void backtrack(const Arc& arc) {}
  2.1322 -    /// \brief Called when we step back from the node.
  2.1323 -    ///
  2.1324 -    /// It is called when we step back from the node.
  2.1325 -    void leave(const Node& node) {}
  2.1326 -    /// \brief Called when the arc examined but target of the arc
  2.1327 +    /// \brief Called when an arc is examined but its target node is
  2.1328      /// already discovered.
  2.1329      ///
  2.1330 -    /// It called when the arc examined but the target of the arc
  2.1331 +    /// This function is called when an arc is examined but its target node is
  2.1332      /// already discovered.
  2.1333      void examine(const Arc& arc) {}
  2.1334 -    /// \brief Called for the source node of the dfs.
  2.1335 +    /// \brief Called when the DFS steps back from a node.
  2.1336      ///
  2.1337 -    /// It is called for the source node of the dfs.
  2.1338 -    void start(const Node& node) {}
  2.1339 -    /// \brief Called when we leave the source node of the dfs.
  2.1340 +    /// This function is called when the DFS steps back from a node.
  2.1341 +    void leave(const Node& node) {}
  2.1342 +    /// \brief Called when the DFS steps back on an arc.
  2.1343      ///
  2.1344 -    /// It is called when we leave the source node of the dfs.
  2.1345 -    void stop(const Node& node) {}
  2.1346 -
  2.1347 +    /// This function is called when the DFS steps back on an arc.
  2.1348 +    void backtrack(const Arc& arc) {}
  2.1349    };
  2.1350  #else
  2.1351    template <typename _Digraph>
  2.1352 @@ -1130,26 +1145,26 @@
  2.1353      typedef _Digraph Digraph;
  2.1354      typedef typename Digraph::Arc Arc;
  2.1355      typedef typename Digraph::Node Node;
  2.1356 -    void discover(const Arc&) {}
  2.1357 -    void reach(const Node&) {}
  2.1358 -    void backtrack(const Arc&) {}
  2.1359 -    void leave(const Node&) {}
  2.1360 -    void examine(const Arc&) {}
  2.1361      void start(const Node&) {}
  2.1362      void stop(const Node&) {}
  2.1363 +    void reach(const Node&) {}
  2.1364 +    void discover(const Arc&) {}
  2.1365 +    void examine(const Arc&) {}
  2.1366 +    void leave(const Node&) {}
  2.1367 +    void backtrack(const Arc&) {}
  2.1368  
  2.1369      template <typename _Visitor>
  2.1370      struct Constraints {
  2.1371        void constraints() {
  2.1372          Arc arc;
  2.1373          Node node;
  2.1374 -        visitor.discover(arc);
  2.1375 -        visitor.reach(node);
  2.1376 -        visitor.backtrack(arc);
  2.1377 -        visitor.leave(node);
  2.1378 -        visitor.examine(arc);
  2.1379          visitor.start(node);
  2.1380          visitor.stop(arc);
  2.1381 +        visitor.reach(node);
  2.1382 +        visitor.discover(arc);
  2.1383 +        visitor.examine(arc);
  2.1384 +        visitor.leave(node);
  2.1385 +        visitor.backtrack(arc);
  2.1386        }
  2.1387        _Visitor& visitor;
  2.1388      };
  2.1389 @@ -1159,21 +1174,20 @@
  2.1390    /// \brief Default traits class of DfsVisit class.
  2.1391    ///
  2.1392    /// Default traits class of DfsVisit class.
  2.1393 -  /// \tparam _Digraph Digraph type.
  2.1394 +  /// \tparam _Digraph The type of the digraph the algorithm runs on.
  2.1395    template<class _Digraph>
  2.1396    struct DfsVisitDefaultTraits {
  2.1397  
  2.1398 -    /// \brief The digraph type the algorithm runs on.
  2.1399 +    /// \brief The type of the digraph the algorithm runs on.
  2.1400      typedef _Digraph Digraph;
  2.1401  
  2.1402      /// \brief The type of the map that indicates which nodes are reached.
  2.1403      ///
  2.1404      /// The type of the map that indicates which nodes are reached.
  2.1405 -    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  2.1406 -    /// \todo named parameter to set this type, function to read and write.
  2.1407 +    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  2.1408      typedef typename Digraph::template NodeMap<bool> ReachedMap;
  2.1409  
  2.1410 -    /// \brief Instantiates a ReachedMap.
  2.1411 +    /// \brief Instantiates a \ref ReachedMap.
  2.1412      ///
  2.1413      /// This function instantiates a \ref ReachedMap.
  2.1414      /// \param digraph is the digraph, to which
  2.1415 @@ -1184,31 +1198,30 @@
  2.1416  
  2.1417    };
  2.1418  
  2.1419 -  /// %DFS Visit algorithm class.
  2.1420 -
  2.1421    /// \ingroup search
  2.1422 +  ///
  2.1423 +  /// \brief %DFS algorithm class with visitor interface.
  2.1424 +  ///
  2.1425    /// This class provides an efficient implementation of the %DFS algorithm
  2.1426    /// with visitor interface.
  2.1427    ///
  2.1428    /// The %DfsVisit class provides an alternative interface to the Dfs
  2.1429    /// class. It works with callback mechanism, the DfsVisit object calls
  2.1430 -  /// on every dfs event the \c Visitor class member functions.
  2.1431 +  /// the member functions of the \c Visitor class on every DFS event.
  2.1432    ///
  2.1433 -  /// \tparam _Digraph The digraph type the algorithm runs on.
  2.1434 +  /// \tparam _Digraph The type of the digraph the algorithm runs on.
  2.1435    /// The default value is
  2.1436 -  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
  2.1437 -  /// is only passed to \ref DfsDefaultTraits.
  2.1438 -  /// \tparam _Visitor The Visitor object for the algorithm. The
  2.1439 -  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
  2.1440 -  /// does not observe the Dfs events. If you want to observe the dfs
  2.1441 -  /// events you should implement your own Visitor class.
  2.1442 +  /// \ref ListDigraph. The value of _Digraph is not used directly by
  2.1443 +  /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
  2.1444 +  /// \tparam _Visitor The Visitor type that is used by the algorithm.
  2.1445 +  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
  2.1446 +  /// does not observe the DFS events. If you want to observe the DFS
  2.1447 +  /// events, you should implement your own visitor class.
  2.1448    /// \tparam _Traits Traits class to set various data types used by the
  2.1449    /// algorithm. The default traits class is
  2.1450    /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
  2.1451    /// See \ref DfsVisitDefaultTraits for the documentation of
  2.1452 -  /// a Dfs visit traits class.
  2.1453 -  ///
  2.1454 -  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
  2.1455 +  /// a DFS visit traits class.
  2.1456  #ifdef DOXYGEN
  2.1457    template <typename _Digraph, typename _Visitor, typename _Traits>
  2.1458  #else
  2.1459 @@ -1222,7 +1235,7 @@
  2.1460      /// \brief \ref Exception for uninitialized parameters.
  2.1461      ///
  2.1462      /// This error represents problems in the initialization
  2.1463 -    /// of the parameters of the algorithms.
  2.1464 +    /// of the parameters of the algorithm.
  2.1465      class UninitializedParameter : public lemon::UninitializedParameter {
  2.1466      public:
  2.1467        virtual const char* what() const throw()
  2.1468 @@ -1231,13 +1244,16 @@
  2.1469        }
  2.1470      };
  2.1471  
  2.1472 +    ///The traits class.
  2.1473      typedef _Traits Traits;
  2.1474  
  2.1475 +    ///The type of the digraph the algorithm runs on.
  2.1476      typedef typename Traits::Digraph Digraph;
  2.1477  
  2.1478 +    ///The visitor type used by the algorithm.
  2.1479      typedef _Visitor Visitor;
  2.1480  
  2.1481 -    ///The type of the map indicating which nodes are reached.
  2.1482 +    ///The type of the map that indicates which nodes are reached.
  2.1483      typedef typename Traits::ReachedMap ReachedMap;
  2.1484  
  2.1485    private:
  2.1486 @@ -1247,21 +1263,20 @@
  2.1487      typedef typename Digraph::Arc Arc;
  2.1488      typedef typename Digraph::OutArcIt OutArcIt;
  2.1489  
  2.1490 -    /// Pointer to the underlying digraph.
  2.1491 +    //Pointer to the underlying digraph.
  2.1492      const Digraph *_digraph;
  2.1493 -    /// Pointer to the visitor object.
  2.1494 +    //Pointer to the visitor object.
  2.1495      Visitor *_visitor;
  2.1496 -    ///Pointer to the map of reached status of the nodes.
  2.1497 +    //Pointer to the map of reached status of the nodes.
  2.1498      ReachedMap *_reached;
  2.1499 -    ///Indicates if \ref _reached is locally allocated (\c true) or not.
  2.1500 +    //Indicates if _reached is locally allocated (true) or not.
  2.1501      bool local_reached;
  2.1502  
  2.1503      std::vector<typename Digraph::Arc> _stack;
  2.1504      int _stack_head;
  2.1505  
  2.1506 -    /// \brief Creates the maps if necessary.
  2.1507 -    ///
  2.1508 -    /// Creates the maps if necessary.
  2.1509 +    ///Creates the maps if necessary.
  2.1510 +    ///\todo Better memory allocation (instead of new).
  2.1511      void create_maps() {
  2.1512        if(!_reached) {
  2.1513          local_reached = true;
  2.1514 @@ -1288,9 +1303,9 @@
  2.1515        }
  2.1516      };
  2.1517      /// \brief \ref named-templ-param "Named parameter" for setting
  2.1518 -    /// ReachedMap type
  2.1519 +    /// ReachedMap type.
  2.1520      ///
  2.1521 -    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  2.1522 +    /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
  2.1523      template <class T>
  2.1524      struct DefReachedMap : public DfsVisit< Digraph, Visitor,
  2.1525                                              DefReachedMapTraits<T> > {
  2.1526 @@ -1304,25 +1319,22 @@
  2.1527      ///
  2.1528      /// Constructor.
  2.1529      ///
  2.1530 -    /// \param digraph the digraph the algorithm will run on.
  2.1531 -    /// \param visitor The visitor of the algorithm.
  2.1532 -    ///
  2.1533 +    /// \param digraph The digraph the algorithm runs on.
  2.1534 +    /// \param visitor The visitor object of the algorithm.
  2.1535      DfsVisit(const Digraph& digraph, Visitor& visitor)
  2.1536        : _digraph(&digraph), _visitor(&visitor),
  2.1537          _reached(0), local_reached(false) {}
  2.1538  
  2.1539      /// \brief Destructor.
  2.1540 -    ///
  2.1541 -    /// Destructor.
  2.1542      ~DfsVisit() {
  2.1543        if(local_reached) delete _reached;
  2.1544      }
  2.1545  
  2.1546 -    /// \brief Sets the map indicating if a node is reached.
  2.1547 +    /// \brief Sets the map that indicates which nodes are reached.
  2.1548      ///
  2.1549 -    /// Sets the map indicating if a node is reached.
  2.1550 +    /// Sets the map that indicates which nodes are reached.
  2.1551      /// If you don't use this function before calling \ref run(),
  2.1552 -    /// it will allocate one. The destuctor deallocates this
  2.1553 +    /// it will allocate one. The destructor deallocates this
  2.1554      /// automatically allocated map, of course.
  2.1555      /// \return <tt> (*this) </tt>
  2.1556      DfsVisit &reachedMap(ReachedMap &m) {
  2.1557 @@ -1335,21 +1347,23 @@
  2.1558      }
  2.1559  
  2.1560    public:
  2.1561 +
  2.1562      /// \name Execution control
  2.1563      /// The simplest way to execute the algorithm is to use
  2.1564 -    /// one of the member functions called \c run(...).
  2.1565 +    /// one of the member functions called \ref lemon::DfsVisit::run()
  2.1566 +    /// "run()".
  2.1567      /// \n
  2.1568 -    /// If you need more control on the execution,
  2.1569 -    /// first you must call \ref init(), then you can adda source node
  2.1570 -    /// with \ref addSource().
  2.1571 -    /// Finally \ref start() will perform the actual path
  2.1572 -    /// computation.
  2.1573 +    /// If you need more control on the execution, first you must call
  2.1574 +    /// \ref lemon::DfsVisit::init() "init()", then you can add several
  2.1575 +    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
  2.1576 +    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
  2.1577 +    /// actual path computation.
  2.1578  
  2.1579      /// @{
  2.1580 +
  2.1581      /// \brief Initializes the internal data structures.
  2.1582      ///
  2.1583      /// Initializes the internal data structures.
  2.1584 -    ///
  2.1585      void init() {
  2.1586        create_maps();
  2.1587        _stack.resize(countNodes(*_digraph));
  2.1588 @@ -1359,10 +1373,18 @@
  2.1589        }
  2.1590      }
  2.1591  
  2.1592 -    /// \brief Adds a new source node.
  2.1593 +    ///Adds a new source node.
  2.1594 +
  2.1595 +    ///Adds a new source node to the set of nodes to be processed.
  2.1596      ///
  2.1597 -    /// Adds a new source node to the set of nodes to be processed.
  2.1598 -    void addSource(Node s) {
  2.1599 +    ///\pre The stack must be empty. (Otherwise the algorithm gives
  2.1600 +    ///false results.)
  2.1601 +    ///
  2.1602 +    ///\warning Distances will be wrong (or at least strange) in case of
  2.1603 +    ///multiple sources.
  2.1604 +    void addSource(Node s)
  2.1605 +    {
  2.1606 +      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
  2.1607        if(!(*_reached)[s]) {
  2.1608            _reached->set(s,true);
  2.1609            _visitor->start(s);
  2.1610 @@ -1383,7 +1405,7 @@
  2.1611      ///
  2.1612      /// \return The processed arc.
  2.1613      ///
  2.1614 -    /// \pre The stack must not be empty!
  2.1615 +    /// \pre The stack must not be empty.
  2.1616      Arc processNextArc() {
  2.1617        Arc e = _stack[_stack_head];
  2.1618        Node m = _digraph->target(e);
  2.1619 @@ -1417,37 +1439,58 @@
  2.1620      ///
  2.1621      /// \return The next arc to be processed or INVALID if the stack is
  2.1622      /// empty.
  2.1623 -    Arc nextArc() {
  2.1624 +    Arc nextArc() const {
  2.1625        return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
  2.1626      }
  2.1627  
  2.1628      /// \brief Returns \c false if there are nodes
  2.1629 -    /// to be processed in the queue
  2.1630 +    /// to be processed.
  2.1631      ///
  2.1632      /// Returns \c false if there are nodes
  2.1633 -    /// to be processed in the queue
  2.1634 -    bool emptyQueue() { return _stack_head < 0; }
  2.1635 +    /// to be processed in the queue (stack).
  2.1636 +    bool emptyQueue() const { return _stack_head < 0; }
  2.1637  
  2.1638      /// \brief Returns the number of the nodes to be processed.
  2.1639      ///
  2.1640 -    /// Returns the number of the nodes to be processed in the queue.
  2.1641 -    int queueSize() { return _stack_head + 1; }
  2.1642 +    /// Returns the number of the nodes to be processed in the queue (stack).
  2.1643 +    int queueSize() const { return _stack_head + 1; }
  2.1644  
  2.1645      /// \brief Executes the algorithm.
  2.1646      ///
  2.1647      /// Executes the algorithm.
  2.1648      ///
  2.1649 -    /// \pre init() must be called and at least one node should be added
  2.1650 -    /// with addSource() before using this function.
  2.1651 +    /// This method runs the %DFS algorithm from the root node
  2.1652 +    /// in order to compute the %DFS path to each node.
  2.1653 +    ///
  2.1654 +    /// The algorithm computes
  2.1655 +    /// - the %DFS tree,
  2.1656 +    /// - the distance of each node from the root in the %DFS tree.
  2.1657 +    ///
  2.1658 +    /// \pre init() must be called and a root node should be
  2.1659 +    /// added with addSource() before using this function.
  2.1660 +    ///
  2.1661 +    /// \note <tt>d.start()</tt> is just a shortcut of the following code.
  2.1662 +    /// \code
  2.1663 +    ///   while ( !d.emptyQueue() ) {
  2.1664 +    ///     d.processNextArc();
  2.1665 +    ///   }
  2.1666 +    /// \endcode
  2.1667      void start() {
  2.1668        while ( !emptyQueue() ) processNextArc();
  2.1669      }
  2.1670  
  2.1671 -    /// \brief Executes the algorithm until \c dest is reached.
  2.1672 +    /// \brief Executes the algorithm until the given target node is reached.
  2.1673      ///
  2.1674 -    /// Executes the algorithm until \c dest is reached.
  2.1675 +    /// Executes the algorithm until the given target node is reached.
  2.1676      ///
  2.1677 -    /// \pre init() must be called and at least one node should be added
  2.1678 +    /// This method runs the %DFS algorithm from the root node
  2.1679 +    /// in order to compute the DFS path to \c dest.
  2.1680 +    ///
  2.1681 +    /// The algorithm computes
  2.1682 +    /// - the %DFS path to \c dest,
  2.1683 +    /// - the distance of \c dest from the root in the %DFS tree.
  2.1684 +    ///
  2.1685 +    /// \pre init() must be called and a root node should be added
  2.1686      /// with addSource() before using this function.
  2.1687      void start(Node dest) {
  2.1688        while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
  2.1689 @@ -1458,28 +1501,37 @@
  2.1690      ///
  2.1691      /// Executes the algorithm until a condition is met.
  2.1692      ///
  2.1693 -    /// \pre init() must be called and at least one node should be added
  2.1694 +    /// This method runs the %DFS algorithm from the root node
  2.1695 +    /// until an arc \c a with <tt>am[a]</tt> true is found.
  2.1696 +    ///
  2.1697 +    /// \param am A \c bool (or convertible) arc map. The algorithm
  2.1698 +    /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
  2.1699 +    ///
  2.1700 +    /// \return The reached arc \c a with <tt>am[a]</tt> true or
  2.1701 +    /// \c INVALID if no such arc was found.
  2.1702 +    ///
  2.1703 +    /// \pre init() must be called and a root node should be added
  2.1704      /// with addSource() before using this function.
  2.1705      ///
  2.1706 -    /// \param em must be a bool (or convertible) arc map. The algorithm
  2.1707 -    /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
  2.1708 -    ///
  2.1709 -    ///\return The reached arc \c e with <tt>em[e]</tt> true or
  2.1710 -    ///\c INVALID if no such arc was found.
  2.1711 -    ///
  2.1712 -    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
  2.1713 +    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
  2.1714      /// not a node map.
  2.1715 -    template <typename EM>
  2.1716 -    Arc start(const EM &em) {
  2.1717 -      while ( !emptyQueue() && !em[_stack[_stack_head]] )
  2.1718 +    template <typename AM>
  2.1719 +    Arc start(const AM &am) {
  2.1720 +      while ( !emptyQueue() && !am[_stack[_stack_head]] )
  2.1721          processNextArc();
  2.1722        return emptyQueue() ? INVALID : _stack[_stack_head];
  2.1723      }
  2.1724  
  2.1725 -    /// \brief Runs %DFSVisit algorithm from node \c s.
  2.1726 +    /// \brief Runs the algorithm from the given node.
  2.1727      ///
  2.1728 -    /// This method runs the %DFS algorithm from a root node \c s.
  2.1729 -    /// \note d.run(s) is just a shortcut of the following code.
  2.1730 +    /// This method runs the %DFS algorithm from node \c s.
  2.1731 +    /// in order to compute the DFS path to each node.
  2.1732 +    ///
  2.1733 +    /// The algorithm computes
  2.1734 +    /// - the %DFS tree,
  2.1735 +    /// - the distance of each node from the root in the %DFS tree.
  2.1736 +    ///
  2.1737 +    /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
  2.1738      ///\code
  2.1739      ///   d.init();
  2.1740      ///   d.addSource(s);
  2.1741 @@ -1491,22 +1543,46 @@
  2.1742        start();
  2.1743      }
  2.1744  
  2.1745 -    /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
  2.1746 +    /// \brief Finds the %DFS path between \c s and \c t.
  2.1747 +
  2.1748 +    /// This method runs the %DFS algorithm from node \c s
  2.1749 +    /// in order to compute the DFS path to \c t.
  2.1750 +    ///
  2.1751 +    /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
  2.1752 +    /// if \c t is reachable form \c s, \c 0 otherwise.
  2.1753 +    ///
  2.1754 +    /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
  2.1755 +    /// just a shortcut of the following code.
  2.1756 +    ///\code
  2.1757 +    ///   d.init();
  2.1758 +    ///   d.addSource(s);
  2.1759 +    ///   d.start(t);
  2.1760 +    ///\endcode
  2.1761 +    int run(Node s,Node t) {
  2.1762 +      init();
  2.1763 +      addSource(s);
  2.1764 +      start(t);
  2.1765 +      return reached(t)?_stack_head+1:0;
  2.1766 +    }
  2.1767 +
  2.1768 +    /// \brief Runs the algorithm to visit all nodes in the digraph.
  2.1769  
  2.1770      /// This method runs the %DFS algorithm in order to
  2.1771 -    /// compute the %DFS path to each node. The algorithm computes
  2.1772 -    /// - The %DFS tree.
  2.1773 -    /// - The distance of each node from the root in the %DFS tree.
  2.1774 +    /// compute the %DFS path to each node.
  2.1775      ///
  2.1776 -    ///\note d.run() is just a shortcut of the following code.
  2.1777 +    /// The algorithm computes
  2.1778 +    /// - the %DFS tree,
  2.1779 +    /// - the distance of each node from the root in the %DFS tree.
  2.1780 +    ///
  2.1781 +    /// \note <tt>d.run()</tt> is just a shortcut of the following code.
  2.1782      ///\code
  2.1783 -    ///  d.init();
  2.1784 -    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
  2.1785 -    ///    if (!d.reached(it)) {
  2.1786 -    ///      d.addSource(it);
  2.1787 -    ///      d.start();
  2.1788 -    ///    }
  2.1789 -    ///  }
  2.1790 +    ///   d.init();
  2.1791 +    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
  2.1792 +    ///     if (!d.reached(n)) {
  2.1793 +    ///       d.addSource(n);
  2.1794 +    ///       d.start();
  2.1795 +    ///     }
  2.1796 +    ///   }
  2.1797      ///\endcode
  2.1798      void run() {
  2.1799        init();
  2.1800 @@ -1517,27 +1593,28 @@
  2.1801          }
  2.1802        }
  2.1803      }
  2.1804 +
  2.1805      ///@}
  2.1806  
  2.1807      /// \name Query Functions
  2.1808      /// The result of the %DFS algorithm can be obtained using these
  2.1809      /// functions.\n
  2.1810 -    /// Before the use of these functions,
  2.1811 -    /// either run() or start() must be called.
  2.1812 +    /// Either \ref lemon::DfsVisit::run() "run()" or
  2.1813 +    /// \ref lemon::DfsVisit::start() "start()" must be called before
  2.1814 +    /// using them.
  2.1815      ///@{
  2.1816 -    /// \brief Checks if a node is reachable from the root.
  2.1817 +
  2.1818 +    /// \brief Checks if a node is reachable from the root(s).
  2.1819      ///
  2.1820      /// Returns \c true if \c v is reachable from the root(s).
  2.1821 -    /// \warning The source nodes are inditated as unreachable.
  2.1822      /// \pre Either \ref run() or \ref start()
  2.1823      /// must be called before using this function.
  2.1824 -    ///
  2.1825      bool reached(Node v) { return (*_reached)[v]; }
  2.1826 +
  2.1827      ///@}
  2.1828 +
  2.1829    };
  2.1830  
  2.1831 -
  2.1832  } //END OF NAMESPACE LEMON
  2.1833  
  2.1834  #endif
  2.1835 -
     3.1 --- a/lemon/dijkstra.h	Wed Jul 30 12:07:48 2008 +0100
     3.2 +++ b/lemon/dijkstra.h	Mon Aug 04 22:00:36 2008 +0200
     3.3 @@ -33,10 +33,10 @@
     3.4  
     3.5  namespace lemon {
     3.6  
     3.7 -  /// \brief Default OperationTraits for the Dijkstra algorithm class.
     3.8 +  /// \brief Default operation traits for the Dijkstra algorithm class.
     3.9    ///
    3.10 -  /// It defines all computational operations and constants which are
    3.11 -  /// used in the Dijkstra algorithm.
    3.12 +  /// This operation traits class defines all computational operations and
    3.13 +  /// constants which are used in the Dijkstra algorithm.
    3.14    template <typename Value>
    3.15    struct DijkstraDefaultOperationTraits {
    3.16      /// \brief Gives back the zero value of the type.
    3.17 @@ -47,16 +47,19 @@
    3.18      static Value plus(const Value& left, const Value& right) {
    3.19        return left + right;
    3.20      }
    3.21 -    /// \brief Gives back true only if the first value less than the second.
    3.22 +    /// \brief Gives back true only if the first value is less than the second.
    3.23      static bool less(const Value& left, const Value& right) {
    3.24        return left < right;
    3.25      }
    3.26    };
    3.27  
    3.28 -  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
    3.29 +  /// \brief Widest path operation traits for the Dijkstra algorithm class.
    3.30    ///
    3.31 -  /// It defines all computational operations and constants which are
    3.32 -  /// used in the Dijkstra algorithm for widest path computation.
    3.33 +  /// This operation traits class defines all computational operations and
    3.34 +  /// constants which are used in the Dijkstra algorithm for widest path
    3.35 +  /// computation.
    3.36 +  ///
    3.37 +  /// \see DijkstraDefaultOperationTraits
    3.38    template <typename Value>
    3.39    struct DijkstraWidestPathOperationTraits {
    3.40      /// \brief Gives back the maximum value of the type.
    3.41 @@ -67,7 +70,7 @@
    3.42      static Value plus(const Value& left, const Value& right) {
    3.43        return std::min(left, right);
    3.44      }
    3.45 -    /// \brief Gives back true only if the first value less than the second.
    3.46 +    /// \brief Gives back true only if the first value is less than the second.
    3.47      static bool less(const Value& left, const Value& right) {
    3.48        return left < right;
    3.49      }
    3.50 @@ -76,141 +79,145 @@
    3.51    ///Default traits class of Dijkstra class.
    3.52  
    3.53    ///Default traits class of Dijkstra class.
    3.54 -  ///\tparam GR Digraph type.
    3.55 -  ///\tparam LM Type of length map.
    3.56 +  ///\tparam GR The type of the digraph.
    3.57 +  ///\tparam LM The type of the length map.
    3.58    template<class GR, class LM>
    3.59    struct DijkstraDefaultTraits
    3.60    {
    3.61 -    ///The digraph type the algorithm runs on.
    3.62 +    ///The type of the digraph the algorithm runs on.
    3.63      typedef GR Digraph;
    3.64 +
    3.65      ///The type of the map that stores the arc lengths.
    3.66  
    3.67      ///The type of the map that stores the arc lengths.
    3.68      ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
    3.69      typedef LM LengthMap;
    3.70 -    //The type of the length of the arcs.
    3.71 +    ///The type of the length of the arcs.
    3.72      typedef typename LM::Value Value;
    3.73 +
    3.74      /// Operation traits for Dijkstra algorithm.
    3.75  
    3.76 -    /// It defines the used operation by the algorithm.
    3.77 +    /// This class defines the operations that are used in the algorithm.
    3.78      /// \see DijkstraDefaultOperationTraits
    3.79      typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
    3.80 -    /// The cross reference type used by heap.
    3.81  
    3.82 +    /// The cross reference type used by the heap.
    3.83  
    3.84 -    /// The cross reference type used by heap.
    3.85 +    /// The cross reference type used by the heap.
    3.86      /// Usually it is \c Digraph::NodeMap<int>.
    3.87      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    3.88 -    ///Instantiates a HeapCrossRef.
    3.89 +    ///Instantiates a \ref HeapCrossRef.
    3.90  
    3.91 -    ///This function instantiates a \c HeapCrossRef.
    3.92 -    /// \param G is the digraph, to which we would like to define the
    3.93 -    /// HeapCrossRef.
    3.94 -    static HeapCrossRef *createHeapCrossRef(const GR &G)
    3.95 +    ///This function instantiates a \ref HeapCrossRef.
    3.96 +    /// \param g is the digraph, to which we would like to define the
    3.97 +    /// \ref HeapCrossRef.
    3.98 +    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
    3.99      {
   3.100 -      return new HeapCrossRef(G);
   3.101 +      return new HeapCrossRef(g);
   3.102      }
   3.103  
   3.104 -    ///The heap type used by Dijkstra algorithm.
   3.105 +    ///The heap type used by the Dijkstra algorithm.
   3.106  
   3.107 -    ///The heap type used by Dijkstra algorithm.
   3.108 +    ///The heap type used by the Dijkstra algorithm.
   3.109      ///
   3.110      ///\sa BinHeap
   3.111      ///\sa Dijkstra
   3.112      typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
   3.113 +    ///Instantiates a \ref Heap.
   3.114  
   3.115 -    static Heap *createHeap(HeapCrossRef& R)
   3.116 +    ///This function instantiates a \ref Heap.
   3.117 +    static Heap *createHeap(HeapCrossRef& r)
   3.118      {
   3.119 -      return new Heap(R);
   3.120 +      return new Heap(r);
   3.121      }
   3.122  
   3.123 -    ///\brief The type of the map that stores the last
   3.124 +    ///\brief The type of the map that stores the predecessor
   3.125      ///arcs of the shortest paths.
   3.126      ///
   3.127 -    ///The type of the map that stores the last
   3.128 +    ///The type of the map that stores the predecessor
   3.129      ///arcs of the shortest paths.
   3.130      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   3.131 -    ///
   3.132 -    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
   3.133 -    ///Instantiates a PredMap.
   3.134 +    typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   3.135 +    ///Instantiates a \ref PredMap.
   3.136  
   3.137 -    ///This function instantiates a \c PredMap.
   3.138 -    ///\param G is the digraph, to which we would like to define the PredMap.
   3.139 +    ///This function instantiates a \ref PredMap.
   3.140 +    ///\param g is the digraph, to which we would like to define the
   3.141 +    ///\ref PredMap.
   3.142      ///\todo The digraph alone may be insufficient for the initialization
   3.143 -    static PredMap *createPredMap(const GR &G)
   3.144 +    static PredMap *createPredMap(const Digraph &g)
   3.145      {
   3.146 -      return new PredMap(G);
   3.147 +      return new PredMap(g);
   3.148      }
   3.149  
   3.150 -    ///The type of the map that stores whether a nodes is processed.
   3.151 +    ///The type of the map that indicates which nodes are processed.
   3.152  
   3.153 -    ///The type of the map that stores whether a nodes is processed.
   3.154 +    ///The type of the map that indicates which nodes are processed.
   3.155      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   3.156      ///By default it is a NullMap.
   3.157      ///\todo If it is set to a real map,
   3.158      ///Dijkstra::processed() should read this.
   3.159 -    ///\todo named parameter to set this type, function to read and write.
   3.160      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   3.161 -    ///Instantiates a ProcessedMap.
   3.162 +    ///Instantiates a \ref ProcessedMap.
   3.163  
   3.164 -    ///This function instantiates a \c ProcessedMap.
   3.165 +    ///This function instantiates a \ref ProcessedMap.
   3.166      ///\param g is the digraph, to which
   3.167 -    ///we would like to define the \c ProcessedMap
   3.168 +    ///we would like to define the \ref ProcessedMap
   3.169  #ifdef DOXYGEN
   3.170 -    static ProcessedMap *createProcessedMap(const GR &g)
   3.171 +    static ProcessedMap *createProcessedMap(const Digraph &g)
   3.172  #else
   3.173 -    static ProcessedMap *createProcessedMap(const GR &)
   3.174 +    static ProcessedMap *createProcessedMap(const Digraph &)
   3.175  #endif
   3.176      {
   3.177        return new ProcessedMap();
   3.178      }
   3.179 -    ///The type of the map that stores the dists of the nodes.
   3.180  
   3.181 -    ///The type of the map that stores the dists of the nodes.
   3.182 +    ///The type of the map that stores the distances of the nodes.
   3.183 +
   3.184 +    ///The type of the map that stores the distances of the nodes.
   3.185      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   3.186 -    ///
   3.187      typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
   3.188 -    ///Instantiates a DistMap.
   3.189 +    ///Instantiates a \ref DistMap.
   3.190  
   3.191      ///This function instantiates a \ref DistMap.
   3.192 -    ///\param G is the digraph, to which we would like to define
   3.193 +    ///\param g is the digraph, to which we would like to define
   3.194      ///the \ref DistMap
   3.195 -    static DistMap *createDistMap(const GR &G)
   3.196 +    static DistMap *createDistMap(const Digraph &g)
   3.197      {
   3.198 -      return new DistMap(G);
   3.199 +      return new DistMap(g);
   3.200      }
   3.201    };
   3.202  
   3.203    ///%Dijkstra algorithm class.
   3.204  
   3.205    /// \ingroup shortest_path
   3.206 -  ///This class provides an efficient implementation of %Dijkstra algorithm.
   3.207 +  ///This class provides an efficient implementation of the %Dijkstra algorithm.
   3.208 +  ///
   3.209    ///The arc lengths are passed to the algorithm using a
   3.210    ///\ref concepts::ReadMap "ReadMap",
   3.211    ///so it is easy to change it to any kind of length.
   3.212 -  ///
   3.213    ///The type of the length is determined by the
   3.214    ///\ref concepts::ReadMap::Value "Value" of the length map.
   3.215 -  ///
   3.216    ///It is also possible to change the underlying priority heap.
   3.217    ///
   3.218 -  ///\tparam GR The digraph type the algorithm runs on. The default value
   3.219 -  ///is \ref ListDigraph. The value of GR is not used directly by
   3.220 -  ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
   3.221 -  ///\tparam LM This read-only ArcMap determines the lengths of the
   3.222 +  ///There is also a \ref dijkstra() "function type interface" for the
   3.223 +  ///%Dijkstra algorithm, which is convenient in the simplier cases and
   3.224 +  ///it can be used easier.
   3.225 +  ///
   3.226 +  ///\tparam GR The type of the digraph the algorithm runs on.
   3.227 +  ///The default value is \ref ListDigraph.
   3.228 +  ///The value of GR is not used directly by \ref Dijkstra, it is only
   3.229 +  ///passed to \ref DijkstraDefaultTraits.
   3.230 +  ///\tparam LM A readable arc map that determines the lengths of the
   3.231    ///arcs. It is read once for each arc, so the map may involve in
   3.232 -  ///relatively time consuming process to compute the arc length if
   3.233 +  ///relatively time consuming process to compute the arc lengths if
   3.234    ///it is necessary. The default map type is \ref
   3.235 -  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".  The value
   3.236 -  ///of LM is not used directly by Dijkstra, it is only passed to \ref
   3.237 -  ///DijkstraDefaultTraits.
   3.238 -  ///\tparam TR Traits class to set
   3.239 -  ///various data types used by the algorithm.  The default traits
   3.240 -  ///class is \ref DijkstraDefaultTraits
   3.241 -  ///"DijkstraDefaultTraits<GR,LM>".  See \ref
   3.242 -  ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
   3.243 -  ///class.
   3.244 -
   3.245 +  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
   3.246 +  ///The value of LM is not used directly by \ref Dijkstra, it is only
   3.247 +  ///passed to \ref DijkstraDefaultTraits.
   3.248 +  ///\tparam TR Traits class to set various data types used by the algorithm.
   3.249 +  ///The default traits class is \ref DijkstraDefaultTraits
   3.250 +  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
   3.251 +  ///for the documentation of a Dijkstra traits class.
   3.252  #ifdef DOXYGEN
   3.253    template <typename GR, typename LM, typename TR>
   3.254  #else
   3.255 @@ -220,12 +227,10 @@
   3.256  #endif
   3.257    class Dijkstra {
   3.258    public:
   3.259 -    /**
   3.260 -     * \brief \ref Exception for uninitialized parameters.
   3.261 -     *
   3.262 -     * This error represents problems in the initialization
   3.263 -     * of the parameters of the algorithms.
   3.264 -     */
   3.265 +    ///\ref Exception for uninitialized parameters.
   3.266 +
   3.267 +    ///This error represents problems in the initialization of the
   3.268 +    ///parameters of the algorithm.
   3.269      class UninitializedParameter : public lemon::UninitializedParameter {
   3.270      public:
   3.271        virtual const char* what() const throw() {
   3.272 @@ -233,63 +238,65 @@
   3.273        }
   3.274      };
   3.275  
   3.276 -    typedef TR Traits;
   3.277 -    ///The type of the underlying digraph.
   3.278 +    ///The type of the digraph the algorithm runs on.
   3.279      typedef typename TR::Digraph Digraph;
   3.280 -    ///\e
   3.281 -    typedef typename Digraph::Node Node;
   3.282 -    ///\e
   3.283 -    typedef typename Digraph::NodeIt NodeIt;
   3.284 -    ///\e
   3.285 -    typedef typename Digraph::Arc Arc;
   3.286 -    ///\e
   3.287 -    typedef typename Digraph::OutArcIt OutArcIt;
   3.288  
   3.289      ///The type of the length of the arcs.
   3.290      typedef typename TR::LengthMap::Value Value;
   3.291      ///The type of the map that stores the arc lengths.
   3.292      typedef typename TR::LengthMap LengthMap;
   3.293 -    ///\brief The type of the map that stores the last
   3.294 -    ///arcs of the shortest paths.
   3.295 +    ///\brief The type of the map that stores the predecessor arcs of the
   3.296 +    ///shortest paths.
   3.297      typedef typename TR::PredMap PredMap;
   3.298 -    ///The type of the map indicating if a node is processed.
   3.299 +    ///The type of the map that stores the distances of the nodes.
   3.300 +    typedef typename TR::DistMap DistMap;
   3.301 +    ///The type of the map that indicates which nodes are processed.
   3.302      typedef typename TR::ProcessedMap ProcessedMap;
   3.303 -    ///The type of the map that stores the dists of the nodes.
   3.304 -    typedef typename TR::DistMap DistMap;
   3.305 +    ///The type of the paths.
   3.306 +    typedef PredMapPath<Digraph, PredMap> Path;
   3.307      ///The cross reference type used for the current heap.
   3.308      typedef typename TR::HeapCrossRef HeapCrossRef;
   3.309 -    ///The heap type used by the dijkstra algorithm.
   3.310 +    ///The heap type used by the algorithm.
   3.311      typedef typename TR::Heap Heap;
   3.312 -    ///The operation traits.
   3.313 +    ///The operation traits class.
   3.314      typedef typename TR::OperationTraits OperationTraits;
   3.315 +
   3.316 +    ///The traits class.
   3.317 +    typedef TR Traits;
   3.318 +
   3.319    private:
   3.320 -    /// Pointer to the underlying digraph.
   3.321 +
   3.322 +    typedef typename Digraph::Node Node;
   3.323 +    typedef typename Digraph::NodeIt NodeIt;
   3.324 +    typedef typename Digraph::Arc Arc;
   3.325 +    typedef typename Digraph::OutArcIt OutArcIt;
   3.326 +
   3.327 +    //Pointer to the underlying digraph.
   3.328      const Digraph *G;
   3.329 -    /// Pointer to the length map
   3.330 +    //Pointer to the length map.
   3.331      const LengthMap *length;
   3.332 -    ///Pointer to the map of predecessors arcs.
   3.333 +    //Pointer to the map of predecessors arcs.
   3.334      PredMap *_pred;
   3.335 -    ///Indicates if \ref _pred is locally allocated (\c true) or not.
   3.336 +    //Indicates if _pred is locally allocated (true) or not.
   3.337      bool local_pred;
   3.338 -    ///Pointer to the map of distances.
   3.339 +    //Pointer to the map of distances.
   3.340      DistMap *_dist;
   3.341 -    ///Indicates if \ref _dist is locally allocated (\c true) or not.
   3.342 +    //Indicates if _dist is locally allocated (true) or not.
   3.343      bool local_dist;
   3.344 -    ///Pointer to the map of processed status of the nodes.
   3.345 +    //Pointer to the map of processed status of the nodes.
   3.346      ProcessedMap *_processed;
   3.347 -    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   3.348 +    //Indicates if _processed is locally allocated (true) or not.
   3.349      bool local_processed;
   3.350 -    ///Pointer to the heap cross references.
   3.351 +    //Pointer to the heap cross references.
   3.352      HeapCrossRef *_heap_cross_ref;
   3.353 -    ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
   3.354 +    //Indicates if _heap_cross_ref is locally allocated (true) or not.
   3.355      bool local_heap_cross_ref;
   3.356 -    ///Pointer to the heap.
   3.357 +    //Pointer to the heap.
   3.358      Heap *_heap;
   3.359 -    ///Indicates if \ref _heap is locally allocated (\c true) or not.
   3.360 +    //Indicates if _heap is locally allocated (true) or not.
   3.361      bool local_heap;
   3.362  
   3.363      ///Creates the maps if necessary.
   3.364 -
   3.365      ///\todo Better memory allocation (instead of new).
   3.366      void create_maps()
   3.367      {
   3.368 @@ -315,7 +322,7 @@
   3.369        }
   3.370      }
   3.371  
   3.372 -  public :
   3.373 +  public:
   3.374  
   3.375      typedef Dijkstra Create;
   3.376  
   3.377 @@ -331,10 +338,11 @@
   3.378          throw UninitializedParameter();
   3.379        }
   3.380      };
   3.381 -    ///\ref named-templ-param "Named parameter" for setting PredMap type
   3.382 -
   3.383 -    ///\ref named-templ-param "Named parameter" for setting PredMap type
   3.384 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.385 +    ///\ref PredMap type.
   3.386      ///
   3.387 +    ///\ref named-templ-param "Named parameter" for setting
   3.388 +    ///\ref PredMap type.
   3.389      template <class T>
   3.390      struct DefPredMap
   3.391        : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
   3.392 @@ -349,10 +357,11 @@
   3.393          throw UninitializedParameter();
   3.394        }
   3.395      };
   3.396 -    ///\ref named-templ-param "Named parameter" for setting DistMap type
   3.397 -
   3.398 -    ///\ref named-templ-param "Named parameter" for setting DistMap type
   3.399 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.400 +    ///\ref DistMap type.
   3.401      ///
   3.402 +    ///\ref named-templ-param "Named parameter" for setting
   3.403 +    ///\ref DistMap type.
   3.404      template <class T>
   3.405      struct DefDistMap
   3.406        : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
   3.407 @@ -362,15 +371,16 @@
   3.408      template <class T>
   3.409      struct DefProcessedMapTraits : public Traits {
   3.410        typedef T ProcessedMap;
   3.411 -      static ProcessedMap *createProcessedMap(const Digraph &G)
   3.412 +      static ProcessedMap *createProcessedMap(const Digraph &)
   3.413        {
   3.414          throw UninitializedParameter();
   3.415        }
   3.416      };
   3.417 -    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   3.418 -
   3.419 -    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   3.420 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.421 +    ///\ref ProcessedMap type.
   3.422      ///
   3.423 +    ///\ref named-templ-param "Named parameter" for setting
   3.424 +    ///\ref ProcessedMap type.
   3.425      template <class T>
   3.426      struct DefProcessedMap
   3.427        : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
   3.428 @@ -379,17 +389,17 @@
   3.429  
   3.430      struct DefDigraphProcessedMapTraits : public Traits {
   3.431        typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   3.432 -      static ProcessedMap *createProcessedMap(const Digraph &G)
   3.433 +      static ProcessedMap *createProcessedMap(const Digraph &g)
   3.434        {
   3.435 -        return new ProcessedMap(G);
   3.436 +        return new ProcessedMap(g);
   3.437        }
   3.438      };
   3.439 -    ///\brief \ref named-templ-param "Named parameter"
   3.440 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   3.441 +    ///\brief \ref named-templ-param "Named parameter" for setting
   3.442 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   3.443      ///
   3.444 -    ///\ref named-templ-param "Named parameter"
   3.445 -    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   3.446 -    ///If you don't set it explicitely, it will be automatically allocated.
   3.447 +    ///\ref named-templ-param "Named parameter" for setting
   3.448 +    ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   3.449 +    ///If you don't set it explicitly, it will be automatically allocated.
   3.450      template <class T>
   3.451      struct DefProcessedMapToBeDefaultMap
   3.452        : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
   3.453 @@ -413,8 +423,7 @@
   3.454      ///heap and cross reference type
   3.455      ///
   3.456      ///\ref named-templ-param "Named parameter" for setting heap and cross
   3.457 -    ///reference type
   3.458 -    ///
   3.459 +    ///reference type.
   3.460      template <class H, class CR = typename Digraph::template NodeMap<int> >
   3.461      struct DefHeap
   3.462        : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
   3.463 @@ -453,10 +462,10 @@
   3.464      };
   3.465  
   3.466      /// \brief \ref named-templ-param "Named parameter" for setting
   3.467 -    /// OperationTraits type
   3.468 +    ///\ref OperationTraits type
   3.469      ///
   3.470 -    /// \ref named-templ-param "Named parameter" for setting OperationTraits
   3.471 -    /// type
   3.472 +    ///\ref named-templ-param "Named parameter" for setting
   3.473 +    ///\ref OperationTraits type.
   3.474      template <class T>
   3.475      struct DefOperationTraits
   3.476        : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
   3.477 @@ -466,7 +475,6 @@
   3.478  
   3.479      ///@}
   3.480  
   3.481 -
   3.482    protected:
   3.483  
   3.484      Dijkstra() {}
   3.485 @@ -475,10 +483,11 @@
   3.486  
   3.487      ///Constructor.
   3.488  
   3.489 -    ///\param _G the digraph the algorithm will run on.
   3.490 -    ///\param _length the length map used by the algorithm.
   3.491 -    Dijkstra(const Digraph& _G, const LengthMap& _length) :
   3.492 -      G(&_G), length(&_length),
   3.493 +    ///Constructor.
   3.494 +    ///\param _g The digraph the algorithm runs on.
   3.495 +    ///\param _length The length map used by the algorithm.
   3.496 +    Dijkstra(const Digraph& _g, const LengthMap& _length) :
   3.497 +      G(&_g), length(&_length),
   3.498        _pred(NULL), local_pred(false),
   3.499        _dist(NULL), local_dist(false),
   3.500        _processed(NULL), local_processed(false),
   3.501 @@ -506,11 +515,11 @@
   3.502        return *this;
   3.503      }
   3.504  
   3.505 -    ///Sets the map storing the predecessor arcs.
   3.506 +    ///Sets the map that stores the predecessor arcs.
   3.507  
   3.508 -    ///Sets the map storing the predecessor arcs.
   3.509 +    ///Sets the map that stores the predecessor arcs.
   3.510      ///If you don't use this function before calling \ref run(),
   3.511 -    ///it will allocate one. The destuctor deallocates this
   3.512 +    ///it will allocate one. The destructor deallocates this
   3.513      ///automatically allocated map, of course.
   3.514      ///\return <tt> (*this) </tt>
   3.515      Dijkstra &predMap(PredMap &m)
   3.516 @@ -523,11 +532,29 @@
   3.517        return *this;
   3.518      }
   3.519  
   3.520 -    ///Sets the map storing the distances calculated by the algorithm.
   3.521 +    ///Sets the map that indicates which nodes are processed.
   3.522  
   3.523 -    ///Sets the map storing the distances calculated by the algorithm.
   3.524 +    ///Sets the map that indicates which nodes are processed.
   3.525      ///If you don't use this function before calling \ref run(),
   3.526 -    ///it will allocate one. The destuctor deallocates this
   3.527 +    ///it will allocate one. The destructor deallocates this
   3.528 +    ///automatically allocated map, of course.
   3.529 +    ///\return <tt> (*this) </tt>
   3.530 +    Dijkstra &processedMap(ProcessedMap &m)
   3.531 +    {
   3.532 +      if(local_processed) {
   3.533 +        delete _processed;
   3.534 +        local_processed=false;
   3.535 +      }
   3.536 +      _processed = &m;
   3.537 +      return *this;
   3.538 +    }
   3.539 +
   3.540 +    ///Sets the map that stores the distances of the nodes.
   3.541 +
   3.542 +    ///Sets the map that stores the distances of the nodes calculated by the
   3.543 +    ///algorithm.
   3.544 +    ///If you don't use this function before calling \ref run(),
   3.545 +    ///it will allocate one. The destructor deallocates this
   3.546      ///automatically allocated map, of course.
   3.547      ///\return <tt> (*this) </tt>
   3.548      Dijkstra &distMap(DistMap &m)
   3.549 @@ -544,7 +571,7 @@
   3.550  
   3.551      ///Sets the heap and the cross reference used by algorithm.
   3.552      ///If you don't use this function before calling \ref run(),
   3.553 -    ///it will allocate one. The destuctor deallocates this
   3.554 +    ///it will allocate one. The destructor deallocates this
   3.555      ///automatically allocated heap and cross reference, of course.
   3.556      ///\return <tt> (*this) </tt>
   3.557      Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   3.558 @@ -563,6 +590,7 @@
   3.559      }
   3.560  
   3.561    private:
   3.562 +
   3.563      void finalizeNodeData(Node v,Value dst)
   3.564      {
   3.565        _processed->set(v,true);
   3.566 @@ -571,17 +599,15 @@
   3.567  
   3.568    public:
   3.569  
   3.570 -    typedef PredMapPath<Digraph, PredMap> Path;
   3.571 -
   3.572      ///\name Execution control
   3.573 -    ///The simplest way to execute the algorithm is to use
   3.574 -    ///one of the member functions called \c run(...).
   3.575 +    ///The simplest way to execute the algorithm is to use one of the
   3.576 +    ///member functions called \ref lemon::Dijkstra::run() "run()".
   3.577      ///\n
   3.578 -    ///If you need more control on the execution,
   3.579 -    ///first you must call \ref init(), then you can add several source nodes
   3.580 -    ///with \ref addSource().
   3.581 -    ///Finally \ref start() will perform the actual path
   3.582 -    ///computation.
   3.583 +    ///If you need more control on the execution, first you must call
   3.584 +    ///\ref lemon::Dijkstra::init() "init()", then you can add several
   3.585 +    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
   3.586 +    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
   3.587 +    ///actual path computation.
   3.588  
   3.589      ///@{
   3.590  
   3.591 @@ -603,10 +629,9 @@
   3.592      ///Adds a new source node.
   3.593  
   3.594      ///Adds a new source node to the priority heap.
   3.595 -    ///
   3.596      ///The optional second parameter is the initial distance of the node.
   3.597      ///
   3.598 -    ///It checks if the node has already been added to the heap and
   3.599 +    ///The function checks if the node has already been added to the heap and
   3.600      ///it is pushed to the heap only if either it was not in the heap
   3.601      ///or the shortest path found till then is shorter than \c dst.
   3.602      void addSource(Node s,Value dst=OperationTraits::zero())
   3.603 @@ -625,7 +650,7 @@
   3.604      ///
   3.605      ///\return The processed node.
   3.606      ///
   3.607 -    ///\warning The priority heap must not be empty!
   3.608 +    ///\warning The priority heap must not be empty.
   3.609      Node processNextNode()
   3.610      {
   3.611        Node v=_heap->top();
   3.612 @@ -656,62 +681,66 @@
   3.613        return v;
   3.614      }
   3.615  
   3.616 -    ///Next node to be processed.
   3.617 +    ///The next node to be processed.
   3.618  
   3.619 -    ///Next node to be processed.
   3.620 -    ///
   3.621 -    ///\return The next node to be processed or INVALID if the priority heap
   3.622 -    /// is empty.
   3.623 -    Node nextNode()
   3.624 +    ///Returns the next node to be processed or \c INVALID if the
   3.625 +    ///priority heap is empty.
   3.626 +    Node nextNode() const
   3.627      {
   3.628        return !_heap->empty()?_heap->top():INVALID;
   3.629      }
   3.630  
   3.631      ///\brief Returns \c false if there are nodes
   3.632 -    ///to be processed in the priority heap
   3.633 +    ///to be processed.
   3.634      ///
   3.635      ///Returns \c false if there are nodes
   3.636 -    ///to be processed in the priority heap
   3.637 -    bool emptyQueue() { return _heap->empty(); }
   3.638 +    ///to be processed in the priority heap.
   3.639 +    bool emptyQueue() const { return _heap->empty(); }
   3.640 +
   3.641      ///Returns the number of the nodes to be processed in the priority heap
   3.642  
   3.643 -    ///Returns the number of the nodes to be processed in the priority heap
   3.644 +    ///Returns the number of the nodes to be processed in the priority heap.
   3.645      ///
   3.646 -    int queueSize() { return _heap->size(); }
   3.647 +    int queueSize() const { return _heap->size(); }
   3.648  
   3.649      ///Executes the algorithm.
   3.650  
   3.651      ///Executes the algorithm.
   3.652      ///
   3.653 -    ///\pre init() must be called and at least one node should be added
   3.654 -    ///with addSource() before using this function.
   3.655 +    ///This method runs the %Dijkstra algorithm from the root node(s)
   3.656 +    ///in order to compute the shortest path to each node.
   3.657 +    ///
   3.658 +    ///The algorithm computes
   3.659 +    ///- the shortest path tree (forest),
   3.660 +    ///- the distance of each node from the root(s).
   3.661 +    ///
   3.662 +    ///\pre init() must be called and at least one root node should be
   3.663 +    ///added with addSource() before using this function.
   3.664 +    ///
   3.665 +    ///\note <tt>d.start()</tt> is just a shortcut of the following code.
   3.666 +    ///\code
   3.667 +    ///  while ( !d.emptyQueue() ) {
   3.668 +    ///    d.processNextNode();
   3.669 +    ///  }
   3.670 +    ///\endcode
   3.671 +    void start()
   3.672 +    {
   3.673 +      while ( !emptyQueue() ) processNextNode();
   3.674 +    }
   3.675 +
   3.676 +    ///Executes the algorithm until the given target node is reached.
   3.677 +
   3.678 +    ///Executes the algorithm until the given target node is reached.
   3.679      ///
   3.680      ///This method runs the %Dijkstra algorithm from the root node(s)
   3.681 -    ///in order to
   3.682 -    ///compute the
   3.683 -    ///shortest path to each node. The algorithm computes
   3.684 -    ///- The shortest path tree.
   3.685 -    ///- The distance of each node from the root(s).
   3.686 +    ///in order to compute the shortest path to \c dest.
   3.687      ///
   3.688 -    void start()
   3.689 -    {
   3.690 -      while ( !_heap->empty() ) processNextNode();
   3.691 -    }
   3.692 -
   3.693 -    ///Executes the algorithm until \c dest is reached.
   3.694 -
   3.695 -    ///Executes the algorithm until \c dest is reached.
   3.696 +    ///The algorithm computes
   3.697 +    ///- the shortest path to \c dest,
   3.698 +    ///- the distance of \c dest from the root(s).
   3.699      ///
   3.700 -    ///\pre init() must be called and at least one node should be added
   3.701 -    ///with addSource() before using this function.
   3.702 -    ///
   3.703 -    ///This method runs the %Dijkstra algorithm from the root node(s)
   3.704 -    ///in order to
   3.705 -    ///compute the
   3.706 -    ///shortest path to \c dest. The algorithm computes
   3.707 -    ///- The shortest path to \c  dest.
   3.708 -    ///- The distance of \c dest from the root(s).
   3.709 -    ///
   3.710 +    ///\pre init() must be called and at least one root node should be
   3.711 +    ///added with addSource() before using this function.
   3.712      void start(Node dest)
   3.713      {
   3.714        while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
   3.715 @@ -722,14 +751,18 @@
   3.716  
   3.717      ///Executes the algorithm until a condition is met.
   3.718      ///
   3.719 -    ///\pre init() must be called and at least one node should be added
   3.720 -    ///with addSource() before using this function.
   3.721 +    ///This method runs the %Dijkstra algorithm from the root node(s) in
   3.722 +    ///order to compute the shortest path to a node \c v with
   3.723 +    /// <tt>nm[v]</tt> true, if such a node can be found.
   3.724      ///
   3.725 -    ///\param nm must be a bool (or convertible) node map. The algorithm
   3.726 +    ///\param nm A \c bool (or convertible) node map. The algorithm
   3.727      ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
   3.728      ///
   3.729      ///\return The reached node \c v with <tt>nm[v]</tt> true or
   3.730      ///\c INVALID if no such node was found.
   3.731 +    ///
   3.732 +    ///\pre init() must be called and at least one root node should be
   3.733 +    ///added with addSource() before using this function.
   3.734      template<class NodeBoolMap>
   3.735      Node start(const NodeBoolMap &nm)
   3.736      {
   3.737 @@ -739,16 +772,16 @@
   3.738        return _heap->top();
   3.739      }
   3.740  
   3.741 -    ///Runs %Dijkstra algorithm from node \c s.
   3.742 +    ///Runs the algorithm from the given node.
   3.743  
   3.744 -    ///This method runs the %Dijkstra algorithm from a root node \c s
   3.745 -    ///in order to
   3.746 -    ///compute the
   3.747 -    ///shortest path to each node. The algorithm computes
   3.748 -    ///- The shortest path tree.
   3.749 -    ///- The distance of each node from the root.
   3.750 +    ///This method runs the %Dijkstra algorithm from node \c s
   3.751 +    ///in order to compute the shortest path to each node.
   3.752      ///
   3.753 -    ///\note d.run(s) is just a shortcut of the following code.
   3.754 +    ///The algorithm computes
   3.755 +    ///- the shortest path tree,
   3.756 +    ///- the distance of each node from the root.
   3.757 +    ///
   3.758 +    ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
   3.759      ///\code
   3.760      ///  d.init();
   3.761      ///  d.addSource(s);
   3.762 @@ -762,12 +795,14 @@
   3.763  
   3.764      ///Finds the shortest path between \c s and \c t.
   3.765  
   3.766 -    ///Finds the shortest path between \c s and \c t.
   3.767 +    ///This method runs the %Dijkstra algorithm from node \c s
   3.768 +    ///in order to compute the shortest path to \c t.
   3.769      ///
   3.770 -    ///\return The length of the shortest s---t path if there exists one,
   3.771 -    ///0 otherwise.
   3.772 -    ///\note Apart from the return value, d.run(s) is
   3.773 -    ///just a shortcut of the following code.
   3.774 +    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
   3.775 +    ///if \c t is reachable form \c s, \c 0 otherwise.
   3.776 +    ///
   3.777 +    ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
   3.778 +    ///shortcut of the following code.
   3.779      ///\code
   3.780      ///  d.init();
   3.781      ///  d.addSource(s);
   3.782 @@ -785,241 +820,262 @@
   3.783      ///\name Query Functions
   3.784      ///The result of the %Dijkstra algorithm can be obtained using these
   3.785      ///functions.\n
   3.786 -    ///Before the use of these functions,
   3.787 -    ///either run() or start() must be called.
   3.788 +    ///Either \ref lemon::Dijkstra::run() "run()" or
   3.789 +    ///\ref lemon::Dijkstra::start() "start()" must be called before
   3.790 +    ///using them.
   3.791  
   3.792      ///@{
   3.793  
   3.794 -    ///Gives back the shortest path.
   3.795 +    ///The shortest path to a node.
   3.796  
   3.797 -    ///Gives back the shortest path.
   3.798 -    ///\pre The \c t should be reachable from the source.
   3.799 -    Path path(Node t)
   3.800 -    {
   3.801 -      return Path(*G, *_pred, t);
   3.802 -    }
   3.803 +    ///Returns the shortest path to a node.
   3.804 +    ///
   3.805 +    ///\warning \c t should be reachable from the root(s).
   3.806 +    ///
   3.807 +    ///\pre Either \ref run() or \ref start() must be called before
   3.808 +    ///using this function.
   3.809 +    Path path(Node t) const { return Path(*G, *_pred, t); }
   3.810  
   3.811 -    ///The distance of a node from the root.
   3.812 +    ///The distance of a node from the root(s).
   3.813  
   3.814 -    ///Returns the distance of a node from the root.
   3.815 -    ///\pre \ref run() must be called before using this function.
   3.816 -    ///\warning If node \c v in unreachable from the root the return value
   3.817 -    ///of this funcion is undefined.
   3.818 +    ///Returns the distance of a node from the root(s).
   3.819 +    ///
   3.820 +    ///\warning If node \c v is not reachable from the root(s), then
   3.821 +    ///the return value of this function is undefined.
   3.822 +    ///
   3.823 +    ///\pre Either \ref run() or \ref start() must be called before
   3.824 +    ///using this function.
   3.825      Value dist(Node v) const { return (*_dist)[v]; }
   3.826  
   3.827 -    ///The current distance of a node from the root.
   3.828 +    ///Returns the 'previous arc' of the shortest path tree for a node.
   3.829  
   3.830 -    ///Returns the current distance of a node from the root.
   3.831 -    ///It may be decreased in the following processes.
   3.832 -    ///\pre \c node should be reached but not processed
   3.833 -    Value currentDist(Node v) const { return (*_heap)[v]; }
   3.834 -
   3.835 -    ///Returns the 'previous arc' of the shortest path tree.
   3.836 -
   3.837 -    ///For a node \c v it returns the 'previous arc' of the shortest path tree,
   3.838 -    ///i.e. it returns the last arc of a shortest path from the root to \c
   3.839 -    ///v. It is \ref INVALID
   3.840 -    ///if \c v is unreachable from the root or if \c v=s. The
   3.841 -    ///shortest path tree used here is equal to the shortest path tree used in
   3.842 -    ///\ref predNode().  \pre \ref run() must be called before using
   3.843 -    ///this function.
   3.844 +    ///This function returns the 'previous arc' of the shortest path
   3.845 +    ///tree for the node \c v, i.e. it returns the last arc of a
   3.846 +    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   3.847 +    ///is not reachable from the root(s) or if \c v is a root.
   3.848 +    ///
   3.849 +    ///The shortest path tree used here is equal to the shortest path
   3.850 +    ///tree used in \ref predNode().
   3.851 +    ///
   3.852 +    ///\pre Either \ref run() or \ref start() must be called before
   3.853 +    ///using this function.
   3.854      Arc predArc(Node v) const { return (*_pred)[v]; }
   3.855  
   3.856 -    ///Returns the 'previous node' of the shortest path tree.
   3.857 +    ///Returns the 'previous node' of the shortest path tree for a node.
   3.858  
   3.859 -    ///For a node \c v it returns the 'previous node' of the shortest path tree,
   3.860 -    ///i.e. it returns the last but one node from a shortest path from the
   3.861 -    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
   3.862 -    ///\c v=s. The shortest path tree used here is equal to the shortest path
   3.863 -    ///tree used in \ref predArc().  \pre \ref run() must be called before
   3.864 +    ///This function returns the 'previous node' of the shortest path
   3.865 +    ///tree for the node \c v, i.e. it returns the last but one node
   3.866 +    ///from a shortest path from the root(s) to \c v. It is \c INVALID
   3.867 +    ///if \c v is not reachable from the root(s) or if \c v is a root.
   3.868 +    ///
   3.869 +    ///The shortest path tree used here is equal to the shortest path
   3.870 +    ///tree used in \ref predArc().
   3.871 +    ///
   3.872 +    ///\pre Either \ref run() or \ref start() must be called before
   3.873      ///using this function.
   3.874      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   3.875                                    G->source((*_pred)[v]); }
   3.876  
   3.877 -    ///Returns a reference to the NodeMap of distances.
   3.878 -
   3.879 -    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
   3.880 -    ///be called before using this function.
   3.881 +    ///\brief Returns a const reference to the node map that stores the
   3.882 +    ///distances of the nodes.
   3.883 +    ///
   3.884 +    ///Returns a const reference to the node map that stores the distances
   3.885 +    ///of the nodes calculated by the algorithm.
   3.886 +    ///
   3.887 +    ///\pre Either \ref run() or \ref init()
   3.888 +    ///must be called before using this function.
   3.889      const DistMap &distMap() const { return *_dist;}
   3.890  
   3.891 -    ///Returns a reference to the shortest path tree map.
   3.892 -
   3.893 -    ///Returns a reference to the NodeMap of the arcs of the
   3.894 -    ///shortest path tree.
   3.895 -    ///\pre \ref run() must be called before using this function.
   3.896 +    ///\brief Returns a const reference to the node map that stores the
   3.897 +    ///predecessor arcs.
   3.898 +    ///
   3.899 +    ///Returns a const reference to the node map that stores the predecessor
   3.900 +    ///arcs, which form the shortest path tree.
   3.901 +    ///
   3.902 +    ///\pre Either \ref run() or \ref init()
   3.903 +    ///must be called before using this function.
   3.904      const PredMap &predMap() const { return *_pred;}
   3.905  
   3.906 -    ///Checks if a node is reachable from the root.
   3.907 +    ///Checks if a node is reachable from the root(s).
   3.908  
   3.909 -    ///Returns \c true if \c v is reachable from the root.
   3.910 -    ///\warning The source nodes are inditated as unreached.
   3.911 -    ///\pre \ref run() must be called before using this function.
   3.912 -    ///
   3.913 -    bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
   3.914 +    ///Returns \c true if \c v is reachable from the root(s).
   3.915 +    ///\pre Either \ref run() or \ref start()
   3.916 +    ///must be called before using this function.
   3.917 +    bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   3.918 +                                        Heap::PRE_HEAP; }
   3.919  
   3.920      ///Checks if a node is processed.
   3.921  
   3.922      ///Returns \c true if \c v is processed, i.e. the shortest
   3.923      ///path to \c v has already found.
   3.924 -    ///\pre \ref run() must be called before using this function.
   3.925 -    ///
   3.926 -    bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
   3.927 +    ///\pre Either \ref run() or \ref start()
   3.928 +    ///must be called before using this function.
   3.929 +    bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   3.930 +                                          Heap::POST_HEAP; }
   3.931 +
   3.932 +    ///The current distance of a node from the root(s).
   3.933 +
   3.934 +    ///Returns the current distance of a node from the root(s).
   3.935 +    ///It may be decreased in the following processes.
   3.936 +    ///\pre \c v should be reached but not processed.
   3.937 +    Value currentDist(Node v) const { return (*_heap)[v]; }
   3.938  
   3.939      ///@}
   3.940    };
   3.941  
   3.942  
   3.943 +  ///Default traits class of dijkstra() function.
   3.944  
   3.945 -
   3.946 -
   3.947 -  ///Default traits class of Dijkstra function.
   3.948 -
   3.949 -  ///Default traits class of Dijkstra function.
   3.950 -  ///\tparam GR Digraph type.
   3.951 -  ///\tparam LM Type of length map.
   3.952 +  ///Default traits class of dijkstra() function.
   3.953 +  ///\tparam GR The type of the digraph.
   3.954 +  ///\tparam LM The type of the length map.
   3.955    template<class GR, class LM>
   3.956    struct DijkstraWizardDefaultTraits
   3.957    {
   3.958 -    ///The digraph type the algorithm runs on.
   3.959 +    ///The type of the digraph the algorithm runs on.
   3.960      typedef GR Digraph;
   3.961      ///The type of the map that stores the arc lengths.
   3.962  
   3.963      ///The type of the map that stores the arc lengths.
   3.964      ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   3.965      typedef LM LengthMap;
   3.966 -    //The type of the length of the arcs.
   3.967 +    ///The type of the length of the arcs.
   3.968      typedef typename LM::Value Value;
   3.969 +
   3.970      /// Operation traits for Dijkstra algorithm.
   3.971  
   3.972 -    /// It defines the used operation by the algorithm.
   3.973 +    /// This class defines the operations that are used in the algorithm.
   3.974      /// \see DijkstraDefaultOperationTraits
   3.975      typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
   3.976 -    ///The heap type used by Dijkstra algorithm.
   3.977  
   3.978 -    /// The cross reference type used by heap.
   3.979 +    /// The cross reference type used by the heap.
   3.980  
   3.981 -    /// The cross reference type used by heap.
   3.982 +    /// The cross reference type used by the heap.
   3.983      /// Usually it is \c Digraph::NodeMap<int>.
   3.984      typedef typename Digraph::template NodeMap<int> HeapCrossRef;
   3.985 -    ///Instantiates a HeapCrossRef.
   3.986 +    ///Instantiates a \ref HeapCrossRef.
   3.987  
   3.988      ///This function instantiates a \ref HeapCrossRef.
   3.989 -    /// \param G is the digraph, to which we would like to define the
   3.990 +    /// \param g is the digraph, to which we would like to define the
   3.991      /// HeapCrossRef.
   3.992      /// \todo The digraph alone may be insufficient for the initialization
   3.993 -    static HeapCrossRef *createHeapCrossRef(const GR &G)
   3.994 +    static HeapCrossRef *createHeapCrossRef(const Digraph &g)
   3.995      {
   3.996 -      return new HeapCrossRef(G);
   3.997 +      return new HeapCrossRef(g);
   3.998      }
   3.999  
  3.1000 -    ///The heap type used by Dijkstra algorithm.
  3.1001 +    ///The heap type used by the Dijkstra algorithm.
  3.1002  
  3.1003 -    ///The heap type used by Dijkstra algorithm.
  3.1004 +    ///The heap type used by the Dijkstra algorithm.
  3.1005      ///
  3.1006      ///\sa BinHeap
  3.1007      ///\sa Dijkstra
  3.1008 -    typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
  3.1009 +    typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
  3.1010                      std::less<Value> > Heap;
  3.1011  
  3.1012 -    static Heap *createHeap(HeapCrossRef& R)
  3.1013 +    ///Instantiates a \ref Heap.
  3.1014 +
  3.1015 +    ///This function instantiates a \ref Heap.
  3.1016 +    /// \param r is the HeapCrossRef which is used.
  3.1017 +    static Heap *createHeap(HeapCrossRef& r)
  3.1018      {
  3.1019 -      return new Heap(R);
  3.1020 +      return new Heap(r);
  3.1021      }
  3.1022  
  3.1023 -    ///\brief The type of the map that stores the last
  3.1024 +    ///\brief The type of the map that stores the predecessor
  3.1025      ///arcs of the shortest paths.
  3.1026      ///
  3.1027 -    ///The type of the map that stores the last
  3.1028 +    ///The type of the map that stores the predecessor
  3.1029      ///arcs of the shortest paths.
  3.1030      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  3.1031 -    ///
  3.1032 -    typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
  3.1033 -    ///Instantiates a PredMap.
  3.1034 +    typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
  3.1035 +    ///Instantiates a \ref PredMap.
  3.1036  
  3.1037      ///This function instantiates a \ref PredMap.
  3.1038 -    ///\param g is the digraph, to which we would like to define the PredMap.
  3.1039 -    ///\todo The digraph alone may be insufficient for the initialization
  3.1040 +    ///\param g is the digraph, to which we would like to define the
  3.1041 +    ///\ref PredMap.
  3.1042 +    ///\todo The digraph alone may be insufficient to initialize
  3.1043  #ifdef DOXYGEN
  3.1044 -    static PredMap *createPredMap(const GR &g)
  3.1045 +    static PredMap *createPredMap(const Digraph &g)
  3.1046  #else
  3.1047 -    static PredMap *createPredMap(const GR &)
  3.1048 +    static PredMap *createPredMap(const Digraph &)
  3.1049  #endif
  3.1050      {
  3.1051        return new PredMap();
  3.1052      }
  3.1053 -    ///The type of the map that stores whether a nodes is processed.
  3.1054  
  3.1055 -    ///The type of the map that stores whether a nodes is processed.
  3.1056 +    ///The type of the map that indicates which nodes are processed.
  3.1057 +
  3.1058 +    ///The type of the map that indicates which nodes are processed.
  3.1059      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  3.1060      ///By default it is a NullMap.
  3.1061      ///\todo If it is set to a real map,
  3.1062      ///Dijkstra::processed() should read this.
  3.1063      ///\todo named parameter to set this type, function to read and write.
  3.1064      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
  3.1065 -    ///Instantiates a ProcessedMap.
  3.1066 +    ///Instantiates a \ref ProcessedMap.
  3.1067  
  3.1068      ///This function instantiates a \ref ProcessedMap.
  3.1069      ///\param g is the digraph, to which
  3.1070 -    ///we would like to define the \ref ProcessedMap
  3.1071 +    ///we would like to define the \ref ProcessedMap.
  3.1072  #ifdef DOXYGEN
  3.1073 -    static ProcessedMap *createProcessedMap(const GR &g)
  3.1074 +    static ProcessedMap *createProcessedMap(const Digraph &g)
  3.1075  #else
  3.1076 -    static ProcessedMap *createProcessedMap(const GR &)
  3.1077 +    static ProcessedMap *createProcessedMap(const Digraph &)
  3.1078  #endif
  3.1079      {
  3.1080        return new ProcessedMap();
  3.1081      }
  3.1082 -    ///The type of the map that stores the dists of the nodes.
  3.1083  
  3.1084 -    ///The type of the map that stores the dists of the nodes.
  3.1085 +    ///The type of the map that stores the distances of the nodes.
  3.1086 +
  3.1087 +    ///The type of the map that stores the distances of the nodes.
  3.1088      ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
  3.1089 -    ///
  3.1090 -    typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
  3.1091 -    ///Instantiates a DistMap.
  3.1092 +    typedef NullMap<typename Digraph::Node,Value> DistMap;
  3.1093 +    ///Instantiates a \ref DistMap.
  3.1094  
  3.1095      ///This function instantiates a \ref DistMap.
  3.1096      ///\param g is the digraph, to which we would like to define
  3.1097      ///the \ref DistMap
  3.1098  #ifdef DOXYGEN
  3.1099 -    static DistMap *createDistMap(const GR &g)
  3.1100 +    static DistMap *createDistMap(const Digraph &g)
  3.1101  #else
  3.1102 -    static DistMap *createDistMap(const GR &)
  3.1103 +    static DistMap *createDistMap(const Digraph &)
  3.1104  #endif
  3.1105      {
  3.1106        return new DistMap();
  3.1107      }
  3.1108    };
  3.1109  
  3.1110 -  /// Default traits used by \ref DijkstraWizard
  3.1111 +  /// Default traits class used by \ref DijkstraWizard
  3.1112  
  3.1113    /// To make it easier to use Dijkstra algorithm
  3.1114 -  ///we have created a wizard class.
  3.1115 +  /// we have created a wizard class.
  3.1116    /// This \ref DijkstraWizard class needs default traits,
  3.1117 -  ///as well as the \ref Dijkstra class.
  3.1118 +  /// as well as the \ref Dijkstra class.
  3.1119    /// The \ref DijkstraWizardBase is a class to be the default traits of the
  3.1120    /// \ref DijkstraWizard class.
  3.1121    /// \todo More named parameters are required...
  3.1122    template<class GR,class LM>
  3.1123    class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
  3.1124    {
  3.1125 -
  3.1126      typedef DijkstraWizardDefaultTraits<GR,LM> Base;
  3.1127    protected:
  3.1128 -    /// Type of the nodes in the digraph.
  3.1129 +    //The type of the nodes in the digraph.
  3.1130      typedef typename Base::Digraph::Node Node;
  3.1131  
  3.1132 -    /// Pointer to the underlying digraph.
  3.1133 +    //Pointer to the digraph the algorithm runs on.
  3.1134      void *_g;
  3.1135 -    /// Pointer to the length map
  3.1136 +    //Pointer to the length map
  3.1137      void *_length;
  3.1138 -    ///Pointer to the map of predecessors arcs.
  3.1139 +    //Pointer to the map of predecessors arcs.
  3.1140      void *_pred;
  3.1141 -    ///Pointer to the map of distances.
  3.1142 +    //Pointer to the map of distances.
  3.1143      void *_dist;
  3.1144 -    ///Pointer to the source node.
  3.1145 +    //Pointer to the source node.
  3.1146      Node _source;
  3.1147  
  3.1148 -    public:
  3.1149 +  public:
  3.1150      /// Constructor.
  3.1151  
  3.1152      /// This constructor does not require parameters, therefore it initiates
  3.1153 @@ -1032,9 +1088,9 @@
  3.1154      /// This constructor requires some parameters,
  3.1155      /// listed in the parameters list.
  3.1156      /// Others are initiated to 0.
  3.1157 -    /// \param g is the initial value of  \ref _g
  3.1158 -    /// \param l is the initial value of  \ref _length
  3.1159 -    /// \param s is the initial value of  \ref _source
  3.1160 +    /// \param g The digraph the algorithm runs on.
  3.1161 +    /// \param l The length map.
  3.1162 +    /// \param s The source node.
  3.1163      DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
  3.1164        _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
  3.1165        _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
  3.1166 @@ -1042,11 +1098,13 @@
  3.1167  
  3.1168    };
  3.1169  
  3.1170 -  /// A class to make the usage of Dijkstra algorithm easier
  3.1171 +  /// Auxiliary class for the function type interface of Dijkstra algorithm.
  3.1172  
  3.1173 -  /// This class is created to make it easier to use Dijkstra algorithm.
  3.1174 -  /// It uses the functions and features of the plain \ref Dijkstra,
  3.1175 -  /// but it is much simpler to use it.
  3.1176 +  /// This auxiliary class is created to implement the function type
  3.1177 +  /// interface of \ref Dijkstra algorithm. It uses the functions and features
  3.1178 +  /// of the plain \ref Dijkstra, but it is much simpler to use it.
  3.1179 +  /// It should only be used through the \ref dijkstra() function, which makes
  3.1180 +  /// it easier to use the algorithm.
  3.1181    ///
  3.1182    /// Simplicity means that the way to change the types defined
  3.1183    /// in the traits class is based on functions that returns the new class
  3.1184 @@ -1055,40 +1113,41 @@
  3.1185    /// the new class with the modified type comes from
  3.1186    /// the original class by using the ::
  3.1187    /// operator. In the case of \ref DijkstraWizard only
  3.1188 -  /// a function have to be called and it will
  3.1189 +  /// a function have to be called, and it will
  3.1190    /// return the needed class.
  3.1191    ///
  3.1192 -  /// It does not have own \ref run method. When its \ref run method is called
  3.1193 -  /// it initiates a plain \ref Dijkstra class, and calls the \ref
  3.1194 -  /// Dijkstra::run method of it.
  3.1195 +  /// It does not have own \ref run() method. When its \ref run() method
  3.1196 +  /// is called, it initiates a plain \ref Dijkstra object, and calls the
  3.1197 +  /// \ref Dijkstra::run() method of it.
  3.1198    template<class TR>
  3.1199    class DijkstraWizard : public TR
  3.1200    {
  3.1201      typedef TR Base;
  3.1202  
  3.1203 -    ///The type of the underlying digraph.
  3.1204 +    ///The type of the digraph the algorithm runs on.
  3.1205      typedef typename TR::Digraph Digraph;
  3.1206 -    //\e
  3.1207 +
  3.1208      typedef typename Digraph::Node Node;
  3.1209 -    //\e
  3.1210      typedef typename Digraph::NodeIt NodeIt;
  3.1211 -    //\e
  3.1212      typedef typename Digraph::Arc Arc;
  3.1213 -    //\e
  3.1214      typedef typename Digraph::OutArcIt OutArcIt;
  3.1215  
  3.1216      ///The type of the map that stores the arc lengths.
  3.1217      typedef typename TR::LengthMap LengthMap;
  3.1218      ///The type of the length of the arcs.
  3.1219      typedef typename LengthMap::Value Value;
  3.1220 -    ///\brief The type of the map that stores the last
  3.1221 +    ///\brief The type of the map that stores the predecessor
  3.1222      ///arcs of the shortest paths.
  3.1223      typedef typename TR::PredMap PredMap;
  3.1224 -    ///The type of the map that stores the dists of the nodes.
  3.1225 +    ///The type of the map that stores the distances of the nodes.
  3.1226      typedef typename TR::DistMap DistMap;
  3.1227 +    ///The type of the map that indicates which nodes are processed.
  3.1228 +    typedef typename TR::ProcessedMap ProcessedMap;
  3.1229      ///The heap type used by the dijkstra algorithm.
  3.1230      typedef typename TR::Heap Heap;
  3.1231 +
  3.1232    public:
  3.1233 +
  3.1234      /// Constructor.
  3.1235      DijkstraWizard() : TR() {}
  3.1236  
  3.1237 @@ -1104,10 +1163,10 @@
  3.1238  
  3.1239      ~DijkstraWizard() {}
  3.1240  
  3.1241 -    ///Runs Dijkstra algorithm from a given node.
  3.1242 +    ///Runs Dijkstra algorithm from a source node.
  3.1243  
  3.1244 -    ///Runs Dijkstra algorithm from a given node.
  3.1245 -    ///The node can be given by the \ref source function.
  3.1246 +    ///Runs Dijkstra algorithm from a source node.
  3.1247 +    ///The node can be given with the \ref source() function.
  3.1248      void run()
  3.1249      {
  3.1250        if(Base::_source==INVALID) throw UninitializedParameter();
  3.1251 @@ -1129,19 +1188,27 @@
  3.1252        run();
  3.1253      }
  3.1254  
  3.1255 +    /// Sets the source node, from which the Dijkstra algorithm runs.
  3.1256 +
  3.1257 +    /// Sets the source node, from which the Dijkstra algorithm runs.
  3.1258 +    /// \param s is the source node.
  3.1259 +    DijkstraWizard<TR> &source(Node s)
  3.1260 +    {
  3.1261 +      Base::_source=s;
  3.1262 +      return *this;
  3.1263 +    }
  3.1264 +
  3.1265      template<class T>
  3.1266      struct DefPredMapBase : public Base {
  3.1267        typedef T PredMap;
  3.1268        static PredMap *createPredMap(const Digraph &) { return 0; };
  3.1269        DefPredMapBase(const TR &b) : TR(b) {}
  3.1270      };
  3.1271 -
  3.1272      ///\brief \ref named-templ-param "Named parameter"
  3.1273 -    ///function for setting PredMap type
  3.1274 +    ///for setting \ref PredMap object.
  3.1275      ///
  3.1276 -    /// \ref named-templ-param "Named parameter"
  3.1277 -    ///function for setting PredMap type
  3.1278 -    ///
  3.1279 +    ///\ref named-templ-param "Named parameter"
  3.1280 +    ///for setting \ref PredMap object.
  3.1281      template<class T>
  3.1282      DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
  3.1283      {
  3.1284 @@ -1150,18 +1217,34 @@
  3.1285      }
  3.1286  
  3.1287      template<class T>
  3.1288 +    struct DefProcessedMapBase : public Base {
  3.1289 +      typedef T ProcessedMap;
  3.1290 +      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  3.1291 +      DefProcessedMapBase(const TR &b) : TR(b) {}
  3.1292 +    };
  3.1293 +    ///\brief \ref named-templ-param "Named parameter"
  3.1294 +    ///for setting \ref ProcessedMap object.
  3.1295 +    ///
  3.1296 +    /// \ref named-templ-param "Named parameter"
  3.1297 +    ///for setting \ref ProcessedMap object.
  3.1298 +    template<class T>
  3.1299 +    DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  3.1300 +    {
  3.1301 +      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  3.1302 +      return DijkstraWizard<DefProcessedMapBase<T> >(*this);
  3.1303 +    }
  3.1304 +
  3.1305 +    template<class T>
  3.1306      struct DefDistMapBase : public Base {
  3.1307        typedef T DistMap;
  3.1308        static DistMap *createDistMap(const Digraph &) { return 0; };
  3.1309        DefDistMapBase(const TR &b) : TR(b) {}
  3.1310      };
  3.1311 -
  3.1312      ///\brief \ref named-templ-param "Named parameter"
  3.1313 -    ///function for setting DistMap type
  3.1314 +    ///for setting \ref DistMap object.
  3.1315      ///
  3.1316 -    /// \ref named-templ-param "Named parameter"
  3.1317 -    ///function for setting DistMap type
  3.1318 -    ///
  3.1319 +    ///\ref named-templ-param "Named parameter"
  3.1320 +    ///for setting \ref DistMap object.
  3.1321      template<class T>
  3.1322      DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
  3.1323      {
  3.1324 @@ -1169,16 +1252,6 @@
  3.1325        return DijkstraWizard<DefDistMapBase<T> >(*this);
  3.1326      }
  3.1327  
  3.1328 -    /// Sets the source node, from which the Dijkstra algorithm runs.
  3.1329 -
  3.1330 -    /// Sets the source node, from which the Dijkstra algorithm runs.
  3.1331 -    /// \param s is the source node.
  3.1332 -    DijkstraWizard<TR> &source(Node s)
  3.1333 -    {
  3.1334 -      Base::_source=s;
  3.1335 -      return *this;
  3.1336 -    }
  3.1337 -
  3.1338    };
  3.1339  
  3.1340    ///Function type interface for Dijkstra algorithm.