Changeset 281:e9b4fbe163f5 in lemon for lemon/dfs.h
 Timestamp:
 09/26/08 09:52:28 (11 years ago)
 Branch:
 default
 Parents:
 280:e7f8647ce760 (diff), 279:6307bbbf285b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.  Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dfs.h
r278 r281 56 56 ///\param g is the digraph, to which we would like to define the 57 57 ///\ref PredMap. 58 ///\todo The digraph alone may be insufficient to initialize59 58 static PredMap *createPredMap(const Digraph &g) 60 59 { … … 66 65 ///The type of the map that indicates which nodes are processed. 67 66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 68 ///By default it is a NullMap.69 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 70 68 ///Instantiates a \ref ProcessedMap. … … 197 195 int _stack_head; 198 196 199 ///Creates the maps if necessary. 200 ///\todo Better memory allocation (instead of new). 197 //Creates the maps if necessary. 201 198 void create_maps() 202 199 { … … 783 780 ///\param g is the digraph, to which we would like to define the 784 781 ///\ref PredMap. 785 ///\todo The digraph alone may be insufficient to initialize786 782 static PredMap *createPredMap(const Digraph &g) 787 783 { … … 1318 1314 int _stack_head; 1319 1315 1320 ///Creates the maps if necessary. 1321 ///\todo Better memory allocation (instead of new). 1316 //Creates the maps if necessary. 1322 1317 void create_maps() { 1323 1318 if(!_reached) { 
lemon/dfs.h
r280 r281 30 30 #include <lemon/assert.h> 31 31 #include <lemon/maps.h> 32 #include <lemon/path.h> 32 33 33 34 namespace lemon { … … 115 116 ///This class provides an efficient implementation of the %DFS algorithm. 116 117 /// 117 ///There is also a \ref dfs() "function 118 ///There is also a \ref dfs() "functiontype interface" for the DFS 118 119 ///algorithm, which is convenient in the simplier cases and it can be 119 120 ///used easier. … … 773 774 ///arcs of the %DFS paths. 774 775 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 775 /// 776 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap; 776 typedef typename Digraph::template NodeMap<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 DOXYGEN783 782 static PredMap *createPredMap(const Digraph &g) 784 #else 785 static PredMap *createPredMap(const Digraph &) 786 #endif 787 { 788 return new PredMap(); 783 { 784 return new PredMap(g); 789 785 } 790 786 … … 793 789 ///The type of the map that indicates which nodes are processed. 794 790 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 791 ///By default it is a NullMap. 795 792 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 796 793 ///Instantiates a \ref ProcessedMap. … … 827 824 ///The type of the map that stores the distances of the nodes. 828 825 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 829 /// 830 typedef NullMap<typename Digraph::Node,int> DistMap; 826 typedef typename Digraph::template NodeMap<int> DistMap; 831 827 ///Instantiates a \ref DistMap. 832 828 … … 834 830 ///\param g is the digraph, to which we would like to define 835 831 ///the \ref DistMap 836 #ifdef DOXYGEN837 832 static DistMap *createDistMap(const Digraph &g) 838 #else 839 static DistMap *createDistMap(const Digraph &) 840 #endif 841 { 842 return new DistMap(); 843 } 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; 844 842 }; 845 843 … … 871 869 //Pointer to the map of distances. 872 870 void *_dist; 873 //Pointer to the source node. 874 Node _source; 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; 875 875 876 876 public: … … 878 878 879 879 /// This constructor does not require parameters, therefore it initiates 880 /// all of the attributes to default values (0, INVALID).880 /// all of the attributes to \c 0. 881 881 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 882 _dist(0), _ source(INVALID) {}882 _dist(0), _path(0), _di(0) {} 883 883 884 884 /// Constructor. 885 885 886 /// This constructor requires some parameters, 887 /// listed in the parameters list. 888 /// Others are initiated to 0. 886 /// This constructor requires one parameter, 887 /// others are initiated to \c 0. 889 888 /// \param g The digraph the algorithm runs on. 890 /// \param s The source node. 891 DfsWizardBase(const GR &g, Node s=INVALID) : 889 DfsWizardBase(const GR &g) : 892 890 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 893 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}891 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 894 892 895 893 }; 896 894 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. 895 /// Auxiliary class for the functiontype interface of DFS algorithm. 896 897 /// This auxiliary class is created to implement the 898 /// \ref dfs() "functiontype 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. 904 901 /// 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 builtin 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. 902 /// This class should only be used through the \ref dfs() function, 903 /// which makes it easier to use the algorithm. 918 904 template<class TR> 919 905 class DfsWizard : public TR … … 930 916 931 917 ///\brief The type of the map that stores the predecessor 932 ///arcs of the shortestpaths.918 ///arcs of the DFS paths. 933 919 typedef typename TR::PredMap PredMap; 934 920 ///\brief The type of the map that stores the distances of the nodes. … … 938 924 ///\brief The type of the map that indicates which nodes are processed. 939 925 typedef typename TR::ProcessedMap ProcessedMap; 926 ///The type of the DFS paths 927 typedef typename TR::Path Path; 940 928 941 929 public: … … 948 936 /// Constructor that requires parameters. 949 937 /// These parameters will be the default values for the traits class. 950 DfsWizard(const Digraph &g, Node s=INVALID) : 951 TR(g,s) {} 938 /// \param g The digraph the algorithm runs on. 939 DfsWizard(const Digraph &g) : 940 TR(g) {} 952 941 953 942 ///Copy constructor … … 956 945 ~DfsWizard() {} 957 946 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. 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. 951 void run(Node s) 952 { 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. 962 999 void run() 963 1000 { 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. 981 void run(Node s) 982 { 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; 1001 run(INVALID); 995 1002 } 996 1003 … … 1001 1008 SetPredMapBase(const TR &b) : TR(b) {} 1002 1009 }; 1003 ///\brief \ref named templparam "Named parameter"1010 ///\brief \ref namedfuncparam "Named parameter" 1004 1011 ///for setting \ref PredMap object. 1005 1012 /// 1006 ///\ref named templparam "Named parameter"1013 ///\ref namedfuncparam "Named parameter" 1007 1014 ///for setting \ref PredMap object. 1008 1015 template<class T> … … 1019 1026 SetReachedMapBase(const TR &b) : TR(b) {} 1020 1027 }; 1021 ///\brief \ref named templparam "Named parameter"1028 ///\brief \ref namedfuncparam "Named parameter" 1022 1029 ///for setting \ref ReachedMap object. 1023 1030 /// 1024 /// \ref named templparam "Named parameter"1031 /// \ref namedfuncparam "Named parameter" 1025 1032 ///for setting \ref ReachedMap object. 1026 1033 template<class T> … … 1029 1036 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1030 1037 return DfsWizard<SetReachedMapBase<T> >(*this); 1038 } 1039 1040 template<class T> 1041 struct SetDistMapBase : public Base { 1042 typedef T DistMap; 1043 static DistMap *createDistMap(const Digraph &) { return 0; }; 1044 SetDistMapBase(const TR &b) : TR(b) {} 1045 }; 1046 ///\brief \ref namedfuncparam "Named parameter" 1047 ///for setting \ref DistMap object. 1048 /// 1049 /// \ref namedfuncparam "Named parameter" 1050 ///for setting \ref DistMap object. 1051 template<class T> 1052 DfsWizard<SetDistMapBase<T> > distMap(const T &t) 1053 { 1054 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1055 return DfsWizard<SetDistMapBase<T> >(*this); 1031 1056 } 1032 1057 … … 1037 1062 SetProcessedMapBase(const TR &b) : TR(b) {} 1038 1063 }; 1039 ///\brief \ref named templparam "Named parameter"1064 ///\brief \ref namedfuncparam "Named parameter" 1040 1065 ///for setting \ref ProcessedMap object. 1041 1066 /// 1042 /// \ref named templparam "Named parameter"1067 /// \ref namedfuncparam "Named parameter" 1043 1068 ///for setting \ref ProcessedMap object. 1044 1069 template<class T> … … 1050 1075 1051 1076 template<class T> 1052 struct SetDistMapBase : public Base { 1053 typedef T DistMap; 1054 static DistMap *createDistMap(const Digraph &) { return 0; }; 1055 SetDistMapBase(const TR &b) : TR(b) {} 1056 }; 1057 ///\brief \ref namedtemplparam "Named parameter" 1058 ///for setting \ref DistMap object. 1059 /// 1060 ///\ref namedtemplparam "Named parameter" 1061 ///for setting \ref DistMap object. 1077 struct SetPathBase : public Base { 1078 typedef T Path; 1079 SetPathBase(const TR &b) : TR(b) {} 1080 }; 1081 ///\brief \ref namedfuncparam "Named parameter" 1082 ///for getting the DFS path to the target node. 1083 /// 1084 ///\ref namedfuncparam "Named parameter" 1085 ///for getting the DFS path to the target node. 1062 1086 template<class T> 1063 DfsWizard<SetDistMapBase<T> > distMap(const T &t) 1064 { 1065 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1066 return DfsWizard<SetDistMapBase<T> >(*this); 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 namedfuncparam "Named parameter" 1094 ///for getting the distance of the target node. 1095 /// 1096 ///\ref namedfuncparam "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; 1067 1102 } 1068 1103 1069 1104 }; 1070 1105 1071 ///Function type interface for Dfsalgorithm.1106 ///Functiontype interface for DFS algorithm. 1072 1107 1073 1108 ///\ingroup search 1074 ///Function type interface for Dfsalgorithm.1109 ///Functiontype interface for DFS algorithm. 1075 1110 /// 1076 ///This function also has several 1077 ///\ref namedtemplfuncparam "named parameters", 1111 ///This function also has several \ref namedfuncparam "named parameters", 1078 1112 ///they are declared as the members of class \ref DfsWizard. 1079 ///The following 1080 ///example shows how to use these parameters. 1113 ///The following examples show how to use these parameters. 1081 1114 ///\code 1082 /// dfs(g,source).predMap(preds).run(); 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); 1083 1120 ///\endcode 1121 1084 1122 ///\warning Don't forget to put the \ref DfsWizard::run() "run()" 1085 1123 ///to the end of the parameter list. … … 1088 1126 template<class GR> 1089 1127 DfsWizard<DfsWizardBase<GR> > 1090 dfs(const GR & g,typename GR::Node s=INVALID)1128 dfs(const GR &digraph) 1091 1129 { 1092 return DfsWizard<DfsWizardBase<GR> >( g,s);1130 return DfsWizard<DfsWizardBase<GR> >(digraph); 1093 1131 } 1094 1132
Note: See TracChangeset
for help on using the changeset viewer.