Changes in lemon/dfs.h [278:931190050520:258:0310c8984732] in lemon-1.2
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/dfs.h
r278 r258 30 30 #include <lemon/assert.h> 31 31 #include <lemon/maps.h> 32 #include <lemon/path.h>33 32 34 33 namespace lemon { … … 118 117 ///This class provides an efficient implementation of the %DFS algorithm. 119 118 /// 120 ///There is also a \ref dfs() "function -type interface" for the DFS119 ///There is also a \ref dfs() "function type interface" for the DFS 121 120 ///algorithm, which is convenient in the simplier cases and it can be 122 121 ///used easier. … … 777 776 ///arcs of the %DFS paths. 778 777 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 779 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 778 /// 779 typedef NullMap<typename Digraph::Node,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 DOXYGEN 786 787 static PredMap *createPredMap(const Digraph &g) 787 { 788 return new PredMap(g); 788 #else 789 static PredMap *createPredMap(const Digraph &) 790 #endif 791 { 792 return new PredMap(); 789 793 } 790 794 … … 793 797 ///The type of the map that indicates which nodes are processed. 794 798 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 795 ///By default it is a NullMap.796 799 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 797 800 ///Instantiates a \ref ProcessedMap. … … 828 831 ///The type of the map that stores the distances of the nodes. 829 832 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 830 typedef typename Digraph::template NodeMap<int> DistMap; 833 /// 834 typedef NullMap<typename Digraph::Node,int> DistMap; 831 835 ///Instantiates a \ref DistMap. 832 836 … … 834 838 ///\param g is the digraph, to which we would like to define 835 839 ///the \ref DistMap 840 #ifdef DOXYGEN 836 841 static DistMap *createDistMap(const Digraph &g) 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; 842 #else 843 static DistMap *createDistMap(const Digraph &) 844 #endif 845 { 846 return new DistMap(); 847 } 846 848 }; 847 849 … … 873 875 //Pointer to the map of distances. 874 876 void *_dist; 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; 877 //Pointer to the source node. 878 Node _source; 879 879 880 880 public: … … 882 882 883 883 /// This constructor does not require parameters, therefore it initiates 884 /// all of the attributes to \c 0.884 /// all of the attributes to default values (0, INVALID). 885 885 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 886 _dist(0), _ path(0), _di(0) {}886 _dist(0), _source(INVALID) {} 887 887 888 888 /// Constructor. 889 889 890 /// This constructor requires one parameter, 891 /// others are initiated to \c 0. 890 /// This constructor requires some parameters, 891 /// listed in the parameters list. 892 /// Others are initiated to 0. 892 893 /// \param g The digraph the algorithm runs on. 893 DfsWizardBase(const GR &g) : 894 /// \param s The source node. 895 DfsWizardBase(const GR &g, Node s=INVALID) : 894 896 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 895 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}897 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} 896 898 897 899 }; 898 900 899 /// Auxiliary class for the function-type interface of DFS algorithm. 900 901 /// This auxiliary class is created to implement the 902 /// \ref dfs() "function-type 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. 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. 905 908 /// 906 /// This class should only be used through the \ref dfs() function, 907 /// which makes it easier to use the algorithm. 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 built-in 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. 908 922 template<class TR> 909 923 class DfsWizard : public TR … … 920 934 921 935 ///\brief The type of the map that stores the predecessor 922 ///arcs of the DFSpaths.936 ///arcs of the shortest paths. 923 937 typedef typename TR::PredMap PredMap; 924 938 ///\brief The type of the map that stores the distances of the nodes. … … 928 942 ///\brief The type of the map that indicates which nodes are processed. 929 943 typedef typename TR::ProcessedMap ProcessedMap; 930 ///The type of the DFS paths931 typedef typename TR::Path Path;932 944 933 945 public: … … 940 952 /// Constructor that requires parameters. 941 953 /// These parameters will be the default values for the traits class. 942 /// \param g The digraph the algorithm runs on. 943 DfsWizard(const Digraph &g) : 944 TR(g) {} 954 DfsWizard(const Digraph &g, Node s=INVALID) : 955 TR(g,s) {} 945 956 946 957 ///Copy constructor … … 949 960 ~DfsWizard() {} 950 961 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. 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. 966 void run() 967 { 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. 955 985 void run(Node s) 956 986 { 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. 1003 void run() 1004 { 1005 run(INVALID); 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; 1006 999 } 1007 1000 … … 1012 1005 SetPredMapBase(const TR &b) : TR(b) {} 1013 1006 }; 1014 ///\brief \ref named- func-param "Named parameter"1007 ///\brief \ref named-templ-param "Named parameter" 1015 1008 ///for setting \ref PredMap object. 1016 1009 /// 1017 ///\ref named- func-param "Named parameter"1010 ///\ref named-templ-param "Named parameter" 1018 1011 ///for setting \ref PredMap object. 1019 1012 template<class T> … … 1030 1023 SetReachedMapBase(const TR &b) : TR(b) {} 1031 1024 }; 1032 ///\brief \ref named- func-param "Named parameter"1025 ///\brief \ref named-templ-param "Named parameter" 1033 1026 ///for setting \ref ReachedMap object. 1034 1027 /// 1035 /// \ref named- func-param "Named parameter"1028 /// \ref named-templ-param "Named parameter" 1036 1029 ///for setting \ref ReachedMap object. 1037 1030 template<class T> … … 1040 1033 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1041 1034 return DfsWizard<SetReachedMapBase<T> >(*this); 1035 } 1036 1037 template<class T> 1038 struct SetProcessedMapBase : public Base { 1039 typedef T ProcessedMap; 1040 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; 1041 SetProcessedMapBase(const TR &b) : TR(b) {} 1042 }; 1043 ///\brief \ref named-templ-param "Named parameter" 1044 ///for setting \ref ProcessedMap object. 1045 /// 1046 /// \ref named-templ-param "Named parameter" 1047 ///for setting \ref ProcessedMap object. 1048 template<class T> 1049 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) 1050 { 1051 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); 1052 return DfsWizard<SetProcessedMapBase<T> >(*this); 1042 1053 } 1043 1054 … … 1048 1059 SetDistMapBase(const TR &b) : TR(b) {} 1049 1060 }; 1050 ///\brief \ref named- func-param "Named parameter"1061 ///\brief \ref named-templ-param "Named parameter" 1051 1062 ///for setting \ref DistMap object. 1052 1063 /// 1053 /// \ref named-func-param "Named parameter"1064 ///\ref named-templ-param "Named parameter" 1054 1065 ///for setting \ref DistMap object. 1055 1066 template<class T> … … 1060 1071 } 1061 1072 1062 template<class T>1063 struct SetProcessedMapBase : public Base {1064 typedef T ProcessedMap;1065 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };1066 SetProcessedMapBase(const TR &b) : TR(b) {}1067 };1068 ///\brief \ref named-func-param "Named parameter"1069 ///for setting \ref ProcessedMap object.1070 ///1071 /// \ref named-func-param "Named parameter"1072 ///for setting \ref ProcessedMap object.1073 template<class T>1074 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)1075 {1076 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));1077 return DfsWizard<SetProcessedMapBase<T> >(*this);1078 }1079 1080 template<class T>1081 struct SetPathBase : public Base {1082 typedef T Path;1083 SetPathBase(const TR &b) : TR(b) {}1084 };1085 ///\brief \ref named-func-param "Named parameter"1086 ///for getting the DFS path to the target node.1087 ///1088 ///\ref named-func-param "Named parameter"1089 ///for getting the DFS path to the target node.1090 template<class T>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 named-func-param "Named parameter"1098 ///for getting the distance of the target node.1099 ///1100 ///\ref named-func-param "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;1106 }1107 1108 1073 }; 1109 1074 1110 ///Function -type interface for DFSalgorithm.1075 ///Function type interface for Dfs algorithm. 1111 1076 1112 1077 ///\ingroup search 1113 ///Function -type interface for DFSalgorithm.1078 ///Function type interface for Dfs algorithm. 1114 1079 /// 1115 ///This function also has several \ref named-func-param "named parameters", 1080 ///This function also has several 1081 ///\ref named-templ-func-param "named parameters", 1116 1082 ///they are declared as the members of class \ref DfsWizard. 1117 ///The following examples show how to use these parameters. 1083 ///The following 1084 ///example shows how to use these parameters. 1118 1085 ///\code 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); 1086 /// dfs(g,source).predMap(preds).run(); 1124 1087 ///\endcode 1125 1126 1088 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1127 1089 ///to the end of the parameter list. … … 1130 1092 template<class GR> 1131 1093 DfsWizard<DfsWizardBase<GR> > 1132 dfs(const GR & digraph)1094 dfs(const GR &g,typename GR::Node s=INVALID) 1133 1095 { 1134 return DfsWizard<DfsWizardBase<GR> >( digraph);1096 return DfsWizard<DfsWizardBase<GR> >(g,s); 1135 1097 } 1136 1098
Note: See TracChangeset
for help on using the changeset viewer.