Changeset 278:931190050520 in lemon for lemon/dfs.h
 Timestamp:
 09/22/08 15:33:23 (12 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dfs.h
r258 r278 30 30 #include <lemon/assert.h> 31 31 #include <lemon/maps.h> 32 #include <lemon/path.h> 32 33 33 34 namespace lemon { … … 117 118 ///This class provides an efficient implementation of the %DFS algorithm. 118 119 /// 119 ///There is also a \ref dfs() "function 120 ///There is also a \ref dfs() "functiontype interface" for the DFS 120 121 ///algorithm, which is convenient in the simplier cases and it can be 121 122 ///used easier. … … 776 777 ///arcs of the %DFS paths. 777 778 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 778 /// 779 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 779 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 780 780 ///Instantiates a \ref PredMap. 781 781 … … 784 784 ///\ref PredMap. 785 785 ///\todo The digraph alone may be insufficient to initialize 786 #ifdef DOXYGEN787 786 static PredMap *createPredMap(const Digraph &g) 788 #else 789 static PredMap *createPredMap(const Digraph &) 790 #endif 791 { 792 return new PredMap(); 787 { 788 return new PredMap(g); 793 789 } 794 790 … … 797 793 ///The type of the map that indicates which nodes are processed. 798 794 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 795 ///By default it is a NullMap. 799 796 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 800 797 ///Instantiates a \ref ProcessedMap. … … 831 828 ///The type of the map that stores the distances of the nodes. 832 829 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 833 /// 834 typedef NullMap<typename Digraph::Node,int> DistMap; 830 typedef typename Digraph::template NodeMap<int> DistMap; 835 831 ///Instantiates a \ref DistMap. 836 832 … … 838 834 ///\param g is the digraph, to which we would like to define 839 835 ///the \ref DistMap 840 #ifdef DOXYGEN841 836 static DistMap *createDistMap(const Digraph &g) 842 #else 843 static DistMap *createDistMap(const Digraph &) 844 #endif 845 { 846 return new DistMap(); 847 } 837 { 838 return new DistMap(g); 839 } 840 841 ///The type of the DFS paths. 842 843 ///The type of the DFS paths. 844 ///It must meet the \ref concepts::Path "Path" concept. 845 typedef lemon::Path<Digraph> Path; 848 846 }; 849 847 … … 875 873 //Pointer to the map of distances. 876 874 void *_dist; 877 //Pointer to the source node. 878 Node _source; 875 //Pointer to the DFS path to the target node. 876 void *_path; 877 //Pointer to the distance of the target node. 878 int *_di; 879 879 880 880 public: … … 882 882 883 883 /// This constructor does not require parameters, therefore it initiates 884 /// all of the attributes to default values (0, INVALID).884 /// all of the attributes to \c 0. 885 885 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 886 _dist(0), _ source(INVALID) {}886 _dist(0), _path(0), _di(0) {} 887 887 888 888 /// Constructor. 889 889 890 /// This constructor requires some parameters, 891 /// listed in the parameters list. 892 /// Others are initiated to 0. 890 /// This constructor requires one parameter, 891 /// others are initiated to \c 0. 893 892 /// \param g The digraph the algorithm runs on. 894 /// \param s The source node. 895 DfsWizardBase(const GR &g, Node s=INVALID) : 893 DfsWizardBase(const GR &g) : 896 894 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 897 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}895 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 898 896 899 897 }; 900 898 901 /// Auxiliary class for the function type interface of DFS algorithm. 902 903 /// This auxiliary class is created to implement the function type 904 /// interface of \ref Dfs algorithm. It uses the functions and features 905 /// of the plain \ref Dfs, but it is much simpler to use it. 906 /// It should only be used through the \ref dfs() function, which makes 907 /// it easier to use the algorithm. 899 /// Auxiliary class for the functiontype interface of DFS algorithm. 900 901 /// This auxiliary class is created to implement the 902 /// \ref dfs() "functiontype interface" of \ref Dfs algorithm. 903 /// It does not have own \ref run() method, it uses the functions 904 /// and features of the plain \ref Dfs. 908 905 /// 909 /// Simplicity means that the way to change the types defined 910 /// in the traits class is based on functions that returns the new class 911 /// and not on templatable builtin classes. 912 /// When using the plain \ref Dfs 913 /// the new class with the modified type comes from 914 /// the original class by using the :: 915 /// operator. In the case of \ref DfsWizard only 916 /// a function have to be called, and it will 917 /// return the needed class. 918 /// 919 /// It does not have own \ref run() method. When its \ref run() method 920 /// is called, it initiates a plain \ref Dfs object, and calls the 921 /// \ref Dfs::run() method of it. 906 /// This class should only be used through the \ref dfs() function, 907 /// which makes it easier to use the algorithm. 922 908 template<class TR> 923 909 class DfsWizard : public TR … … 934 920 935 921 ///\brief The type of the map that stores the predecessor 936 ///arcs of the shortestpaths.922 ///arcs of the DFS paths. 937 923 typedef typename TR::PredMap PredMap; 938 924 ///\brief The type of the map that stores the distances of the nodes. … … 942 928 ///\brief The type of the map that indicates which nodes are processed. 943 929 typedef typename TR::ProcessedMap ProcessedMap; 930 ///The type of the DFS paths 931 typedef typename TR::Path Path; 944 932 945 933 public: … … 952 940 /// Constructor that requires parameters. 953 941 /// These parameters will be the default values for the traits class. 954 DfsWizard(const Digraph &g, Node s=INVALID) : 955 TR(g,s) {} 942 /// \param g The digraph the algorithm runs on. 943 DfsWizard(const Digraph &g) : 944 TR(g) {} 956 945 957 946 ///Copy constructor … … 960 949 ~DfsWizard() {} 961 950 962 ///Runs DFS algorithm from a source node. 963 964 ///Runs DFS algorithm from a source node. 965 ///The node can be given with the \ref source() function. 951 ///Runs DFS algorithm from the given source node. 952 953 ///This method runs DFS algorithm from node \c s 954 ///in order to compute the DFS path to each node. 955 void run(Node s) 956 { 957 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 958 if (Base::_pred) 959 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 960 if (Base::_dist) 961 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 962 if (Base::_reached) 963 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 964 if (Base::_processed) 965 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 966 if (s!=INVALID) 967 alg.run(s); 968 else 969 alg.run(); 970 } 971 972 ///Finds the DFS path between \c s and \c t. 973 974 ///This method runs DFS algorithm from node \c s 975 ///in order to compute the DFS path to node \c t 976 ///(it stops searching when \c t is processed). 977 /// 978 ///\return \c true if \c t is reachable form \c s. 979 bool run(Node s, Node t) 980 { 981 if (s==INVALID  t==INVALID) throw UninitializedParameter(); 982 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 983 if (Base::_pred) 984 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 985 if (Base::_dist) 986 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 987 if (Base::_reached) 988 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 989 if (Base::_processed) 990 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 991 alg.run(s,t); 992 if (Base::_path) 993 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 994 if (Base::_di) 995 *Base::_di = alg.dist(t); 996 return alg.reached(t); 997 } 998 999 ///Runs DFS algorithm to visit all nodes in the digraph. 1000 1001 ///This method runs DFS algorithm in order to compute 1002 ///the DFS path to each node. 966 1003 void run() 967 1004 { 968 if(Base::_source==INVALID) throw UninitializedParameter(); 969 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 970 if(Base::_reached) 971 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 972 if(Base::_processed) 973 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 974 if(Base::_pred) 975 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 976 if(Base::_dist) 977 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 978 alg.run(Base::_source); 979 } 980 981 ///Runs DFS algorithm from the given node. 982 983 ///Runs DFS algorithm from the given node. 984 ///\param s is the given source. 985 void run(Node s) 986 { 987 Base::_source=s; 988 run(); 989 } 990 991 /// Sets the source node, from which the Dfs algorithm runs. 992 993 /// Sets the source node, from which the Dfs algorithm runs. 994 /// \param s is the source node. 995 DfsWizard<TR> &source(Node s) 996 { 997 Base::_source=s; 998 return *this; 1005 run(INVALID); 999 1006 } 1000 1007 … … 1005 1012 SetPredMapBase(const TR &b) : TR(b) {} 1006 1013 }; 1007 ///\brief \ref named templparam "Named parameter"1014 ///\brief \ref namedfuncparam "Named parameter" 1008 1015 ///for setting \ref PredMap object. 1009 1016 /// 1010 ///\ref named templparam "Named parameter"1017 ///\ref namedfuncparam "Named parameter" 1011 1018 ///for setting \ref PredMap object. 1012 1019 template<class T> … … 1023 1030 SetReachedMapBase(const TR &b) : TR(b) {} 1024 1031 }; 1025 ///\brief \ref named templparam "Named parameter"1032 ///\brief \ref namedfuncparam "Named parameter" 1026 1033 ///for setting \ref ReachedMap object. 1027 1034 /// 1028 /// \ref named templparam "Named parameter"1035 /// \ref namedfuncparam "Named parameter" 1029 1036 ///for setting \ref ReachedMap object. 1030 1037 template<class T> … … 1033 1040 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1034 1041 return DfsWizard<SetReachedMapBase<T> >(*this); 1042 } 1043 1044 template<class T> 1045 struct SetDistMapBase : public Base { 1046 typedef T DistMap; 1047 static DistMap *createDistMap(const Digraph &) { return 0; }; 1048 SetDistMapBase(const TR &b) : TR(b) {} 1049 }; 1050 ///\brief \ref namedfuncparam "Named parameter" 1051 ///for setting \ref DistMap object. 1052 /// 1053 /// \ref namedfuncparam "Named parameter" 1054 ///for setting \ref DistMap object. 1055 template<class T> 1056 DfsWizard<SetDistMapBase<T> > distMap(const T &t) 1057 { 1058 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1059 return DfsWizard<SetDistMapBase<T> >(*this); 1035 1060 } 1036 1061 … … 1041 1066 SetProcessedMapBase(const TR &b) : TR(b) {} 1042 1067 }; 1043 ///\brief \ref named templparam "Named parameter"1068 ///\brief \ref namedfuncparam "Named parameter" 1044 1069 ///for setting \ref ProcessedMap object. 1045 1070 /// 1046 /// \ref named templparam "Named parameter"1071 /// \ref namedfuncparam "Named parameter" 1047 1072 ///for setting \ref ProcessedMap object. 1048 1073 template<class T> … … 1054 1079 1055 1080 template<class T> 1056 struct SetDistMapBase : public Base { 1057 typedef T DistMap; 1058 static DistMap *createDistMap(const Digraph &) { return 0; }; 1059 SetDistMapBase(const TR &b) : TR(b) {} 1060 }; 1061 ///\brief \ref namedtemplparam "Named parameter" 1062 ///for setting \ref DistMap object. 1063 /// 1064 ///\ref namedtemplparam "Named parameter" 1065 ///for setting \ref DistMap object. 1081 struct SetPathBase : public Base { 1082 typedef T Path; 1083 SetPathBase(const TR &b) : TR(b) {} 1084 }; 1085 ///\brief \ref namedfuncparam "Named parameter" 1086 ///for getting the DFS path to the target node. 1087 /// 1088 ///\ref namedfuncparam "Named parameter" 1089 ///for getting the DFS path to the target node. 1066 1090 template<class T> 1067 DfsWizard<SetDistMapBase<T> > distMap(const T &t) 1068 { 1069 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1070 return DfsWizard<SetDistMapBase<T> >(*this); 1091 DfsWizard<SetPathBase<T> > path(const T &t) 1092 { 1093 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1094 return DfsWizard<SetPathBase<T> >(*this); 1095 } 1096 1097 ///\brief \ref namedfuncparam "Named parameter" 1098 ///for getting the distance of the target node. 1099 /// 1100 ///\ref namedfuncparam "Named parameter" 1101 ///for getting the distance of the target node. 1102 DfsWizard dist(const int &d) 1103 { 1104 Base::_di=const_cast<int*>(&d); 1105 return *this; 1071 1106 } 1072 1107 1073 1108 }; 1074 1109 1075 ///Function type interface for Dfsalgorithm.1110 ///Functiontype interface for DFS algorithm. 1076 1111 1077 1112 ///\ingroup search 1078 ///Function type interface for Dfsalgorithm.1113 ///Functiontype interface for DFS algorithm. 1079 1114 /// 1080 ///This function also has several 1081 ///\ref namedtemplfuncparam "named parameters", 1115 ///This function also has several \ref namedfuncparam "named parameters", 1082 1116 ///they are declared as the members of class \ref DfsWizard. 1083 ///The following 1084 ///example shows how to use these parameters. 1117 ///The following examples show how to use these parameters. 1085 1118 ///\code 1086 /// dfs(g,source).predMap(preds).run(); 1119 /// // Compute the DFS tree 1120 /// dfs(g).predMap(preds).distMap(dists).run(s); 1121 /// 1122 /// // Compute the DFS path from s to t 1123 /// bool reached = dfs(g).path(p).dist(d).run(s,t); 1087 1124 ///\endcode 1125 1088 1126 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1089 1127 ///to the end of the parameter list. … … 1092 1130 template<class GR> 1093 1131 DfsWizard<DfsWizardBase<GR> > 1094 dfs(const GR & g,typename GR::Node s=INVALID)1132 dfs(const GR &digraph) 1095 1133 { 1096 return DfsWizard<DfsWizardBase<GR> >( g,s);1134 return DfsWizard<DfsWizardBase<GR> >(digraph); 1097 1135 } 1098 1136
Note: See TracChangeset
for help on using the changeset viewer.