335 class DefReachedMap : public Dijkstra< Graph, |
335 class DefReachedMap : public Dijkstra< Graph, |
336 LengthMap, |
336 LengthMap, |
337 DefReachedMapTraits<T> > { }; |
337 DefReachedMapTraits<T> > { }; |
338 |
338 |
339 struct DefGraphReachedMapTraits : public Traits { |
339 struct DefGraphReachedMapTraits : public Traits { |
340 typedef typename Graph::NodeMap<bool> ReachedMap; |
340 typedef typename Graph::template NodeMap<bool> ReachedMap; |
341 static ReachedMap *createReachedMap(const Graph &G) |
341 static ReachedMap *createReachedMap(const Graph &G) |
342 { |
342 { |
343 return new ReachedMap(G); |
343 return new ReachedMap(G); |
344 } |
344 } |
345 }; |
345 }; |
537 |
537 |
538 ///Returns \c false if there are nodes to be processed in the priority heap |
538 ///Returns \c false if there are nodes to be processed in the priority heap |
539 |
539 |
540 ///Returns \c false if there are nodes to be processed in the priority heap |
540 ///Returns \c false if there are nodes to be processed in the priority heap |
541 /// |
541 /// |
542 bool emptyHeap() { return heap.empty(); } |
542 bool emptyHeap() { return _heap.empty(); } |
543 ///Returns the number of the nodes to be processed in the priority heap |
543 ///Returns the number of the nodes to be processed in the priority heap |
544 |
544 |
545 ///Returns the number of the nodes to be processed in the priority heap |
545 ///Returns the number of the nodes to be processed in the priority heap |
546 /// |
546 /// |
547 int heapSize() { return heap.size(); } |
547 int heapSize() { return _heap.size(); } |
548 |
548 |
549 ///Executes the algorithm. |
549 ///Executes the algorithm. |
550 |
550 |
551 ///Executes the algorithm. |
551 ///Executes the algorithm. |
552 /// |
552 /// |
595 ///\param nm must be a bool (or convertible) node map. The algorithm |
595 ///\param nm must be a bool (or convertible) node map. The algorithm |
596 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
596 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
597 template<class NM> |
597 template<class NM> |
598 void start(const NM &nm) |
598 void start(const NM &nm) |
599 { |
599 { |
600 while ( !_heap.empty() && !mn[_heap.top()] ) processNextNode(); |
600 while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode(); |
601 if ( !_heap.empty() ) finalizeNodeData(_heap.top()); |
601 if ( !_heap.empty() ) finalizeNodeData(_heap.top()); |
602 } |
602 } |
603 |
603 |
604 ///Runs %Dijkstra algorithm from node \c s. |
604 ///Runs %Dijkstra algorithm from node \c s. |
605 |
605 |
838 |
838 |
839 ///Runs Dijkstra algorithm from a given node. |
839 ///Runs Dijkstra algorithm from a given node. |
840 ///The node can be given by the \ref source function. |
840 ///The node can be given by the \ref source function. |
841 void run() |
841 void run() |
842 { |
842 { |
843 if(_source==0) throw UninitializedParameter(); |
843 if(Base::_source==0) throw UninitializedParameter(); |
844 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length); |
844 Dijkstra<Graph,LengthMap,TR> |
845 if(_pred) Dij.predMap(*(PredMap*)_pred); |
845 Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length); |
846 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); |
846 if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred); |
847 if(_dist) Dij.distMap(*(DistMap*)_dist); |
847 if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode); |
848 Dij.run(*(Node*)_source); |
848 if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist); |
|
849 Dij.run(*(Node*)Base::_source); |
849 } |
850 } |
850 |
851 |
851 ///Runs Dijkstra algorithm from the given node. |
852 ///Runs Dijkstra algorithm from the given node. |
852 |
853 |
853 ///Runs Dijkstra algorithm from the given node. |
854 ///Runs Dijkstra algorithm from the given node. |
854 ///\param s is the given source. |
855 ///\param s is the given source. |
855 void run(Node s) |
856 void run(Node s) |
856 { |
857 { |
857 _source=(void *)&s; |
858 Base::_source=(void *)&s; |
858 run(); |
859 run(); |
859 } |
860 } |
860 |
861 |
861 template<class T> |
862 template<class T> |
862 struct DefPredMapBase : public Base { |
863 struct DefPredMapBase : public Base { |
893 ///function for setting PredNodeMap type |
894 ///function for setting PredNodeMap type |
894 /// |
895 /// |
895 template<class T> |
896 template<class T> |
896 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
897 DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t) |
897 { |
898 { |
898 _predNode=(void *)&t; |
899 Base::_predNode=(void *)&t; |
899 return DijkstraWizard<DefPredNodeMapBase<T> >(*this); |
900 return DijkstraWizard<DefPredNodeMapBase<T> >(*this); |
900 } |
901 } |
901 |
902 |
902 template<class T> |
903 template<class T> |
903 struct DefDistMapBase : public Base { |
904 struct DefDistMapBase : public Base { |
913 ///function for setting DistMap type |
914 ///function for setting DistMap type |
914 /// |
915 /// |
915 template<class T> |
916 template<class T> |
916 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
917 DijkstraWizard<DefDistMapBase<T> > distMap(const T &t) |
917 { |
918 { |
918 _dist=(void *)&t; |
919 Base::_dist=(void *)&t; |
919 return DijkstraWizard<DefDistMapBase<T> >(*this); |
920 return DijkstraWizard<DefDistMapBase<T> >(*this); |
920 } |
921 } |
921 |
922 |
922 /// Sets the source node, from which the Dijkstra algorithm runs. |
923 /// Sets the source node, from which the Dijkstra algorithm runs. |
923 |
924 |
924 /// Sets the source node, from which the Dijkstra algorithm runs. |
925 /// Sets the source node, from which the Dijkstra algorithm runs. |
925 /// \param s is the source node. |
926 /// \param s is the source node. |
926 DijkstraWizard<TR> &source(Node s) |
927 DijkstraWizard<TR> &source(Node s) |
927 { |
928 { |
928 source=(void *)&s; |
929 Base::_source=(void *)&s; |
929 return *this; |
930 return *this; |
930 } |
931 } |
931 |
932 |
932 }; |
933 }; |
933 |
934 |