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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bfs.h
r258 r278 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/path.h> 31 32 32 33 namespace lemon { … … 116 117 ///This class provides an efficient implementation of the %BFS algorithm. 117 118 /// 118 ///There is also a \ref bfs() "function 119 ///There is also a \ref bfs() "functiontype interface" for the BFS 119 120 ///algorithm, which is convenient in the simplier cases and it can be 120 121 ///used easier. … … 842 843 ///arcs of the shortest paths. 843 844 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 844 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;845 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 845 846 ///Instantiates a \ref PredMap. 846 847 … … 849 850 ///\ref PredMap. 850 851 ///\todo The digraph alone may be insufficient to initialize 851 #ifdef DOXYGEN852 852 static PredMap *createPredMap(const Digraph &g) 853 #else 854 static PredMap *createPredMap(const Digraph &) 855 #endif 856 { 857 return new PredMap(); 853 { 854 return new PredMap(g); 858 855 } 859 856 … … 862 859 ///The type of the map that indicates which nodes are processed. 863 860 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 861 ///By default it is a NullMap. 864 862 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 865 863 ///Instantiates a \ref ProcessedMap. … … 896 894 ///The type of the map that stores the distances of the nodes. 897 895 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 898 /// 899 typedef NullMap<typename Digraph::Node,int> DistMap; 896 typedef typename Digraph::template NodeMap<int> DistMap; 900 897 ///Instantiates a \ref DistMap. 901 898 … … 903 900 ///\param g is the digraph, to which we would like to define 904 901 ///the \ref DistMap 905 #ifdef DOXYGEN906 902 static DistMap *createDistMap(const Digraph &g) 907 #else 908 static DistMap *createDistMap(const Digraph &) 909 #endif 910 { 911 return new DistMap(); 912 } 903 { 904 return new DistMap(g); 905 } 906 907 ///The type of the shortest paths. 908 909 ///The type of the shortest paths. 910 ///It must meet the \ref concepts::Path "Path" concept. 911 typedef lemon::Path<Digraph> Path; 913 912 }; 914 913 … … 940 939 //Pointer to the map of distances. 941 940 void *_dist; 942 //Pointer to the source node. 943 Node _source; 941 //Pointer to the shortest path to the target node. 942 void *_path; 943 //Pointer to the distance of the target node. 944 int *_di; 944 945 945 946 public: … … 947 948 948 949 /// This constructor does not require parameters, therefore it initiates 949 /// all of the attributes to default values (0, INVALID).950 /// all of the attributes to \c 0. 950 951 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), 951 _dist(0), _ source(INVALID) {}952 _dist(0), _path(0), _di(0) {} 952 953 953 954 /// Constructor. 954 955 955 /// This constructor requires some parameters, 956 /// listed in the parameters list. 957 /// Others are initiated to 0. 956 /// This constructor requires one parameter, 957 /// others are initiated to \c 0. 958 958 /// \param g The digraph the algorithm runs on. 959 /// \param s The source node. 960 BfsWizardBase(const GR &g, Node s=INVALID) : 959 BfsWizardBase(const GR &g) : 961 960 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 962 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}961 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 963 962 964 963 }; 965 964 966 /// Auxiliary class for the function type interface of BFS algorithm. 967 968 /// This auxiliary class is created to implement the function type 969 /// interface of \ref Bfs algorithm. It uses the functions and features 970 /// of the plain \ref Bfs, but it is much simpler to use it. 971 /// It should only be used through the \ref bfs() function, which makes 972 /// it easier to use the algorithm. 965 /// Auxiliary class for the functiontype interface of BFS algorithm. 966 967 /// This auxiliary class is created to implement the 968 /// \ref bfs() "functiontype interface" of \ref Bfs algorithm. 969 /// It does not have own \ref run() method, it uses the functions 970 /// and features of the plain \ref Bfs. 973 971 /// 974 /// Simplicity means that the way to change the types defined 975 /// in the traits class is based on functions that returns the new class 976 /// and not on templatable builtin classes. 977 /// When using the plain \ref Bfs 978 /// the new class with the modified type comes from 979 /// the original class by using the :: 980 /// operator. In the case of \ref BfsWizard only 981 /// a function have to be called, and it will 982 /// return the needed class. 983 /// 984 /// It does not have own \ref run() method. When its \ref run() method 985 /// is called, it initiates a plain \ref Bfs object, and calls the 986 /// \ref Bfs::run() method of it. 972 /// This class should only be used through the \ref bfs() function, 973 /// which makes it easier to use the algorithm. 987 974 template<class TR> 988 975 class BfsWizard : public TR … … 1007 994 ///\brief The type of the map that indicates which nodes are processed. 1008 995 typedef typename TR::ProcessedMap ProcessedMap; 996 ///The type of the shortest paths 997 typedef typename TR::Path Path; 1009 998 1010 999 public: … … 1017 1006 /// Constructor that requires parameters. 1018 1007 /// These parameters will be the default values for the traits class. 1019 BfsWizard(const Digraph &g, Node s=INVALID) : 1020 TR(g,s) {} 1008 /// \param g The digraph the algorithm runs on. 1009 BfsWizard(const Digraph &g) : 1010 TR(g) {} 1021 1011 1022 1012 ///Copy constructor … … 1025 1015 ~BfsWizard() {} 1026 1016 1027 ///Runs BFS algorithm from a source node. 1028 1029 ///Runs BFS algorithm from a source node. 1030 ///The node can be given with the \ref source() function. 1017 ///Runs BFS algorithm from the given source node. 1018 1019 ///This method runs BFS algorithm from node \c s 1020 ///in order to compute the shortest path to each node. 1021 void run(Node s) 1022 { 1023 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1024 if (Base::_pred) 1025 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1026 if (Base::_dist) 1027 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1028 if (Base::_reached) 1029 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1030 if (Base::_processed) 1031 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1032 if (s!=INVALID) 1033 alg.run(s); 1034 else 1035 alg.run(); 1036 } 1037 1038 ///Finds the shortest path between \c s and \c t. 1039 1040 ///This method runs BFS algorithm from node \c s 1041 ///in order to compute the shortest path to node \c t 1042 ///(it stops searching when \c t is processed). 1043 /// 1044 ///\return \c true if \c t is reachable form \c s. 1045 bool run(Node s, Node t) 1046 { 1047 if (s==INVALID  t==INVALID) throw UninitializedParameter(); 1048 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1049 if (Base::_pred) 1050 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1051 if (Base::_dist) 1052 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1053 if (Base::_reached) 1054 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1055 if (Base::_processed) 1056 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1057 alg.run(s,t); 1058 if (Base::_path) 1059 *reinterpret_cast<Path*>(Base::_path) = alg.path(t); 1060 if (Base::_di) 1061 *Base::_di = alg.dist(t); 1062 return alg.reached(t); 1063 } 1064 1065 ///Runs BFS algorithm to visit all nodes in the digraph. 1066 1067 ///This method runs BFS algorithm in order to compute 1068 ///the shortest path to each node. 1031 1069 void run() 1032 1070 { 1033 if(Base::_source==INVALID) throw UninitializedParameter(); 1034 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); 1035 if(Base::_reached) 1036 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); 1037 if(Base::_processed) 1038 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1039 if(Base::_pred) 1040 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1041 if(Base::_dist) 1042 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1043 alg.run(Base::_source); 1044 } 1045 1046 ///Runs BFS algorithm from the given node. 1047 1048 ///Runs BFS algorithm from the given node. 1049 ///\param s is the given source. 1050 void run(Node s) 1051 { 1052 Base::_source=s; 1053 run(); 1054 } 1055 1056 /// Sets the source node, from which the Bfs algorithm runs. 1057 1058 /// Sets the source node, from which the Bfs algorithm runs. 1059 /// \param s is the source node. 1060 BfsWizard<TR> &source(Node s) 1061 { 1062 Base::_source=s; 1063 return *this; 1071 run(INVALID); 1064 1072 } 1065 1073 … … 1070 1078 SetPredMapBase(const TR &b) : TR(b) {} 1071 1079 }; 1072 ///\brief \ref named templparam "Named parameter"1080 ///\brief \ref namedfuncparam "Named parameter" 1073 1081 ///for setting \ref PredMap object. 1074 1082 /// 1075 /// \ref namedtemplparam "Named parameter"1083 ///\ref namedfuncparam "Named parameter" 1076 1084 ///for setting \ref PredMap object. 1077 1085 template<class T> … … 1088 1096 SetReachedMapBase(const TR &b) : TR(b) {} 1089 1097 }; 1090 ///\brief \ref named templparam "Named parameter"1098 ///\brief \ref namedfuncparam "Named parameter" 1091 1099 ///for setting \ref ReachedMap object. 1092 1100 /// 1093 /// \ref named templparam "Named parameter"1101 /// \ref namedfuncparam "Named parameter" 1094 1102 ///for setting \ref ReachedMap object. 1095 1103 template<class T> … … 1098 1106 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); 1099 1107 return BfsWizard<SetReachedMapBase<T> >(*this); 1108 } 1109 1110 template<class T> 1111 struct SetDistMapBase : public Base { 1112 typedef T DistMap; 1113 static DistMap *createDistMap(const Digraph &) { return 0; }; 1114 SetDistMapBase(const TR &b) : TR(b) {} 1115 }; 1116 ///\brief \ref namedfuncparam "Named parameter" 1117 ///for setting \ref DistMap object. 1118 /// 1119 /// \ref namedfuncparam "Named parameter" 1120 ///for setting \ref DistMap object. 1121 template<class T> 1122 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1123 { 1124 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1125 return BfsWizard<SetDistMapBase<T> >(*this); 1100 1126 } 1101 1127 … … 1106 1132 SetProcessedMapBase(const TR &b) : TR(b) {} 1107 1133 }; 1108 ///\brief \ref named templparam "Named parameter"1134 ///\brief \ref namedfuncparam "Named parameter" 1109 1135 ///for setting \ref ProcessedMap object. 1110 1136 /// 1111 /// \ref named templparam "Named parameter"1137 /// \ref namedfuncparam "Named parameter" 1112 1138 ///for setting \ref ProcessedMap object. 1113 1139 template<class T> … … 1119 1145 1120 1146 template<class T> 1121 struct SetDistMapBase : public Base { 1122 typedef T DistMap; 1123 static DistMap *createDistMap(const Digraph &) { return 0; }; 1124 SetDistMapBase(const TR &b) : TR(b) {} 1125 }; 1126 ///\brief \ref namedtemplparam "Named parameter" 1127 ///for setting \ref DistMap object. 1128 /// 1129 /// \ref namedtemplparam "Named parameter" 1130 ///for setting \ref DistMap object. 1147 struct SetPathBase : public Base { 1148 typedef T Path; 1149 SetPathBase(const TR &b) : TR(b) {} 1150 }; 1151 ///\brief \ref namedfuncparam "Named parameter" 1152 ///for getting the shortest path to the target node. 1153 /// 1154 ///\ref namedfuncparam "Named parameter" 1155 ///for getting the shortest path to the target node. 1131 1156 template<class T> 1132 BfsWizard<SetDistMapBase<T> > distMap(const T &t) 1133 { 1134 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1135 return BfsWizard<SetDistMapBase<T> >(*this); 1157 BfsWizard<SetPathBase<T> > path(const T &t) 1158 { 1159 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1160 return BfsWizard<SetPathBase<T> >(*this); 1161 } 1162 1163 ///\brief \ref namedfuncparam "Named parameter" 1164 ///for getting the distance of the target node. 1165 /// 1166 ///\ref namedfuncparam "Named parameter" 1167 ///for getting the distance of the target node. 1168 BfsWizard dist(const int &d) 1169 { 1170 Base::_di=const_cast<int*>(&d); 1171 return *this; 1136 1172 } 1137 1173 1138 1174 }; 1139 1175 1140 ///Function type interface for Bfsalgorithm.1176 ///Functiontype interface for BFS algorithm. 1141 1177 1142 1178 /// \ingroup search 1143 ///Function type interface for Bfsalgorithm.1179 ///Functiontype interface for BFS algorithm. 1144 1180 /// 1145 ///This function also has several 1146 ///\ref namedtemplfuncparam "named parameters", 1181 ///This function also has several \ref namedfuncparam "named parameters", 1147 1182 ///they are declared as the members of class \ref BfsWizard. 1148 ///The following 1149 ///example shows how to use these parameters. 1183 ///The following examples show how to use these parameters. 1150 1184 ///\code 1151 /// bfs(g,source).predMap(preds).run(); 1185 /// // Compute shortest path from node s to each node 1186 /// bfs(g).predMap(preds).distMap(dists).run(s); 1187 /// 1188 /// // Compute shortest path from s to t 1189 /// bool reached = bfs(g).path(p).dist(d).run(s,t); 1152 1190 ///\endcode 1153 1191 ///\warning Don't forget to put the \ref BfsWizard::run() "run()" … … 1157 1195 template<class GR> 1158 1196 BfsWizard<BfsWizardBase<GR> > 1159 bfs(const GR & g,typename GR::Node s=INVALID)1197 bfs(const GR &digraph) 1160 1198 { 1161 return BfsWizard<BfsWizardBase<GR> >( g,s);1199 return BfsWizard<BfsWizardBase<GR> >(digraph); 1162 1200 } 1163 1201
Note: See TracChangeset
for help on using the changeset viewer.