changeset 405 | 6b9057cdcd8b |
parent 313 | 64f8f7cc6168 |
child 408 | 69f33ef03334 |
19:8de33c082451 | 21:4c1d108d1294 |
---|---|
200 ///There is also a \ref dijkstra() "function-type interface" for the |
200 ///There is also a \ref dijkstra() "function-type interface" for the |
201 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
201 ///%Dijkstra algorithm, which is convenient in the simplier cases and |
202 ///it can be used easier. |
202 ///it can be used easier. |
203 /// |
203 /// |
204 ///\tparam GR The type of the digraph the algorithm runs on. |
204 ///\tparam GR The type of the digraph the algorithm runs on. |
205 ///The default value is \ref ListDigraph. |
205 ///The default type is \ref ListDigraph. |
206 ///The value of GR is not used directly by \ref Dijkstra, it is only |
206 ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies |
207 ///passed to \ref DijkstraDefaultTraits. |
207 ///the lengths of the arcs. |
208 ///\tparam LM A readable arc map that determines the lengths of the |
208 ///It is read once for each arc, so the map may involve in |
209 ///arcs. It is read once for each arc, so the map may involve in |
|
210 ///relatively time consuming process to compute the arc lengths if |
209 ///relatively time consuming process to compute the arc lengths if |
211 ///it is necessary. The default map type is \ref |
210 ///it is necessary. The default map type is \ref |
212 ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>". |
211 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". |
213 ///The value of LM is not used directly by \ref Dijkstra, it is only |
|
214 ///passed to \ref DijkstraDefaultTraits. |
|
215 ///\tparam TR Traits class to set various data types used by the algorithm. |
|
216 ///The default traits class is \ref DijkstraDefaultTraits |
|
217 ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits |
|
218 ///for the documentation of a Dijkstra traits class. |
|
219 #ifdef DOXYGEN |
212 #ifdef DOXYGEN |
220 template <typename GR, typename LM, typename TR> |
213 template <typename GR, typename LM, typename TR> |
221 #else |
214 #else |
222 template <typename GR=ListDigraph, |
215 template <typename GR=ListDigraph, |
223 typename LM=typename GR::template ArcMap<int>, |
216 typename LM=typename GR::template ArcMap<int>, |
247 ///The heap type used by the algorithm. |
240 ///The heap type used by the algorithm. |
248 typedef typename TR::Heap Heap; |
241 typedef typename TR::Heap Heap; |
249 ///The operation traits class. |
242 ///The operation traits class. |
250 typedef typename TR::OperationTraits OperationTraits; |
243 typedef typename TR::OperationTraits OperationTraits; |
251 |
244 |
252 ///The traits class. |
245 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. |
253 typedef TR Traits; |
246 typedef TR Traits; |
254 |
247 |
255 private: |
248 private: |
256 |
249 |
257 typedef typename Digraph::Node Node; |
250 typedef typename Digraph::Node Node; |
329 ///\brief \ref named-templ-param "Named parameter" for setting |
322 ///\brief \ref named-templ-param "Named parameter" for setting |
330 ///PredMap type. |
323 ///PredMap type. |
331 /// |
324 /// |
332 ///\ref named-templ-param "Named parameter" for setting |
325 ///\ref named-templ-param "Named parameter" for setting |
333 ///PredMap type. |
326 ///PredMap type. |
327 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
334 template <class T> |
328 template <class T> |
335 struct SetPredMap |
329 struct SetPredMap |
336 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > { |
330 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > { |
337 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create; |
331 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create; |
338 }; |
332 }; |
349 ///\brief \ref named-templ-param "Named parameter" for setting |
343 ///\brief \ref named-templ-param "Named parameter" for setting |
350 ///DistMap type. |
344 ///DistMap type. |
351 /// |
345 /// |
352 ///\ref named-templ-param "Named parameter" for setting |
346 ///\ref named-templ-param "Named parameter" for setting |
353 ///DistMap type. |
347 ///DistMap type. |
348 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
354 template <class T> |
349 template <class T> |
355 struct SetDistMap |
350 struct SetDistMap |
356 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > { |
351 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > { |
357 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create; |
352 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create; |
358 }; |
353 }; |
369 ///\brief \ref named-templ-param "Named parameter" for setting |
364 ///\brief \ref named-templ-param "Named parameter" for setting |
370 ///ProcessedMap type. |
365 ///ProcessedMap type. |
371 /// |
366 /// |
372 ///\ref named-templ-param "Named parameter" for setting |
367 ///\ref named-templ-param "Named parameter" for setting |
373 ///ProcessedMap type. |
368 ///ProcessedMap type. |
369 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
|
374 template <class T> |
370 template <class T> |
375 struct SetProcessedMap |
371 struct SetProcessedMap |
376 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
372 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > { |
377 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
373 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create; |
378 }; |
374 }; |
409 LEMON_ASSERT(false, "Heap is not initialized"); |
405 LEMON_ASSERT(false, "Heap is not initialized"); |
410 return 0; // ignore warnings |
406 return 0; // ignore warnings |
411 } |
407 } |
412 }; |
408 }; |
413 ///\brief \ref named-templ-param "Named parameter" for setting |
409 ///\brief \ref named-templ-param "Named parameter" for setting |
414 ///heap and cross reference type |
410 ///heap and cross reference types |
415 /// |
411 /// |
416 ///\ref named-templ-param "Named parameter" for setting heap and cross |
412 ///\ref named-templ-param "Named parameter" for setting heap and cross |
417 ///reference type. |
413 ///reference types. If this named parameter is used, then external |
414 ///heap and cross reference objects must be passed to the algorithm |
|
415 ///using the \ref heap() function before calling \ref run(Node) "run()" |
|
416 ///or \ref init(). |
|
417 ///\sa SetStandardHeap |
|
418 template <class H, class CR = typename Digraph::template NodeMap<int> > |
418 template <class H, class CR = typename Digraph::template NodeMap<int> > |
419 struct SetHeap |
419 struct SetHeap |
420 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > { |
420 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > { |
421 typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create; |
421 typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create; |
422 }; |
422 }; |
432 { |
432 { |
433 return new Heap(R); |
433 return new Heap(R); |
434 } |
434 } |
435 }; |
435 }; |
436 ///\brief \ref named-templ-param "Named parameter" for setting |
436 ///\brief \ref named-templ-param "Named parameter" for setting |
437 ///heap and cross reference type with automatic allocation |
437 ///heap and cross reference types with automatic allocation |
438 /// |
438 /// |
439 ///\ref named-templ-param "Named parameter" for setting heap and cross |
439 ///\ref named-templ-param "Named parameter" for setting heap and cross |
440 ///reference type. It can allocate the heap and the cross reference |
440 ///reference types with automatic allocation. |
441 ///object if the cross reference's constructor waits for the digraph as |
441 ///They should have standard constructor interfaces to be able to |
442 ///parameter and the heap's constructor waits for the cross reference. |
442 ///automatically created by the algorithm (i.e. the digraph should be |
443 ///passed to the constructor of the cross reference and the cross |
|
444 ///reference should be passed to the constructor of the heap). |
|
445 ///However external heap and cross reference objects could also be |
|
446 ///passed to the algorithm using the \ref heap() function before |
|
447 ///calling \ref run(Node) "run()" or \ref init(). |
|
448 ///\sa SetHeap |
|
443 template <class H, class CR = typename Digraph::template NodeMap<int> > |
449 template <class H, class CR = typename Digraph::template NodeMap<int> > |
444 struct SetStandardHeap |
450 struct SetStandardHeap |
445 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > { |
451 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > { |
446 typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > |
452 typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > |
447 Create; |
453 Create; |
507 } |
513 } |
508 |
514 |
509 ///Sets the map that stores the predecessor arcs. |
515 ///Sets the map that stores the predecessor arcs. |
510 |
516 |
511 ///Sets the map that stores the predecessor arcs. |
517 ///Sets the map that stores the predecessor arcs. |
512 ///If you don't use this function before calling \ref run(), |
518 ///If you don't use this function before calling \ref run(Node) "run()" |
513 ///it will allocate one. The destructor deallocates this |
519 ///or \ref init(), an instance will be allocated automatically. |
514 ///automatically allocated map, of course. |
520 ///The destructor deallocates this automatically allocated map, |
521 ///of course. |
|
515 ///\return <tt> (*this) </tt> |
522 ///\return <tt> (*this) </tt> |
516 Dijkstra &predMap(PredMap &m) |
523 Dijkstra &predMap(PredMap &m) |
517 { |
524 { |
518 if(local_pred) { |
525 if(local_pred) { |
519 delete _pred; |
526 delete _pred; |
524 } |
531 } |
525 |
532 |
526 ///Sets the map that indicates which nodes are processed. |
533 ///Sets the map that indicates which nodes are processed. |
527 |
534 |
528 ///Sets the map that indicates which nodes are processed. |
535 ///Sets the map that indicates which nodes are processed. |
529 ///If you don't use this function before calling \ref run(), |
536 ///If you don't use this function before calling \ref run(Node) "run()" |
530 ///it will allocate one. The destructor deallocates this |
537 ///or \ref init(), an instance will be allocated automatically. |
531 ///automatically allocated map, of course. |
538 ///The destructor deallocates this automatically allocated map, |
539 ///of course. |
|
532 ///\return <tt> (*this) </tt> |
540 ///\return <tt> (*this) </tt> |
533 Dijkstra &processedMap(ProcessedMap &m) |
541 Dijkstra &processedMap(ProcessedMap &m) |
534 { |
542 { |
535 if(local_processed) { |
543 if(local_processed) { |
536 delete _processed; |
544 delete _processed; |
542 |
550 |
543 ///Sets the map that stores the distances of the nodes. |
551 ///Sets the map that stores the distances of the nodes. |
544 |
552 |
545 ///Sets the map that stores the distances of the nodes calculated by the |
553 ///Sets the map that stores the distances of the nodes calculated by the |
546 ///algorithm. |
554 ///algorithm. |
547 ///If you don't use this function before calling \ref run(), |
555 ///If you don't use this function before calling \ref run(Node) "run()" |
548 ///it will allocate one. The destructor deallocates this |
556 ///or \ref init(), an instance will be allocated automatically. |
549 ///automatically allocated map, of course. |
557 ///The destructor deallocates this automatically allocated map, |
558 ///of course. |
|
550 ///\return <tt> (*this) </tt> |
559 ///\return <tt> (*this) </tt> |
551 Dijkstra &distMap(DistMap &m) |
560 Dijkstra &distMap(DistMap &m) |
552 { |
561 { |
553 if(local_dist) { |
562 if(local_dist) { |
554 delete _dist; |
563 delete _dist; |
559 } |
568 } |
560 |
569 |
561 ///Sets the heap and the cross reference used by algorithm. |
570 ///Sets the heap and the cross reference used by algorithm. |
562 |
571 |
563 ///Sets the heap and the cross reference used by algorithm. |
572 ///Sets the heap and the cross reference used by algorithm. |
564 ///If you don't use this function before calling \ref run(), |
573 ///If you don't use this function before calling \ref run(Node) "run()" |
565 ///it will allocate one. The destructor deallocates this |
574 ///or \ref init(), heap and cross reference instances will be |
566 ///automatically allocated heap and cross reference, of course. |
575 ///allocated automatically. |
576 ///The destructor deallocates these automatically allocated objects, |
|
577 ///of course. |
|
567 ///\return <tt> (*this) </tt> |
578 ///\return <tt> (*this) </tt> |
568 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) |
579 Dijkstra &heap(Heap& hp, HeapCrossRef &cr) |
569 { |
580 { |
570 if(local_heap_cross_ref) { |
581 if(local_heap_cross_ref) { |
571 delete _heap_cross_ref; |
582 delete _heap_cross_ref; |
588 _dist->set(v, dst); |
599 _dist->set(v, dst); |
589 } |
600 } |
590 |
601 |
591 public: |
602 public: |
592 |
603 |
593 ///\name Execution control |
604 ///\name Execution Control |
594 ///The simplest way to execute the algorithm is to use one of the |
605 ///The simplest way to execute the %Dijkstra algorithm is to use |
595 ///member functions called \ref lemon::Dijkstra::run() "run()". |
606 ///one of the member functions called \ref run(Node) "run()".\n |
596 ///\n |
607 ///If you need more control on the execution, first you have to call |
597 ///If you need more control on the execution, first you must call |
608 ///\ref init(), then you can add several source nodes with |
598 ///\ref lemon::Dijkstra::init() "init()", then you can add several |
609 ///\ref addSource(). Finally the actual path computation can be |
599 ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". |
610 ///performed with one of the \ref start() functions. |
600 ///Finally \ref lemon::Dijkstra::start() "start()" will perform the |
|
601 ///actual path computation. |
|
602 |
611 |
603 ///@{ |
612 ///@{ |
604 |
613 |
614 ///\brief Initializes the internal data structures. |
|
615 /// |
|
605 ///Initializes the internal data structures. |
616 ///Initializes the internal data structures. |
606 |
|
607 ///Initializes the internal data structures. |
|
608 /// |
|
609 void init() |
617 void init() |
610 { |
618 { |
611 create_maps(); |
619 create_maps(); |
612 _heap->clear(); |
620 _heap->clear(); |
613 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
621 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
679 Node nextNode() const |
687 Node nextNode() const |
680 { |
688 { |
681 return !_heap->empty()?_heap->top():INVALID; |
689 return !_heap->empty()?_heap->top():INVALID; |
682 } |
690 } |
683 |
691 |
684 ///\brief Returns \c false if there are nodes |
692 ///Returns \c false if there are nodes to be processed. |
685 ///to be processed. |
693 |
686 /// |
694 ///Returns \c false if there are nodes to be processed |
687 ///Returns \c false if there are nodes |
695 ///in the priority heap. |
688 ///to be processed in the priority heap. |
|
689 bool emptyQueue() const { return _heap->empty(); } |
696 bool emptyQueue() const { return _heap->empty(); } |
690 |
697 |
691 ///Returns the number of the nodes to be processed in the priority heap |
698 ///Returns the number of the nodes to be processed. |
692 |
699 |
693 ///Returns the number of the nodes to be processed in the priority heap. |
700 ///Returns the number of the nodes to be processed |
694 /// |
701 ///in the priority heap. |
695 int queueSize() const { return _heap->size(); } |
702 int queueSize() const { return _heap->size(); } |
696 |
703 |
697 ///Executes the algorithm. |
704 ///Executes the algorithm. |
698 |
705 |
699 ///Executes the algorithm. |
706 ///Executes the algorithm. |
810 } |
817 } |
811 |
818 |
812 ///@} |
819 ///@} |
813 |
820 |
814 ///\name Query Functions |
821 ///\name Query Functions |
815 ///The result of the %Dijkstra algorithm can be obtained using these |
822 ///The results of the %Dijkstra algorithm can be obtained using these |
816 ///functions.\n |
823 ///functions.\n |
817 ///Either \ref lemon::Dijkstra::run() "run()" or |
824 ///Either \ref run(Node) "run()" or \ref start() should be called |
818 ///\ref lemon::Dijkstra::start() "start()" must be called before |
825 ///before using them. |
819 ///using them. |
|
820 |
826 |
821 ///@{ |
827 ///@{ |
822 |
828 |
823 ///The shortest path to a node. |
829 ///The shortest path to a node. |
824 |
830 |
825 ///Returns the shortest path to a node. |
831 ///Returns the shortest path to a node. |
826 /// |
832 /// |
827 ///\warning \c t should be reachable from the root(s). |
833 ///\warning \c t should be reached from the root(s). |
828 /// |
834 /// |
829 ///\pre Either \ref run() or \ref start() must be called before |
835 ///\pre Either \ref run(Node) "run()" or \ref init() |
830 ///using this function. |
836 ///must be called before using this function. |
831 Path path(Node t) const { return Path(*G, *_pred, t); } |
837 Path path(Node t) const { return Path(*G, *_pred, t); } |
832 |
838 |
833 ///The distance of a node from the root(s). |
839 ///The distance of a node from the root(s). |
834 |
840 |
835 ///Returns the distance of a node from the root(s). |
841 ///Returns the distance of a node from the root(s). |
836 /// |
842 /// |
837 ///\warning If node \c v is not reachable from the root(s), then |
843 ///\warning If node \c v is not reached from the root(s), then |
838 ///the return value of this function is undefined. |
844 ///the return value of this function is undefined. |
839 /// |
845 /// |
840 ///\pre Either \ref run() or \ref start() must be called before |
846 ///\pre Either \ref run(Node) "run()" or \ref init() |
841 ///using this function. |
847 ///must be called before using this function. |
842 Value dist(Node v) const { return (*_dist)[v]; } |
848 Value dist(Node v) const { return (*_dist)[v]; } |
843 |
849 |
844 ///Returns the 'previous arc' of the shortest path tree for a node. |
850 ///Returns the 'previous arc' of the shortest path tree for a node. |
845 |
851 |
846 ///This function returns the 'previous arc' of the shortest path |
852 ///This function returns the 'previous arc' of the shortest path |
847 ///tree for the node \c v, i.e. it returns the last arc of a |
853 ///tree for the node \c v, i.e. it returns the last arc of a |
848 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v |
854 ///shortest path from a root to \c v. It is \c INVALID if \c v |
849 ///is not reachable from the root(s) or if \c v is a root. |
855 ///is not reached from the root(s) or if \c v is a root. |
850 /// |
856 /// |
851 ///The shortest path tree used here is equal to the shortest path |
857 ///The shortest path tree used here is equal to the shortest path |
852 ///tree used in \ref predNode(). |
858 ///tree used in \ref predNode(). |
853 /// |
859 /// |
854 ///\pre Either \ref run() or \ref start() must be called before |
860 ///\pre Either \ref run(Node) "run()" or \ref init() |
855 ///using this function. |
861 ///must be called before using this function. |
856 Arc predArc(Node v) const { return (*_pred)[v]; } |
862 Arc predArc(Node v) const { return (*_pred)[v]; } |
857 |
863 |
858 ///Returns the 'previous node' of the shortest path tree for a node. |
864 ///Returns the 'previous node' of the shortest path tree for a node. |
859 |
865 |
860 ///This function returns the 'previous node' of the shortest path |
866 ///This function returns the 'previous node' of the shortest path |
861 ///tree for the node \c v, i.e. it returns the last but one node |
867 ///tree for the node \c v, i.e. it returns the last but one node |
862 ///from a shortest path from the root(s) to \c v. It is \c INVALID |
868 ///from a shortest path from a root to \c v. It is \c INVALID |
863 ///if \c v is not reachable from the root(s) or if \c v is a root. |
869 ///if \c v is not reached from the root(s) or if \c v is a root. |
864 /// |
870 /// |
865 ///The shortest path tree used here is equal to the shortest path |
871 ///The shortest path tree used here is equal to the shortest path |
866 ///tree used in \ref predArc(). |
872 ///tree used in \ref predArc(). |
867 /// |
873 /// |
868 ///\pre Either \ref run() or \ref start() must be called before |
874 ///\pre Either \ref run(Node) "run()" or \ref init() |
869 ///using this function. |
875 ///must be called before using this function. |
870 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
876 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
871 G->source((*_pred)[v]); } |
877 G->source((*_pred)[v]); } |
872 |
878 |
873 ///\brief Returns a const reference to the node map that stores the |
879 ///\brief Returns a const reference to the node map that stores the |
874 ///distances of the nodes. |
880 ///distances of the nodes. |
875 /// |
881 /// |
876 ///Returns a const reference to the node map that stores the distances |
882 ///Returns a const reference to the node map that stores the distances |
877 ///of the nodes calculated by the algorithm. |
883 ///of the nodes calculated by the algorithm. |
878 /// |
884 /// |
879 ///\pre Either \ref run() or \ref init() |
885 ///\pre Either \ref run(Node) "run()" or \ref init() |
880 ///must be called before using this function. |
886 ///must be called before using this function. |
881 const DistMap &distMap() const { return *_dist;} |
887 const DistMap &distMap() const { return *_dist;} |
882 |
888 |
883 ///\brief Returns a const reference to the node map that stores the |
889 ///\brief Returns a const reference to the node map that stores the |
884 ///predecessor arcs. |
890 ///predecessor arcs. |
885 /// |
891 /// |
886 ///Returns a const reference to the node map that stores the predecessor |
892 ///Returns a const reference to the node map that stores the predecessor |
887 ///arcs, which form the shortest path tree. |
893 ///arcs, which form the shortest path tree. |
888 /// |
894 /// |
889 ///\pre Either \ref run() or \ref init() |
895 ///\pre Either \ref run(Node) "run()" or \ref init() |
890 ///must be called before using this function. |
896 ///must be called before using this function. |
891 const PredMap &predMap() const { return *_pred;} |
897 const PredMap &predMap() const { return *_pred;} |
892 |
898 |
893 ///Checks if a node is reachable from the root(s). |
899 ///Checks if a node is reached from the root(s). |
894 |
900 |
895 ///Returns \c true if \c v is reachable from the root(s). |
901 ///Returns \c true if \c v is reached from the root(s). |
896 ///\pre Either \ref run() or \ref start() |
902 /// |
903 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
897 ///must be called before using this function. |
904 ///must be called before using this function. |
898 bool reached(Node v) const { return (*_heap_cross_ref)[v] != |
905 bool reached(Node v) const { return (*_heap_cross_ref)[v] != |
899 Heap::PRE_HEAP; } |
906 Heap::PRE_HEAP; } |
900 |
907 |
901 ///Checks if a node is processed. |
908 ///Checks if a node is processed. |
902 |
909 |
903 ///Returns \c true if \c v is processed, i.e. the shortest |
910 ///Returns \c true if \c v is processed, i.e. the shortest |
904 ///path to \c v has already found. |
911 ///path to \c v has already found. |
905 ///\pre Either \ref run() or \ref init() |
912 /// |
913 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
906 ///must be called before using this function. |
914 ///must be called before using this function. |
907 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
915 bool processed(Node v) const { return (*_heap_cross_ref)[v] == |
908 Heap::POST_HEAP; } |
916 Heap::POST_HEAP; } |
909 |
917 |
910 ///The current distance of a node from the root(s). |
918 ///The current distance of a node from the root(s). |
911 |
919 |
912 ///Returns the current distance of a node from the root(s). |
920 ///Returns the current distance of a node from the root(s). |
913 ///It may be decreased in the following processes. |
921 ///It may be decreased in the following processes. |
914 ///\pre Either \ref run() or \ref init() |
922 /// |
923 ///\pre Either \ref run(Node) "run()" or \ref init() |
|
915 ///must be called before using this function and |
924 ///must be called before using this function and |
916 ///node \c v must be reached but not necessarily processed. |
925 ///node \c v must be reached but not necessarily processed. |
917 Value currentDist(Node v) const { |
926 Value currentDist(Node v) const { |
918 return processed(v) ? (*_dist)[v] : (*_heap)[v]; |
927 return processed(v) ? (*_dist)[v] : (*_heap)[v]; |
919 } |
928 } |
1092 |
1101 |
1093 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1102 /// Auxiliary class for the function-type interface of Dijkstra algorithm. |
1094 |
1103 |
1095 /// This auxiliary class is created to implement the |
1104 /// This auxiliary class is created to implement the |
1096 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. |
1105 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. |
1097 /// It does not have own \ref run() method, it uses the functions |
1106 /// It does not have own \ref run(Node) "run()" method, it uses the |
1098 /// and features of the plain \ref Dijkstra. |
1107 /// functions and features of the plain \ref Dijkstra. |
1099 /// |
1108 /// |
1100 /// This class should only be used through the \ref dijkstra() function, |
1109 /// This class should only be used through the \ref dijkstra() function, |
1101 /// which makes it easier to use the algorithm. |
1110 /// which makes it easier to use the algorithm. |
1102 template<class TR> |
1111 template<class TR> |
1103 class DijkstraWizard : public TR |
1112 class DijkstraWizard : public TR |
1288 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); |
1297 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); |
1289 /// |
1298 /// |
1290 /// // Compute shortest path from s to t |
1299 /// // Compute shortest path from s to t |
1291 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); |
1300 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); |
1292 ///\endcode |
1301 ///\endcode |
1293 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" |
1302 ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" |
1294 ///to the end of the parameter list. |
1303 ///to the end of the parameter list. |
1295 ///\sa DijkstraWizard |
1304 ///\sa DijkstraWizard |
1296 ///\sa Dijkstra |
1305 ///\sa Dijkstra |
1297 template<class GR, class LM> |
1306 template<class GR, class LM> |
1298 DijkstraWizard<DijkstraWizardBase<GR,LM> > |
1307 DijkstraWizard<DijkstraWizardBase<GR,LM> > |