1.1 --- a/lemon/dijkstra.h Wed Jul 30 12:07:48 2008 +0100
1.2 +++ b/lemon/dijkstra.h Mon Aug 04 22:00:36 2008 +0200
1.3 @@ -33,10 +33,10 @@
1.4
1.5 namespace lemon {
1.6
1.7 - /// \brief Default OperationTraits for the Dijkstra algorithm class.
1.8 + /// \brief Default operation traits for the Dijkstra algorithm class.
1.9 ///
1.10 - /// It defines all computational operations and constants which are
1.11 - /// used in the Dijkstra algorithm.
1.12 + /// This operation traits class defines all computational operations and
1.13 + /// constants which are used in the Dijkstra algorithm.
1.14 template <typename Value>
1.15 struct DijkstraDefaultOperationTraits {
1.16 /// \brief Gives back the zero value of the type.
1.17 @@ -47,16 +47,19 @@
1.18 static Value plus(const Value& left, const Value& right) {
1.19 return left + right;
1.20 }
1.21 - /// \brief Gives back true only if the first value less than the second.
1.22 + /// \brief Gives back true only if the first value is less than the second.
1.23 static bool less(const Value& left, const Value& right) {
1.24 return left < right;
1.25 }
1.26 };
1.27
1.28 - /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
1.29 + /// \brief Widest path operation traits for the Dijkstra algorithm class.
1.30 ///
1.31 - /// It defines all computational operations and constants which are
1.32 - /// used in the Dijkstra algorithm for widest path computation.
1.33 + /// This operation traits class defines all computational operations and
1.34 + /// constants which are used in the Dijkstra algorithm for widest path
1.35 + /// computation.
1.36 + ///
1.37 + /// \see DijkstraDefaultOperationTraits
1.38 template <typename Value>
1.39 struct DijkstraWidestPathOperationTraits {
1.40 /// \brief Gives back the maximum value of the type.
1.41 @@ -67,7 +70,7 @@
1.42 static Value plus(const Value& left, const Value& right) {
1.43 return std::min(left, right);
1.44 }
1.45 - /// \brief Gives back true only if the first value less than the second.
1.46 + /// \brief Gives back true only if the first value is less than the second.
1.47 static bool less(const Value& left, const Value& right) {
1.48 return left < right;
1.49 }
1.50 @@ -76,141 +79,145 @@
1.51 ///Default traits class of Dijkstra class.
1.52
1.53 ///Default traits class of Dijkstra class.
1.54 - ///\tparam GR Digraph type.
1.55 - ///\tparam LM Type of length map.
1.56 + ///\tparam GR The type of the digraph.
1.57 + ///\tparam LM The type of the length map.
1.58 template<class GR, class LM>
1.59 struct DijkstraDefaultTraits
1.60 {
1.61 - ///The digraph type the algorithm runs on.
1.62 + ///The type of the digraph the algorithm runs on.
1.63 typedef GR Digraph;
1.64 +
1.65 ///The type of the map that stores the arc lengths.
1.66
1.67 ///The type of the map that stores the arc lengths.
1.68 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.69 typedef LM LengthMap;
1.70 - //The type of the length of the arcs.
1.71 + ///The type of the length of the arcs.
1.72 typedef typename LM::Value Value;
1.73 +
1.74 /// Operation traits for Dijkstra algorithm.
1.75
1.76 - /// It defines the used operation by the algorithm.
1.77 + /// This class defines the operations that are used in the algorithm.
1.78 /// \see DijkstraDefaultOperationTraits
1.79 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
1.80 - /// The cross reference type used by heap.
1.81
1.82 + /// The cross reference type used by the heap.
1.83
1.84 - /// The cross reference type used by heap.
1.85 + /// The cross reference type used by the heap.
1.86 /// Usually it is \c Digraph::NodeMap<int>.
1.87 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.88 - ///Instantiates a HeapCrossRef.
1.89 + ///Instantiates a \ref HeapCrossRef.
1.90
1.91 - ///This function instantiates a \c HeapCrossRef.
1.92 - /// \param G is the digraph, to which we would like to define the
1.93 - /// HeapCrossRef.
1.94 - static HeapCrossRef *createHeapCrossRef(const GR &G)
1.95 + ///This function instantiates a \ref HeapCrossRef.
1.96 + /// \param g is the digraph, to which we would like to define the
1.97 + /// \ref HeapCrossRef.
1.98 + static HeapCrossRef *createHeapCrossRef(const Digraph &g)
1.99 {
1.100 - return new HeapCrossRef(G);
1.101 + return new HeapCrossRef(g);
1.102 }
1.103
1.104 - ///The heap type used by Dijkstra algorithm.
1.105 + ///The heap type used by the Dijkstra algorithm.
1.106
1.107 - ///The heap type used by Dijkstra algorithm.
1.108 + ///The heap type used by the Dijkstra algorithm.
1.109 ///
1.110 ///\sa BinHeap
1.111 ///\sa Dijkstra
1.112 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.113 + ///Instantiates a \ref Heap.
1.114
1.115 - static Heap *createHeap(HeapCrossRef& R)
1.116 + ///This function instantiates a \ref Heap.
1.117 + static Heap *createHeap(HeapCrossRef& r)
1.118 {
1.119 - return new Heap(R);
1.120 + return new Heap(r);
1.121 }
1.122
1.123 - ///\brief The type of the map that stores the last
1.124 + ///\brief The type of the map that stores the predecessor
1.125 ///arcs of the shortest paths.
1.126 ///
1.127 - ///The type of the map that stores the last
1.128 + ///The type of the map that stores the predecessor
1.129 ///arcs of the shortest paths.
1.130 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.131 - ///
1.132 - typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.133 - ///Instantiates a PredMap.
1.134 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.135 + ///Instantiates a \ref PredMap.
1.136
1.137 - ///This function instantiates a \c PredMap.
1.138 - ///\param G is the digraph, to which we would like to define the PredMap.
1.139 + ///This function instantiates a \ref PredMap.
1.140 + ///\param g is the digraph, to which we would like to define the
1.141 + ///\ref PredMap.
1.142 ///\todo The digraph alone may be insufficient for the initialization
1.143 - static PredMap *createPredMap(const GR &G)
1.144 + static PredMap *createPredMap(const Digraph &g)
1.145 {
1.146 - return new PredMap(G);
1.147 + return new PredMap(g);
1.148 }
1.149
1.150 - ///The type of the map that stores whether a nodes is processed.
1.151 + ///The type of the map that indicates which nodes are processed.
1.152
1.153 - ///The type of the map that stores whether a nodes is processed.
1.154 + ///The type of the map that indicates which nodes are processed.
1.155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.156 ///By default it is a NullMap.
1.157 ///\todo If it is set to a real map,
1.158 ///Dijkstra::processed() should read this.
1.159 - ///\todo named parameter to set this type, function to read and write.
1.160 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.161 - ///Instantiates a ProcessedMap.
1.162 + ///Instantiates a \ref ProcessedMap.
1.163
1.164 - ///This function instantiates a \c ProcessedMap.
1.165 + ///This function instantiates a \ref ProcessedMap.
1.166 ///\param g is the digraph, to which
1.167 - ///we would like to define the \c ProcessedMap
1.168 + ///we would like to define the \ref ProcessedMap
1.169 #ifdef DOXYGEN
1.170 - static ProcessedMap *createProcessedMap(const GR &g)
1.171 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.172 #else
1.173 - static ProcessedMap *createProcessedMap(const GR &)
1.174 + static ProcessedMap *createProcessedMap(const Digraph &)
1.175 #endif
1.176 {
1.177 return new ProcessedMap();
1.178 }
1.179 - ///The type of the map that stores the dists of the nodes.
1.180
1.181 - ///The type of the map that stores the dists of the nodes.
1.182 + ///The type of the map that stores the distances of the nodes.
1.183 +
1.184 + ///The type of the map that stores the distances of the nodes.
1.185 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.186 - ///
1.187 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.188 - ///Instantiates a DistMap.
1.189 + ///Instantiates a \ref DistMap.
1.190
1.191 ///This function instantiates a \ref DistMap.
1.192 - ///\param G is the digraph, to which we would like to define
1.193 + ///\param g is the digraph, to which we would like to define
1.194 ///the \ref DistMap
1.195 - static DistMap *createDistMap(const GR &G)
1.196 + static DistMap *createDistMap(const Digraph &g)
1.197 {
1.198 - return new DistMap(G);
1.199 + return new DistMap(g);
1.200 }
1.201 };
1.202
1.203 ///%Dijkstra algorithm class.
1.204
1.205 /// \ingroup shortest_path
1.206 - ///This class provides an efficient implementation of %Dijkstra algorithm.
1.207 + ///This class provides an efficient implementation of the %Dijkstra algorithm.
1.208 + ///
1.209 ///The arc lengths are passed to the algorithm using a
1.210 ///\ref concepts::ReadMap "ReadMap",
1.211 ///so it is easy to change it to any kind of length.
1.212 - ///
1.213 ///The type of the length is determined by the
1.214 ///\ref concepts::ReadMap::Value "Value" of the length map.
1.215 - ///
1.216 ///It is also possible to change the underlying priority heap.
1.217 ///
1.218 - ///\tparam GR The digraph type the algorithm runs on. The default value
1.219 - ///is \ref ListDigraph. The value of GR is not used directly by
1.220 - ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
1.221 - ///\tparam LM This read-only ArcMap determines the lengths of the
1.222 + ///There is also a \ref dijkstra() "function type interface" for the
1.223 + ///%Dijkstra algorithm, which is convenient in the simplier cases and
1.224 + ///it can be used easier.
1.225 + ///
1.226 + ///\tparam GR The type of the digraph the algorithm runs on.
1.227 + ///The default value is \ref ListDigraph.
1.228 + ///The value of GR is not used directly by \ref Dijkstra, it is only
1.229 + ///passed to \ref DijkstraDefaultTraits.
1.230 + ///\tparam LM A readable arc map that determines the lengths of the
1.231 ///arcs. It is read once for each arc, so the map may involve in
1.232 - ///relatively time consuming process to compute the arc length if
1.233 + ///relatively time consuming process to compute the arc lengths if
1.234 ///it is necessary. The default map type is \ref
1.235 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value
1.236 - ///of LM is not used directly by Dijkstra, it is only passed to \ref
1.237 - ///DijkstraDefaultTraits.
1.238 - ///\tparam TR Traits class to set
1.239 - ///various data types used by the algorithm. The default traits
1.240 - ///class is \ref DijkstraDefaultTraits
1.241 - ///"DijkstraDefaultTraits<GR,LM>". See \ref
1.242 - ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
1.243 - ///class.
1.244 -
1.245 + ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.246 + ///The value of LM is not used directly by \ref Dijkstra, it is only
1.247 + ///passed to \ref DijkstraDefaultTraits.
1.248 + ///\tparam TR Traits class to set various data types used by the algorithm.
1.249 + ///The default traits class is \ref DijkstraDefaultTraits
1.250 + ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
1.251 + ///for the documentation of a Dijkstra traits class.
1.252 #ifdef DOXYGEN
1.253 template <typename GR, typename LM, typename TR>
1.254 #else
1.255 @@ -220,12 +227,10 @@
1.256 #endif
1.257 class Dijkstra {
1.258 public:
1.259 - /**
1.260 - * \brief \ref Exception for uninitialized parameters.
1.261 - *
1.262 - * This error represents problems in the initialization
1.263 - * of the parameters of the algorithms.
1.264 - */
1.265 + ///\ref Exception for uninitialized parameters.
1.266 +
1.267 + ///This error represents problems in the initialization of the
1.268 + ///parameters of the algorithm.
1.269 class UninitializedParameter : public lemon::UninitializedParameter {
1.270 public:
1.271 virtual const char* what() const throw() {
1.272 @@ -233,63 +238,65 @@
1.273 }
1.274 };
1.275
1.276 - typedef TR Traits;
1.277 - ///The type of the underlying digraph.
1.278 + ///The type of the digraph the algorithm runs on.
1.279 typedef typename TR::Digraph Digraph;
1.280 - ///\e
1.281 - typedef typename Digraph::Node Node;
1.282 - ///\e
1.283 - typedef typename Digraph::NodeIt NodeIt;
1.284 - ///\e
1.285 - typedef typename Digraph::Arc Arc;
1.286 - ///\e
1.287 - typedef typename Digraph::OutArcIt OutArcIt;
1.288
1.289 ///The type of the length of the arcs.
1.290 typedef typename TR::LengthMap::Value Value;
1.291 ///The type of the map that stores the arc lengths.
1.292 typedef typename TR::LengthMap LengthMap;
1.293 - ///\brief The type of the map that stores the last
1.294 - ///arcs of the shortest paths.
1.295 + ///\brief The type of the map that stores the predecessor arcs of the
1.296 + ///shortest paths.
1.297 typedef typename TR::PredMap PredMap;
1.298 - ///The type of the map indicating if a node is processed.
1.299 + ///The type of the map that stores the distances of the nodes.
1.300 + typedef typename TR::DistMap DistMap;
1.301 + ///The type of the map that indicates which nodes are processed.
1.302 typedef typename TR::ProcessedMap ProcessedMap;
1.303 - ///The type of the map that stores the dists of the nodes.
1.304 - typedef typename TR::DistMap DistMap;
1.305 + ///The type of the paths.
1.306 + typedef PredMapPath<Digraph, PredMap> Path;
1.307 ///The cross reference type used for the current heap.
1.308 typedef typename TR::HeapCrossRef HeapCrossRef;
1.309 - ///The heap type used by the dijkstra algorithm.
1.310 + ///The heap type used by the algorithm.
1.311 typedef typename TR::Heap Heap;
1.312 - ///The operation traits.
1.313 + ///The operation traits class.
1.314 typedef typename TR::OperationTraits OperationTraits;
1.315 +
1.316 + ///The traits class.
1.317 + typedef TR Traits;
1.318 +
1.319 private:
1.320 - /// Pointer to the underlying digraph.
1.321 +
1.322 + typedef typename Digraph::Node Node;
1.323 + typedef typename Digraph::NodeIt NodeIt;
1.324 + typedef typename Digraph::Arc Arc;
1.325 + typedef typename Digraph::OutArcIt OutArcIt;
1.326 +
1.327 + //Pointer to the underlying digraph.
1.328 const Digraph *G;
1.329 - /// Pointer to the length map
1.330 + //Pointer to the length map.
1.331 const LengthMap *length;
1.332 - ///Pointer to the map of predecessors arcs.
1.333 + //Pointer to the map of predecessors arcs.
1.334 PredMap *_pred;
1.335 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.336 + //Indicates if _pred is locally allocated (true) or not.
1.337 bool local_pred;
1.338 - ///Pointer to the map of distances.
1.339 + //Pointer to the map of distances.
1.340 DistMap *_dist;
1.341 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.342 + //Indicates if _dist is locally allocated (true) or not.
1.343 bool local_dist;
1.344 - ///Pointer to the map of processed status of the nodes.
1.345 + //Pointer to the map of processed status of the nodes.
1.346 ProcessedMap *_processed;
1.347 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.348 + //Indicates if _processed is locally allocated (true) or not.
1.349 bool local_processed;
1.350 - ///Pointer to the heap cross references.
1.351 + //Pointer to the heap cross references.
1.352 HeapCrossRef *_heap_cross_ref;
1.353 - ///Indicates if \ref _heap_cross_ref is locally allocated (\c true) or not.
1.354 + //Indicates if _heap_cross_ref is locally allocated (true) or not.
1.355 bool local_heap_cross_ref;
1.356 - ///Pointer to the heap.
1.357 + //Pointer to the heap.
1.358 Heap *_heap;
1.359 - ///Indicates if \ref _heap is locally allocated (\c true) or not.
1.360 + //Indicates if _heap is locally allocated (true) or not.
1.361 bool local_heap;
1.362
1.363 ///Creates the maps if necessary.
1.364 -
1.365 ///\todo Better memory allocation (instead of new).
1.366 void create_maps()
1.367 {
1.368 @@ -315,7 +322,7 @@
1.369 }
1.370 }
1.371
1.372 - public :
1.373 + public:
1.374
1.375 typedef Dijkstra Create;
1.376
1.377 @@ -331,10 +338,11 @@
1.378 throw UninitializedParameter();
1.379 }
1.380 };
1.381 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.382 -
1.383 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.384 + ///\brief \ref named-templ-param "Named parameter" for setting
1.385 + ///\ref PredMap type.
1.386 ///
1.387 + ///\ref named-templ-param "Named parameter" for setting
1.388 + ///\ref PredMap type.
1.389 template <class T>
1.390 struct DefPredMap
1.391 : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
1.392 @@ -349,10 +357,11 @@
1.393 throw UninitializedParameter();
1.394 }
1.395 };
1.396 - ///\ref named-templ-param "Named parameter" for setting DistMap type
1.397 -
1.398 - ///\ref named-templ-param "Named parameter" for setting DistMap type
1.399 + ///\brief \ref named-templ-param "Named parameter" for setting
1.400 + ///\ref DistMap type.
1.401 ///
1.402 + ///\ref named-templ-param "Named parameter" for setting
1.403 + ///\ref DistMap type.
1.404 template <class T>
1.405 struct DefDistMap
1.406 : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
1.407 @@ -362,15 +371,16 @@
1.408 template <class T>
1.409 struct DefProcessedMapTraits : public Traits {
1.410 typedef T ProcessedMap;
1.411 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.412 + static ProcessedMap *createProcessedMap(const Digraph &)
1.413 {
1.414 throw UninitializedParameter();
1.415 }
1.416 };
1.417 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.418 -
1.419 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.420 + ///\brief \ref named-templ-param "Named parameter" for setting
1.421 + ///\ref ProcessedMap type.
1.422 ///
1.423 + ///\ref named-templ-param "Named parameter" for setting
1.424 + ///\ref ProcessedMap type.
1.425 template <class T>
1.426 struct DefProcessedMap
1.427 : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
1.428 @@ -379,17 +389,17 @@
1.429
1.430 struct DefDigraphProcessedMapTraits : public Traits {
1.431 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.432 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.433 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.434 {
1.435 - return new ProcessedMap(G);
1.436 + return new ProcessedMap(g);
1.437 }
1.438 };
1.439 - ///\brief \ref named-templ-param "Named parameter"
1.440 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.441 + ///\brief \ref named-templ-param "Named parameter" for setting
1.442 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.443 ///
1.444 - ///\ref named-templ-param "Named parameter"
1.445 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.446 - ///If you don't set it explicitely, it will be automatically allocated.
1.447 + ///\ref named-templ-param "Named parameter" for setting
1.448 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.449 + ///If you don't set it explicitly, it will be automatically allocated.
1.450 template <class T>
1.451 struct DefProcessedMapToBeDefaultMap
1.452 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
1.453 @@ -413,8 +423,7 @@
1.454 ///heap and cross reference type
1.455 ///
1.456 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.457 - ///reference type
1.458 - ///
1.459 + ///reference type.
1.460 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.461 struct DefHeap
1.462 : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
1.463 @@ -453,10 +462,10 @@
1.464 };
1.465
1.466 /// \brief \ref named-templ-param "Named parameter" for setting
1.467 - /// OperationTraits type
1.468 + ///\ref OperationTraits type
1.469 ///
1.470 - /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.471 - /// type
1.472 + ///\ref named-templ-param "Named parameter" for setting
1.473 + ///\ref OperationTraits type.
1.474 template <class T>
1.475 struct DefOperationTraits
1.476 : public Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> > {
1.477 @@ -466,7 +475,6 @@
1.478
1.479 ///@}
1.480
1.481 -
1.482 protected:
1.483
1.484 Dijkstra() {}
1.485 @@ -475,10 +483,11 @@
1.486
1.487 ///Constructor.
1.488
1.489 - ///\param _G the digraph the algorithm will run on.
1.490 - ///\param _length the length map used by the algorithm.
1.491 - Dijkstra(const Digraph& _G, const LengthMap& _length) :
1.492 - G(&_G), length(&_length),
1.493 + ///Constructor.
1.494 + ///\param _g The digraph the algorithm runs on.
1.495 + ///\param _length The length map used by the algorithm.
1.496 + Dijkstra(const Digraph& _g, const LengthMap& _length) :
1.497 + G(&_g), length(&_length),
1.498 _pred(NULL), local_pred(false),
1.499 _dist(NULL), local_dist(false),
1.500 _processed(NULL), local_processed(false),
1.501 @@ -506,11 +515,11 @@
1.502 return *this;
1.503 }
1.504
1.505 - ///Sets the map storing the predecessor arcs.
1.506 + ///Sets the map that stores the predecessor arcs.
1.507
1.508 - ///Sets the map storing the predecessor arcs.
1.509 + ///Sets the map that stores the predecessor arcs.
1.510 ///If you don't use this function before calling \ref run(),
1.511 - ///it will allocate one. The destuctor deallocates this
1.512 + ///it will allocate one. The destructor deallocates this
1.513 ///automatically allocated map, of course.
1.514 ///\return <tt> (*this) </tt>
1.515 Dijkstra &predMap(PredMap &m)
1.516 @@ -523,11 +532,29 @@
1.517 return *this;
1.518 }
1.519
1.520 - ///Sets the map storing the distances calculated by the algorithm.
1.521 + ///Sets the map that indicates which nodes are processed.
1.522
1.523 - ///Sets the map storing the distances calculated by the algorithm.
1.524 + ///Sets the map that indicates which nodes are processed.
1.525 ///If you don't use this function before calling \ref run(),
1.526 - ///it will allocate one. The destuctor deallocates this
1.527 + ///it will allocate one. The destructor deallocates this
1.528 + ///automatically allocated map, of course.
1.529 + ///\return <tt> (*this) </tt>
1.530 + Dijkstra &processedMap(ProcessedMap &m)
1.531 + {
1.532 + if(local_processed) {
1.533 + delete _processed;
1.534 + local_processed=false;
1.535 + }
1.536 + _processed = &m;
1.537 + return *this;
1.538 + }
1.539 +
1.540 + ///Sets the map that stores the distances of the nodes.
1.541 +
1.542 + ///Sets the map that stores the distances of the nodes calculated by the
1.543 + ///algorithm.
1.544 + ///If you don't use this function before calling \ref run(),
1.545 + ///it will allocate one. The destructor deallocates this
1.546 ///automatically allocated map, of course.
1.547 ///\return <tt> (*this) </tt>
1.548 Dijkstra &distMap(DistMap &m)
1.549 @@ -544,7 +571,7 @@
1.550
1.551 ///Sets the heap and the cross reference used by algorithm.
1.552 ///If you don't use this function before calling \ref run(),
1.553 - ///it will allocate one. The destuctor deallocates this
1.554 + ///it will allocate one. The destructor deallocates this
1.555 ///automatically allocated heap and cross reference, of course.
1.556 ///\return <tt> (*this) </tt>
1.557 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
1.558 @@ -563,6 +590,7 @@
1.559 }
1.560
1.561 private:
1.562 +
1.563 void finalizeNodeData(Node v,Value dst)
1.564 {
1.565 _processed->set(v,true);
1.566 @@ -571,17 +599,15 @@
1.567
1.568 public:
1.569
1.570 - typedef PredMapPath<Digraph, PredMap> Path;
1.571 -
1.572 ///\name Execution control
1.573 - ///The simplest way to execute the algorithm is to use
1.574 - ///one of the member functions called \c run(...).
1.575 + ///The simplest way to execute the algorithm is to use one of the
1.576 + ///member functions called \ref lemon::Dijkstra::run() "run()".
1.577 ///\n
1.578 - ///If you need more control on the execution,
1.579 - ///first you must call \ref init(), then you can add several source nodes
1.580 - ///with \ref addSource().
1.581 - ///Finally \ref start() will perform the actual path
1.582 - ///computation.
1.583 + ///If you need more control on the execution, first you must call
1.584 + ///\ref lemon::Dijkstra::init() "init()", then you can add several
1.585 + ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
1.586 + ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
1.587 + ///actual path computation.
1.588
1.589 ///@{
1.590
1.591 @@ -603,10 +629,9 @@
1.592 ///Adds a new source node.
1.593
1.594 ///Adds a new source node to the priority heap.
1.595 - ///
1.596 ///The optional second parameter is the initial distance of the node.
1.597 ///
1.598 - ///It checks if the node has already been added to the heap and
1.599 + ///The function checks if the node has already been added to the heap and
1.600 ///it is pushed to the heap only if either it was not in the heap
1.601 ///or the shortest path found till then is shorter than \c dst.
1.602 void addSource(Node s,Value dst=OperationTraits::zero())
1.603 @@ -625,7 +650,7 @@
1.604 ///
1.605 ///\return The processed node.
1.606 ///
1.607 - ///\warning The priority heap must not be empty!
1.608 + ///\warning The priority heap must not be empty.
1.609 Node processNextNode()
1.610 {
1.611 Node v=_heap->top();
1.612 @@ -656,62 +681,66 @@
1.613 return v;
1.614 }
1.615
1.616 - ///Next node to be processed.
1.617 + ///The next node to be processed.
1.618
1.619 - ///Next node to be processed.
1.620 - ///
1.621 - ///\return The next node to be processed or INVALID if the priority heap
1.622 - /// is empty.
1.623 - Node nextNode()
1.624 + ///Returns the next node to be processed or \c INVALID if the
1.625 + ///priority heap is empty.
1.626 + Node nextNode() const
1.627 {
1.628 return !_heap->empty()?_heap->top():INVALID;
1.629 }
1.630
1.631 ///\brief Returns \c false if there are nodes
1.632 - ///to be processed in the priority heap
1.633 + ///to be processed.
1.634 ///
1.635 ///Returns \c false if there are nodes
1.636 - ///to be processed in the priority heap
1.637 - bool emptyQueue() { return _heap->empty(); }
1.638 + ///to be processed in the priority heap.
1.639 + bool emptyQueue() const { return _heap->empty(); }
1.640 +
1.641 ///Returns the number of the nodes to be processed in the priority heap
1.642
1.643 - ///Returns the number of the nodes to be processed in the priority heap
1.644 + ///Returns the number of the nodes to be processed in the priority heap.
1.645 ///
1.646 - int queueSize() { return _heap->size(); }
1.647 + int queueSize() const { return _heap->size(); }
1.648
1.649 ///Executes the algorithm.
1.650
1.651 ///Executes the algorithm.
1.652 ///
1.653 - ///\pre init() must be called and at least one node should be added
1.654 - ///with addSource() before using this function.
1.655 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.656 + ///in order to compute the shortest path to each node.
1.657 + ///
1.658 + ///The algorithm computes
1.659 + ///- the shortest path tree (forest),
1.660 + ///- the distance of each node from the root(s).
1.661 + ///
1.662 + ///\pre init() must be called and at least one root node should be
1.663 + ///added with addSource() before using this function.
1.664 + ///
1.665 + ///\note <tt>d.start()</tt> is just a shortcut of the following code.
1.666 + ///\code
1.667 + /// while ( !d.emptyQueue() ) {
1.668 + /// d.processNextNode();
1.669 + /// }
1.670 + ///\endcode
1.671 + void start()
1.672 + {
1.673 + while ( !emptyQueue() ) processNextNode();
1.674 + }
1.675 +
1.676 + ///Executes the algorithm until the given target node is reached.
1.677 +
1.678 + ///Executes the algorithm until the given target node is reached.
1.679 ///
1.680 ///This method runs the %Dijkstra algorithm from the root node(s)
1.681 - ///in order to
1.682 - ///compute the
1.683 - ///shortest path to each node. The algorithm computes
1.684 - ///- The shortest path tree.
1.685 - ///- The distance of each node from the root(s).
1.686 + ///in order to compute the shortest path to \c dest.
1.687 ///
1.688 - void start()
1.689 - {
1.690 - while ( !_heap->empty() ) processNextNode();
1.691 - }
1.692 -
1.693 - ///Executes the algorithm until \c dest is reached.
1.694 -
1.695 - ///Executes the algorithm until \c dest is reached.
1.696 + ///The algorithm computes
1.697 + ///- the shortest path to \c dest,
1.698 + ///- the distance of \c dest from the root(s).
1.699 ///
1.700 - ///\pre init() must be called and at least one node should be added
1.701 - ///with addSource() before using this function.
1.702 - ///
1.703 - ///This method runs the %Dijkstra algorithm from the root node(s)
1.704 - ///in order to
1.705 - ///compute the
1.706 - ///shortest path to \c dest. The algorithm computes
1.707 - ///- The shortest path to \c dest.
1.708 - ///- The distance of \c dest from the root(s).
1.709 - ///
1.710 + ///\pre init() must be called and at least one root node should be
1.711 + ///added with addSource() before using this function.
1.712 void start(Node dest)
1.713 {
1.714 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
1.715 @@ -722,14 +751,18 @@
1.716
1.717 ///Executes the algorithm until a condition is met.
1.718 ///
1.719 - ///\pre init() must be called and at least one node should be added
1.720 - ///with addSource() before using this function.
1.721 + ///This method runs the %Dijkstra algorithm from the root node(s) in
1.722 + ///order to compute the shortest path to a node \c v with
1.723 + /// <tt>nm[v]</tt> true, if such a node can be found.
1.724 ///
1.725 - ///\param nm must be a bool (or convertible) node map. The algorithm
1.726 + ///\param nm A \c bool (or convertible) node map. The algorithm
1.727 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
1.728 ///
1.729 ///\return The reached node \c v with <tt>nm[v]</tt> true or
1.730 ///\c INVALID if no such node was found.
1.731 + ///
1.732 + ///\pre init() must be called and at least one root node should be
1.733 + ///added with addSource() before using this function.
1.734 template<class NodeBoolMap>
1.735 Node start(const NodeBoolMap &nm)
1.736 {
1.737 @@ -739,16 +772,16 @@
1.738 return _heap->top();
1.739 }
1.740
1.741 - ///Runs %Dijkstra algorithm from node \c s.
1.742 + ///Runs the algorithm from the given node.
1.743
1.744 - ///This method runs the %Dijkstra algorithm from a root node \c s
1.745 - ///in order to
1.746 - ///compute the
1.747 - ///shortest path to each node. The algorithm computes
1.748 - ///- The shortest path tree.
1.749 - ///- The distance of each node from the root.
1.750 + ///This method runs the %Dijkstra algorithm from node \c s
1.751 + ///in order to compute the shortest path to each node.
1.752 ///
1.753 - ///\note d.run(s) is just a shortcut of the following code.
1.754 + ///The algorithm computes
1.755 + ///- the shortest path tree,
1.756 + ///- the distance of each node from the root.
1.757 + ///
1.758 + ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
1.759 ///\code
1.760 /// d.init();
1.761 /// d.addSource(s);
1.762 @@ -762,12 +795,14 @@
1.763
1.764 ///Finds the shortest path between \c s and \c t.
1.765
1.766 - ///Finds the shortest path between \c s and \c t.
1.767 + ///This method runs the %Dijkstra algorithm from node \c s
1.768 + ///in order to compute the shortest path to \c t.
1.769 ///
1.770 - ///\return The length of the shortest s---t path if there exists one,
1.771 - ///0 otherwise.
1.772 - ///\note Apart from the return value, d.run(s) is
1.773 - ///just a shortcut of the following code.
1.774 + ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
1.775 + ///if \c t is reachable form \c s, \c 0 otherwise.
1.776 + ///
1.777 + ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
1.778 + ///shortcut of the following code.
1.779 ///\code
1.780 /// d.init();
1.781 /// d.addSource(s);
1.782 @@ -785,241 +820,262 @@
1.783 ///\name Query Functions
1.784 ///The result of the %Dijkstra algorithm can be obtained using these
1.785 ///functions.\n
1.786 - ///Before the use of these functions,
1.787 - ///either run() or start() must be called.
1.788 + ///Either \ref lemon::Dijkstra::run() "run()" or
1.789 + ///\ref lemon::Dijkstra::start() "start()" must be called before
1.790 + ///using them.
1.791
1.792 ///@{
1.793
1.794 - ///Gives back the shortest path.
1.795 + ///The shortest path to a node.
1.796
1.797 - ///Gives back the shortest path.
1.798 - ///\pre The \c t should be reachable from the source.
1.799 - Path path(Node t)
1.800 - {
1.801 - return Path(*G, *_pred, t);
1.802 - }
1.803 + ///Returns the shortest path to a node.
1.804 + ///
1.805 + ///\warning \c t should be reachable from the root(s).
1.806 + ///
1.807 + ///\pre Either \ref run() or \ref start() must be called before
1.808 + ///using this function.
1.809 + Path path(Node t) const { return Path(*G, *_pred, t); }
1.810
1.811 - ///The distance of a node from the root.
1.812 + ///The distance of a node from the root(s).
1.813
1.814 - ///Returns the distance of a node from the root.
1.815 - ///\pre \ref run() must be called before using this function.
1.816 - ///\warning If node \c v in unreachable from the root the return value
1.817 - ///of this funcion is undefined.
1.818 + ///Returns the distance of a node from the root(s).
1.819 + ///
1.820 + ///\warning If node \c v is not reachable from the root(s), then
1.821 + ///the return value of this function is undefined.
1.822 + ///
1.823 + ///\pre Either \ref run() or \ref start() must be called before
1.824 + ///using this function.
1.825 Value dist(Node v) const { return (*_dist)[v]; }
1.826
1.827 - ///The current distance of a node from the root.
1.828 + ///Returns the 'previous arc' of the shortest path tree for a node.
1.829
1.830 - ///Returns the current distance of a node from the root.
1.831 - ///It may be decreased in the following processes.
1.832 - ///\pre \c node should be reached but not processed
1.833 - Value currentDist(Node v) const { return (*_heap)[v]; }
1.834 -
1.835 - ///Returns the 'previous arc' of the shortest path tree.
1.836 -
1.837 - ///For a node \c v it returns the 'previous arc' of the shortest path tree,
1.838 - ///i.e. it returns the last arc of a shortest path from the root to \c
1.839 - ///v. It is \ref INVALID
1.840 - ///if \c v is unreachable from the root or if \c v=s. The
1.841 - ///shortest path tree used here is equal to the shortest path tree used in
1.842 - ///\ref predNode(). \pre \ref run() must be called before using
1.843 - ///this function.
1.844 + ///This function returns the 'previous arc' of the shortest path
1.845 + ///tree for the node \c v, i.e. it returns the last arc of a
1.846 + ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.847 + ///is not reachable from the root(s) or if \c v is a root.
1.848 + ///
1.849 + ///The shortest path tree used here is equal to the shortest path
1.850 + ///tree used in \ref predNode().
1.851 + ///
1.852 + ///\pre Either \ref run() or \ref start() must be called before
1.853 + ///using this function.
1.854 Arc predArc(Node v) const { return (*_pred)[v]; }
1.855
1.856 - ///Returns the 'previous node' of the shortest path tree.
1.857 + ///Returns the 'previous node' of the shortest path tree for a node.
1.858
1.859 - ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.860 - ///i.e. it returns the last but one node from a shortest path from the
1.861 - ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.862 - ///\c v=s. The shortest path tree used here is equal to the shortest path
1.863 - ///tree used in \ref predArc(). \pre \ref run() must be called before
1.864 + ///This function returns the 'previous node' of the shortest path
1.865 + ///tree for the node \c v, i.e. it returns the last but one node
1.866 + ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.867 + ///if \c v is not reachable from the root(s) or if \c v is a root.
1.868 + ///
1.869 + ///The shortest path tree used here is equal to the shortest path
1.870 + ///tree used in \ref predArc().
1.871 + ///
1.872 + ///\pre Either \ref run() or \ref start() must be called before
1.873 ///using this function.
1.874 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.875 G->source((*_pred)[v]); }
1.876
1.877 - ///Returns a reference to the NodeMap of distances.
1.878 -
1.879 - ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.880 - ///be called before using this function.
1.881 + ///\brief Returns a const reference to the node map that stores the
1.882 + ///distances of the nodes.
1.883 + ///
1.884 + ///Returns a const reference to the node map that stores the distances
1.885 + ///of the nodes calculated by the algorithm.
1.886 + ///
1.887 + ///\pre Either \ref run() or \ref init()
1.888 + ///must be called before using this function.
1.889 const DistMap &distMap() const { return *_dist;}
1.890
1.891 - ///Returns a reference to the shortest path tree map.
1.892 -
1.893 - ///Returns a reference to the NodeMap of the arcs of the
1.894 - ///shortest path tree.
1.895 - ///\pre \ref run() must be called before using this function.
1.896 + ///\brief Returns a const reference to the node map that stores the
1.897 + ///predecessor arcs.
1.898 + ///
1.899 + ///Returns a const reference to the node map that stores the predecessor
1.900 + ///arcs, which form the shortest path tree.
1.901 + ///
1.902 + ///\pre Either \ref run() or \ref init()
1.903 + ///must be called before using this function.
1.904 const PredMap &predMap() const { return *_pred;}
1.905
1.906 - ///Checks if a node is reachable from the root.
1.907 + ///Checks if a node is reachable from the root(s).
1.908
1.909 - ///Returns \c true if \c v is reachable from the root.
1.910 - ///\warning The source nodes are inditated as unreached.
1.911 - ///\pre \ref run() must be called before using this function.
1.912 - ///
1.913 - bool reached(Node v) { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; }
1.914 + ///Returns \c true if \c v is reachable from the root(s).
1.915 + ///\pre Either \ref run() or \ref start()
1.916 + ///must be called before using this function.
1.917 + bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
1.918 + Heap::PRE_HEAP; }
1.919
1.920 ///Checks if a node is processed.
1.921
1.922 ///Returns \c true if \c v is processed, i.e. the shortest
1.923 ///path to \c v has already found.
1.924 - ///\pre \ref run() must be called before using this function.
1.925 - ///
1.926 - bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
1.927 + ///\pre Either \ref run() or \ref start()
1.928 + ///must be called before using this function.
1.929 + bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.930 + Heap::POST_HEAP; }
1.931 +
1.932 + ///The current distance of a node from the root(s).
1.933 +
1.934 + ///Returns the current distance of a node from the root(s).
1.935 + ///It may be decreased in the following processes.
1.936 + ///\pre \c v should be reached but not processed.
1.937 + Value currentDist(Node v) const { return (*_heap)[v]; }
1.938
1.939 ///@}
1.940 };
1.941
1.942
1.943 + ///Default traits class of dijkstra() function.
1.944
1.945 -
1.946 -
1.947 - ///Default traits class of Dijkstra function.
1.948 -
1.949 - ///Default traits class of Dijkstra function.
1.950 - ///\tparam GR Digraph type.
1.951 - ///\tparam LM Type of length map.
1.952 + ///Default traits class of dijkstra() function.
1.953 + ///\tparam GR The type of the digraph.
1.954 + ///\tparam LM The type of the length map.
1.955 template<class GR, class LM>
1.956 struct DijkstraWizardDefaultTraits
1.957 {
1.958 - ///The digraph type the algorithm runs on.
1.959 + ///The type of the digraph the algorithm runs on.
1.960 typedef GR Digraph;
1.961 ///The type of the map that stores the arc lengths.
1.962
1.963 ///The type of the map that stores the arc lengths.
1.964 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.965 typedef LM LengthMap;
1.966 - //The type of the length of the arcs.
1.967 + ///The type of the length of the arcs.
1.968 typedef typename LM::Value Value;
1.969 +
1.970 /// Operation traits for Dijkstra algorithm.
1.971
1.972 - /// It defines the used operation by the algorithm.
1.973 + /// This class defines the operations that are used in the algorithm.
1.974 /// \see DijkstraDefaultOperationTraits
1.975 typedef DijkstraDefaultOperationTraits<Value> OperationTraits;
1.976 - ///The heap type used by Dijkstra algorithm.
1.977
1.978 - /// The cross reference type used by heap.
1.979 + /// The cross reference type used by the heap.
1.980
1.981 - /// The cross reference type used by heap.
1.982 + /// The cross reference type used by the heap.
1.983 /// Usually it is \c Digraph::NodeMap<int>.
1.984 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.985 - ///Instantiates a HeapCrossRef.
1.986 + ///Instantiates a \ref HeapCrossRef.
1.987
1.988 ///This function instantiates a \ref HeapCrossRef.
1.989 - /// \param G is the digraph, to which we would like to define the
1.990 + /// \param g is the digraph, to which we would like to define the
1.991 /// HeapCrossRef.
1.992 /// \todo The digraph alone may be insufficient for the initialization
1.993 - static HeapCrossRef *createHeapCrossRef(const GR &G)
1.994 + static HeapCrossRef *createHeapCrossRef(const Digraph &g)
1.995 {
1.996 - return new HeapCrossRef(G);
1.997 + return new HeapCrossRef(g);
1.998 }
1.999
1.1000 - ///The heap type used by Dijkstra algorithm.
1.1001 + ///The heap type used by the Dijkstra algorithm.
1.1002
1.1003 - ///The heap type used by Dijkstra algorithm.
1.1004 + ///The heap type used by the Dijkstra algorithm.
1.1005 ///
1.1006 ///\sa BinHeap
1.1007 ///\sa Dijkstra
1.1008 - typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
1.1009 + typedef BinHeap<Value, typename Digraph::template NodeMap<int>,
1.1010 std::less<Value> > Heap;
1.1011
1.1012 - static Heap *createHeap(HeapCrossRef& R)
1.1013 + ///Instantiates a \ref Heap.
1.1014 +
1.1015 + ///This function instantiates a \ref Heap.
1.1016 + /// \param r is the HeapCrossRef which is used.
1.1017 + static Heap *createHeap(HeapCrossRef& r)
1.1018 {
1.1019 - return new Heap(R);
1.1020 + return new Heap(r);
1.1021 }
1.1022
1.1023 - ///\brief The type of the map that stores the last
1.1024 + ///\brief The type of the map that stores the predecessor
1.1025 ///arcs of the shortest paths.
1.1026 ///
1.1027 - ///The type of the map that stores the last
1.1028 + ///The type of the map that stores the predecessor
1.1029 ///arcs of the shortest paths.
1.1030 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1031 - ///
1.1032 - typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
1.1033 - ///Instantiates a PredMap.
1.1034 + typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
1.1035 + ///Instantiates a \ref PredMap.
1.1036
1.1037 ///This function instantiates a \ref PredMap.
1.1038 - ///\param g is the digraph, to which we would like to define the PredMap.
1.1039 - ///\todo The digraph alone may be insufficient for the initialization
1.1040 + ///\param g is the digraph, to which we would like to define the
1.1041 + ///\ref PredMap.
1.1042 + ///\todo The digraph alone may be insufficient to initialize
1.1043 #ifdef DOXYGEN
1.1044 - static PredMap *createPredMap(const GR &g)
1.1045 + static PredMap *createPredMap(const Digraph &g)
1.1046 #else
1.1047 - static PredMap *createPredMap(const GR &)
1.1048 + static PredMap *createPredMap(const Digraph &)
1.1049 #endif
1.1050 {
1.1051 return new PredMap();
1.1052 }
1.1053 - ///The type of the map that stores whether a nodes is processed.
1.1054
1.1055 - ///The type of the map that stores whether a nodes is processed.
1.1056 + ///The type of the map that indicates which nodes are processed.
1.1057 +
1.1058 + ///The type of the map that indicates which nodes are processed.
1.1059 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1060 ///By default it is a NullMap.
1.1061 ///\todo If it is set to a real map,
1.1062 ///Dijkstra::processed() should read this.
1.1063 ///\todo named parameter to set this type, function to read and write.
1.1064 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.1065 - ///Instantiates a ProcessedMap.
1.1066 + ///Instantiates a \ref ProcessedMap.
1.1067
1.1068 ///This function instantiates a \ref ProcessedMap.
1.1069 ///\param g is the digraph, to which
1.1070 - ///we would like to define the \ref ProcessedMap
1.1071 + ///we would like to define the \ref ProcessedMap.
1.1072 #ifdef DOXYGEN
1.1073 - static ProcessedMap *createProcessedMap(const GR &g)
1.1074 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.1075 #else
1.1076 - static ProcessedMap *createProcessedMap(const GR &)
1.1077 + static ProcessedMap *createProcessedMap(const Digraph &)
1.1078 #endif
1.1079 {
1.1080 return new ProcessedMap();
1.1081 }
1.1082 - ///The type of the map that stores the dists of the nodes.
1.1083
1.1084 - ///The type of the map that stores the dists of the nodes.
1.1085 + ///The type of the map that stores the distances of the nodes.
1.1086 +
1.1087 + ///The type of the map that stores the distances of the nodes.
1.1088 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1089 - ///
1.1090 - typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
1.1091 - ///Instantiates a DistMap.
1.1092 + typedef NullMap<typename Digraph::Node,Value> DistMap;
1.1093 + ///Instantiates a \ref DistMap.
1.1094
1.1095 ///This function instantiates a \ref DistMap.
1.1096 ///\param g is the digraph, to which we would like to define
1.1097 ///the \ref DistMap
1.1098 #ifdef DOXYGEN
1.1099 - static DistMap *createDistMap(const GR &g)
1.1100 + static DistMap *createDistMap(const Digraph &g)
1.1101 #else
1.1102 - static DistMap *createDistMap(const GR &)
1.1103 + static DistMap *createDistMap(const Digraph &)
1.1104 #endif
1.1105 {
1.1106 return new DistMap();
1.1107 }
1.1108 };
1.1109
1.1110 - /// Default traits used by \ref DijkstraWizard
1.1111 + /// Default traits class used by \ref DijkstraWizard
1.1112
1.1113 /// To make it easier to use Dijkstra algorithm
1.1114 - ///we have created a wizard class.
1.1115 + /// we have created a wizard class.
1.1116 /// This \ref DijkstraWizard class needs default traits,
1.1117 - ///as well as the \ref Dijkstra class.
1.1118 + /// as well as the \ref Dijkstra class.
1.1119 /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.1120 /// \ref DijkstraWizard class.
1.1121 /// \todo More named parameters are required...
1.1122 template<class GR,class LM>
1.1123 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.1124 {
1.1125 -
1.1126 typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.1127 protected:
1.1128 - /// Type of the nodes in the digraph.
1.1129 + //The type of the nodes in the digraph.
1.1130 typedef typename Base::Digraph::Node Node;
1.1131
1.1132 - /// Pointer to the underlying digraph.
1.1133 + //Pointer to the digraph the algorithm runs on.
1.1134 void *_g;
1.1135 - /// Pointer to the length map
1.1136 + //Pointer to the length map
1.1137 void *_length;
1.1138 - ///Pointer to the map of predecessors arcs.
1.1139 + //Pointer to the map of predecessors arcs.
1.1140 void *_pred;
1.1141 - ///Pointer to the map of distances.
1.1142 + //Pointer to the map of distances.
1.1143 void *_dist;
1.1144 - ///Pointer to the source node.
1.1145 + //Pointer to the source node.
1.1146 Node _source;
1.1147
1.1148 - public:
1.1149 + public:
1.1150 /// Constructor.
1.1151
1.1152 /// This constructor does not require parameters, therefore it initiates
1.1153 @@ -1032,9 +1088,9 @@
1.1154 /// This constructor requires some parameters,
1.1155 /// listed in the parameters list.
1.1156 /// Others are initiated to 0.
1.1157 - /// \param g is the initial value of \ref _g
1.1158 - /// \param l is the initial value of \ref _length
1.1159 - /// \param s is the initial value of \ref _source
1.1160 + /// \param g The digraph the algorithm runs on.
1.1161 + /// \param l The length map.
1.1162 + /// \param s The source node.
1.1163 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.1164 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.1165 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.1166 @@ -1042,11 +1098,13 @@
1.1167
1.1168 };
1.1169
1.1170 - /// A class to make the usage of Dijkstra algorithm easier
1.1171 + /// Auxiliary class for the function type interface of Dijkstra algorithm.
1.1172
1.1173 - /// This class is created to make it easier to use Dijkstra algorithm.
1.1174 - /// It uses the functions and features of the plain \ref Dijkstra,
1.1175 - /// but it is much simpler to use it.
1.1176 + /// This auxiliary class is created to implement the function type
1.1177 + /// interface of \ref Dijkstra algorithm. It uses the functions and features
1.1178 + /// of the plain \ref Dijkstra, but it is much simpler to use it.
1.1179 + /// It should only be used through the \ref dijkstra() function, which makes
1.1180 + /// it easier to use the algorithm.
1.1181 ///
1.1182 /// Simplicity means that the way to change the types defined
1.1183 /// in the traits class is based on functions that returns the new class
1.1184 @@ -1055,40 +1113,41 @@
1.1185 /// the new class with the modified type comes from
1.1186 /// the original class by using the ::
1.1187 /// operator. In the case of \ref DijkstraWizard only
1.1188 - /// a function have to be called and it will
1.1189 + /// a function have to be called, and it will
1.1190 /// return the needed class.
1.1191 ///
1.1192 - /// It does not have own \ref run method. When its \ref run method is called
1.1193 - /// it initiates a plain \ref Dijkstra class, and calls the \ref
1.1194 - /// Dijkstra::run method of it.
1.1195 + /// It does not have own \ref run() method. When its \ref run() method
1.1196 + /// is called, it initiates a plain \ref Dijkstra object, and calls the
1.1197 + /// \ref Dijkstra::run() method of it.
1.1198 template<class TR>
1.1199 class DijkstraWizard : public TR
1.1200 {
1.1201 typedef TR Base;
1.1202
1.1203 - ///The type of the underlying digraph.
1.1204 + ///The type of the digraph the algorithm runs on.
1.1205 typedef typename TR::Digraph Digraph;
1.1206 - //\e
1.1207 +
1.1208 typedef typename Digraph::Node Node;
1.1209 - //\e
1.1210 typedef typename Digraph::NodeIt NodeIt;
1.1211 - //\e
1.1212 typedef typename Digraph::Arc Arc;
1.1213 - //\e
1.1214 typedef typename Digraph::OutArcIt OutArcIt;
1.1215
1.1216 ///The type of the map that stores the arc lengths.
1.1217 typedef typename TR::LengthMap LengthMap;
1.1218 ///The type of the length of the arcs.
1.1219 typedef typename LengthMap::Value Value;
1.1220 - ///\brief The type of the map that stores the last
1.1221 + ///\brief The type of the map that stores the predecessor
1.1222 ///arcs of the shortest paths.
1.1223 typedef typename TR::PredMap PredMap;
1.1224 - ///The type of the map that stores the dists of the nodes.
1.1225 + ///The type of the map that stores the distances of the nodes.
1.1226 typedef typename TR::DistMap DistMap;
1.1227 + ///The type of the map that indicates which nodes are processed.
1.1228 + typedef typename TR::ProcessedMap ProcessedMap;
1.1229 ///The heap type used by the dijkstra algorithm.
1.1230 typedef typename TR::Heap Heap;
1.1231 +
1.1232 public:
1.1233 +
1.1234 /// Constructor.
1.1235 DijkstraWizard() : TR() {}
1.1236
1.1237 @@ -1104,10 +1163,10 @@
1.1238
1.1239 ~DijkstraWizard() {}
1.1240
1.1241 - ///Runs Dijkstra algorithm from a given node.
1.1242 + ///Runs Dijkstra algorithm from a source node.
1.1243
1.1244 - ///Runs Dijkstra algorithm from a given node.
1.1245 - ///The node can be given by the \ref source function.
1.1246 + ///Runs Dijkstra algorithm from a source node.
1.1247 + ///The node can be given with the \ref source() function.
1.1248 void run()
1.1249 {
1.1250 if(Base::_source==INVALID) throw UninitializedParameter();
1.1251 @@ -1129,19 +1188,27 @@
1.1252 run();
1.1253 }
1.1254
1.1255 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.1256 +
1.1257 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.1258 + /// \param s is the source node.
1.1259 + DijkstraWizard<TR> &source(Node s)
1.1260 + {
1.1261 + Base::_source=s;
1.1262 + return *this;
1.1263 + }
1.1264 +
1.1265 template<class T>
1.1266 struct DefPredMapBase : public Base {
1.1267 typedef T PredMap;
1.1268 static PredMap *createPredMap(const Digraph &) { return 0; };
1.1269 DefPredMapBase(const TR &b) : TR(b) {}
1.1270 };
1.1271 -
1.1272 ///\brief \ref named-templ-param "Named parameter"
1.1273 - ///function for setting PredMap type
1.1274 + ///for setting \ref PredMap object.
1.1275 ///
1.1276 - /// \ref named-templ-param "Named parameter"
1.1277 - ///function for setting PredMap type
1.1278 - ///
1.1279 + ///\ref named-templ-param "Named parameter"
1.1280 + ///for setting \ref PredMap object.
1.1281 template<class T>
1.1282 DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.1283 {
1.1284 @@ -1150,18 +1217,34 @@
1.1285 }
1.1286
1.1287 template<class T>
1.1288 + struct DefProcessedMapBase : public Base {
1.1289 + typedef T ProcessedMap;
1.1290 + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.1291 + DefProcessedMapBase(const TR &b) : TR(b) {}
1.1292 + };
1.1293 + ///\brief \ref named-templ-param "Named parameter"
1.1294 + ///for setting \ref ProcessedMap object.
1.1295 + ///
1.1296 + /// \ref named-templ-param "Named parameter"
1.1297 + ///for setting \ref ProcessedMap object.
1.1298 + template<class T>
1.1299 + DijkstraWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1300 + {
1.1301 + Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1302 + return DijkstraWizard<DefProcessedMapBase<T> >(*this);
1.1303 + }
1.1304 +
1.1305 + template<class T>
1.1306 struct DefDistMapBase : public Base {
1.1307 typedef T DistMap;
1.1308 static DistMap *createDistMap(const Digraph &) { return 0; };
1.1309 DefDistMapBase(const TR &b) : TR(b) {}
1.1310 };
1.1311 -
1.1312 ///\brief \ref named-templ-param "Named parameter"
1.1313 - ///function for setting DistMap type
1.1314 + ///for setting \ref DistMap object.
1.1315 ///
1.1316 - /// \ref named-templ-param "Named parameter"
1.1317 - ///function for setting DistMap type
1.1318 - ///
1.1319 + ///\ref named-templ-param "Named parameter"
1.1320 + ///for setting \ref DistMap object.
1.1321 template<class T>
1.1322 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.1323 {
1.1324 @@ -1169,16 +1252,6 @@
1.1325 return DijkstraWizard<DefDistMapBase<T> >(*this);
1.1326 }
1.1327
1.1328 - /// Sets the source node, from which the Dijkstra algorithm runs.
1.1329 -
1.1330 - /// Sets the source node, from which the Dijkstra algorithm runs.
1.1331 - /// \param s is the source node.
1.1332 - DijkstraWizard<TR> &source(Node s)
1.1333 - {
1.1334 - Base::_source=s;
1.1335 - return *this;
1.1336 - }
1.1337 -
1.1338 };
1.1339
1.1340 ///Function type interface for Dijkstra algorithm.