1.1 --- a/lemon/dijkstra.h Sun Nov 30 09:39:34 2008 +0000
1.2 +++ b/lemon/dijkstra.h Sun Nov 30 19:17:51 2008 +0100
1.3 @@ -202,20 +202,13 @@
1.4 ///it can be used easier.
1.5 ///
1.6 ///\tparam GR The type of the digraph the algorithm runs on.
1.7 - ///The default value is \ref ListDigraph.
1.8 - ///The value of GR is not used directly by \ref Dijkstra, it is only
1.9 - ///passed to \ref DijkstraDefaultTraits.
1.10 - ///\tparam LM A readable arc map that determines the lengths of the
1.11 - ///arcs. It is read once for each arc, so the map may involve in
1.12 + ///The default type is \ref ListDigraph.
1.13 + ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
1.14 + ///the lengths of the arcs.
1.15 + ///It is read once for each arc, so the map may involve in
1.16 ///relatively time consuming process to compute the arc lengths if
1.17 ///it is necessary. The default map type is \ref
1.18 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.19 - ///The value of LM is not used directly by \ref Dijkstra, it is only
1.20 - ///passed to \ref DijkstraDefaultTraits.
1.21 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.22 - ///The default traits class is \ref DijkstraDefaultTraits
1.23 - ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
1.24 - ///for the documentation of a Dijkstra traits class.
1.25 + ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.26 #ifdef DOXYGEN
1.27 template <typename GR, typename LM, typename TR>
1.28 #else
1.29 @@ -249,7 +242,7 @@
1.30 ///The operation traits class.
1.31 typedef typename TR::OperationTraits OperationTraits;
1.32
1.33 - ///The traits class.
1.34 + ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
1.35 typedef TR Traits;
1.36
1.37 private:
1.38 @@ -331,6 +324,7 @@
1.39 ///
1.40 ///\ref named-templ-param "Named parameter" for setting
1.41 ///PredMap type.
1.42 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.43 template <class T>
1.44 struct SetPredMap
1.45 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
1.46 @@ -351,6 +345,7 @@
1.47 ///
1.48 ///\ref named-templ-param "Named parameter" for setting
1.49 ///DistMap type.
1.50 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.51 template <class T>
1.52 struct SetDistMap
1.53 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
1.54 @@ -371,6 +366,7 @@
1.55 ///
1.56 ///\ref named-templ-param "Named parameter" for setting
1.57 ///ProcessedMap type.
1.58 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.59 template <class T>
1.60 struct SetProcessedMap
1.61 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
1.62 @@ -411,10 +407,14 @@
1.63 }
1.64 };
1.65 ///\brief \ref named-templ-param "Named parameter" for setting
1.66 - ///heap and cross reference type
1.67 + ///heap and cross reference types
1.68 ///
1.69 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.70 - ///reference type.
1.71 + ///reference types. If this named parameter is used, then external
1.72 + ///heap and cross reference objects must be passed to the algorithm
1.73 + ///using the \ref heap() function before calling \ref run(Node) "run()"
1.74 + ///or \ref init().
1.75 + ///\sa SetStandardHeap
1.76 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.77 struct SetHeap
1.78 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
1.79 @@ -434,12 +434,18 @@
1.80 }
1.81 };
1.82 ///\brief \ref named-templ-param "Named parameter" for setting
1.83 - ///heap and cross reference type with automatic allocation
1.84 + ///heap and cross reference types with automatic allocation
1.85 ///
1.86 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.87 - ///reference type. It can allocate the heap and the cross reference
1.88 - ///object if the cross reference's constructor waits for the digraph as
1.89 - ///parameter and the heap's constructor waits for the cross reference.
1.90 + ///reference types with automatic allocation.
1.91 + ///They should have standard constructor interfaces to be able to
1.92 + ///automatically created by the algorithm (i.e. the digraph should be
1.93 + ///passed to the constructor of the cross reference and the cross
1.94 + ///reference should be passed to the constructor of the heap).
1.95 + ///However external heap and cross reference objects could also be
1.96 + ///passed to the algorithm using the \ref heap() function before
1.97 + ///calling \ref run(Node) "run()" or \ref init().
1.98 + ///\sa SetHeap
1.99 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.100 struct SetStandardHeap
1.101 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
1.102 @@ -509,9 +515,10 @@
1.103 ///Sets the map that stores the predecessor arcs.
1.104
1.105 ///Sets the map that stores the predecessor arcs.
1.106 - ///If you don't use this function before calling \ref run(),
1.107 - ///it will allocate one. The destructor deallocates this
1.108 - ///automatically allocated map, of course.
1.109 + ///If you don't use this function before calling \ref run(Node) "run()"
1.110 + ///or \ref init(), an instance will be allocated automatically.
1.111 + ///The destructor deallocates this automatically allocated map,
1.112 + ///of course.
1.113 ///\return <tt> (*this) </tt>
1.114 Dijkstra &predMap(PredMap &m)
1.115 {
1.116 @@ -526,9 +533,10 @@
1.117 ///Sets the map that indicates which nodes are processed.
1.118
1.119 ///Sets the map that indicates which nodes are processed.
1.120 - ///If you don't use this function before calling \ref run(),
1.121 - ///it will allocate one. The destructor deallocates this
1.122 - ///automatically allocated map, of course.
1.123 + ///If you don't use this function before calling \ref run(Node) "run()"
1.124 + ///or \ref init(), an instance will be allocated automatically.
1.125 + ///The destructor deallocates this automatically allocated map,
1.126 + ///of course.
1.127 ///\return <tt> (*this) </tt>
1.128 Dijkstra &processedMap(ProcessedMap &m)
1.129 {
1.130 @@ -544,9 +552,10 @@
1.131
1.132 ///Sets the map that stores the distances of the nodes calculated by the
1.133 ///algorithm.
1.134 - ///If you don't use this function before calling \ref run(),
1.135 - ///it will allocate one. The destructor deallocates this
1.136 - ///automatically allocated map, of course.
1.137 + ///If you don't use this function before calling \ref run(Node) "run()"
1.138 + ///or \ref init(), an instance will be allocated automatically.
1.139 + ///The destructor deallocates this automatically allocated map,
1.140 + ///of course.
1.141 ///\return <tt> (*this) </tt>
1.142 Dijkstra &distMap(DistMap &m)
1.143 {
1.144 @@ -561,9 +570,11 @@
1.145 ///Sets the heap and the cross reference used by algorithm.
1.146
1.147 ///Sets the heap and the cross reference used by algorithm.
1.148 - ///If you don't use this function before calling \ref run(),
1.149 - ///it will allocate one. The destructor deallocates this
1.150 - ///automatically allocated heap and cross reference, of course.
1.151 + ///If you don't use this function before calling \ref run(Node) "run()"
1.152 + ///or \ref init(), heap and cross reference instances will be
1.153 + ///allocated automatically.
1.154 + ///The destructor deallocates these automatically allocated objects,
1.155 + ///of course.
1.156 ///\return <tt> (*this) </tt>
1.157 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
1.158 {
1.159 @@ -590,22 +601,19 @@
1.160
1.161 public:
1.162
1.163 - ///\name Execution control
1.164 - ///The simplest way to execute the algorithm is to use one of the
1.165 - ///member functions called \ref lemon::Dijkstra::run() "run()".
1.166 - ///\n
1.167 - ///If you need more control on the execution, first you must call
1.168 - ///\ref lemon::Dijkstra::init() "init()", then you can add several
1.169 - ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
1.170 - ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
1.171 - ///actual path computation.
1.172 + ///\name Execution Control
1.173 + ///The simplest way to execute the %Dijkstra algorithm is to use
1.174 + ///one of the member functions called \ref run(Node) "run()".\n
1.175 + ///If you need more control on the execution, first you have to call
1.176 + ///\ref init(), then you can add several source nodes with
1.177 + ///\ref addSource(). Finally the actual path computation can be
1.178 + ///performed with one of the \ref start() functions.
1.179
1.180 ///@{
1.181
1.182 + ///\brief Initializes the internal data structures.
1.183 + ///
1.184 ///Initializes the internal data structures.
1.185 -
1.186 - ///Initializes the internal data structures.
1.187 - ///
1.188 void init()
1.189 {
1.190 create_maps();
1.191 @@ -681,17 +689,16 @@
1.192 return !_heap->empty()?_heap->top():INVALID;
1.193 }
1.194
1.195 - ///\brief Returns \c false if there are nodes
1.196 - ///to be processed.
1.197 - ///
1.198 - ///Returns \c false if there are nodes
1.199 - ///to be processed in the priority heap.
1.200 + ///Returns \c false if there are nodes to be processed.
1.201 +
1.202 + ///Returns \c false if there are nodes to be processed
1.203 + ///in the priority heap.
1.204 bool emptyQueue() const { return _heap->empty(); }
1.205
1.206 - ///Returns the number of the nodes to be processed in the priority heap
1.207 + ///Returns the number of the nodes to be processed.
1.208
1.209 - ///Returns the number of the nodes to be processed in the priority heap.
1.210 - ///
1.211 + ///Returns the number of the nodes to be processed
1.212 + ///in the priority heap.
1.213 int queueSize() const { return _heap->size(); }
1.214
1.215 ///Executes the algorithm.
1.216 @@ -812,11 +819,10 @@
1.217 ///@}
1.218
1.219 ///\name Query Functions
1.220 - ///The result of the %Dijkstra algorithm can be obtained using these
1.221 + ///The results of the %Dijkstra algorithm can be obtained using these
1.222 ///functions.\n
1.223 - ///Either \ref lemon::Dijkstra::run() "run()" or
1.224 - ///\ref lemon::Dijkstra::start() "start()" must be called before
1.225 - ///using them.
1.226 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.227 + ///before using them.
1.228
1.229 ///@{
1.230
1.231 @@ -824,49 +830,49 @@
1.232
1.233 ///Returns the shortest path to a node.
1.234 ///
1.235 - ///\warning \c t should be reachable from the root(s).
1.236 + ///\warning \c t should be reached from the root(s).
1.237 ///
1.238 - ///\pre Either \ref run() or \ref start() must be called before
1.239 - ///using this function.
1.240 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.241 + ///must be called before using this function.
1.242 Path path(Node t) const { return Path(*G, *_pred, t); }
1.243
1.244 ///The distance of a node from the root(s).
1.245
1.246 ///Returns the distance of a node from the root(s).
1.247 ///
1.248 - ///\warning If node \c v is not reachable from the root(s), then
1.249 + ///\warning If node \c v is not reached from the root(s), then
1.250 ///the return value of this function is undefined.
1.251 ///
1.252 - ///\pre Either \ref run() or \ref start() must be called before
1.253 - ///using this function.
1.254 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.255 + ///must be called before using this function.
1.256 Value dist(Node v) const { return (*_dist)[v]; }
1.257
1.258 ///Returns the 'previous arc' of the shortest path tree for a node.
1.259
1.260 ///This function returns the 'previous arc' of the shortest path
1.261 ///tree for the node \c v, i.e. it returns the last arc of a
1.262 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.263 - ///is not reachable from the root(s) or if \c v is a root.
1.264 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.265 + ///is not reached from the root(s) or if \c v is a root.
1.266 ///
1.267 ///The shortest path tree used here is equal to the shortest path
1.268 ///tree used in \ref predNode().
1.269 ///
1.270 - ///\pre Either \ref run() or \ref start() must be called before
1.271 - ///using this function.
1.272 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.273 + ///must be called before using this function.
1.274 Arc predArc(Node v) const { return (*_pred)[v]; }
1.275
1.276 ///Returns the 'previous node' of the shortest path tree for a node.
1.277
1.278 ///This function returns the 'previous node' of the shortest path
1.279 ///tree for the node \c v, i.e. it returns the last but one node
1.280 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.281 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.282 + ///from a shortest path from a root to \c v. It is \c INVALID
1.283 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.284 ///
1.285 ///The shortest path tree used here is equal to the shortest path
1.286 ///tree used in \ref predArc().
1.287 ///
1.288 - ///\pre Either \ref run() or \ref start() must be called before
1.289 - ///using this function.
1.290 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.291 + ///must be called before using this function.
1.292 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.293 G->source((*_pred)[v]); }
1.294
1.295 @@ -876,7 +882,7 @@
1.296 ///Returns a const reference to the node map that stores the distances
1.297 ///of the nodes calculated by the algorithm.
1.298 ///
1.299 - ///\pre Either \ref run() or \ref init()
1.300 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.301 ///must be called before using this function.
1.302 const DistMap &distMap() const { return *_dist;}
1.303
1.304 @@ -886,14 +892,15 @@
1.305 ///Returns a const reference to the node map that stores the predecessor
1.306 ///arcs, which form the shortest path tree.
1.307 ///
1.308 - ///\pre Either \ref run() or \ref init()
1.309 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.310 ///must be called before using this function.
1.311 const PredMap &predMap() const { return *_pred;}
1.312
1.313 - ///Checks if a node is reachable from the root(s).
1.314 + ///Checks if a node is reached from the root(s).
1.315
1.316 - ///Returns \c true if \c v is reachable from the root(s).
1.317 - ///\pre Either \ref run() or \ref start()
1.318 + ///Returns \c true if \c v is reached from the root(s).
1.319 + ///
1.320 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.321 ///must be called before using this function.
1.322 bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
1.323 Heap::PRE_HEAP; }
1.324 @@ -902,7 +909,8 @@
1.325
1.326 ///Returns \c true if \c v is processed, i.e. the shortest
1.327 ///path to \c v has already found.
1.328 - ///\pre Either \ref run() or \ref init()
1.329 + ///
1.330 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.331 ///must be called before using this function.
1.332 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.333 Heap::POST_HEAP; }
1.334 @@ -911,7 +919,8 @@
1.335
1.336 ///Returns the current distance of a node from the root(s).
1.337 ///It may be decreased in the following processes.
1.338 - ///\pre Either \ref run() or \ref init()
1.339 + ///
1.340 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.341 ///must be called before using this function and
1.342 ///node \c v must be reached but not necessarily processed.
1.343 Value currentDist(Node v) const {
1.344 @@ -1094,8 +1103,8 @@
1.345
1.346 /// This auxiliary class is created to implement the
1.347 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1.348 - /// It does not have own \ref run() method, it uses the functions
1.349 - /// and features of the plain \ref Dijkstra.
1.350 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.351 + /// functions and features of the plain \ref Dijkstra.
1.352 ///
1.353 /// This class should only be used through the \ref dijkstra() function,
1.354 /// which makes it easier to use the algorithm.
1.355 @@ -1290,7 +1299,7 @@
1.356 /// // Compute shortest path from s to t
1.357 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
1.358 ///\endcode
1.359 - ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.360 + ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
1.361 ///to the end of the parameter list.
1.362 ///\sa DijkstraWizard
1.363 ///\sa Dijkstra