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