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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dijkstra.h
r258 r278 31 31 #include <lemon/error.h> 32 32 #include <lemon/maps.h> 33 #include <lemon/path.h> 33 34 34 35 namespace lemon { … … 200 201 ///It is also possible to change the underlying priority heap. 201 202 /// 202 ///There is also a \ref dijkstra() "function 203 ///There is also a \ref dijkstra() "functiontype interface" for the 203 204 ///%Dijkstra algorithm, which is convenient in the simplier cases and 204 205 ///it can be used easier. … … 988 989 ///arcs of the shortest paths. 989 990 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 990 typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;991 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 991 992 ///Instantiates a \ref PredMap. 992 993 … … 995 996 ///\ref PredMap. 996 997 ///\todo The digraph alone may be insufficient to initialize 997 #ifdef DOXYGEN998 998 static PredMap *createPredMap(const Digraph &g) 999 #else 1000 static PredMap *createPredMap(const Digraph &) 1001 #endif 1002 { 1003 return new PredMap(); 999 { 1000 return new PredMap(g); 1004 1001 } 1005 1002 … … 1031 1028 ///The type of the map that stores the distances of the nodes. 1032 1029 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1033 typedef NullMap<typename Digraph::Node,Value> DistMap;1030 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 1034 1031 ///Instantiates a \ref DistMap. 1035 1032 … … 1037 1034 ///\param g is the digraph, to which we would like to define 1038 1035 ///the \ref DistMap 1039 #ifdef DOXYGEN1040 1036 static DistMap *createDistMap(const Digraph &g) 1041 #else 1042 static DistMap *createDistMap(const Digraph &) 1043 #endif 1044 { 1045 return new DistMap(); 1046 } 1037 { 1038 return new DistMap(g); 1039 } 1040 1041 ///The type of the shortest paths. 1042 1043 ///The type of the shortest paths. 1044 ///It must meet the \ref concepts::Path "Path" concept. 1045 typedef lemon::Path<Digraph> Path; 1047 1046 }; 1048 1047 … … 1066 1065 //Pointer to the digraph the algorithm runs on. 1067 1066 void *_g; 1068 //Pointer to the length map 1067 //Pointer to the length map. 1069 1068 void *_length; 1070 1069 //Pointer to the map of processed nodes. … … 1074 1073 //Pointer to the map of distances. 1075 1074 void *_dist; 1076 //Pointer to the source node. 1077 Node _source; 1075 //Pointer to the shortest path to the target node. 1076 void *_path; 1077 //Pointer to the distance of the target node. 1078 void *_di; 1078 1079 1079 1080 public: … … 1081 1082 1082 1083 /// This constructor does not require parameters, therefore it initiates 1083 /// all of the attributes to default values (0, INVALID).1084 /// all of the attributes to \c 0. 1084 1085 DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0), 1085 _dist(0), _ source(INVALID) {}1086 _dist(0), _path(0), _di(0) {} 1086 1087 1087 1088 /// Constructor. 1088 1089 1089 /// This constructor requires some parameters, 1090 /// listed in the parameters list. 1091 /// Others are initiated to 0. 1090 /// This constructor requires two parameters, 1091 /// others are initiated to \c 0. 1092 1092 /// \param g The digraph the algorithm runs on. 1093 1093 /// \param l The length map. 1094 /// \param s The source node. 1095 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 1094 DijkstraWizardBase(const GR &g,const LM &l) : 1096 1095 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 1097 1096 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 1098 _processed(0), _pred(0), _dist(0), _ source(s) {}1097 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 1099 1098 1100 1099 }; 1101 1100 1102 /// Auxiliary class for the function type interface of Dijkstra algorithm. 1103 1104 /// This auxiliary class is created to implement the function type 1105 /// interface of \ref Dijkstra algorithm. It uses the functions and features 1106 /// of the plain \ref Dijkstra, but it is much simpler to use it. 1107 /// It should only be used through the \ref dijkstra() function, which makes 1108 /// it easier to use the algorithm. 1101 /// Auxiliary class for the functiontype interface of Dijkstra algorithm. 1102 1103 /// This auxiliary class is created to implement the 1104 /// \ref dijkstra() "functiontype interface" of \ref Dijkstra algorithm. 1105 /// It does not have own \ref run() method, it uses the functions 1106 /// and features of the plain \ref Dijkstra. 1109 1107 /// 1110 /// Simplicity means that the way to change the types defined 1111 /// in the traits class is based on functions that returns the new class 1112 /// and not on templatable builtin classes. 1113 /// When using the plain \ref Dijkstra 1114 /// the new class with the modified type comes from 1115 /// the original class by using the :: 1116 /// operator. In the case of \ref DijkstraWizard only 1117 /// a function have to be called, and it will 1118 /// return the needed class. 1119 /// 1120 /// It does not have own \ref run() method. When its \ref run() method 1121 /// is called, it initiates a plain \ref Dijkstra object, and calls the 1122 /// \ref Dijkstra::run() method of it. 1108 /// This class should only be used through the \ref dijkstra() function, 1109 /// which makes it easier to use the algorithm. 1123 1110 template<class TR> 1124 1111 class DijkstraWizard : public TR … … 1145 1132 ///The type of the map that indicates which nodes are processed. 1146 1133 typedef typename TR::ProcessedMap ProcessedMap; 1134 ///The type of the shortest paths 1135 typedef typename TR::Path Path; 1147 1136 ///The heap type used by the dijkstra algorithm. 1148 1137 typedef typename TR::Heap Heap; … … 1157 1146 /// Constructor that requires parameters. 1158 1147 /// These parameters will be the default values for the traits class. 1159 DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) : 1160 TR(g,l,s) {} 1148 /// \param g The digraph the algorithm runs on. 1149 /// \param l The length map. 1150 DijkstraWizard(const Digraph &g, const LengthMap &l) : 1151 TR(g,l) {} 1161 1152 1162 1153 ///Copy constructor … … 1165 1156 ~DijkstraWizard() {} 1166 1157 1167 ///Runs Dijkstra algorithm from asource node.1168 1169 /// Runs Dijkstra algorithm from a source node.1170 /// The node can be given with the \ref source() function.1171 void run( )1172 { 1173 if (Base::_source==INVALID) throw UninitializedParameter();1158 ///Runs Dijkstra algorithm from the given source node. 1159 1160 ///This method runs %Dijkstra algorithm from the given source node 1161 ///in order to compute the shortest path to each node. 1162 void run(Node s) 1163 { 1164 if (s==INVALID) throw UninitializedParameter(); 1174 1165 Dijkstra<Digraph,LengthMap,TR> 1175 dij(*reinterpret_cast<const Digraph*>(Base::_g), 1176 *reinterpret_cast<const LengthMap*>(Base::_length)); 1177 if(Base::_processed) 1178 dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1179 if(Base::_pred) 1180 dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1181 if(Base::_dist) 1182 dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1183 dij.run(Base::_source); 1184 } 1185 1186 ///Runs Dijkstra algorithm from the given node. 1187 1188 ///Runs Dijkstra algorithm from the given node. 1189 ///\param s is the given source. 1190 void run(Node s) 1191 { 1192 Base::_source=s; 1193 run(); 1194 } 1195 1196 /// Sets the source node, from which the Dijkstra algorithm runs. 1197 1198 /// Sets the source node, from which the Dijkstra algorithm runs. 1199 /// \param s is the source node. 1200 DijkstraWizard<TR> &source(Node s) 1201 { 1202 Base::_source=s; 1203 return *this; 1166 dijk(*reinterpret_cast<const Digraph*>(Base::_g), 1167 *reinterpret_cast<const LengthMap*>(Base::_length)); 1168 if (Base::_pred) 1169 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1170 if (Base::_dist) 1171 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1172 if (Base::_processed) 1173 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1174 dijk.run(s); 1175 } 1176 1177 ///Finds the shortest path between \c s and \c t. 1178 1179 ///This method runs the %Dijkstra algorithm from node \c s 1180 ///in order to compute the shortest path to node \c t 1181 ///(it stops searching when \c t is processed). 1182 /// 1183 ///\return \c true if \c t is reachable form \c s. 1184 bool run(Node s, Node t) 1185 { 1186 if (s==INVALID  t==INVALID) throw UninitializedParameter(); 1187 Dijkstra<Digraph,LengthMap,TR> 1188 dijk(*reinterpret_cast<const Digraph*>(Base::_g), 1189 *reinterpret_cast<const LengthMap*>(Base::_length)); 1190 if (Base::_pred) 1191 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1192 if (Base::_dist) 1193 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1194 if (Base::_processed) 1195 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1196 dijk.run(s,t); 1197 if (Base::_path) 1198 *reinterpret_cast<Path*>(Base::_path) = dijk.path(t); 1199 if (Base::_di) 1200 *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t); 1201 return dijk.reached(t); 1204 1202 } 1205 1203 … … 1210 1208 SetPredMapBase(const TR &b) : TR(b) {} 1211 1209 }; 1212 ///\brief \ref named templparam "Named parameter"1210 ///\brief \ref namedfuncparam "Named parameter" 1213 1211 ///for setting \ref PredMap object. 1214 1212 /// 1215 ///\ref named templparam "Named parameter"1213 ///\ref namedfuncparam "Named parameter" 1216 1214 ///for setting \ref PredMap object. 1217 1215 template<class T> … … 1220 1218 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1221 1219 return DijkstraWizard<SetPredMapBase<T> >(*this); 1220 } 1221 1222 template<class T> 1223 struct SetDistMapBase : public Base { 1224 typedef T DistMap; 1225 static DistMap *createDistMap(const Digraph &) { return 0; }; 1226 SetDistMapBase(const TR &b) : TR(b) {} 1227 }; 1228 ///\brief \ref namedfuncparam "Named parameter" 1229 ///for setting \ref DistMap object. 1230 /// 1231 ///\ref namedfuncparam "Named parameter" 1232 ///for setting \ref DistMap object. 1233 template<class T> 1234 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) 1235 { 1236 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1237 return DijkstraWizard<SetDistMapBase<T> >(*this); 1222 1238 } 1223 1239 … … 1228 1244 SetProcessedMapBase(const TR &b) : TR(b) {} 1229 1245 }; 1230 ///\brief \ref named templparam "Named parameter"1246 ///\brief \ref namedfuncparam "Named parameter" 1231 1247 ///for setting \ref ProcessedMap object. 1232 1248 /// 1233 /// \ref named templparam "Named parameter"1249 /// \ref namedfuncparam "Named parameter" 1234 1250 ///for setting \ref ProcessedMap object. 1235 1251 template<class T> … … 1241 1257 1242 1258 template<class T> 1243 struct SetDistMapBase : public Base { 1244 typedef T DistMap; 1245 static DistMap *createDistMap(const Digraph &) { return 0; }; 1246 SetDistMapBase(const TR &b) : TR(b) {} 1247 }; 1248 ///\brief \ref namedtemplparam "Named parameter" 1249 ///for setting \ref DistMap object. 1250 /// 1251 ///\ref namedtemplparam "Named parameter" 1252 ///for setting \ref DistMap object. 1259 struct SetPathBase : public Base { 1260 typedef T Path; 1261 SetPathBase(const TR &b) : TR(b) {} 1262 }; 1263 ///\brief \ref namedfuncparam "Named parameter" 1264 ///for getting the shortest path to the target node. 1265 /// 1266 ///\ref namedfuncparam "Named parameter" 1267 ///for getting the shortest path to the target node. 1253 1268 template<class T> 1254 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) 1255 { 1256 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1257 return DijkstraWizard<SetDistMapBase<T> >(*this); 1269 DijkstraWizard<SetPathBase<T> > path(const T &t) 1270 { 1271 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1272 return DijkstraWizard<SetPathBase<T> >(*this); 1273 } 1274 1275 ///\brief \ref namedfuncparam "Named parameter" 1276 ///for getting the distance of the target node. 1277 /// 1278 ///\ref namedfuncparam "Named parameter" 1279 ///for getting the distance of the target node. 1280 DijkstraWizard dist(const Value &d) 1281 { 1282 Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d)); 1283 return *this; 1258 1284 } 1259 1285 1260 1286 }; 1261 1287 1262 ///Function 1288 ///Functiontype interface for Dijkstra algorithm. 1263 1289 1264 1290 /// \ingroup shortest_path 1265 ///Function 1291 ///Functiontype interface for Dijkstra algorithm. 1266 1292 /// 1267 ///This function also has several 1268 ///\ref namedtemplfuncparam "named parameters", 1293 ///This function also has several \ref namedfuncparam "named parameters", 1269 1294 ///they are declared as the members of class \ref DijkstraWizard. 1270 ///The following 1271 ///example shows how to use these parameters. 1295 ///The following examples show how to use these parameters. 1272 1296 ///\code 1273 /// dijkstra(g,length,source).predMap(preds).run(); 1297 /// // Compute shortest path from node s to each node 1298 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); 1299 /// 1300 /// // Compute shortest path from s to t 1301 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1274 1302 ///\endcode 1275 1303 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" … … 1279 1307 template<class GR, class LM> 1280 1308 DijkstraWizard<DijkstraWizardBase<GR,LM> > 1281 dijkstra(const GR & g,const LM &l,typename GR::Node s=INVALID)1309 dijkstra(const GR &digraph, const LM &length) 1282 1310 { 1283 return DijkstraWizard<DijkstraWizardBase<GR,LM> >( g,l,s);1311 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length); 1284 1312 } 1285 1313
Note: See TracChangeset
for help on using the changeset viewer.