45 ///\brief The type of the map that stores the predecessor |
45 ///\brief The type of the map that stores the predecessor |
46 ///arcs of the %DFS paths. |
46 ///arcs of the %DFS paths. |
47 /// |
47 /// |
48 ///The type of the map that stores the predecessor |
48 ///The type of the map that stores the predecessor |
49 ///arcs of the %DFS paths. |
49 ///arcs of the %DFS paths. |
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
52 ///Instantiates a \c PredMap. |
52 ///Instantiates a \c PredMap. |
53 |
53 |
54 ///This function instantiates a \ref PredMap. |
54 ///This function instantiates a \ref PredMap. |
55 ///\param g is the digraph, to which we would like to define the |
55 ///\param g is the digraph, to which we would like to define the |
60 } |
60 } |
61 |
61 |
62 ///The type of the map that indicates which nodes are processed. |
62 ///The type of the map that indicates which nodes are processed. |
63 |
63 |
64 ///The type of the map that indicates which nodes are processed. |
64 ///The type of the map that indicates which nodes are processed. |
65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
|
66 ///By default it is a NullMap. |
66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
67 ///Instantiates a \c ProcessedMap. |
68 ///Instantiates a \c ProcessedMap. |
68 |
69 |
69 ///This function instantiates a \ref ProcessedMap. |
70 ///This function instantiates a \ref ProcessedMap. |
70 ///\param g is the digraph, to which |
71 ///\param g is the digraph, to which |
79 } |
80 } |
80 |
81 |
81 ///The type of the map that indicates which nodes are reached. |
82 ///The type of the map that indicates which nodes are reached. |
82 |
83 |
83 ///The type of the map that indicates which nodes are reached. |
84 ///The type of the map that indicates which nodes are reached. |
84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
85 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
85 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
86 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
86 ///Instantiates a \c ReachedMap. |
87 ///Instantiates a \c ReachedMap. |
87 |
88 |
88 ///This function instantiates a \ref ReachedMap. |
89 ///This function instantiates a \ref ReachedMap. |
89 ///\param g is the digraph, to which |
90 ///\param g is the digraph, to which |
94 } |
95 } |
95 |
96 |
96 ///The type of the map that stores the distances of the nodes. |
97 ///The type of the map that stores the distances of the nodes. |
97 |
98 |
98 ///The type of the map that stores the distances of the nodes. |
99 ///The type of the map that stores the distances of the nodes. |
99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
100 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
100 typedef typename Digraph::template NodeMap<int> DistMap; |
101 typedef typename Digraph::template NodeMap<int> DistMap; |
101 ///Instantiates a \c DistMap. |
102 ///Instantiates a \c DistMap. |
102 |
103 |
103 ///This function instantiates a \ref DistMap. |
104 ///This function instantiates a \ref DistMap. |
104 ///\param g is the digraph, to which we would like to define the |
105 ///\param g is the digraph, to which we would like to define the |
262 ///\brief \ref named-templ-param "Named parameter" for setting |
263 ///\brief \ref named-templ-param "Named parameter" for setting |
263 ///\c ReachedMap type. |
264 ///\c ReachedMap type. |
264 /// |
265 /// |
265 ///\ref named-templ-param "Named parameter" for setting |
266 ///\ref named-templ-param "Named parameter" for setting |
266 ///\c ReachedMap type. |
267 ///\c ReachedMap type. |
267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
268 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
268 template <class T> |
269 template <class T> |
269 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { |
270 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { |
270 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create; |
271 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create; |
271 }; |
272 }; |
272 |
273 |
282 ///\brief \ref named-templ-param "Named parameter" for setting |
283 ///\brief \ref named-templ-param "Named parameter" for setting |
283 ///\c ProcessedMap type. |
284 ///\c ProcessedMap type. |
284 /// |
285 /// |
285 ///\ref named-templ-param "Named parameter" for setting |
286 ///\ref named-templ-param "Named parameter" for setting |
286 ///\c ProcessedMap type. |
287 ///\c ProcessedMap type. |
287 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
288 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
288 template <class T> |
289 template <class T> |
289 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { |
290 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { |
290 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create; |
291 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create; |
291 }; |
292 }; |
292 |
293 |
667 ///Either \ref run(Node) "run()" or \ref start() should be called |
668 ///Either \ref run(Node) "run()" or \ref start() should be called |
668 ///before using them. |
669 ///before using them. |
669 |
670 |
670 ///@{ |
671 ///@{ |
671 |
672 |
672 ///The DFS path to a node. |
673 ///The DFS path to the given node. |
673 |
674 |
674 ///Returns the DFS path to a node. |
675 ///Returns the DFS path to the given node from the root(s). |
675 /// |
676 /// |
676 ///\warning \c t should be reached from the root(s). |
677 ///\warning \c t should be reached from the root(s). |
677 /// |
678 /// |
678 ///\pre Either \ref run(Node) "run()" or \ref init() |
679 ///\pre Either \ref run(Node) "run()" or \ref init() |
679 ///must be called before using this function. |
680 ///must be called before using this function. |
680 Path path(Node t) const { return Path(*G, *_pred, t); } |
681 Path path(Node t) const { return Path(*G, *_pred, t); } |
681 |
682 |
682 ///The distance of a node from the root(s). |
683 ///The distance of the given node from the root(s). |
683 |
684 |
684 ///Returns the distance of a node from the root(s). |
685 ///Returns the distance of the given node from the root(s). |
685 /// |
686 /// |
686 ///\warning If node \c v is not reached from the root(s), then |
687 ///\warning If node \c v is not reached from the root(s), then |
687 ///the return value of this function is undefined. |
688 ///the return value of this function is undefined. |
688 /// |
689 /// |
689 ///\pre Either \ref run(Node) "run()" or \ref init() |
690 ///\pre Either \ref run(Node) "run()" or \ref init() |
690 ///must be called before using this function. |
691 ///must be called before using this function. |
691 int dist(Node v) const { return (*_dist)[v]; } |
692 int dist(Node v) const { return (*_dist)[v]; } |
692 |
693 |
693 ///Returns the 'previous arc' of the %DFS tree for a node. |
694 ///Returns the 'previous arc' of the %DFS tree for the given node. |
694 |
695 |
695 ///This function returns the 'previous arc' of the %DFS tree for the |
696 ///This function returns the 'previous arc' of the %DFS tree for the |
696 ///node \c v, i.e. it returns the last arc of a %DFS path from a |
697 ///node \c v, i.e. it returns the last arc of a %DFS path from a |
697 ///root to \c v. It is \c INVALID if \c v is not reached from the |
698 ///root to \c v. It is \c INVALID if \c v is not reached from the |
698 ///root(s) or if \c v is a root. |
699 ///root(s) or if \c v is a root. |
699 /// |
700 /// |
700 ///The %DFS tree used here is equal to the %DFS tree used in |
701 ///The %DFS tree used here is equal to the %DFS tree used in |
701 ///\ref predNode(). |
702 ///\ref predNode() and \ref predMap(). |
702 /// |
703 /// |
703 ///\pre Either \ref run(Node) "run()" or \ref init() |
704 ///\pre Either \ref run(Node) "run()" or \ref init() |
704 ///must be called before using this function. |
705 ///must be called before using this function. |
705 Arc predArc(Node v) const { return (*_pred)[v];} |
706 Arc predArc(Node v) const { return (*_pred)[v];} |
706 |
707 |
707 ///Returns the 'previous node' of the %DFS tree. |
708 ///Returns the 'previous node' of the %DFS tree for the given node. |
708 |
709 |
709 ///This function returns the 'previous node' of the %DFS |
710 ///This function returns the 'previous node' of the %DFS |
710 ///tree for the node \c v, i.e. it returns the last but one node |
711 ///tree for the node \c v, i.e. it returns the last but one node |
711 ///from a %DFS path from a root to \c v. It is \c INVALID |
712 ///of a %DFS path from a root to \c v. It is \c INVALID |
712 ///if \c v is not reached from the root(s) or if \c v is a root. |
713 ///if \c v is not reached from the root(s) or if \c v is a root. |
713 /// |
714 /// |
714 ///The %DFS tree used here is equal to the %DFS tree used in |
715 ///The %DFS tree used here is equal to the %DFS tree used in |
715 ///\ref predArc(). |
716 ///\ref predArc() and \ref predMap(). |
716 /// |
717 /// |
717 ///\pre Either \ref run(Node) "run()" or \ref init() |
718 ///\pre Either \ref run(Node) "run()" or \ref init() |
718 ///must be called before using this function. |
719 ///must be called before using this function. |
719 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
720 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
720 G->source((*_pred)[v]); } |
721 G->source((*_pred)[v]); } |
731 |
732 |
732 ///\brief Returns a const reference to the node map that stores the |
733 ///\brief Returns a const reference to the node map that stores the |
733 ///predecessor arcs. |
734 ///predecessor arcs. |
734 /// |
735 /// |
735 ///Returns a const reference to the node map that stores the predecessor |
736 ///Returns a const reference to the node map that stores the predecessor |
736 ///arcs, which form the DFS tree. |
737 ///arcs, which form the DFS tree (forest). |
737 /// |
738 /// |
738 ///\pre Either \ref run(Node) "run()" or \ref init() |
739 ///\pre Either \ref run(Node) "run()" or \ref init() |
739 ///must be called before using this function. |
740 ///must be called before using this function. |
740 const PredMap &predMap() const { return *_pred;} |
741 const PredMap &predMap() const { return *_pred;} |
741 |
742 |
742 ///Checks if a node is reached from the root(s). |
743 ///Checks if the given node. node is reached from the root(s). |
743 |
744 |
744 ///Returns \c true if \c v is reached from the root(s). |
745 ///Returns \c true if \c v is reached from the root(s). |
745 /// |
746 /// |
746 ///\pre Either \ref run(Node) "run()" or \ref init() |
747 ///\pre Either \ref run(Node) "run()" or \ref init() |
747 ///must be called before using this function. |
748 ///must be called before using this function. |
763 ///\brief The type of the map that stores the predecessor |
764 ///\brief The type of the map that stores the predecessor |
764 ///arcs of the %DFS paths. |
765 ///arcs of the %DFS paths. |
765 /// |
766 /// |
766 ///The type of the map that stores the predecessor |
767 ///The type of the map that stores the predecessor |
767 ///arcs of the %DFS paths. |
768 ///arcs of the %DFS paths. |
768 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
769 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
769 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
770 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; |
770 ///Instantiates a PredMap. |
771 ///Instantiates a PredMap. |
771 |
772 |
772 ///This function instantiates a PredMap. |
773 ///This function instantiates a PredMap. |
773 ///\param g is the digraph, to which we would like to define the |
774 ///\param g is the digraph, to which we would like to define the |
798 } |
799 } |
799 |
800 |
800 ///The type of the map that indicates which nodes are reached. |
801 ///The type of the map that indicates which nodes are reached. |
801 |
802 |
802 ///The type of the map that indicates which nodes are reached. |
803 ///The type of the map that indicates which nodes are reached. |
803 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
804 ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. |
804 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
805 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
805 ///Instantiates a ReachedMap. |
806 ///Instantiates a ReachedMap. |
806 |
807 |
807 ///This function instantiates a ReachedMap. |
808 ///This function instantiates a ReachedMap. |
808 ///\param g is the digraph, to which |
809 ///\param g is the digraph, to which |
813 } |
814 } |
814 |
815 |
815 ///The type of the map that stores the distances of the nodes. |
816 ///The type of the map that stores the distances of the nodes. |
816 |
817 |
817 ///The type of the map that stores the distances of the nodes. |
818 ///The type of the map that stores the distances of the nodes. |
818 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
819 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. |
819 typedef typename Digraph::template NodeMap<int> DistMap; |
820 typedef typename Digraph::template NodeMap<int> DistMap; |
820 ///Instantiates a DistMap. |
821 ///Instantiates a DistMap. |
821 |
822 |
822 ///This function instantiates a DistMap. |
823 ///This function instantiates a DistMap. |
823 ///\param g is the digraph, to which we would like to define |
824 ///\param g is the digraph, to which we would like to define |
828 } |
829 } |
829 |
830 |
830 ///The type of the DFS paths. |
831 ///The type of the DFS paths. |
831 |
832 |
832 ///The type of the DFS paths. |
833 ///The type of the DFS paths. |
833 ///It must meet the \ref concepts::Path "Path" concept. |
834 ///It must conform to the \ref concepts::Path "Path" concept. |
834 typedef lemon::Path<Digraph> Path; |
835 typedef lemon::Path<Digraph> Path; |
835 }; |
836 }; |
836 |
837 |
837 /// Default traits class used by DfsWizard |
838 /// Default traits class used by DfsWizard |
838 |
839 |
839 /// To make it easier to use Dfs algorithm |
840 /// Default traits class used by DfsWizard. |
840 /// we have created a wizard class. |
841 /// \tparam GR The type of the digraph. |
841 /// This \ref DfsWizard class needs default traits, |
|
842 /// as well as the \ref Dfs class. |
|
843 /// The \ref DfsWizardBase is a class to be the default traits of the |
|
844 /// \ref DfsWizard class. |
|
845 template<class GR> |
842 template<class GR> |
846 class DfsWizardBase : public DfsWizardDefaultTraits<GR> |
843 class DfsWizardBase : public DfsWizardDefaultTraits<GR> |
847 { |
844 { |
848 |
845 |
849 typedef DfsWizardDefaultTraits<GR> Base; |
846 typedef DfsWizardDefaultTraits<GR> Base; |
897 template<class TR> |
894 template<class TR> |
898 class DfsWizard : public TR |
895 class DfsWizard : public TR |
899 { |
896 { |
900 typedef TR Base; |
897 typedef TR Base; |
901 |
898 |
902 ///The type of the digraph the algorithm runs on. |
|
903 typedef typename TR::Digraph Digraph; |
899 typedef typename TR::Digraph Digraph; |
904 |
900 |
905 typedef typename Digraph::Node Node; |
901 typedef typename Digraph::Node Node; |
906 typedef typename Digraph::NodeIt NodeIt; |
902 typedef typename Digraph::NodeIt NodeIt; |
907 typedef typename Digraph::Arc Arc; |
903 typedef typename Digraph::Arc Arc; |
908 typedef typename Digraph::OutArcIt OutArcIt; |
904 typedef typename Digraph::OutArcIt OutArcIt; |
909 |
905 |
910 ///\brief The type of the map that stores the predecessor |
|
911 ///arcs of the DFS paths. |
|
912 typedef typename TR::PredMap PredMap; |
906 typedef typename TR::PredMap PredMap; |
913 ///\brief The type of the map that stores the distances of the nodes. |
|
914 typedef typename TR::DistMap DistMap; |
907 typedef typename TR::DistMap DistMap; |
915 ///\brief The type of the map that indicates which nodes are reached. |
|
916 typedef typename TR::ReachedMap ReachedMap; |
908 typedef typename TR::ReachedMap ReachedMap; |
917 ///\brief The type of the map that indicates which nodes are processed. |
|
918 typedef typename TR::ProcessedMap ProcessedMap; |
909 typedef typename TR::ProcessedMap ProcessedMap; |
919 ///The type of the DFS paths |
|
920 typedef typename TR::Path Path; |
910 typedef typename TR::Path Path; |
921 |
911 |
922 public: |
912 public: |
923 |
913 |
924 /// Constructor. |
914 /// Constructor. |
997 struct SetPredMapBase : public Base { |
987 struct SetPredMapBase : public Base { |
998 typedef T PredMap; |
988 typedef T PredMap; |
999 static PredMap *createPredMap(const Digraph &) { return 0; }; |
989 static PredMap *createPredMap(const Digraph &) { return 0; }; |
1000 SetPredMapBase(const TR &b) : TR(b) {} |
990 SetPredMapBase(const TR &b) : TR(b) {} |
1001 }; |
991 }; |
1002 ///\brief \ref named-func-param "Named parameter" |
992 |
1003 ///for setting PredMap object. |
993 ///\brief \ref named-templ-param "Named parameter" for setting |
1004 /// |
994 ///the predecessor map. |
1005 ///\ref named-func-param "Named parameter" |
995 /// |
1006 ///for setting PredMap object. |
996 ///\ref named-templ-param "Named parameter" function for setting |
|
997 ///the map that stores the predecessor arcs of the nodes. |
1007 template<class T> |
998 template<class T> |
1008 DfsWizard<SetPredMapBase<T> > predMap(const T &t) |
999 DfsWizard<SetPredMapBase<T> > predMap(const T &t) |
1009 { |
1000 { |
1010 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1001 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1011 return DfsWizard<SetPredMapBase<T> >(*this); |
1002 return DfsWizard<SetPredMapBase<T> >(*this); |
1015 struct SetReachedMapBase : public Base { |
1006 struct SetReachedMapBase : public Base { |
1016 typedef T ReachedMap; |
1007 typedef T ReachedMap; |
1017 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1008 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1018 SetReachedMapBase(const TR &b) : TR(b) {} |
1009 SetReachedMapBase(const TR &b) : TR(b) {} |
1019 }; |
1010 }; |
1020 ///\brief \ref named-func-param "Named parameter" |
1011 |
1021 ///for setting ReachedMap object. |
1012 ///\brief \ref named-templ-param "Named parameter" for setting |
1022 /// |
1013 ///the reached map. |
1023 /// \ref named-func-param "Named parameter" |
1014 /// |
1024 ///for setting ReachedMap object. |
1015 ///\ref named-templ-param "Named parameter" function for setting |
|
1016 ///the map that indicates which nodes are reached. |
1025 template<class T> |
1017 template<class T> |
1026 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1018 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) |
1027 { |
1019 { |
1028 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1020 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1029 return DfsWizard<SetReachedMapBase<T> >(*this); |
1021 return DfsWizard<SetReachedMapBase<T> >(*this); |
1033 struct SetDistMapBase : public Base { |
1025 struct SetDistMapBase : public Base { |
1034 typedef T DistMap; |
1026 typedef T DistMap; |
1035 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1027 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1036 SetDistMapBase(const TR &b) : TR(b) {} |
1028 SetDistMapBase(const TR &b) : TR(b) {} |
1037 }; |
1029 }; |
1038 ///\brief \ref named-func-param "Named parameter" |
1030 |
1039 ///for setting DistMap object. |
1031 ///\brief \ref named-templ-param "Named parameter" for setting |
1040 /// |
1032 ///the distance map. |
1041 /// \ref named-func-param "Named parameter" |
1033 /// |
1042 ///for setting DistMap object. |
1034 ///\ref named-templ-param "Named parameter" function for setting |
|
1035 ///the map that stores the distances of the nodes calculated |
|
1036 ///by the algorithm. |
1043 template<class T> |
1037 template<class T> |
1044 DfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1038 DfsWizard<SetDistMapBase<T> > distMap(const T &t) |
1045 { |
1039 { |
1046 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1040 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1047 return DfsWizard<SetDistMapBase<T> >(*this); |
1041 return DfsWizard<SetDistMapBase<T> >(*this); |
1051 struct SetProcessedMapBase : public Base { |
1045 struct SetProcessedMapBase : public Base { |
1052 typedef T ProcessedMap; |
1046 typedef T ProcessedMap; |
1053 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1047 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1054 SetProcessedMapBase(const TR &b) : TR(b) {} |
1048 SetProcessedMapBase(const TR &b) : TR(b) {} |
1055 }; |
1049 }; |
1056 ///\brief \ref named-func-param "Named parameter" |
1050 |
1057 ///for setting ProcessedMap object. |
1051 ///\brief \ref named-func-param "Named parameter" for setting |
1058 /// |
1052 ///the processed map. |
1059 /// \ref named-func-param "Named parameter" |
1053 /// |
1060 ///for setting ProcessedMap object. |
1054 ///\ref named-templ-param "Named parameter" function for setting |
|
1055 ///the map that indicates which nodes are processed. |
1061 template<class T> |
1056 template<class T> |
1062 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1057 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) |
1063 { |
1058 { |
1064 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1059 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1065 return DfsWizard<SetProcessedMapBase<T> >(*this); |
1060 return DfsWizard<SetProcessedMapBase<T> >(*this); |