equal
deleted
inserted
replaced
598 /// |
598 /// |
599 ///\pre init() must be called and at least one node should be added |
599 ///\pre init() must be called and at least one node should be added |
600 ///with addSource() before using this function. |
600 ///with addSource() before using this function. |
601 /// |
601 /// |
602 ///\param nm must be a bool (or convertible) edge map. The algorithm |
602 ///\param nm must be a bool (or convertible) edge map. The algorithm |
603 ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>. |
603 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>. |
604 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map, |
604 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map, |
605 ///not a node map. |
605 ///not a node map. |
606 template<class NM> |
606 template<class NM> |
607 void start(const NM &nm) |
607 void start(const NM &nm) |
608 { |
608 { |
609 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); |
609 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); |
661 ///@{ |
661 ///@{ |
662 |
662 |
663 ///Copies the path to \c t on the DFS tree into \c p |
663 ///Copies the path to \c t on the DFS tree into \c p |
664 |
664 |
665 ///This function copies the path on the DFS tree to \c t into \c p. |
665 ///This function copies the path on the DFS tree to \c t into \c p. |
666 ///If it \c \t is a source itself or unreachable, then it does not |
666 ///If \c t is a source itself or unreachable, then it does not |
667 ///alter \c p. |
667 ///alter \c p. |
668 ///\todo Is it the right way to handle unreachable nodes? |
668 ///\todo Is this the right way to handle unreachable nodes? |
|
669 /// |
669 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
670 ///\return Returns \c true if a path to \c t was actually copied to \c p, |
670 ///\c false otherwise. |
671 ///\c false otherwise. |
671 ///\sa DirPath |
672 ///\sa DirPath |
672 template<class P> |
673 template<class P> |
673 bool getPath(P &p,Node t) |
674 bool getPath(P &p,Node t) |
685 |
686 |
686 ///The distance of a node from the root(s). |
687 ///The distance of a node from the root(s). |
687 |
688 |
688 ///Returns the distance of a node from the root(s). |
689 ///Returns the distance of a node from the root(s). |
689 ///\pre \ref run() must be called before using this function. |
690 ///\pre \ref run() must be called before using this function. |
690 ///\warning If node \c v in unreachable from the root(s) the return value |
691 ///\warning If node \c v is unreachable from the root(s) then the return value |
691 ///of this funcion is undefined. |
692 ///of this funcion is undefined. |
692 int dist(Node v) const { return (*_dist)[v]; } |
693 int dist(Node v) const { return (*_dist)[v]; } |
693 |
694 |
694 ///Returns the 'previous edge' of the %DFS tree. |
695 ///Returns the 'previous edge' of the %DFS tree. |
695 |
696 |
742 // ///\pre \ref run() must be called before using this function. |
743 // ///\pre \ref run() must be called before using this function. |
743 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
744 // const PredNodeMap &predNodeMap() const { return *_predNode;} |
744 |
745 |
745 ///Checks if a node is reachable from the root. |
746 ///Checks if a node is reachable from the root. |
746 |
747 |
747 ///Returns \c true if \c v is reachable from the root. |
748 ///Returns \c true if \c v is reachable from the root(s). |
748 ///\warning The source nodes are inditated as unreached. |
749 ///\warning The source nodes are inditated as unreachable. |
749 ///\pre Either \ref run() or \ref start() |
750 ///\pre Either \ref run() or \ref start() |
750 ///must be called before using this function. |
751 ///must be called before using this function. |
751 /// |
752 /// |
752 bool reached(Node v) { return (*_reached)[v]; } |
753 bool reached(Node v) { return (*_reached)[v]; } |
753 |
754 |
914 /// operator. In the case of \ref DfsWizard only |
915 /// operator. In the case of \ref DfsWizard only |
915 /// a function have to be called and it will |
916 /// a function have to be called and it will |
916 /// return the needed class. |
917 /// return the needed class. |
917 /// |
918 /// |
918 /// It does not have own \ref run method. When its \ref run method is called |
919 /// It does not have own \ref run method. When its \ref run method is called |
919 /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run |
920 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run |
920 /// method of it. |
921 /// method of it. |
921 template<class TR> |
922 template<class TR> |
922 class DfsWizard : public TR |
923 class DfsWizard : public TR |
923 { |
924 { |
924 typedef TR Base; |
925 typedef TR Base; |