1.1 --- a/lemon/dijkstra.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/dijkstra.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -34,7 +34,7 @@
1.13 namespace lemon {
1.14
1.15 /// \brief Default OperationTraits for the Dijkstra algorithm class.
1.16 - ///
1.17 + ///
1.18 /// It defines all computational operations and constants which are
1.19 /// used in the Dijkstra algorithm.
1.20 template <typename Value>
1.21 @@ -54,7 +54,7 @@
1.22 };
1.23
1.24 /// \brief Widest path OperationTraits for the Dijkstra algorithm class.
1.25 - ///
1.26 + ///
1.27 /// It defines all computational operations and constants which are
1.28 /// used in the Dijkstra algorithm for widest path computation.
1.29 template <typename Value>
1.30 @@ -72,7 +72,7 @@
1.31 return left < right;
1.32 }
1.33 };
1.34 -
1.35 +
1.36 ///Default traits class of Dijkstra class.
1.37
1.38 ///Default traits class of Dijkstra class.
1.39 @@ -81,7 +81,7 @@
1.40 template<class GR, class LM>
1.41 struct DijkstraDefaultTraits
1.42 {
1.43 - ///The digraph type the algorithm runs on.
1.44 + ///The digraph type the algorithm runs on.
1.45 typedef GR Digraph;
1.46 ///The type of the map that stores the arc lengths.
1.47
1.48 @@ -103,14 +103,14 @@
1.49 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.50 ///Instantiates a HeapCrossRef.
1.51
1.52 - ///This function instantiates a \c HeapCrossRef.
1.53 - /// \param G is the digraph, to which we would like to define the
1.54 + ///This function instantiates a \c HeapCrossRef.
1.55 + /// \param G is the digraph, to which we would like to define the
1.56 /// HeapCrossRef.
1.57 - static HeapCrossRef *createHeapCrossRef(const GR &G)
1.58 + static HeapCrossRef *createHeapCrossRef(const GR &G)
1.59 {
1.60 return new HeapCrossRef(G);
1.61 }
1.62 -
1.63 +
1.64 ///The heap type used by Dijkstra algorithm.
1.65
1.66 ///The heap type used by Dijkstra algorithm.
1.67 @@ -119,31 +119,31 @@
1.68 ///\sa Dijkstra
1.69 typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.70
1.71 - static Heap *createHeap(HeapCrossRef& R)
1.72 + static Heap *createHeap(HeapCrossRef& R)
1.73 {
1.74 return new Heap(R);
1.75 }
1.76
1.77 ///\brief The type of the map that stores the last
1.78 ///arcs of the shortest paths.
1.79 - ///
1.80 + ///
1.81 ///The type of the map that stores the last
1.82 ///arcs of the shortest paths.
1.83 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.84 ///
1.85 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.86 ///Instantiates a PredMap.
1.87 -
1.88 - ///This function instantiates a \c PredMap.
1.89 +
1.90 + ///This function instantiates a \c PredMap.
1.91 ///\param G is the digraph, to which we would like to define the PredMap.
1.92 ///\todo The digraph alone may be insufficient for the initialization
1.93 - static PredMap *createPredMap(const GR &G)
1.94 + static PredMap *createPredMap(const GR &G)
1.95 {
1.96 return new PredMap(G);
1.97 }
1.98
1.99 ///The type of the map that stores whether a nodes is processed.
1.100 -
1.101 +
1.102 ///The type of the map that stores whether a nodes is processed.
1.103 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.104 ///By default it is a NullMap.
1.105 @@ -152,8 +152,8 @@
1.106 ///\todo named parameter to set this type, function to read and write.
1.107 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.108 ///Instantiates a ProcessedMap.
1.109 -
1.110 - ///This function instantiates a \c ProcessedMap.
1.111 +
1.112 + ///This function instantiates a \c ProcessedMap.
1.113 ///\param g is the digraph, to which
1.114 ///we would like to define the \c ProcessedMap
1.115 #ifdef DOXYGEN
1.116 @@ -165,23 +165,23 @@
1.117 return new ProcessedMap();
1.118 }
1.119 ///The type of the map that stores the dists of the nodes.
1.120 -
1.121 +
1.122 ///The type of the map that stores the dists of the nodes.
1.123 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.124 ///
1.125 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.126 ///Instantiates a DistMap.
1.127 -
1.128 - ///This function instantiates a \ref DistMap.
1.129 +
1.130 + ///This function instantiates a \ref DistMap.
1.131 ///\param G is the digraph, to which we would like to define the \ref DistMap
1.132 static DistMap *createDistMap(const GR &G)
1.133 {
1.134 return new DistMap(G);
1.135 }
1.136 };
1.137 -
1.138 +
1.139 ///%Dijkstra algorithm class.
1.140 -
1.141 +
1.142 /// \ingroup shortest_path
1.143 ///This class provides an efficient implementation of %Dijkstra algorithm.
1.144 ///The arc lengths are passed to the algorithm using a
1.145 @@ -202,7 +202,7 @@
1.146 ///it is necessary. The default map type is \ref
1.147 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". The value
1.148 ///of LM is not used directly by Dijkstra, it is only passed to \ref
1.149 - ///DijkstraDefaultTraits.
1.150 + ///DijkstraDefaultTraits.
1.151 ///\tparam TR Traits class to set
1.152 ///various data types used by the algorithm. The default traits
1.153 ///class is \ref DijkstraDefaultTraits
1.154 @@ -214,8 +214,8 @@
1.155 template <typename GR, typename LM, typename TR>
1.156 #else
1.157 template <typename GR=ListDigraph,
1.158 - typename LM=typename GR::template ArcMap<int>,
1.159 - typename TR=DijkstraDefaultTraits<GR,LM> >
1.160 + typename LM=typename GR::template ArcMap<int>,
1.161 + typename TR=DijkstraDefaultTraits<GR,LM> >
1.162 #endif
1.163 class Dijkstra {
1.164 public:
1.165 @@ -228,7 +228,7 @@
1.166 class UninitializedParameter : public lemon::UninitializedParameter {
1.167 public:
1.168 virtual const char* what() const throw() {
1.169 - return "lemon::Dijkstra::UninitializedParameter";
1.170 + return "lemon::Dijkstra::UninitializedParameter";
1.171 }
1.172 };
1.173
1.174 @@ -243,7 +243,7 @@
1.175 typedef typename Digraph::Arc Arc;
1.176 ///\e
1.177 typedef typename Digraph::OutArcIt OutArcIt;
1.178 -
1.179 +
1.180 ///The type of the length of the arcs.
1.181 typedef typename TR::LengthMap::Value Value;
1.182 ///The type of the map that stores the arc lengths.
1.183 @@ -288,36 +288,36 @@
1.184 bool local_heap;
1.185
1.186 ///Creates the maps if necessary.
1.187 -
1.188 +
1.189 ///\todo Better memory allocation (instead of new).
1.190 - void create_maps()
1.191 + void create_maps()
1.192 {
1.193 if(!_pred) {
1.194 - local_pred = true;
1.195 - _pred = Traits::createPredMap(*G);
1.196 + local_pred = true;
1.197 + _pred = Traits::createPredMap(*G);
1.198 }
1.199 if(!_dist) {
1.200 - local_dist = true;
1.201 - _dist = Traits::createDistMap(*G);
1.202 + local_dist = true;
1.203 + _dist = Traits::createDistMap(*G);
1.204 }
1.205 if(!_processed) {
1.206 - local_processed = true;
1.207 - _processed = Traits::createProcessedMap(*G);
1.208 + local_processed = true;
1.209 + _processed = Traits::createProcessedMap(*G);
1.210 }
1.211 if (!_heap_cross_ref) {
1.212 - local_heap_cross_ref = true;
1.213 - _heap_cross_ref = Traits::createHeapCrossRef(*G);
1.214 + local_heap_cross_ref = true;
1.215 + _heap_cross_ref = Traits::createHeapCrossRef(*G);
1.216 }
1.217 if (!_heap) {
1.218 - local_heap = true;
1.219 - _heap = Traits::createHeap(*_heap_cross_ref);
1.220 + local_heap = true;
1.221 + _heap = Traits::createHeap(*_heap_cross_ref);
1.222 }
1.223 }
1.224 -
1.225 +
1.226 public :
1.227
1.228 typedef Dijkstra Create;
1.229 -
1.230 +
1.231 ///\name Named template parameters
1.232
1.233 ///@{
1.234 @@ -327,7 +327,7 @@
1.235 typedef T PredMap;
1.236 static PredMap *createPredMap(const Digraph &)
1.237 {
1.238 - throw UninitializedParameter();
1.239 + throw UninitializedParameter();
1.240 }
1.241 };
1.242 ///\ref named-templ-param "Named parameter" for setting PredMap type
1.243 @@ -335,17 +335,17 @@
1.244 ///\ref named-templ-param "Named parameter" for setting PredMap type
1.245 ///
1.246 template <class T>
1.247 - struct DefPredMap
1.248 - : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
1.249 - typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
1.250 + struct DefPredMap
1.251 + : public Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > {
1.252 + typedef Dijkstra< Digraph, LengthMap, DefPredMapTraits<T> > Create;
1.253 };
1.254 -
1.255 +
1.256 template <class T>
1.257 struct DefDistMapTraits : public Traits {
1.258 typedef T DistMap;
1.259 static DistMap *createDistMap(const Digraph &)
1.260 {
1.261 - throw UninitializedParameter();
1.262 + throw UninitializedParameter();
1.263 }
1.264 };
1.265 ///\ref named-templ-param "Named parameter" for setting DistMap type
1.266 @@ -353,17 +353,17 @@
1.267 ///\ref named-templ-param "Named parameter" for setting DistMap type
1.268 ///
1.269 template <class T>
1.270 - struct DefDistMap
1.271 - : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
1.272 + struct DefDistMap
1.273 + : public Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > {
1.274 typedef Dijkstra< Digraph, LengthMap, DefDistMapTraits<T> > Create;
1.275 };
1.276 -
1.277 +
1.278 template <class T>
1.279 struct DefProcessedMapTraits : public Traits {
1.280 typedef T ProcessedMap;
1.281 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.282 + static ProcessedMap *createProcessedMap(const Digraph &G)
1.283 {
1.284 - throw UninitializedParameter();
1.285 + throw UninitializedParameter();
1.286 }
1.287 };
1.288 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.289 @@ -371,16 +371,16 @@
1.290 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.291 ///
1.292 template <class T>
1.293 - struct DefProcessedMap
1.294 - : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
1.295 - typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
1.296 + struct DefProcessedMap
1.297 + : public Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > {
1.298 + typedef Dijkstra< Digraph, LengthMap, DefProcessedMapTraits<T> > Create;
1.299 };
1.300 -
1.301 +
1.302 struct DefDigraphProcessedMapTraits : public Traits {
1.303 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.304 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.305 + static ProcessedMap *createProcessedMap(const Digraph &G)
1.306 {
1.307 - return new ProcessedMap(G);
1.308 + return new ProcessedMap(G);
1.309 }
1.310 };
1.311 ///\brief \ref named-templ-param "Named parameter"
1.312 @@ -390,7 +390,7 @@
1.313 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.314 ///If you don't set it explicitely, it will be automatically allocated.
1.315 template <class T>
1.316 - struct DefProcessedMapToBeDefaultMap
1.317 + struct DefProcessedMapToBeDefaultMap
1.318 : public Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> {
1.319 typedef Dijkstra< Digraph, LengthMap, DefDigraphProcessedMapTraits> Create;
1.320 };
1.321 @@ -400,23 +400,23 @@
1.322 typedef CR HeapCrossRef;
1.323 typedef H Heap;
1.324 static HeapCrossRef *createHeapCrossRef(const Digraph &) {
1.325 - throw UninitializedParameter();
1.326 + throw UninitializedParameter();
1.327 }
1.328 - static Heap *createHeap(HeapCrossRef &)
1.329 + static Heap *createHeap(HeapCrossRef &)
1.330 {
1.331 - throw UninitializedParameter();
1.332 + throw UninitializedParameter();
1.333 }
1.334 };
1.335 ///\brief \ref named-templ-param "Named parameter" for setting
1.336 ///heap and cross reference type
1.337 ///
1.338 - ///\ref named-templ-param "Named parameter" for setting heap and cross
1.339 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.340 ///reference type
1.341 ///
1.342 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.343 struct DefHeap
1.344 - : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
1.345 - typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
1.346 + : public Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > {
1.347 + typedef Dijkstra< Digraph, LengthMap, DefHeapTraits<H, CR> > Create;
1.348 };
1.349
1.350 template <class H, class CR>
1.351 @@ -424,24 +424,24 @@
1.352 typedef CR HeapCrossRef;
1.353 typedef H Heap;
1.354 static HeapCrossRef *createHeapCrossRef(const Digraph &G) {
1.355 - return new HeapCrossRef(G);
1.356 + return new HeapCrossRef(G);
1.357 }
1.358 - static Heap *createHeap(HeapCrossRef &R)
1.359 + static Heap *createHeap(HeapCrossRef &R)
1.360 {
1.361 - return new Heap(R);
1.362 + return new Heap(R);
1.363 }
1.364 };
1.365 ///\brief \ref named-templ-param "Named parameter" for setting
1.366 ///heap and cross reference type with automatic allocation
1.367 ///
1.368 - ///\ref named-templ-param "Named parameter" for setting heap and cross
1.369 - ///reference type. It can allocate the heap and the cross reference
1.370 - ///object if the cross reference's constructor waits for the digraph as
1.371 + ///\ref named-templ-param "Named parameter" for setting heap and cross
1.372 + ///reference type. It can allocate the heap and the cross reference
1.373 + ///object if the cross reference's constructor waits for the digraph as
1.374 ///parameter and the heap's constructor waits for the cross reference.
1.375 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.376 struct DefStandardHeap
1.377 - : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
1.378 - typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
1.379 + : public Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> > {
1.380 + typedef Dijkstra< Digraph, LengthMap, DefStandardHeapTraits<H, CR> >
1.381 Create;
1.382 };
1.383
1.384 @@ -449,8 +449,8 @@
1.385 struct DefOperationTraitsTraits : public Traits {
1.386 typedef T OperationTraits;
1.387 };
1.388 -
1.389 - /// \brief \ref named-templ-param "Named parameter" for setting
1.390 +
1.391 + /// \brief \ref named-templ-param "Named parameter" for setting
1.392 /// OperationTraits type
1.393 ///
1.394 /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.395 @@ -461,7 +461,7 @@
1.396 typedef Dijkstra<Digraph, LengthMap, DefOperationTraitsTraits<T> >
1.397 Create;
1.398 };
1.399 -
1.400 +
1.401 ///@}
1.402
1.403
1.404 @@ -469,10 +469,10 @@
1.405
1.406 Dijkstra() {}
1.407
1.408 - public:
1.409 -
1.410 + public:
1.411 +
1.412 ///Constructor.
1.413 -
1.414 +
1.415 ///\param _G the digraph the algorithm will run on.
1.416 ///\param _length the length map used by the algorithm.
1.417 Dijkstra(const Digraph& _G, const LengthMap& _length) :
1.418 @@ -483,9 +483,9 @@
1.419 _heap_cross_ref(NULL), local_heap_cross_ref(false),
1.420 _heap(NULL), local_heap(false)
1.421 { }
1.422 -
1.423 +
1.424 ///Destructor.
1.425 - ~Dijkstra()
1.426 + ~Dijkstra()
1.427 {
1.428 if(local_pred) delete _pred;
1.429 if(local_dist) delete _dist;
1.430 @@ -498,7 +498,7 @@
1.431
1.432 ///Sets the length map.
1.433 ///\return <tt> (*this) </tt>
1.434 - Dijkstra &lengthMap(const LengthMap &m)
1.435 + Dijkstra &lengthMap(const LengthMap &m)
1.436 {
1.437 length = &m;
1.438 return *this;
1.439 @@ -511,11 +511,11 @@
1.440 ///it will allocate one. The destuctor deallocates this
1.441 ///automatically allocated map, of course.
1.442 ///\return <tt> (*this) </tt>
1.443 - Dijkstra &predMap(PredMap &m)
1.444 + Dijkstra &predMap(PredMap &m)
1.445 {
1.446 if(local_pred) {
1.447 - delete _pred;
1.448 - local_pred=false;
1.449 + delete _pred;
1.450 + local_pred=false;
1.451 }
1.452 _pred = &m;
1.453 return *this;
1.454 @@ -528,11 +528,11 @@
1.455 ///it will allocate one. The destuctor deallocates this
1.456 ///automatically allocated map, of course.
1.457 ///\return <tt> (*this) </tt>
1.458 - Dijkstra &distMap(DistMap &m)
1.459 + Dijkstra &distMap(DistMap &m)
1.460 {
1.461 if(local_dist) {
1.462 - delete _dist;
1.463 - local_dist=false;
1.464 + delete _dist;
1.465 + local_dist=false;
1.466 }
1.467 _dist = &m;
1.468 return *this;
1.469 @@ -548,13 +548,13 @@
1.470 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
1.471 {
1.472 if(local_heap_cross_ref) {
1.473 - delete _heap_cross_ref;
1.474 - local_heap_cross_ref=false;
1.475 + delete _heap_cross_ref;
1.476 + local_heap_cross_ref=false;
1.477 }
1.478 _heap_cross_ref = &cr;
1.479 if(local_heap) {
1.480 - delete _heap;
1.481 - local_heap=false;
1.482 + delete _heap;
1.483 + local_heap=false;
1.484 }
1.485 _heap = &hp;
1.486 return *this;
1.487 @@ -592,12 +592,12 @@
1.488 create_maps();
1.489 _heap->clear();
1.490 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.491 - _pred->set(u,INVALID);
1.492 - _processed->set(u,false);
1.493 - _heap_cross_ref->set(u,Heap::PRE_HEAP);
1.494 + _pred->set(u,INVALID);
1.495 + _processed->set(u,false);
1.496 + _heap_cross_ref->set(u,Heap::PRE_HEAP);
1.497 }
1.498 }
1.499 -
1.500 +
1.501 ///Adds a new source node.
1.502
1.503 ///Adds a new source node to the priority heap.
1.504 @@ -610,13 +610,13 @@
1.505 void addSource(Node s,Value dst=OperationTraits::zero())
1.506 {
1.507 if(_heap->state(s) != Heap::IN_HEAP) {
1.508 - _heap->push(s,dst);
1.509 + _heap->push(s,dst);
1.510 } else if(OperationTraits::less((*_heap)[s], dst)) {
1.511 - _heap->set(s,dst);
1.512 - _pred->set(s,INVALID);
1.513 + _heap->set(s,dst);
1.514 + _pred->set(s,INVALID);
1.515 }
1.516 }
1.517 -
1.518 +
1.519 ///Processes the next node in the priority heap
1.520
1.521 ///Processes the next node in the priority heap.
1.522 @@ -626,45 +626,45 @@
1.523 ///\warning The priority heap must not be empty!
1.524 Node processNextNode()
1.525 {
1.526 - Node v=_heap->top();
1.527 + Node v=_heap->top();
1.528 Value oldvalue=_heap->prio();
1.529 _heap->pop();
1.530 finalizeNodeData(v,oldvalue);
1.531 -
1.532 +
1.533 for(OutArcIt e(*G,v); e!=INVALID; ++e) {
1.534 - Node w=G->target(e);
1.535 - switch(_heap->state(w)) {
1.536 - case Heap::PRE_HEAP:
1.537 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.538 - _pred->set(w,e);
1.539 - break;
1.540 - case Heap::IN_HEAP:
1.541 - {
1.542 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.543 - if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.544 - _heap->decrease(w, newvalue);
1.545 - _pred->set(w,e);
1.546 - }
1.547 - }
1.548 - break;
1.549 - case Heap::POST_HEAP:
1.550 - break;
1.551 - }
1.552 + Node w=G->target(e);
1.553 + switch(_heap->state(w)) {
1.554 + case Heap::PRE_HEAP:
1.555 + _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.556 + _pred->set(w,e);
1.557 + break;
1.558 + case Heap::IN_HEAP:
1.559 + {
1.560 + Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.561 + if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.562 + _heap->decrease(w, newvalue);
1.563 + _pred->set(w,e);
1.564 + }
1.565 + }
1.566 + break;
1.567 + case Heap::POST_HEAP:
1.568 + break;
1.569 + }
1.570 }
1.571 return v;
1.572 }
1.573
1.574 ///Next node to be processed.
1.575 -
1.576 +
1.577 ///Next node to be processed.
1.578 ///
1.579 ///\return The next node to be processed or INVALID if the priority heap
1.580 /// is empty.
1.581 Node nextNode()
1.582 - {
1.583 + {
1.584 return !_heap->empty()?_heap->top():INVALID;
1.585 }
1.586 -
1.587 +
1.588 ///\brief Returns \c false if there are nodes
1.589 ///to be processed in the priority heap
1.590 ///
1.591 @@ -676,7 +676,7 @@
1.592 ///Returns the number of the nodes to be processed in the priority heap
1.593 ///
1.594 int queueSize() { return _heap->size(); }
1.595 -
1.596 +
1.597 ///Executes the algorithm.
1.598
1.599 ///Executes the algorithm.
1.600 @@ -695,7 +695,7 @@
1.601 {
1.602 while ( !_heap->empty() ) processNextNode();
1.603 }
1.604 -
1.605 +
1.606 ///Executes the algorithm until \c dest is reached.
1.607
1.608 ///Executes the algorithm until \c dest is reached.
1.609 @@ -715,7 +715,7 @@
1.610 while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
1.611 if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
1.612 }
1.613 -
1.614 +
1.615 ///Executes the algorithm until a condition is met.
1.616
1.617 ///Executes the algorithm until a condition is met.
1.618 @@ -736,9 +736,9 @@
1.619 finalizeNodeData(_heap->top(),_heap->prio());
1.620 return _heap->top();
1.621 }
1.622 -
1.623 +
1.624 ///Runs %Dijkstra algorithm from node \c s.
1.625 -
1.626 +
1.627 ///This method runs the %Dijkstra algorithm from a root node \c s
1.628 ///in order to
1.629 ///compute the
1.630 @@ -757,9 +757,9 @@
1.631 addSource(s);
1.632 start();
1.633 }
1.634 -
1.635 +
1.636 ///Finds the shortest path between \c s and \c t.
1.637 -
1.638 +
1.639 ///Finds the shortest path between \c s and \c t.
1.640 ///
1.641 ///\return The length of the shortest s---t path if there exists one,
1.642 @@ -777,7 +777,7 @@
1.643 start(t);
1.644 return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
1.645 }
1.646 -
1.647 +
1.648 ///@}
1.649
1.650 ///\name Query Functions
1.651 @@ -785,14 +785,14 @@
1.652 ///functions.\n
1.653 ///Before the use of these functions,
1.654 ///either run() or start() must be called.
1.655 -
1.656 +
1.657 ///@{
1.658
1.659 ///Gives back the shortest path.
1.660 -
1.661 +
1.662 ///Gives back the shortest path.
1.663 ///\pre The \c t should be reachable from the source.
1.664 - Path path(Node t)
1.665 + Path path(Node t)
1.666 {
1.667 return Path(*G, *_pred, t);
1.668 }
1.669 @@ -832,21 +832,21 @@
1.670 ///tree used in \ref predArc(). \pre \ref run() must be called before
1.671 ///using this function.
1.672 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.673 - G->source((*_pred)[v]); }
1.674 -
1.675 + G->source((*_pred)[v]); }
1.676 +
1.677 ///Returns a reference to the NodeMap of distances.
1.678
1.679 ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.680 ///be called before using this function.
1.681 const DistMap &distMap() const { return *_dist;}
1.682 -
1.683 +
1.684 ///Returns a reference to the shortest path tree map.
1.685
1.686 ///Returns a reference to the NodeMap of the arcs of the
1.687 ///shortest path tree.
1.688 ///\pre \ref run() must be called before using this function.
1.689 const PredMap &predMap() const { return *_pred;}
1.690 -
1.691 +
1.692 ///Checks if a node is reachable from the root.
1.693
1.694 ///Returns \c true if \c v is reachable from the root.
1.695 @@ -862,14 +862,14 @@
1.696 ///\pre \ref run() must be called before using this function.
1.697 ///
1.698 bool processed(Node v) { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; }
1.699 -
1.700 +
1.701 ///@}
1.702 };
1.703
1.704
1.705
1.706
1.707 -
1.708 +
1.709 ///Default traits class of Dijkstra function.
1.710
1.711 ///Default traits class of Dijkstra function.
1.712 @@ -878,7 +878,7 @@
1.713 template<class GR, class LM>
1.714 struct DijkstraWizardDefaultTraits
1.715 {
1.716 - ///The digraph type the algorithm runs on.
1.717 + ///The digraph type the algorithm runs on.
1.718 typedef GR Digraph;
1.719 ///The type of the map that stores the arc lengths.
1.720
1.721 @@ -901,15 +901,15 @@
1.722 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.723 ///Instantiates a HeapCrossRef.
1.724
1.725 - ///This function instantiates a \ref HeapCrossRef.
1.726 - /// \param G is the digraph, to which we would like to define the
1.727 + ///This function instantiates a \ref HeapCrossRef.
1.728 + /// \param G is the digraph, to which we would like to define the
1.729 /// HeapCrossRef.
1.730 /// \todo The digraph alone may be insufficient for the initialization
1.731 - static HeapCrossRef *createHeapCrossRef(const GR &G)
1.732 + static HeapCrossRef *createHeapCrossRef(const GR &G)
1.733 {
1.734 return new HeapCrossRef(G);
1.735 }
1.736 -
1.737 +
1.738 ///The heap type used by Dijkstra algorithm.
1.739
1.740 ///The heap type used by Dijkstra algorithm.
1.741 @@ -917,36 +917,36 @@
1.742 ///\sa BinHeap
1.743 ///\sa Dijkstra
1.744 typedef BinHeap<typename LM::Value, typename GR::template NodeMap<int>,
1.745 - std::less<Value> > Heap;
1.746 + std::less<Value> > Heap;
1.747
1.748 - static Heap *createHeap(HeapCrossRef& R)
1.749 + static Heap *createHeap(HeapCrossRef& R)
1.750 {
1.751 return new Heap(R);
1.752 }
1.753
1.754 ///\brief The type of the map that stores the last
1.755 ///arcs of the shortest paths.
1.756 - ///
1.757 + ///
1.758 ///The type of the map that stores the last
1.759 ///arcs of the shortest paths.
1.760 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.761 ///
1.762 typedef NullMap <typename GR::Node,typename GR::Arc> PredMap;
1.763 ///Instantiates a PredMap.
1.764 -
1.765 - ///This function instantiates a \ref PredMap.
1.766 +
1.767 + ///This function instantiates a \ref PredMap.
1.768 ///\param g is the digraph, to which we would like to define the PredMap.
1.769 ///\todo The digraph alone may be insufficient for the initialization
1.770 #ifdef DOXYGEN
1.771 - static PredMap *createPredMap(const GR &g)
1.772 + static PredMap *createPredMap(const GR &g)
1.773 #else
1.774 - static PredMap *createPredMap(const GR &)
1.775 + static PredMap *createPredMap(const GR &)
1.776 #endif
1.777 {
1.778 return new PredMap();
1.779 }
1.780 ///The type of the map that stores whether a nodes is processed.
1.781 -
1.782 +
1.783 ///The type of the map that stores whether a nodes is processed.
1.784 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.785 ///By default it is a NullMap.
1.786 @@ -955,8 +955,8 @@
1.787 ///\todo named parameter to set this type, function to read and write.
1.788 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.789 ///Instantiates a ProcessedMap.
1.790 -
1.791 - ///This function instantiates a \ref ProcessedMap.
1.792 +
1.793 + ///This function instantiates a \ref ProcessedMap.
1.794 ///\param g is the digraph, to which
1.795 ///we would like to define the \ref ProcessedMap
1.796 #ifdef DOXYGEN
1.797 @@ -968,14 +968,14 @@
1.798 return new ProcessedMap();
1.799 }
1.800 ///The type of the map that stores the dists of the nodes.
1.801 -
1.802 +
1.803 ///The type of the map that stores the dists of the nodes.
1.804 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.805 ///
1.806 typedef NullMap<typename Digraph::Node,typename LM::Value> DistMap;
1.807 ///Instantiates a DistMap.
1.808 -
1.809 - ///This function instantiates a \ref DistMap.
1.810 +
1.811 + ///This function instantiates a \ref DistMap.
1.812 ///\param g is the digraph, to which we would like to define the \ref DistMap
1.813 #ifdef DOXYGEN
1.814 static DistMap *createDistMap(const GR &g)
1.815 @@ -986,7 +986,7 @@
1.816 return new DistMap();
1.817 }
1.818 };
1.819 -
1.820 +
1.821 /// Default traits used by \ref DijkstraWizard
1.822
1.823 /// To make it easier to use Dijkstra algorithm
1.824 @@ -1018,14 +1018,14 @@
1.825
1.826 public:
1.827 /// Constructor.
1.828 -
1.829 +
1.830 /// This constructor does not require parameters, therefore it initiates
1.831 /// all of the attributes to default values (0, INVALID).
1.832 DijkstraWizardBase() : _g(0), _length(0), _pred(0),
1.833 - _dist(0), _source(INVALID) {}
1.834 + _dist(0), _source(INVALID) {}
1.835
1.836 /// Constructor.
1.837 -
1.838 +
1.839 /// This constructor requires some parameters,
1.840 /// listed in the parameters list.
1.841 /// Others are initiated to 0.
1.842 @@ -1033,12 +1033,12 @@
1.843 /// \param l is the initial value of \ref _length
1.844 /// \param s is the initial value of \ref _source
1.845 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.846 - _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.847 - _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.848 + _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.849 + _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.850 _pred(0), _dist(0), _source(s) {}
1.851
1.852 };
1.853 -
1.854 +
1.855 /// A class to make the usage of Dijkstra algorithm easier
1.856
1.857 /// This class is created to make it easier to use Dijkstra algorithm.
1.858 @@ -1056,7 +1056,7 @@
1.859 /// return the needed class.
1.860 ///
1.861 /// It does not have own \ref run method. When its \ref run method is called
1.862 - /// it initiates a plain \ref Dijkstra class, and calls the \ref
1.863 + /// it initiates a plain \ref Dijkstra class, and calls the \ref
1.864 /// Dijkstra::run method of it.
1.865 template<class TR>
1.866 class DijkstraWizard : public TR
1.867 @@ -1073,7 +1073,7 @@
1.868 typedef typename Digraph::Arc Arc;
1.869 //\e
1.870 typedef typename Digraph::OutArcIt OutArcIt;
1.871 -
1.872 +
1.873 ///The type of the map that stores the arc lengths.
1.874 typedef typename TR::LengthMap LengthMap;
1.875 ///The type of the length of the arcs.
1.876 @@ -1102,14 +1102,14 @@
1.877 ~DijkstraWizard() {}
1.878
1.879 ///Runs Dijkstra algorithm from a given node.
1.880 -
1.881 +
1.882 ///Runs Dijkstra algorithm from a given node.
1.883 ///The node can be given by the \ref source function.
1.884 void run()
1.885 {
1.886 if(Base::_source==INVALID) throw UninitializedParameter();
1.887 - Dijkstra<Digraph,LengthMap,TR>
1.888 - dij(*reinterpret_cast<const Digraph*>(Base::_g),
1.889 + Dijkstra<Digraph,LengthMap,TR>
1.890 + dij(*reinterpret_cast<const Digraph*>(Base::_g),
1.891 *reinterpret_cast<const LengthMap*>(Base::_length));
1.892 if(Base::_pred) dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.893 if(Base::_dist) dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.894 @@ -1132,7 +1132,7 @@
1.895 static PredMap *createPredMap(const Digraph &) { return 0; };
1.896 DefPredMapBase(const TR &b) : TR(b) {}
1.897 };
1.898 -
1.899 +
1.900 ///\brief \ref named-templ-param "Named parameter"
1.901 ///function for setting PredMap type
1.902 ///
1.903 @@ -1140,19 +1140,19 @@
1.904 ///function for setting PredMap type
1.905 ///
1.906 template<class T>
1.907 - DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.908 + DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.909 {
1.910 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.911 return DijkstraWizard<DefPredMapBase<T> >(*this);
1.912 }
1.913 -
1.914 +
1.915 template<class T>
1.916 struct DefDistMapBase : public Base {
1.917 typedef T DistMap;
1.918 static DistMap *createDistMap(const Digraph &) { return 0; };
1.919 DefDistMapBase(const TR &b) : TR(b) {}
1.920 };
1.921 -
1.922 +
1.923 ///\brief \ref named-templ-param "Named parameter"
1.924 ///function for setting DistMap type
1.925 ///
1.926 @@ -1160,24 +1160,24 @@
1.927 ///function for setting DistMap type
1.928 ///
1.929 template<class T>
1.930 - DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.931 + DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.932 {
1.933 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.934 return DijkstraWizard<DefDistMapBase<T> >(*this);
1.935 }
1.936 -
1.937 +
1.938 /// Sets the source node, from which the Dijkstra algorithm runs.
1.939
1.940 /// Sets the source node, from which the Dijkstra algorithm runs.
1.941 /// \param s is the source node.
1.942 - DijkstraWizard<TR> &source(Node s)
1.943 + DijkstraWizard<TR> &source(Node s)
1.944 {
1.945 Base::_source=s;
1.946 return *this;
1.947 }
1.948 -
1.949 +
1.950 };
1.951 -
1.952 +
1.953 ///Function type interface for Dijkstra algorithm.
1.954
1.955 /// \ingroup shortest_path