changeset 435 | 30d22b636e57 |
parent 397 | 62f9787c516c |
parent 405 | 6b9057cdcd8b |
child 440 | 88ed40ad0d4f |
20:90e56769e5c9 | 22:0a499103dbaa |
---|---|
177 ///There is also a \ref dijkstra() "function-type interface" for the |
177 ///There is also a \ref dijkstra() "function-type interface" for the |
178 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
178 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
179 ///it can be used easier. |
179 ///it can be used easier. |
180 /// |
180 /// |
181 ///\tparam GR The type of the digraph the algorithm runs on. |
181 ///\tparam GR The type of the digraph the algorithm runs on. |
182 ///The default value is \ref ListDigraph. |
182 ///The default type is \ref ListDigraph. |
183 ///The value of GR is not used directly by \ref Dijkstra, it is only |
183 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies |
184 ///passed to \ref DijkstraDefaultTraits. |
184 ///the lengths of the arcs. |
185 ///\tparam LM A readable arc map that determines the lengths of the |
185 ///It is read once for each arc, so the map may involve in |
186 ///arcs. It is read once for each arc, so the map may involve in |
|
187 ///relatively time consuming process to compute the arc lengths if |
186 ///relatively time consuming process to compute the arc lengths if |
188 ///it is necessary. The default map type is \ref |
187 ///it is necessary. The default map type is \ref |
189 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
188 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". |
190 ///The value of LM is not used directly by \ref Dijkstra, it is only |
|
191 ///passed to \ref DijkstraDefaultTraits. |
|
192 ///\tparam TR Traits class to set various data types used by the algorithm. |
|
193 ///The default traits class is \ref DijkstraDefaultTraits |
|
194 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits |
|
195 ///for the documentation of a Dijkstra traits class. |
|
196 #ifdef DOXYGEN |
189 #ifdef DOXYGEN |
197 template <typename GR, typename LM, typename TR> |
190 template <typename GR, typename LM, typename TR> |
198 #else |
191 #else |
199 template <typename GR=ListDigraph, |
192 template <typename GR=ListDigraph, |
200 typename LM=typename GR::template ArcMap<int>, |
193 typename LM=typename GR::template ArcMap<int>, |
224 ///The heap type used by the algorithm. |
217 ///The heap type used by the algorithm. |
225 typedef typename TR::Heap Heap; |
218 typedef typename TR::Heap Heap; |
226 ///The operation traits class. |
219 ///The operation traits class. |
227 typedef typename TR::OperationTraits OperationTraits; |
220 typedef typename TR::OperationTraits OperationTraits; |
228 |
221 |
229 ///The traits class. |
222 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. |
230 typedef TR Traits; |
223 typedef TR Traits; |
231 |
224 |
232 private: |
225 private: |
233 |
226 |
234 typedef typename Digraph::Node Node; |
227 typedef typename Digraph::Node Node; |
306 ///\brief \ref named-templ-param "Named parameter" for setting |
299 ///\brief \ref named-templ-param "Named parameter" for setting |
307 ///PredMap type. |
300 ///PredMap type. |
308 /// |
301 /// |
309 ///\ref named-templ-param "Named parameter" for setting |
302 ///\ref named-templ-param "Named parameter" for setting |
310 ///PredMap type. |
303 ///PredMap type. |
304 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
311 template <class T> |
305 template <class T> |
312 struct SetPredMap |
306 struct SetPredMap |
313 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > { |
307 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > { |
314 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create; |
308 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create; |
315 }; |
309 }; |
326 ///\brief \ref named-templ-param "Named parameter" for setting |
320 ///\brief \ref named-templ-param "Named parameter" for setting |
327 ///DistMap type. |
321 ///DistMap type. |
328 /// |
322 /// |
329 ///\ref named-templ-param "Named parameter" for setting |
323 ///\ref named-templ-param "Named parameter" for setting |
330 ///DistMap type. |
324 ///DistMap type. |
325 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
331 template <class T> |
326 template <class T> |
332 struct SetDistMap |
327 struct SetDistMap |
333 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > { |
328 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > { |
334 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create; |
329 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create; |
335 }; |
330 }; |
346 ///\brief \ref named-templ-param "Named parameter" for setting |
341 ///\brief \ref named-templ-param "Named parameter" for setting |
347 ///ProcessedMap type. |
342 ///ProcessedMap type. |
348 /// |
343 /// |
349 ///\ref named-templ-param "Named parameter" for setting |
344 ///\ref named-templ-param "Named parameter" for setting |
350 ///ProcessedMap type. |
345 ///ProcessedMap type. |
346 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
351 template <class T> |
347 template <class T> |
352 struct SetProcessedMap |
348 struct SetProcessedMap |
353 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
349 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
354 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
350 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
355 }; |
351 }; |
386 LEMON_ASSERT(false, "Heap is not initialized"); |
382 LEMON_ASSERT(false, "Heap is not initialized"); |
387 return 0; // ignore warnings |
383 return 0; // ignore warnings |
388 } |
384 } |
389 }; |
385 }; |
390 ///\brief \ref named-templ-param "Named parameter" for setting |
386 ///\brief \ref named-templ-param "Named parameter" for setting |
391 ///heap and cross reference type |
387 ///heap and cross reference types |
392 /// |
388 /// |
393 ///\ref named-templ-param "Named parameter" for setting heap and cross |
389 ///\ref named-templ-param "Named parameter" for setting heap and cross |
394 ///reference type. |
390 ///reference types. If this named parameter is used, then external |
391 ///heap and cross reference objects must be passed to the algorithm |
|
392 ///using the \ref heap() function before calling \ref run(Node) "run()" |
|
393 ///or \ref init(). |
|
394 ///\sa SetStandardHeap |
|
395 template <class H, class CR = typename Digraph::template NodeMap<int> > |
395 template <class H, class CR = typename Digraph::template NodeMap<int> > |
396 struct SetHeap |
396 struct SetHeap |
397 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > { |
397 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > { |
398 typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create; |
398 typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create; |
399 }; |
399 }; |
409 { |
409 { |
410 return new Heap(R); |
410 return new Heap(R); |
411 } |
411 } |
412 }; |
412 }; |
413 ///\brief \ref named-templ-param "Named parameter" for setting |
413 ///\brief \ref named-templ-param "Named parameter" for setting |
414 ///heap and cross reference type with automatic allocation |
414 ///heap and cross reference types with automatic allocation |
415 /// |
415 /// |
416 ///\ref named-templ-param "Named parameter" for setting heap and cross |
416 ///\ref named-templ-param "Named parameter" for setting heap and cross |
417 ///reference type. It can allocate the heap and the cross reference |
417 ///reference types with automatic allocation. |
418 ///object if the cross reference's constructor waits for the digraph as |
418 ///They should have standard constructor interfaces to be able to |
419 ///parameter and the heap's constructor waits for the cross reference. |
419 ///automatically created by the algorithm (i.e. the digraph should be |
420 ///passed to the constructor of the cross reference and the cross |
|
421 ///reference should be passed to the constructor of the heap). |
|
422 ///However external heap and cross reference objects could also be |
|
423 ///passed to the algorithm using the \ref heap() function before |
|
424 ///calling \ref run(Node) "run()" or \ref init(). |
|
425 ///\sa SetHeap |
|
420 template <class H, class CR = typename Digraph::template NodeMap<int> > |
426 template <class H, class CR = typename Digraph::template NodeMap<int> > |
421 struct SetStandardHeap |
427 struct SetStandardHeap |
422 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > { |
428 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > { |
423 typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > |
429 typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > |
424 Create; |
430 Create; |
484 } |
490 } |
485 |
491 |
486 ///Sets the map that stores the predecessor arcs. |
492 ///Sets the map that stores the predecessor arcs. |
487 |
493 |
488 ///Sets the map that stores the predecessor arcs. |
494 ///Sets the map that stores the predecessor arcs. |
489 ///If you don't use this function before calling \ref run(), |
495 ///If you don't use this function before calling \ref run(Node) "run()" |
490 ///it will allocate one. The destructor deallocates this |
496 ///or \ref init(), an instance will be allocated automatically. |
491 ///automatically allocated map, of course. |
497 ///The destructor deallocates this automatically allocated map, |
498 ///of course. |
|
492 ///\return <tt> (*this) </tt> |
499 ///\return <tt> (*this) </tt> |
493 Dijkstra &predMap(PredMap &m) |
500 Dijkstra &predMap(PredMap &m) |
494 { |
501 { |
495 if(local_pred) { |
502 if(local_pred) { |
496 delete _pred; |
503 delete _pred; |
501 } |
508 } |
502 |
509 |
503 ///Sets the map that indicates which nodes are processed. |
510 ///Sets the map that indicates which nodes are processed. |
504 |
511 |
505 ///Sets the map that indicates which nodes are processed. |
512 ///Sets the map that indicates which nodes are processed. |
506 ///If you don't use this function before calling \ref run(), |
513 ///If you don't use this function before calling \ref run(Node) "run()" |
507 ///it will allocate one. The destructor deallocates this |
514 ///or \ref init(), an instance will be allocated automatically. |
508 ///automatically allocated map, of course. |
515 ///The destructor deallocates this automatically allocated map, |
516 ///of course. |
|
509 ///\return <tt> (*this) </tt> |
517 ///\return <tt> (*this) </tt> |
510 Dijkstra &processedMap(ProcessedMap &m) |
518 Dijkstra &processedMap(ProcessedMap &m) |
511 { |
519 { |
512 if(local_processed) { |
520 if(local_processed) { |
513 delete _processed; |
521 delete _processed; |
519 |
527 |
520 ///Sets the map that stores the distances of the nodes. |
528 ///Sets the map that stores the distances of the nodes. |
521 |
529 |
522 ///Sets the map that stores the distances of the nodes calculated by the |
530 ///Sets the map that stores the distances of the nodes calculated by the |
523 ///algorithm. |
531 ///algorithm. |
524 ///If you don't use this function before calling \ref run(), |
532 ///If you don't use this function before calling \ref run(Node) "run()" |
525 ///it will allocate one. The destructor deallocates this |
533 ///or \ref init(), an instance will be allocated automatically. |
526 ///automatically allocated map, of course. |
534 ///The destructor deallocates this automatically allocated map, |
535 ///of course. |
|
527 ///\return <tt> (*this) </tt> |
536 ///\return <tt> (*this) </tt> |
528 Dijkstra &distMap(DistMap &m) |
537 Dijkstra &distMap(DistMap &m) |
529 { |
538 { |
530 if(local_dist) { |
539 if(local_dist) { |
531 delete _dist; |
540 delete _dist; |
536 } |
545 } |
537 |
546 |
538 ///Sets the heap and the cross reference used by algorithm. |
547 ///Sets the heap and the cross reference used by algorithm. |
539 |
548 |
540 ///Sets the heap and the cross reference used by algorithm. |
549 ///Sets the heap and the cross reference used by algorithm. |
541 ///If you don't use this function before calling \ref run(), |
550 ///If you don't use this function before calling \ref run(Node) "run()" |
542 ///it will allocate one. The destructor deallocates this |
551 ///or \ref init(), heap and cross reference instances will be |
543 ///automatically allocated heap and cross reference, of course. |
552 ///allocated automatically. |
553 ///The destructor deallocates these automatically allocated objects, |
|
554 ///of course. |
|
544 ///\return <tt> (*this) </tt> |
555 ///\return <tt> (*this) </tt> |
545 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) |
556 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) |
546 { |
557 { |
547 if(local_heap_cross_ref) { |
558 if(local_heap_cross_ref) { |
548 delete _heap_cross_ref; |
559 delete _heap_cross_ref; |
565 _dist->set(v, dst); |
576 _dist->set(v, dst); |
566 } |
577 } |
567 |
578 |
568 public: |
579 public: |
569 |
580 |
570 ///\name Execution control |
581 ///\name Execution Control |
571 ///The simplest way to execute the algorithm is to use one of the |
582 ///The simplest way to execute the %Dijkstra algorithm is to use |
572 ///member functions called \ref lemon::Dijkstra::run() "run()". |
583 ///one of the member functions called \ref run(Node) "run()".\n |
573 ///\n |
584 ///If you need more control on the execution, first you have to call |
574 ///If you need more control on the execution, first you must call |
585 ///\ref init(), then you can add several source nodes with |
575 ///\ref lemon::Dijkstra::init() "init()", then you can add several |
586 ///\ref addSource(). Finally the actual path computation can be |
576 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". |
587 ///performed with one of the \ref start() functions. |
577 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the |
|
578 ///actual path computation. |
|
579 |
588 |
580 ///@{ |
589 ///@{ |
581 |
590 |
591 ///\brief Initializes the internal data structures. |
|
592 /// |
|
582 ///Initializes the internal data structures. |
593 ///Initializes the internal data structures. |
583 |
|
584 ///Initializes the internal data structures. |
|
585 /// |
|
586 void init() |
594 void init() |
587 { |
595 { |
588 create_maps(); |
596 create_maps(); |
589 _heap->clear(); |
597 _heap->clear(); |
590 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
598 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
656 Node nextNode() const |
664 Node nextNode() const |
657 { |
665 { |
658 return !_heap->empty()?_heap->top():INVALID; |
666 return !_heap->empty()?_heap->top():INVALID; |
659 } |
667 } |
660 |
668 |
661 ///\brief Returns \c false if there are nodes |
669 ///Returns \c false if there are nodes to be processed. |
662 ///to be processed. |
670 |
663 /// |
671 ///Returns \c false if there are nodes to be processed |
664 ///Returns \c false if there are nodes |
672 ///in the priority heap. |
665 ///to be processed in the priority heap. |
|
666 bool emptyQueue() const { return _heap->empty(); } |
673 bool emptyQueue() const { return _heap->empty(); } |
667 |
674 |
668 ///Returns the number of the nodes to be processed in the priority heap |
675 ///Returns the number of the nodes to be processed. |
669 |
676 |
670 ///Returns the number of the nodes to be processed in the priority heap. |
677 ///Returns the number of the nodes to be processed |
671 /// |
678 ///in the priority heap. |
672 int queueSize() const { return _heap->size(); } |
679 int queueSize() const { return _heap->size(); } |
673 |
680 |
674 ///Executes the algorithm. |
681 ///Executes the algorithm. |
675 |
682 |
676 ///Executes the algorithm. |
683 ///Executes the algorithm. |
787 } |
794 } |
788 |
795 |
789 ///@} |
796 ///@} |
790 |
797 |
791 ///\name Query Functions |
798 ///\name Query Functions |
792 ///The result of the %Dijkstra algorithm can be obtained using these |
799 ///The results of the %Dijkstra algorithm can be obtained using these |
793 ///functions.\n |
800 ///functions.\n |
794 ///Either \ref lemon::Dijkstra::run() "run()" or |
801 ///Either \ref run(Node) "run()" or \ref start() should be called |
795 ///\ref lemon::Dijkstra::start() "start()" must be called before |
802 ///before using them. |
796 ///using them. |
|
797 |
803 |
798 ///@{ |
804 ///@{ |
799 |
805 |
800 ///The shortest path to a node. |
806 ///The shortest path to a node. |
801 |
807 |
802 ///Returns the shortest path to a node. |
808 ///Returns the shortest path to a node. |
803 /// |
809 /// |
804 ///\warning \c t should be reachable from the root(s). |
810 ///\warning \c t should be reached from the root(s). |
805 /// |
811 /// |
806 ///\pre Either \ref run() or \ref start() must be called before |
812 ///\pre Either \ref run(Node) "run()" or \ref init() |
807 ///using this function. |
813 ///must be called before using this function. |
808 Path path(Node t) const { return Path(*G, *_pred, t); } |
814 Path path(Node t) const { return Path(*G, *_pred, t); } |
809 |
815 |
810 ///The distance of a node from the root(s). |
816 ///The distance of a node from the root(s). |
811 |
817 |
812 ///Returns the distance of a node from the root(s). |
818 ///Returns the distance of a node from the root(s). |
813 /// |
819 /// |
814 ///\warning If node \c v is not reachable from the root(s), then |
820 ///\warning If node \c v is not reached from the root(s), then |
815 ///the return value of this function is undefined. |
821 ///the return value of this function is undefined. |
816 /// |
822 /// |
817 ///\pre Either \ref run() or \ref start() must be called before |
823 ///\pre Either \ref run(Node) "run()" or \ref init() |
818 ///using this function. |
824 ///must be called before using this function. |
819 Value dist(Node v) const { return (*_dist)[v]; } |
825 Value dist(Node v) const { return (*_dist)[v]; } |
820 |
826 |
821 ///Returns the 'previous arc' of the shortest path tree for a node. |
827 ///Returns the 'previous arc' of the shortest path tree for a node. |
822 |
828 |
823 ///This function returns the 'previous arc' of the shortest path |
829 ///This function returns the 'previous arc' of the shortest path |
824 ///tree for the node \c v, i.e. it returns the last arc of a |
830 ///tree for the node \c v, i.e. it returns the last arc of a |
825 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v |
831 ///shortest path from a root to \c v. It is \c INVALID if \c v |
826 ///is not reachable from the root(s) or if \c v is a root. |
832 ///is not reached from the root(s) or if \c v is a root. |
827 /// |
833 /// |
828 ///The shortest path tree used here is equal to the shortest path |
834 ///The shortest path tree used here is equal to the shortest path |
829 ///tree used in \ref predNode(). |
835 ///tree used in \ref predNode(). |
830 /// |
836 /// |
831 ///\pre Either \ref run() or \ref start() must be called before |
837 ///\pre Either \ref run(Node) "run()" or \ref init() |
832 ///using this function. |
838 ///must be called before using this function. |
833 Arc predArc(Node v) const { return (*_pred)[v]; } |
839 Arc predArc(Node v) const { return (*_pred)[v]; } |
834 |
840 |
835 ///Returns the 'previous node' of the shortest path tree for a node. |
841 ///Returns the 'previous node' of the shortest path tree for a node. |
836 |
842 |
837 ///This function returns the 'previous node' of the shortest path |
843 ///This function returns the 'previous node' of the shortest path |
838 ///tree for the node \c v, i.e. it returns the last but one node |
844 ///tree for the node \c v, i.e. it returns the last but one node |
839 ///from a shortest path from the root(s) to \c v. It is \c INVALID |
845 ///from a shortest path from a root to \c v. It is \c INVALID |
840 ///if \c v is not reachable from the root(s) or if \c v is a root. |
846 ///if \c v is not reached from the root(s) or if \c v is a root. |
841 /// |
847 /// |
842 ///The shortest path tree used here is equal to the shortest path |
848 ///The shortest path tree used here is equal to the shortest path |
843 ///tree used in \ref predArc(). |
849 ///tree used in \ref predArc(). |
844 /// |
850 /// |
845 ///\pre Either \ref run() or \ref start() must be called before |
851 ///\pre Either \ref run(Node) "run()" or \ref init() |
846 ///using this function. |
852 ///must be called before using this function. |
847 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
853 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
848 G->source((*_pred)[v]); } |
854 G->source((*_pred)[v]); } |
849 |
855 |
850 ///\brief Returns a const reference to the node map that stores the |
856 ///\brief Returns a const reference to the node map that stores the |
851 ///distances of the nodes. |
857 ///distances of the nodes. |
852 /// |
858 /// |
853 ///Returns a const reference to the node map that stores the distances |
859 ///Returns a const reference to the node map that stores the distances |
854 ///of the nodes calculated by the algorithm. |
860 ///of the nodes calculated by the algorithm. |
855 /// |
861 /// |
856 ///\pre Either \ref run() or \ref init() |
862 ///\pre Either \ref run(Node) "run()" or \ref init() |
857 ///must be called before using this function. |
863 ///must be called before using this function. |
858 const DistMap &distMap() const { return *_dist;} |
864 const DistMap &distMap() const { return *_dist;} |
859 |
865 |
860 ///\brief Returns a const reference to the node map that stores the |
866 ///\brief Returns a const reference to the node map that stores the |
861 ///predecessor arcs. |
867 ///predecessor arcs. |
862 /// |
868 /// |
863 ///Returns a const reference to the node map that stores the predecessor |
869 ///Returns a const reference to the node map that stores the predecessor |
864 ///arcs, which form the shortest path tree. |
870 ///arcs, which form the shortest path tree. |
865 /// |
871 /// |
866 ///\pre Either \ref run() or \ref init() |
872 ///\pre Either \ref run(Node) "run()" or \ref init() |
867 ///must be called before using this function. |
873 ///must be called before using this function. |
868 const PredMap &predMap() const { return *_pred;} |
874 const PredMap &predMap() const { return *_pred;} |
869 |
875 |
870 ///Checks if a node is reachable from the root(s). |
876 ///Checks if a node is reached from the root(s). |
871 |
877 |
872 ///Returns \c true if \c v is reachable from the root(s). |
878 ///Returns \c true if \c v is reached from the root(s). |
873 ///\pre Either \ref run() or \ref start() |
879 /// |
880 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
874 ///must be called before using this function. |
881 ///must be called before using this function. |
875 bool reached(Node v) const { return (*_heap_cross_ref)[v] != |
882 bool reached(Node v) const { return (*_heap_cross_ref)[v] != |
876 Heap::PRE_HEAP; } |
883 Heap::PRE_HEAP; } |
877 |
884 |
878 ///Checks if a node is processed. |
885 ///Checks if a node is processed. |
879 |
886 |
880 ///Returns \c true if \c v is processed, i.e. the shortest |
887 ///Returns \c true if \c v is processed, i.e. the shortest |
881 ///path to \c v has already found. |
888 ///path to \c v has already found. |
882 ///\pre Either \ref run() or \ref init() |
889 /// |
890 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
883 ///must be called before using this function. |
891 ///must be called before using this function. |
884 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
892 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
885 Heap::POST_HEAP; } |
893 Heap::POST_HEAP; } |
886 |
894 |
887 ///The current distance of a node from the root(s). |
895 ///The current distance of a node from the root(s). |
888 |
896 |
889 ///Returns the current distance of a node from the root(s). |
897 ///Returns the current distance of a node from the root(s). |
890 ///It may be decreased in the following processes. |
898 ///It may be decreased in the following processes. |
891 ///\pre Either \ref run() or \ref init() |
899 /// |
900 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
892 ///must be called before using this function and |
901 ///must be called before using this function and |
893 ///node \c v must be reached but not necessarily processed. |
902 ///node \c v must be reached but not necessarily processed. |
894 Value currentDist(Node v) const { |
903 Value currentDist(Node v) const { |
895 return processed(v) ? (*_dist)[v] : (*_heap)[v]; |
904 return processed(v) ? (*_dist)[v] : (*_heap)[v]; |
896 } |
905 } |
1069 |
1078 |
1070 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1079 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1071 |
1080 |
1072 /// This auxiliary class is created to implement the |
1081 /// This auxiliary class is created to implement the |
1073 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. |
1082 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. |
1074 /// It does not have own \ref run() method, it uses the functions |
1083 /// It does not have own \ref run(Node) "run()" method, it uses the |
1075 /// and features of the plain \ref Dijkstra. |
1084 /// functions and features of the plain \ref Dijkstra. |
1076 /// |
1085 /// |
1077 /// This class should only be used through the \ref dijkstra() function, |
1086 /// This class should only be used through the \ref dijkstra() function, |
1078 /// which makes it easier to use the algorithm. |
1087 /// which makes it easier to use the algorithm. |
1079 template<class TR> |
1088 template<class TR> |
1080 class DijkstraWizard : public TR |
1089 class DijkstraWizard : public TR |
1265 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); |
1274 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); |
1266 /// |
1275 /// |
1267 /// // Compute shortest path from s to t |
1276 /// // Compute shortest path from s to t |
1268 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); |
1277 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); |
1269 ///\endcode |
1278 ///\endcode |
1270 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" |
1279 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" |
1271 ///to the end of the parameter list. |
1280 ///to the end of the parameter list. |
1272 ///\sa DijkstraWizard |
1281 ///\sa DijkstraWizard |
1273 ///\sa Dijkstra |
1282 ///\sa Dijkstra |
1274 template<class GR, class LM> |
1283 template<class GR, class LM> |
1275 DijkstraWizard<DijkstraWizardBase<GR,LM> > |
1284 DijkstraWizard<DijkstraWizardBase<GR,LM> > |