Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Tue, 02 Dec 2008 10:31:20 +0000
changeset 40869f33ef03334
parent 407 e22fc10ab6f1
parent 405 6b9057cdcd8b
child 413 d8b87e9b90c3
Merge
lemon/dijkstra.h
     1.1 --- a/lemon/bfs.h	Tue Dec 02 10:30:52 2008 +0000
     1.2 +++ b/lemon/bfs.h	Tue Dec 02 10:31:20 2008 +0000
     1.3 @@ -51,7 +51,7 @@
     1.4      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
     1.5      ///Instantiates a PredMap.
     1.6  
     1.7 -    ///This function instantiates a PredMap.  
     1.8 +    ///This function instantiates a PredMap.
     1.9      ///\param g is the digraph, to which we would like to define the
    1.10      ///PredMap.
    1.11      static PredMap *createPredMap(const Digraph &g)
    1.12 @@ -80,7 +80,8 @@
    1.13  
    1.14      ///The type of the map that indicates which nodes are reached.
    1.15  
    1.16 -    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.17 +    ///The type of the map that indicates which nodes are reached.
    1.18 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.19      typedef typename Digraph::template NodeMap<bool> ReachedMap;
    1.20      ///Instantiates a ReachedMap.
    1.21  
    1.22 @@ -118,13 +119,7 @@
    1.23    ///used easier.
    1.24    ///
    1.25    ///\tparam GR The type of the digraph the algorithm runs on.
    1.26 -  ///The default value is \ref ListDigraph. The value of GR is not used
    1.27 -  ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
    1.28 -  ///\tparam TR Traits class to set various data types used by the algorithm.
    1.29 -  ///The default traits class is
    1.30 -  ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
    1.31 -  ///See \ref BfsDefaultTraits for the documentation of
    1.32 -  ///a Bfs traits class.
    1.33 +  ///The default type is \ref ListDigraph.
    1.34  #ifdef DOXYGEN
    1.35    template <typename GR,
    1.36              typename TR>
    1.37 @@ -150,7 +145,7 @@
    1.38      ///The type of the paths.
    1.39      typedef PredMapPath<Digraph, PredMap> Path;
    1.40  
    1.41 -    ///The traits class.
    1.42 +    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
    1.43      typedef TR Traits;
    1.44  
    1.45    private:
    1.46 @@ -212,7 +207,7 @@
    1.47  
    1.48      typedef Bfs Create;
    1.49  
    1.50 -    ///\name Named template parameters
    1.51 +    ///\name Named Template Parameters
    1.52  
    1.53      ///@{
    1.54  
    1.55 @@ -230,6 +225,7 @@
    1.56      ///
    1.57      ///\ref named-templ-param "Named parameter" for setting
    1.58      ///PredMap type.
    1.59 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.60      template <class T>
    1.61      struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
    1.62        typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
    1.63 @@ -249,6 +245,7 @@
    1.64      ///
    1.65      ///\ref named-templ-param "Named parameter" for setting
    1.66      ///DistMap type.
    1.67 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.68      template <class T>
    1.69      struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
    1.70        typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
    1.71 @@ -268,6 +265,7 @@
    1.72      ///
    1.73      ///\ref named-templ-param "Named parameter" for setting
    1.74      ///ReachedMap type.
    1.75 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    1.76      template <class T>
    1.77      struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
    1.78        typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
    1.79 @@ -287,6 +285,7 @@
    1.80      ///
    1.81      ///\ref named-templ-param "Named parameter" for setting
    1.82      ///ProcessedMap type.
    1.83 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.84      template <class T>
    1.85      struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
    1.86        typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
    1.87 @@ -339,9 +338,10 @@
    1.88      ///Sets the map that stores the predecessor arcs.
    1.89  
    1.90      ///Sets the map that stores the predecessor arcs.
    1.91 -    ///If you don't use this function before calling \ref run(),
    1.92 -    ///it will allocate one. The destructor deallocates this
    1.93 -    ///automatically allocated map, of course.
    1.94 +    ///If you don't use this function before calling \ref run(Node) "run()"
    1.95 +    ///or \ref init(), an instance will be allocated automatically.
    1.96 +    ///The destructor deallocates this automatically allocated map,
    1.97 +    ///of course.
    1.98      ///\return <tt> (*this) </tt>
    1.99      Bfs &predMap(PredMap &m)
   1.100      {
   1.101 @@ -356,9 +356,10 @@
   1.102      ///Sets the map that indicates which nodes are reached.
   1.103  
   1.104      ///Sets the map that indicates which nodes are reached.
   1.105 -    ///If you don't use this function before calling \ref run(),
   1.106 -    ///it will allocate one. The destructor deallocates this
   1.107 -    ///automatically allocated map, of course.
   1.108 +    ///If you don't use this function before calling \ref run(Node) "run()"
   1.109 +    ///or \ref init(), an instance will be allocated automatically.
   1.110 +    ///The destructor deallocates this automatically allocated map,
   1.111 +    ///of course.
   1.112      ///\return <tt> (*this) </tt>
   1.113      Bfs &reachedMap(ReachedMap &m)
   1.114      {
   1.115 @@ -373,9 +374,10 @@
   1.116      ///Sets the map that indicates which nodes are processed.
   1.117  
   1.118      ///Sets the map that indicates which nodes are processed.
   1.119 -    ///If you don't use this function before calling \ref run(),
   1.120 -    ///it will allocate one. The destructor deallocates this
   1.121 -    ///automatically allocated map, of course.
   1.122 +    ///If you don't use this function before calling \ref run(Node) "run()"
   1.123 +    ///or \ref init(), an instance will be allocated automatically.
   1.124 +    ///The destructor deallocates this automatically allocated map,
   1.125 +    ///of course.
   1.126      ///\return <tt> (*this) </tt>
   1.127      Bfs &processedMap(ProcessedMap &m)
   1.128      {
   1.129 @@ -391,9 +393,10 @@
   1.130  
   1.131      ///Sets the map that stores the distances of the nodes calculated by
   1.132      ///the algorithm.
   1.133 -    ///If you don't use this function before calling \ref run(),
   1.134 -    ///it will allocate one. The destructor deallocates this
   1.135 -    ///automatically allocated map, of course.
   1.136 +    ///If you don't use this function before calling \ref run(Node) "run()"
   1.137 +    ///or \ref init(), an instance will be allocated automatically.
   1.138 +    ///The destructor deallocates this automatically allocated map,
   1.139 +    ///of course.
   1.140      ///\return <tt> (*this) </tt>
   1.141      Bfs &distMap(DistMap &m)
   1.142      {
   1.143 @@ -407,22 +410,19 @@
   1.144  
   1.145    public:
   1.146  
   1.147 -    ///\name Execution control
   1.148 -    ///The simplest way to execute the algorithm is to use
   1.149 -    ///one of the member functions called \ref lemon::Bfs::run() "run()".
   1.150 -    ///\n
   1.151 -    ///If you need more control on the execution, first you must call
   1.152 -    ///\ref lemon::Bfs::init() "init()", then you can add several source
   1.153 -    ///nodes with \ref lemon::Bfs::addSource() "addSource()".
   1.154 -    ///Finally \ref lemon::Bfs::start() "start()" will perform the
   1.155 -    ///actual path computation.
   1.156 +    ///\name Execution Control
   1.157 +    ///The simplest way to execute the BFS algorithm is to use one of the
   1.158 +    ///member functions called \ref run(Node) "run()".\n
   1.159 +    ///If you need more control on the execution, first you have to call
   1.160 +    ///\ref init(), then you can add several source nodes with
   1.161 +    ///\ref addSource(). Finally the actual path computation can be
   1.162 +    ///performed with one of the \ref start() functions.
   1.163  
   1.164      ///@{
   1.165  
   1.166 +    ///\brief Initializes the internal data structures.
   1.167 +    ///
   1.168      ///Initializes the internal data structures.
   1.169 -
   1.170 -    ///Initializes the internal data structures.
   1.171 -    ///
   1.172      void init()
   1.173      {
   1.174        create_maps();
   1.175 @@ -556,16 +556,16 @@
   1.176        return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
   1.177      }
   1.178  
   1.179 -    ///\brief Returns \c false if there are nodes
   1.180 -    ///to be processed.
   1.181 -    ///
   1.182 -    ///Returns \c false if there are nodes
   1.183 -    ///to be processed in the queue.
   1.184 +    ///Returns \c false if there are nodes to be processed.
   1.185 +
   1.186 +    ///Returns \c false if there are nodes to be processed
   1.187 +    ///in the queue.
   1.188      bool emptyQueue() const { return _queue_tail==_queue_head; }
   1.189  
   1.190      ///Returns the number of the nodes to be processed.
   1.191  
   1.192 -    ///Returns the number of the nodes to be processed in the queue.
   1.193 +    ///Returns the number of the nodes to be processed
   1.194 +    ///in the queue.
   1.195      int queueSize() const { return _queue_head-_queue_tail; }
   1.196  
   1.197      ///Executes the algorithm.
   1.198 @@ -730,10 +730,10 @@
   1.199      ///@}
   1.200  
   1.201      ///\name Query Functions
   1.202 -    ///The result of the %BFS algorithm can be obtained using these
   1.203 +    ///The results of the BFS algorithm can be obtained using these
   1.204      ///functions.\n
   1.205 -    ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
   1.206 -    ///"start()" must be called before using them.
   1.207 +    ///Either \ref run(Node) "run()" or \ref start() should be called
   1.208 +    ///before using them.
   1.209  
   1.210      ///@{
   1.211  
   1.212 @@ -741,49 +741,49 @@
   1.213  
   1.214      ///Returns the shortest path to a node.
   1.215      ///
   1.216 -    ///\warning \c t should be reachable from the root(s).
   1.217 +    ///\warning \c t should be reached from the root(s).
   1.218      ///
   1.219 -    ///\pre Either \ref run() or \ref start() must be called before
   1.220 -    ///using this function.
   1.221 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.222 +    ///must be called before using this function.
   1.223      Path path(Node t) const { return Path(*G, *_pred, t); }
   1.224  
   1.225      ///The distance of a node from the root(s).
   1.226  
   1.227      ///Returns the distance of a node from the root(s).
   1.228      ///
   1.229 -    ///\warning If node \c v is not reachable from the root(s), then
   1.230 +    ///\warning If node \c v is not reached from the root(s), then
   1.231      ///the return value of this function is undefined.
   1.232      ///
   1.233 -    ///\pre Either \ref run() or \ref start() must be called before
   1.234 -    ///using this function.
   1.235 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.236 +    ///must be called before using this function.
   1.237      int dist(Node v) const { return (*_dist)[v]; }
   1.238  
   1.239      ///Returns the 'previous arc' of the shortest path tree for a node.
   1.240  
   1.241      ///This function returns the 'previous arc' of the shortest path
   1.242      ///tree for the node \c v, i.e. it returns the last arc of a
   1.243 -    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   1.244 -    ///is not reachable from the root(s) or if \c v is a root.
   1.245 +    ///shortest path from a root to \c v. It is \c INVALID if \c v
   1.246 +    ///is not reached from the root(s) or if \c v is a root.
   1.247      ///
   1.248      ///The shortest path tree used here is equal to the shortest path
   1.249      ///tree used in \ref predNode().
   1.250      ///
   1.251 -    ///\pre Either \ref run() or \ref start() must be called before
   1.252 -    ///using this function.
   1.253 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.254 +    ///must be called before using this function.
   1.255      Arc predArc(Node v) const { return (*_pred)[v];}
   1.256  
   1.257      ///Returns the 'previous node' of the shortest path tree for a node.
   1.258  
   1.259      ///This function returns the 'previous node' of the shortest path
   1.260      ///tree for the node \c v, i.e. it returns the last but one node
   1.261 -    ///from a shortest path from the root(s) to \c v. It is \c INVALID
   1.262 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   1.263 +    ///from a shortest path from a root to \c v. It is \c INVALID
   1.264 +    ///if \c v is not reached from the root(s) or if \c v is a root.
   1.265      ///
   1.266      ///The shortest path tree used here is equal to the shortest path
   1.267      ///tree used in \ref predArc().
   1.268      ///
   1.269 -    ///\pre Either \ref run() or \ref start() must be called before
   1.270 -    ///using this function.
   1.271 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.272 +    ///must be called before using this function.
   1.273      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   1.274                                    G->source((*_pred)[v]); }
   1.275  
   1.276 @@ -793,7 +793,7 @@
   1.277      ///Returns a const reference to the node map that stores the distances
   1.278      ///of the nodes calculated by the algorithm.
   1.279      ///
   1.280 -    ///\pre Either \ref run() or \ref init()
   1.281 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.282      ///must be called before using this function.
   1.283      const DistMap &distMap() const { return *_dist;}
   1.284  
   1.285 @@ -803,14 +803,15 @@
   1.286      ///Returns a const reference to the node map that stores the predecessor
   1.287      ///arcs, which form the shortest path tree.
   1.288      ///
   1.289 -    ///\pre Either \ref run() or \ref init()
   1.290 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.291      ///must be called before using this function.
   1.292      const PredMap &predMap() const { return *_pred;}
   1.293  
   1.294 -    ///Checks if a node is reachable from the root(s).
   1.295 +    ///Checks if a node is reached from the root(s).
   1.296  
   1.297 -    ///Returns \c true if \c v is reachable from the root(s).
   1.298 -    ///\pre Either \ref run() or \ref start()
   1.299 +    ///Returns \c true if \c v is reached from the root(s).
   1.300 +    ///
   1.301 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   1.302      ///must be called before using this function.
   1.303      bool reached(Node v) const { return (*_reached)[v]; }
   1.304  
   1.305 @@ -956,8 +957,8 @@
   1.306  
   1.307    /// This auxiliary class is created to implement the
   1.308    /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
   1.309 -  /// It does not have own \ref run() method, it uses the functions
   1.310 -  /// and features of the plain \ref Bfs.
   1.311 +  /// It does not have own \ref run(Node) "run()" method, it uses the
   1.312 +  /// functions and features of the plain \ref Bfs.
   1.313    ///
   1.314    /// This class should only be used through the \ref bfs() function,
   1.315    /// which makes it easier to use the algorithm.
   1.316 @@ -1177,7 +1178,7 @@
   1.317    ///  // Compute shortest path from s to t
   1.318    ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
   1.319    ///\endcode
   1.320 -  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
   1.321 +  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
   1.322    ///to the end of the parameter list.
   1.323    ///\sa BfsWizard
   1.324    ///\sa Bfs
   1.325 @@ -1363,7 +1364,7 @@
   1.326  
   1.327      typedef BfsVisit Create;
   1.328  
   1.329 -    /// \name Named template parameters
   1.330 +    /// \name Named Template Parameters
   1.331  
   1.332      ///@{
   1.333      template <class T>
   1.334 @@ -1405,9 +1406,10 @@
   1.335      /// \brief Sets the map that indicates which nodes are reached.
   1.336      ///
   1.337      /// Sets the map that indicates which nodes are reached.
   1.338 -    /// If you don't use this function before calling \ref run(),
   1.339 -    /// it will allocate one. The destructor deallocates this
   1.340 -    /// automatically allocated map, of course.
   1.341 +    /// If you don't use this function before calling \ref run(Node) "run()"
   1.342 +    /// or \ref init(), an instance will be allocated automatically.
   1.343 +    /// The destructor deallocates this automatically allocated map,
   1.344 +    /// of course.
   1.345      /// \return <tt> (*this) </tt>
   1.346      BfsVisit &reachedMap(ReachedMap &m) {
   1.347        if(local_reached) {
   1.348 @@ -1420,16 +1422,13 @@
   1.349  
   1.350    public:
   1.351  
   1.352 -    /// \name Execution control
   1.353 -    /// The simplest way to execute the algorithm is to use
   1.354 -    /// one of the member functions called \ref lemon::BfsVisit::run()
   1.355 -    /// "run()".
   1.356 -    /// \n
   1.357 -    /// If you need more control on the execution, first you must call
   1.358 -    /// \ref lemon::BfsVisit::init() "init()", then you can add several
   1.359 -    /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
   1.360 -    /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
   1.361 -    /// actual path computation.
   1.362 +    /// \name Execution Control
   1.363 +    /// The simplest way to execute the BFS algorithm is to use one of the
   1.364 +    /// member functions called \ref run(Node) "run()".\n
   1.365 +    /// If you need more control on the execution, first you have to call
   1.366 +    /// \ref init(), then you can add several source nodes with
   1.367 +    /// \ref addSource(). Finally the actual path computation can be
   1.368 +    /// performed with one of the \ref start() functions.
   1.369  
   1.370      /// @{
   1.371  
   1.372 @@ -1729,17 +1728,18 @@
   1.373      ///@}
   1.374  
   1.375      /// \name Query Functions
   1.376 -    /// The result of the %BFS algorithm can be obtained using these
   1.377 +    /// The results of the BFS algorithm can be obtained using these
   1.378      /// functions.\n
   1.379 -    /// Either \ref lemon::BfsVisit::run() "run()" or
   1.380 -    /// \ref lemon::BfsVisit::start() "start()" must be called before
   1.381 -    /// using them.
   1.382 +    /// Either \ref run(Node) "run()" or \ref start() should be called
   1.383 +    /// before using them.
   1.384 +
   1.385      ///@{
   1.386  
   1.387 -    /// \brief Checks if a node is reachable from the root(s).
   1.388 +    /// \brief Checks if a node is reached from the root(s).
   1.389      ///
   1.390 -    /// Returns \c true if \c v is reachable from the root(s).
   1.391 -    /// \pre Either \ref run() or \ref start()
   1.392 +    /// Returns \c true if \c v is reached from the root(s).
   1.393 +    ///
   1.394 +    /// \pre Either \ref run(Node) "run()" or \ref init()
   1.395      /// must be called before using this function.
   1.396      bool reached(Node v) { return (*_reached)[v]; }
   1.397  
     2.1 --- a/lemon/dfs.h	Tue Dec 02 10:30:52 2008 +0000
     2.2 +++ b/lemon/dfs.h	Tue Dec 02 10:31:20 2008 +0000
     2.3 @@ -119,13 +119,7 @@
     2.4    ///used easier.
     2.5    ///
     2.6    ///\tparam GR The type of the digraph the algorithm runs on.
     2.7 -  ///The default value is \ref ListDigraph. The value of GR is not used
     2.8 -  ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
     2.9 -  ///\tparam TR Traits class to set various data types used by the algorithm.
    2.10 -  ///The default traits class is
    2.11 -  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
    2.12 -  ///See \ref DfsDefaultTraits for the documentation of
    2.13 -  ///a Dfs traits class.
    2.14 +  ///The default type is \ref ListDigraph.
    2.15  #ifdef DOXYGEN
    2.16    template <typename GR,
    2.17              typename TR>
    2.18 @@ -151,7 +145,7 @@
    2.19      ///The type of the paths.
    2.20      typedef PredMapPath<Digraph, PredMap> Path;
    2.21  
    2.22 -    ///The traits class.
    2.23 +    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
    2.24      typedef TR Traits;
    2.25  
    2.26    private:
    2.27 @@ -230,6 +224,7 @@
    2.28      ///
    2.29      ///\ref named-templ-param "Named parameter" for setting
    2.30      ///PredMap type.
    2.31 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.32      template <class T>
    2.33      struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
    2.34        typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
    2.35 @@ -249,6 +244,7 @@
    2.36      ///
    2.37      ///\ref named-templ-param "Named parameter" for setting
    2.38      ///DistMap type.
    2.39 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.40      template <class T>
    2.41      struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
    2.42        typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
    2.43 @@ -268,6 +264,7 @@
    2.44      ///
    2.45      ///\ref named-templ-param "Named parameter" for setting
    2.46      ///ReachedMap type.
    2.47 +    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    2.48      template <class T>
    2.49      struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
    2.50        typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
    2.51 @@ -287,6 +284,7 @@
    2.52      ///
    2.53      ///\ref named-templ-param "Named parameter" for setting
    2.54      ///ProcessedMap type.
    2.55 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    2.56      template <class T>
    2.57      struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
    2.58        typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
    2.59 @@ -338,9 +336,10 @@
    2.60      ///Sets the map that stores the predecessor arcs.
    2.61  
    2.62      ///Sets the map that stores the predecessor arcs.
    2.63 -    ///If you don't use this function before calling \ref run(),
    2.64 -    ///it will allocate one. The destructor deallocates this
    2.65 -    ///automatically allocated map, of course.
    2.66 +    ///If you don't use this function before calling \ref run(Node) "run()"
    2.67 +    ///or \ref init(), an instance will be allocated automatically.
    2.68 +    ///The destructor deallocates this automatically allocated map,
    2.69 +    ///of course.
    2.70      ///\return <tt> (*this) </tt>
    2.71      Dfs &predMap(PredMap &m)
    2.72      {
    2.73 @@ -355,9 +354,10 @@
    2.74      ///Sets the map that indicates which nodes are reached.
    2.75  
    2.76      ///Sets the map that indicates which nodes are reached.
    2.77 -    ///If you don't use this function before calling \ref run(),
    2.78 -    ///it will allocate one. The destructor deallocates this
    2.79 -    ///automatically allocated map, of course.
    2.80 +    ///If you don't use this function before calling \ref run(Node) "run()"
    2.81 +    ///or \ref init(), an instance will be allocated automatically.
    2.82 +    ///The destructor deallocates this automatically allocated map,
    2.83 +    ///of course.
    2.84      ///\return <tt> (*this) </tt>
    2.85      Dfs &reachedMap(ReachedMap &m)
    2.86      {
    2.87 @@ -372,9 +372,10 @@
    2.88      ///Sets the map that indicates which nodes are processed.
    2.89  
    2.90      ///Sets the map that indicates which nodes are processed.
    2.91 -    ///If you don't use this function before calling \ref run(),
    2.92 -    ///it will allocate one. The destructor deallocates this
    2.93 -    ///automatically allocated map, of course.
    2.94 +    ///If you don't use this function before calling \ref run(Node) "run()"
    2.95 +    ///or \ref init(), an instance will be allocated automatically.
    2.96 +    ///The destructor deallocates this automatically allocated map,
    2.97 +    ///of course.
    2.98      ///\return <tt> (*this) </tt>
    2.99      Dfs &processedMap(ProcessedMap &m)
   2.100      {
   2.101 @@ -390,9 +391,10 @@
   2.102  
   2.103      ///Sets the map that stores the distances of the nodes calculated by
   2.104      ///the algorithm.
   2.105 -    ///If you don't use this function before calling \ref run(),
   2.106 -    ///it will allocate one. The destructor deallocates this
   2.107 -    ///automatically allocated map, of course.
   2.108 +    ///If you don't use this function before calling \ref run(Node) "run()"
   2.109 +    ///or \ref init(), an instance will be allocated automatically.
   2.110 +    ///The destructor deallocates this automatically allocated map,
   2.111 +    ///of course.
   2.112      ///\return <tt> (*this) </tt>
   2.113      Dfs &distMap(DistMap &m)
   2.114      {
   2.115 @@ -406,22 +408,20 @@
   2.116  
   2.117    public:
   2.118  
   2.119 -    ///\name Execution control
   2.120 -    ///The simplest way to execute the algorithm is to use
   2.121 -    ///one of the member functions called \ref lemon::Dfs::run() "run()".
   2.122 -    ///\n
   2.123 -    ///If you need more control on the execution, first you must call
   2.124 -    ///\ref lemon::Dfs::init() "init()", then you can add a source node
   2.125 -    ///with \ref lemon::Dfs::addSource() "addSource()".
   2.126 -    ///Finally \ref lemon::Dfs::start() "start()" will perform the
   2.127 -    ///actual path computation.
   2.128 +    ///\name Execution Control
   2.129 +    ///The simplest way to execute the DFS algorithm is to use one of the
   2.130 +    ///member functions called \ref run(Node) "run()".\n
   2.131 +    ///If you need more control on the execution, first you have to call
   2.132 +    ///\ref init(), then you can add a source node with \ref addSource()
   2.133 +    ///and perform the actual computation with \ref start().
   2.134 +    ///This procedure can be repeated if there are nodes that have not
   2.135 +    ///been reached.
   2.136  
   2.137      ///@{
   2.138  
   2.139 +    ///\brief Initializes the internal data structures.
   2.140 +    ///
   2.141      ///Initializes the internal data structures.
   2.142 -
   2.143 -    ///Initializes the internal data structures.
   2.144 -    ///
   2.145      void init()
   2.146      {
   2.147        create_maps();
   2.148 @@ -438,11 +438,10 @@
   2.149  
   2.150      ///Adds a new source node to the set of nodes to be processed.
   2.151      ///
   2.152 -    ///\pre The stack must be empty. (Otherwise the algorithm gives
   2.153 -    ///false results.)
   2.154 -    ///
   2.155 -    ///\warning Distances will be wrong (or at least strange) in case of
   2.156 -    ///multiple sources.
   2.157 +    ///\pre The stack must be empty. Otherwise the algorithm gives
   2.158 +    ///wrong results. (One of the outgoing arcs of all the source nodes
   2.159 +    ///except for the last one will not be visited and distances will
   2.160 +    ///also be wrong.)
   2.161      void addSource(Node s)
   2.162      {
   2.163        LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   2.164 @@ -506,16 +505,16 @@
   2.165        return _stack_head>=0?_stack[_stack_head]:INVALID;
   2.166      }
   2.167  
   2.168 -    ///\brief Returns \c false if there are nodes
   2.169 -    ///to be processed.
   2.170 -    ///
   2.171 -    ///Returns \c false if there are nodes
   2.172 -    ///to be processed in the queue (stack).
   2.173 +    ///Returns \c false if there are nodes to be processed.
   2.174 +
   2.175 +    ///Returns \c false if there are nodes to be processed
   2.176 +    ///in the queue (stack).
   2.177      bool emptyQueue() const { return _stack_head<0; }
   2.178  
   2.179      ///Returns the number of the nodes to be processed.
   2.180  
   2.181 -    ///Returns the number of the nodes to be processed in the queue (stack).
   2.182 +    ///Returns the number of the nodes to be processed
   2.183 +    ///in the queue (stack).
   2.184      int queueSize() const { return _stack_head+1; }
   2.185  
   2.186      ///Executes the algorithm.
   2.187 @@ -637,8 +636,8 @@
   2.188      ///%DFS path to each node.
   2.189      ///
   2.190      ///The algorithm computes
   2.191 -    ///- the %DFS tree,
   2.192 -    ///- the distance of each node from the root in the %DFS tree.
   2.193 +    ///- the %DFS tree (forest),
   2.194 +    ///- the distance of each node from the root(s) in the %DFS tree.
   2.195      ///
   2.196      ///\note <tt>d.run()</tt> is just a shortcut of the following code.
   2.197      ///\code
   2.198 @@ -663,10 +662,10 @@
   2.199      ///@}
   2.200  
   2.201      ///\name Query Functions
   2.202 -    ///The result of the %DFS algorithm can be obtained using these
   2.203 +    ///The results of the DFS algorithm can be obtained using these
   2.204      ///functions.\n
   2.205 -    ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
   2.206 -    ///"start()" must be called before using them.
   2.207 +    ///Either \ref run(Node) "run()" or \ref start() should be called
   2.208 +    ///before using them.
   2.209  
   2.210      ///@{
   2.211  
   2.212 @@ -674,49 +673,49 @@
   2.213  
   2.214      ///Returns the DFS path to a node.
   2.215      ///
   2.216 -    ///\warning \c t should be reachable from the root.
   2.217 +    ///\warning \c t should be reached from the root(s).
   2.218      ///
   2.219 -    ///\pre Either \ref run() or \ref start() must be called before
   2.220 -    ///using this function.
   2.221 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.222 +    ///must be called before using this function.
   2.223      Path path(Node t) const { return Path(*G, *_pred, t); }
   2.224  
   2.225 -    ///The distance of a node from the root.
   2.226 +    ///The distance of a node from the root(s).
   2.227  
   2.228 -    ///Returns the distance of a node from the root.
   2.229 +    ///Returns the distance of a node from the root(s).
   2.230      ///
   2.231 -    ///\warning If node \c v is not reachable from the root, then
   2.232 +    ///\warning If node \c v is not reached from the root(s), then
   2.233      ///the return value of this function is undefined.
   2.234      ///
   2.235 -    ///\pre Either \ref run() or \ref start() must be called before
   2.236 -    ///using this function.
   2.237 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.238 +    ///must be called before using this function.
   2.239      int dist(Node v) const { return (*_dist)[v]; }
   2.240  
   2.241      ///Returns the 'previous arc' of the %DFS tree for a node.
   2.242  
   2.243      ///This function returns the 'previous arc' of the %DFS tree for the
   2.244 -    ///node \c v, i.e. it returns the last arc of a %DFS path from the
   2.245 -    ///root to \c v. It is \c INVALID
   2.246 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   2.247 +    ///node \c v, i.e. it returns the last arc of a %DFS path from a
   2.248 +    ///root to \c v. It is \c INVALID if \c v is not reached from the
   2.249 +    ///root(s) or if \c v is a root.
   2.250      ///
   2.251      ///The %DFS tree used here is equal to the %DFS tree used in
   2.252      ///\ref predNode().
   2.253      ///
   2.254 -    ///\pre Either \ref run() or \ref start() must be called before using
   2.255 -    ///this function.
   2.256 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.257 +    ///must be called before using this function.
   2.258      Arc predArc(Node v) const { return (*_pred)[v];}
   2.259  
   2.260      ///Returns the 'previous node' of the %DFS tree.
   2.261  
   2.262      ///This function returns the 'previous node' of the %DFS
   2.263      ///tree for the node \c v, i.e. it returns the last but one node
   2.264 -    ///from a %DFS path from the root to \c v. It is \c INVALID
   2.265 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   2.266 +    ///from a %DFS path from a root to \c v. It is \c INVALID
   2.267 +    ///if \c v is not reached from the root(s) or if \c v is a root.
   2.268      ///
   2.269      ///The %DFS tree used here is equal to the %DFS tree used in
   2.270      ///\ref predArc().
   2.271      ///
   2.272 -    ///\pre Either \ref run() or \ref start() must be called before
   2.273 -    ///using this function.
   2.274 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.275 +    ///must be called before using this function.
   2.276      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   2.277                                    G->source((*_pred)[v]); }
   2.278  
   2.279 @@ -726,7 +725,7 @@
   2.280      ///Returns a const reference to the node map that stores the
   2.281      ///distances of the nodes calculated by the algorithm.
   2.282      ///
   2.283 -    ///\pre Either \ref run() or \ref init()
   2.284 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.285      ///must be called before using this function.
   2.286      const DistMap &distMap() const { return *_dist;}
   2.287  
   2.288 @@ -736,14 +735,15 @@
   2.289      ///Returns a const reference to the node map that stores the predecessor
   2.290      ///arcs, which form the DFS tree.
   2.291      ///
   2.292 -    ///\pre Either \ref run() or \ref init()
   2.293 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.294      ///must be called before using this function.
   2.295      const PredMap &predMap() const { return *_pred;}
   2.296  
   2.297 -    ///Checks if a node is reachable from the root(s).
   2.298 +    ///Checks if a node is reached from the root(s).
   2.299  
   2.300 -    ///Returns \c true if \c v is reachable from the root(s).
   2.301 -    ///\pre Either \ref run() or \ref start()
   2.302 +    ///Returns \c true if \c v is reached from the root(s).
   2.303 +    ///
   2.304 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   2.305      ///must be called before using this function.
   2.306      bool reached(Node v) const { return (*_reached)[v]; }
   2.307  
   2.308 @@ -889,8 +889,8 @@
   2.309  
   2.310    /// This auxiliary class is created to implement the
   2.311    /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
   2.312 -  /// It does not have own \ref run() method, it uses the functions
   2.313 -  /// and features of the plain \ref Dfs.
   2.314 +  /// It does not have own \ref run(Node) "run()" method, it uses the
   2.315 +  /// functions and features of the plain \ref Dfs.
   2.316    ///
   2.317    /// This class should only be used through the \ref dfs() function,
   2.318    /// which makes it easier to use the algorithm.
   2.319 @@ -1110,8 +1110,7 @@
   2.320    ///  // Compute the DFS path from s to t
   2.321    ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
   2.322    ///\endcode
   2.323 -
   2.324 -  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
   2.325 +  ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
   2.326    ///to the end of the parameter list.
   2.327    ///\sa DfsWizard
   2.328    ///\sa Dfs
   2.329 @@ -1309,7 +1308,7 @@
   2.330  
   2.331      typedef DfsVisit Create;
   2.332  
   2.333 -    /// \name Named template parameters
   2.334 +    /// \name Named Template Parameters
   2.335  
   2.336      ///@{
   2.337      template <class T>
   2.338 @@ -1351,9 +1350,10 @@
   2.339      /// \brief Sets the map that indicates which nodes are reached.
   2.340      ///
   2.341      /// Sets the map that indicates which nodes are reached.
   2.342 -    /// If you don't use this function before calling \ref run(),
   2.343 -    /// it will allocate one. The destructor deallocates this
   2.344 -    /// automatically allocated map, of course.
   2.345 +    /// If you don't use this function before calling \ref run(Node) "run()"
   2.346 +    /// or \ref init(), an instance will be allocated automatically.
   2.347 +    /// The destructor deallocates this automatically allocated map,
   2.348 +    /// of course.
   2.349      /// \return <tt> (*this) </tt>
   2.350      DfsVisit &reachedMap(ReachedMap &m) {
   2.351        if(local_reached) {
   2.352 @@ -1366,16 +1366,14 @@
   2.353  
   2.354    public:
   2.355  
   2.356 -    /// \name Execution control
   2.357 -    /// The simplest way to execute the algorithm is to use
   2.358 -    /// one of the member functions called \ref lemon::DfsVisit::run()
   2.359 -    /// "run()".
   2.360 -    /// \n
   2.361 -    /// If you need more control on the execution, first you must call
   2.362 -    /// \ref lemon::DfsVisit::init() "init()", then you can add several
   2.363 -    /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
   2.364 -    /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
   2.365 -    /// actual path computation.
   2.366 +    /// \name Execution Control
   2.367 +    /// The simplest way to execute the DFS algorithm is to use one of the
   2.368 +    /// member functions called \ref run(Node) "run()".\n
   2.369 +    /// If you need more control on the execution, first you have to call
   2.370 +    /// \ref init(), then you can add a source node with \ref addSource()
   2.371 +    /// and perform the actual computation with \ref start().
   2.372 +    /// This procedure can be repeated if there are nodes that have not
   2.373 +    /// been reached.
   2.374  
   2.375      /// @{
   2.376  
   2.377 @@ -1391,15 +1389,14 @@
   2.378        }
   2.379      }
   2.380  
   2.381 -    ///Adds a new source node.
   2.382 -
   2.383 -    ///Adds a new source node to the set of nodes to be processed.
   2.384 +    /// \brief Adds a new source node.
   2.385      ///
   2.386 -    ///\pre The stack must be empty. (Otherwise the algorithm gives
   2.387 -    ///false results.)
   2.388 +    /// Adds a new source node to the set of nodes to be processed.
   2.389      ///
   2.390 -    ///\warning Distances will be wrong (or at least strange) in case of
   2.391 -    ///multiple sources.
   2.392 +    /// \pre The stack must be empty. Otherwise the algorithm gives
   2.393 +    /// wrong results. (One of the outgoing arcs of all the source nodes
   2.394 +    /// except for the last one will not be visited and distances will
   2.395 +    /// also be wrong.)
   2.396      void addSource(Node s)
   2.397      {
   2.398        LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   2.399 @@ -1589,8 +1586,8 @@
   2.400      /// compute the %DFS path to each node.
   2.401      ///
   2.402      /// The algorithm computes
   2.403 -    /// - the %DFS tree,
   2.404 -    /// - the distance of each node from the root in the %DFS tree.
   2.405 +    /// - the %DFS tree (forest),
   2.406 +    /// - the distance of each node from the root(s) in the %DFS tree.
   2.407      ///
   2.408      /// \note <tt>d.run()</tt> is just a shortcut of the following code.
   2.409      ///\code
   2.410 @@ -1615,17 +1612,18 @@
   2.411      ///@}
   2.412  
   2.413      /// \name Query Functions
   2.414 -    /// The result of the %DFS algorithm can be obtained using these
   2.415 +    /// The results of the DFS algorithm can be obtained using these
   2.416      /// functions.\n
   2.417 -    /// Either \ref lemon::DfsVisit::run() "run()" or
   2.418 -    /// \ref lemon::DfsVisit::start() "start()" must be called before
   2.419 -    /// using them.
   2.420 +    /// Either \ref run(Node) "run()" or \ref start() should be called
   2.421 +    /// before using them.
   2.422 +
   2.423      ///@{
   2.424  
   2.425 -    /// \brief Checks if a node is reachable from the root(s).
   2.426 +    /// \brief Checks if a node is reached from the root(s).
   2.427      ///
   2.428 -    /// Returns \c true if \c v is reachable from the root(s).
   2.429 -    /// \pre Either \ref run() or \ref start()
   2.430 +    /// Returns \c true if \c v is reached from the root(s).
   2.431 +    ///
   2.432 +    /// \pre Either \ref run(Node) "run()" or \ref init()
   2.433      /// must be called before using this function.
   2.434      bool reached(Node v) { return (*_reached)[v]; }
   2.435  
     3.1 --- a/lemon/dijkstra.h	Tue Dec 02 10:30:52 2008 +0000
     3.2 +++ b/lemon/dijkstra.h	Tue Dec 02 10:31:20 2008 +0000
     3.3 @@ -179,20 +179,13 @@
     3.4    ///it can be used easier.
     3.5    ///
     3.6    ///\tparam GR The type of the digraph the algorithm runs on.
     3.7 -  ///The default value is \ref ListDigraph.
     3.8 -  ///The value of GR is not used directly by \ref Dijkstra, it is only
     3.9 -  ///passed to \ref DijkstraDefaultTraits.
    3.10 -  ///\tparam LM A readable arc map that determines the lengths of the
    3.11 -  ///arcs. It is read once for each arc, so the map may involve in
    3.12 +  ///The default type is \ref ListDigraph.
    3.13 +  ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
    3.14 +  ///the lengths of the arcs.
    3.15 +  ///It is read once for each arc, so the map may involve in
    3.16    ///relatively time consuming process to compute the arc lengths if
    3.17    ///it is necessary. The default map type is \ref
    3.18 -  ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    3.19 -  ///The value of LM is not used directly by \ref Dijkstra, it is only
    3.20 -  ///passed to \ref DijkstraDefaultTraits.
    3.21 -  ///\tparam TR Traits class to set various data types used by the algorithm.
    3.22 -  ///The default traits class is \ref DijkstraDefaultTraits
    3.23 -  ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
    3.24 -  ///for the documentation of a Dijkstra traits class.
    3.25 +  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
    3.26  #ifdef DOXYGEN
    3.27    template <typename GR, typename LM, typename TR>
    3.28  #else
    3.29 @@ -226,7 +219,7 @@
    3.30      ///The operation traits class.
    3.31      typedef typename TR::OperationTraits OperationTraits;
    3.32  
    3.33 -    ///The traits class.
    3.34 +    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
    3.35      typedef TR Traits;
    3.36  
    3.37    private:
    3.38 @@ -308,6 +301,7 @@
    3.39      ///
    3.40      ///\ref named-templ-param "Named parameter" for setting
    3.41      ///PredMap type.
    3.42 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    3.43      template <class T>
    3.44      struct SetPredMap
    3.45        : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
    3.46 @@ -328,6 +322,7 @@
    3.47      ///
    3.48      ///\ref named-templ-param "Named parameter" for setting
    3.49      ///DistMap type.
    3.50 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    3.51      template <class T>
    3.52      struct SetDistMap
    3.53        : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
    3.54 @@ -348,6 +343,7 @@
    3.55      ///
    3.56      ///\ref named-templ-param "Named parameter" for setting
    3.57      ///ProcessedMap type.
    3.58 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    3.59      template <class T>
    3.60      struct SetProcessedMap
    3.61        : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
    3.62 @@ -388,10 +384,14 @@
    3.63        }
    3.64      };
    3.65      ///\brief \ref named-templ-param "Named parameter" for setting
    3.66 -    ///heap and cross reference type
    3.67 +    ///heap and cross reference types
    3.68      ///
    3.69      ///\ref named-templ-param "Named parameter" for setting heap and cross
    3.70 -    ///reference type.
    3.71 +    ///reference types. If this named parameter is used, then external
    3.72 +    ///heap and cross reference objects must be passed to the algorithm
    3.73 +    ///using the \ref heap() function before calling \ref run(Node) "run()"
    3.74 +    ///or \ref init().
    3.75 +    ///\sa SetStandardHeap
    3.76      template <class H, class CR = typename Digraph::template NodeMap<int> >
    3.77      struct SetHeap
    3.78        : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
    3.79 @@ -411,12 +411,18 @@
    3.80        }
    3.81      };
    3.82      ///\brief \ref named-templ-param "Named parameter" for setting
    3.83 -    ///heap and cross reference type with automatic allocation
    3.84 +    ///heap and cross reference types with automatic allocation
    3.85      ///
    3.86      ///\ref named-templ-param "Named parameter" for setting heap and cross
    3.87 -    ///reference type. It can allocate the heap and the cross reference
    3.88 -    ///object if the cross reference's constructor waits for the digraph as
    3.89 -    ///parameter and the heap's constructor waits for the cross reference.
    3.90 +    ///reference types with automatic allocation.
    3.91 +    ///They should have standard constructor interfaces to be able to
    3.92 +    ///automatically created by the algorithm (i.e. the digraph should be
    3.93 +    ///passed to the constructor of the cross reference and the cross
    3.94 +    ///reference should be passed to the constructor of the heap).
    3.95 +    ///However external heap and cross reference objects could also be
    3.96 +    ///passed to the algorithm using the \ref heap() function before
    3.97 +    ///calling \ref run(Node) "run()" or \ref init().
    3.98 +    ///\sa SetHeap
    3.99      template <class H, class CR = typename Digraph::template NodeMap<int> >
   3.100      struct SetStandardHeap
   3.101        : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
   3.102 @@ -486,9 +492,10 @@
   3.103      ///Sets the map that stores the predecessor arcs.
   3.104  
   3.105      ///Sets the map that stores the predecessor arcs.
   3.106 -    ///If you don't use this function before calling \ref run(),
   3.107 -    ///it will allocate one. The destructor deallocates this
   3.108 -    ///automatically allocated map, of course.
   3.109 +    ///If you don't use this function before calling \ref run(Node) "run()"
   3.110 +    ///or \ref init(), an instance will be allocated automatically.
   3.111 +    ///The destructor deallocates this automatically allocated map,
   3.112 +    ///of course.
   3.113      ///\return <tt> (*this) </tt>
   3.114      Dijkstra &predMap(PredMap &m)
   3.115      {
   3.116 @@ -503,9 +510,10 @@
   3.117      ///Sets the map that indicates which nodes are processed.
   3.118  
   3.119      ///Sets the map that indicates which nodes are processed.
   3.120 -    ///If you don't use this function before calling \ref run(),
   3.121 -    ///it will allocate one. The destructor deallocates this
   3.122 -    ///automatically allocated map, of course.
   3.123 +    ///If you don't use this function before calling \ref run(Node) "run()"
   3.124 +    ///or \ref init(), an instance will be allocated automatically.
   3.125 +    ///The destructor deallocates this automatically allocated map,
   3.126 +    ///of course.
   3.127      ///\return <tt> (*this) </tt>
   3.128      Dijkstra &processedMap(ProcessedMap &m)
   3.129      {
   3.130 @@ -521,9 +529,10 @@
   3.131  
   3.132      ///Sets the map that stores the distances of the nodes calculated by the
   3.133      ///algorithm.
   3.134 -    ///If you don't use this function before calling \ref run(),
   3.135 -    ///it will allocate one. The destructor deallocates this
   3.136 -    ///automatically allocated map, of course.
   3.137 +    ///If you don't use this function before calling \ref run(Node) "run()"
   3.138 +    ///or \ref init(), an instance will be allocated automatically.
   3.139 +    ///The destructor deallocates this automatically allocated map,
   3.140 +    ///of course.
   3.141      ///\return <tt> (*this) </tt>
   3.142      Dijkstra &distMap(DistMap &m)
   3.143      {
   3.144 @@ -538,9 +547,11 @@
   3.145      ///Sets the heap and the cross reference used by algorithm.
   3.146  
   3.147      ///Sets the heap and the cross reference used by algorithm.
   3.148 -    ///If you don't use this function before calling \ref run(),
   3.149 -    ///it will allocate one. The destructor deallocates this
   3.150 -    ///automatically allocated heap and cross reference, of course.
   3.151 +    ///If you don't use this function before calling \ref run(Node) "run()"
   3.152 +    ///or \ref init(), heap and cross reference instances will be
   3.153 +    ///allocated automatically.
   3.154 +    ///The destructor deallocates these automatically allocated objects,
   3.155 +    ///of course.
   3.156      ///\return <tt> (*this) </tt>
   3.157      Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
   3.158      {
   3.159 @@ -567,22 +578,19 @@
   3.160  
   3.161    public:
   3.162  
   3.163 -    ///\name Execution control
   3.164 -    ///The simplest way to execute the algorithm is to use one of the
   3.165 -    ///member functions called \ref lemon::Dijkstra::run() "run()".
   3.166 -    ///\n
   3.167 -    ///If you need more control on the execution, first you must call
   3.168 -    ///\ref lemon::Dijkstra::init() "init()", then you can add several
   3.169 -    ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
   3.170 -    ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
   3.171 -    ///actual path computation.
   3.172 +    ///\name Execution Control
   3.173 +    ///The simplest way to execute the %Dijkstra algorithm is to use
   3.174 +    ///one of the member functions called \ref run(Node) "run()".\n
   3.175 +    ///If you need more control on the execution, first you have to call
   3.176 +    ///\ref init(), then you can add several source nodes with
   3.177 +    ///\ref addSource(). Finally the actual path computation can be
   3.178 +    ///performed with one of the \ref start() functions.
   3.179  
   3.180      ///@{
   3.181  
   3.182 +    ///\brief Initializes the internal data structures.
   3.183 +    ///
   3.184      ///Initializes the internal data structures.
   3.185 -
   3.186 -    ///Initializes the internal data structures.
   3.187 -    ///
   3.188      void init()
   3.189      {
   3.190        create_maps();
   3.191 @@ -658,17 +666,16 @@
   3.192        return !_heap->empty()?_heap->top():INVALID;
   3.193      }
   3.194  
   3.195 -    ///\brief Returns \c false if there are nodes
   3.196 -    ///to be processed.
   3.197 -    ///
   3.198 -    ///Returns \c false if there are nodes
   3.199 -    ///to be processed in the priority heap.
   3.200 +    ///Returns \c false if there are nodes to be processed.
   3.201 +
   3.202 +    ///Returns \c false if there are nodes to be processed
   3.203 +    ///in the priority heap.
   3.204      bool emptyQueue() const { return _heap->empty(); }
   3.205  
   3.206 -    ///Returns the number of the nodes to be processed in the priority heap
   3.207 +    ///Returns the number of the nodes to be processed.
   3.208  
   3.209 -    ///Returns the number of the nodes to be processed in the priority heap.
   3.210 -    ///
   3.211 +    ///Returns the number of the nodes to be processed
   3.212 +    ///in the priority heap.
   3.213      int queueSize() const { return _heap->size(); }
   3.214  
   3.215      ///Executes the algorithm.
   3.216 @@ -789,11 +796,10 @@
   3.217      ///@}
   3.218  
   3.219      ///\name Query Functions
   3.220 -    ///The result of the %Dijkstra algorithm can be obtained using these
   3.221 +    ///The results of the %Dijkstra algorithm can be obtained using these
   3.222      ///functions.\n
   3.223 -    ///Either \ref lemon::Dijkstra::run() "run()" or
   3.224 -    ///\ref lemon::Dijkstra::start() "start()" must be called before
   3.225 -    ///using them.
   3.226 +    ///Either \ref run(Node) "run()" or \ref start() should be called
   3.227 +    ///before using them.
   3.228  
   3.229      ///@{
   3.230  
   3.231 @@ -801,49 +807,49 @@
   3.232  
   3.233      ///Returns the shortest path to a node.
   3.234      ///
   3.235 -    ///\warning \c t should be reachable from the root(s).
   3.236 +    ///\warning \c t should be reached from the root(s).
   3.237      ///
   3.238 -    ///\pre Either \ref run() or \ref start() must be called before
   3.239 -    ///using this function.
   3.240 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.241 +    ///must be called before using this function.
   3.242      Path path(Node t) const { return Path(*G, *_pred, t); }
   3.243  
   3.244      ///The distance of a node from the root(s).
   3.245  
   3.246      ///Returns the distance of a node from the root(s).
   3.247      ///
   3.248 -    ///\warning If node \c v is not reachable from the root(s), then
   3.249 +    ///\warning If node \c v is not reached from the root(s), then
   3.250      ///the return value of this function is undefined.
   3.251      ///
   3.252 -    ///\pre Either \ref run() or \ref start() must be called before
   3.253 -    ///using this function.
   3.254 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.255 +    ///must be called before using this function.
   3.256      Value dist(Node v) const { return (*_dist)[v]; }
   3.257  
   3.258      ///Returns the 'previous arc' of the shortest path tree for a node.
   3.259  
   3.260      ///This function returns the 'previous arc' of the shortest path
   3.261      ///tree for the node \c v, i.e. it returns the last arc of a
   3.262 -    ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
   3.263 -    ///is not reachable from the root(s) or if \c v is a root.
   3.264 +    ///shortest path from a root to \c v. It is \c INVALID if \c v
   3.265 +    ///is not reached from the root(s) or if \c v is a root.
   3.266      ///
   3.267      ///The shortest path tree used here is equal to the shortest path
   3.268      ///tree used in \ref predNode().
   3.269      ///
   3.270 -    ///\pre Either \ref run() or \ref start() must be called before
   3.271 -    ///using this function.
   3.272 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.273 +    ///must be called before using this function.
   3.274      Arc predArc(Node v) const { return (*_pred)[v]; }
   3.275  
   3.276      ///Returns the 'previous node' of the shortest path tree for a node.
   3.277  
   3.278      ///This function returns the 'previous node' of the shortest path
   3.279      ///tree for the node \c v, i.e. it returns the last but one node
   3.280 -    ///from a shortest path from the root(s) to \c v. It is \c INVALID
   3.281 -    ///if \c v is not reachable from the root(s) or if \c v is a root.
   3.282 +    ///from a shortest path from a root to \c v. It is \c INVALID
   3.283 +    ///if \c v is not reached from the root(s) or if \c v is a root.
   3.284      ///
   3.285      ///The shortest path tree used here is equal to the shortest path
   3.286      ///tree used in \ref predArc().
   3.287      ///
   3.288 -    ///\pre Either \ref run() or \ref start() must be called before
   3.289 -    ///using this function.
   3.290 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.291 +    ///must be called before using this function.
   3.292      Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   3.293                                    G->source((*_pred)[v]); }
   3.294  
   3.295 @@ -853,7 +859,7 @@
   3.296      ///Returns a const reference to the node map that stores the distances
   3.297      ///of the nodes calculated by the algorithm.
   3.298      ///
   3.299 -    ///\pre Either \ref run() or \ref init()
   3.300 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.301      ///must be called before using this function.
   3.302      const DistMap &distMap() const { return *_dist;}
   3.303  
   3.304 @@ -863,14 +869,15 @@
   3.305      ///Returns a const reference to the node map that stores the predecessor
   3.306      ///arcs, which form the shortest path tree.
   3.307      ///
   3.308 -    ///\pre Either \ref run() or \ref init()
   3.309 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.310      ///must be called before using this function.
   3.311      const PredMap &predMap() const { return *_pred;}
   3.312  
   3.313 -    ///Checks if a node is reachable from the root(s).
   3.314 +    ///Checks if a node is reached from the root(s).
   3.315  
   3.316 -    ///Returns \c true if \c v is reachable from the root(s).
   3.317 -    ///\pre Either \ref run() or \ref start()
   3.318 +    ///Returns \c true if \c v is reached from the root(s).
   3.319 +    ///
   3.320 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.321      ///must be called before using this function.
   3.322      bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
   3.323                                          Heap::PRE_HEAP; }
   3.324 @@ -879,7 +886,8 @@
   3.325  
   3.326      ///Returns \c true if \c v is processed, i.e. the shortest
   3.327      ///path to \c v has already found.
   3.328 -    ///\pre Either \ref run() or \ref init()
   3.329 +    ///
   3.330 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.331      ///must be called before using this function.
   3.332      bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   3.333                                            Heap::POST_HEAP; }
   3.334 @@ -888,7 +896,8 @@
   3.335  
   3.336      ///Returns the current distance of a node from the root(s).
   3.337      ///It may be decreased in the following processes.
   3.338 -    ///\pre Either \ref run() or \ref init()
   3.339 +    ///
   3.340 +    ///\pre Either \ref run(Node) "run()" or \ref init()
   3.341      ///must be called before using this function and
   3.342      ///node \c v must be reached but not necessarily processed.
   3.343      Value currentDist(Node v) const {
   3.344 @@ -1071,8 +1080,8 @@
   3.345  
   3.346    /// This auxiliary class is created to implement the
   3.347    /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
   3.348 -  /// It does not have own \ref run() method, it uses the functions
   3.349 -  /// and features of the plain \ref Dijkstra.
   3.350 +  /// It does not have own \ref run(Node) "run()" method, it uses the
   3.351 +  /// functions and features of the plain \ref Dijkstra.
   3.352    ///
   3.353    /// This class should only be used through the \ref dijkstra() function,
   3.354    /// which makes it easier to use the algorithm.
   3.355 @@ -1267,7 +1276,7 @@
   3.356    ///  // Compute shortest path from s to t
   3.357    ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
   3.358    ///\endcode
   3.359 -  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
   3.360 +  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
   3.361    ///to the end of the parameter list.
   3.362    ///\sa DijkstraWizard
   3.363    ///\sa Dijkstra