Changeset 281:e9b4fbe163f5 in lemon for lemon/dijkstra.h
 Timestamp:
 09/26/08 09:52:28 (14 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/dijkstra.h
r278 r281 145 145 ///\param g is the digraph, to which we would like to define the 146 146 ///\ref PredMap. 147 ///\todo The digraph alone may be insufficient for the initialization148 147 static PredMap *createPredMap(const Digraph &g) 149 148 { … … 156 155 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 157 156 ///By default it is a NullMap. 158 ///\todo If it is set to a real map,159 ///Dijkstra::processed() should read this.160 157 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 161 158 ///Instantiates a \ref ProcessedMap. … … 298 295 bool local_heap; 299 296 300 ///Creates the maps if necessary. 301 ///\todo Better memory allocation (instead of new). 297 //Creates the maps if necessary. 302 298 void create_maps() 303 299 { … … 959 955 /// \param g is the digraph, to which we would like to define the 960 956 /// HeapCrossRef. 961 /// \todo The digraph alone may be insufficient for the initialization962 957 static HeapCrossRef *createHeapCrossRef(const Digraph &g) 963 958 { … … 995 990 ///\param g is the digraph, to which we would like to define the 996 991 ///\ref PredMap. 997 ///\todo The digraph alone may be insufficient to initialize998 992 static PredMap *createPredMap(const Digraph &g) 999 993 { … … 1006 1000 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1007 1001 ///By default it is a NullMap. 1008 ///\todo If it is set to a real map,1009 ///Dijkstra::processed() should read this.1010 ///\todo named parameter to set this type, function to read and write.1011 1002 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 1012 1003 ///Instantiates a \ref ProcessedMap. … … 1054 1045 /// The \ref DijkstraWizardBase is a class to be the default traits of the 1055 1046 /// \ref DijkstraWizard class. 1056 /// \todo More named parameters are required...1057 1047 template<class GR,class LM> 1058 1048 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM> 
lemon/dijkstra.h
r280 r281 31 31 #include <lemon/error.h> 32 32 #include <lemon/maps.h> 33 #include <lemon/path.h> 33 34 34 35 namespace lemon { … … 197 198 ///It is also possible to change the underlying priority heap. 198 199 /// 199 ///There is also a \ref dijkstra() "function 200 ///There is also a \ref dijkstra() "functiontype interface" for the 200 201 ///%Dijkstra algorithm, which is convenient in the simplier cases and 201 202 ///it can be used easier. … … 983 984 ///arcs of the shortest paths. 984 985 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 985 typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;986 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 986 987 ///Instantiates a \ref PredMap. 987 988 … … 989 990 ///\param g is the digraph, to which we would like to define the 990 991 ///\ref PredMap. 991 #ifdef DOXYGEN992 992 static PredMap *createPredMap(const Digraph &g) 993 #else 994 static PredMap *createPredMap(const Digraph &) 995 #endif 996 { 997 return new PredMap(); 993 { 994 return new PredMap(g); 998 995 } 999 996 … … 1022 1019 ///The type of the map that stores the distances of the nodes. 1023 1020 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 1024 typedef NullMap<typename Digraph::Node,Value> DistMap;1021 typedef typename Digraph::template NodeMap<typename LM::Value> DistMap; 1025 1022 ///Instantiates a \ref DistMap. 1026 1023 … … 1028 1025 ///\param g is the digraph, to which we would like to define 1029 1026 ///the \ref DistMap 1030 #ifdef DOXYGEN1031 1027 static DistMap *createDistMap(const Digraph &g) 1032 #else 1033 static DistMap *createDistMap(const Digraph &) 1034 #endif 1035 { 1036 return new DistMap(); 1037 } 1028 { 1029 return new DistMap(g); 1030 } 1031 1032 ///The type of the shortest paths. 1033 1034 ///The type of the shortest paths. 1035 ///It must meet the \ref concepts::Path "Path" concept. 1036 typedef lemon::Path<Digraph> Path; 1038 1037 }; 1039 1038 … … 1056 1055 //Pointer to the digraph the algorithm runs on. 1057 1056 void *_g; 1058 //Pointer to the length map 1057 //Pointer to the length map. 1059 1058 void *_length; 1060 1059 //Pointer to the map of processed nodes. … … 1064 1063 //Pointer to the map of distances. 1065 1064 void *_dist; 1066 //Pointer to the source node. 1067 Node _source; 1065 //Pointer to the shortest path to the target node. 1066 void *_path; 1067 //Pointer to the distance of the target node. 1068 void *_di; 1068 1069 1069 1070 public: … … 1071 1072 1072 1073 /// This constructor does not require parameters, therefore it initiates 1073 /// all of the attributes to default values (0, INVALID).1074 /// all of the attributes to \c 0. 1074 1075 DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0), 1075 _dist(0), _ source(INVALID) {}1076 _dist(0), _path(0), _di(0) {} 1076 1077 1077 1078 /// Constructor. 1078 1079 1079 /// This constructor requires some parameters, 1080 /// listed in the parameters list. 1081 /// Others are initiated to 0. 1080 /// This constructor requires two parameters, 1081 /// others are initiated to \c 0. 1082 1082 /// \param g The digraph the algorithm runs on. 1083 1083 /// \param l The length map. 1084 /// \param s The source node. 1085 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : 1084 DijkstraWizardBase(const GR &g,const LM &l) : 1086 1085 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 1087 1086 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))), 1088 _processed(0), _pred(0), _dist(0), _ source(s) {}1087 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} 1089 1088 1090 1089 }; 1091 1090 1092 /// Auxiliary class for the function type interface of Dijkstra algorithm. 1093 1094 /// This auxiliary class is created to implement the function type 1095 /// interface of \ref Dijkstra algorithm. It uses the functions and features 1096 /// of the plain \ref Dijkstra, but it is much simpler to use it. 1097 /// It should only be used through the \ref dijkstra() function, which makes 1098 /// it easier to use the algorithm. 1091 /// Auxiliary class for the functiontype interface of Dijkstra algorithm. 1092 1093 /// This auxiliary class is created to implement the 1094 /// \ref dijkstra() "functiontype interface" of \ref Dijkstra algorithm. 1095 /// It does not have own \ref run() method, it uses the functions 1096 /// and features of the plain \ref Dijkstra. 1099 1097 /// 1100 /// Simplicity means that the way to change the types defined 1101 /// in the traits class is based on functions that returns the new class 1102 /// and not on templatable builtin classes. 1103 /// When using the plain \ref Dijkstra 1104 /// the new class with the modified type comes from 1105 /// the original class by using the :: 1106 /// operator. In the case of \ref DijkstraWizard only 1107 /// a function have to be called, and it will 1108 /// return the needed class. 1109 /// 1110 /// It does not have own \ref run() method. When its \ref run() method 1111 /// is called, it initiates a plain \ref Dijkstra object, and calls the 1112 /// \ref Dijkstra::run() method of it. 1098 /// This class should only be used through the \ref dijkstra() function, 1099 /// which makes it easier to use the algorithm. 1113 1100 template<class TR> 1114 1101 class DijkstraWizard : public TR … … 1135 1122 ///The type of the map that indicates which nodes are processed. 1136 1123 typedef typename TR::ProcessedMap ProcessedMap; 1124 ///The type of the shortest paths 1125 typedef typename TR::Path Path; 1137 1126 ///The heap type used by the dijkstra algorithm. 1138 1127 typedef typename TR::Heap Heap; … … 1147 1136 /// Constructor that requires parameters. 1148 1137 /// These parameters will be the default values for the traits class. 1149 DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) : 1150 TR(g,l,s) {} 1138 /// \param g The digraph the algorithm runs on. 1139 /// \param l The length map. 1140 DijkstraWizard(const Digraph &g, const LengthMap &l) : 1141 TR(g,l) {} 1151 1142 1152 1143 ///Copy constructor … … 1155 1146 ~DijkstraWizard() {} 1156 1147 1157 ///Runs Dijkstra algorithm from asource node.1158 1159 /// Runs Dijkstra algorithm from a source node.1160 /// The node can be given with the \ref source() function.1161 void run( )1162 { 1163 if (Base::_source==INVALID) throw UninitializedParameter();1148 ///Runs Dijkstra algorithm from the given source node. 1149 1150 ///This method runs %Dijkstra algorithm from the given source node 1151 ///in order to compute the shortest path to each node. 1152 void run(Node s) 1153 { 1154 if (s==INVALID) throw UninitializedParameter(); 1164 1155 Dijkstra<Digraph,LengthMap,TR> 1165 dij(*reinterpret_cast<const Digraph*>(Base::_g), 1166 *reinterpret_cast<const LengthMap*>(Base::_length)); 1167 if(Base::_processed) 1168 dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1169 if(Base::_pred) 1170 dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1171 if(Base::_dist) 1172 dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1173 dij.run(Base::_source); 1174 } 1175 1176 ///Runs Dijkstra algorithm from the given node. 1177 1178 ///Runs Dijkstra algorithm from the given node. 1179 ///\param s is the given source. 1180 void run(Node s) 1181 { 1182 Base::_source=s; 1183 run(); 1184 } 1185 1186 /// Sets the source node, from which the Dijkstra algorithm runs. 1187 1188 /// Sets the source node, from which the Dijkstra algorithm runs. 1189 /// \param s is the source node. 1190 DijkstraWizard<TR> &source(Node s) 1191 { 1192 Base::_source=s; 1193 return *this; 1156 dijk(*reinterpret_cast<const Digraph*>(Base::_g), 1157 *reinterpret_cast<const LengthMap*>(Base::_length)); 1158 if (Base::_pred) 1159 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1160 if (Base::_dist) 1161 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1162 if (Base::_processed) 1163 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1164 dijk.run(s); 1165 } 1166 1167 ///Finds the shortest path between \c s and \c t. 1168 1169 ///This method runs the %Dijkstra algorithm from node \c s 1170 ///in order to compute the shortest path to node \c t 1171 ///(it stops searching when \c t is processed). 1172 /// 1173 ///\return \c true if \c t is reachable form \c s. 1174 bool run(Node s, Node t) 1175 { 1176 if (s==INVALID  t==INVALID) throw UninitializedParameter(); 1177 Dijkstra<Digraph,LengthMap,TR> 1178 dijk(*reinterpret_cast<const Digraph*>(Base::_g), 1179 *reinterpret_cast<const LengthMap*>(Base::_length)); 1180 if (Base::_pred) 1181 dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); 1182 if (Base::_dist) 1183 dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); 1184 if (Base::_processed) 1185 dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); 1186 dijk.run(s,t); 1187 if (Base::_path) 1188 *reinterpret_cast<Path*>(Base::_path) = dijk.path(t); 1189 if (Base::_di) 1190 *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t); 1191 return dijk.reached(t); 1194 1192 } 1195 1193 … … 1200 1198 SetPredMapBase(const TR &b) : TR(b) {} 1201 1199 }; 1202 ///\brief \ref named templparam "Named parameter"1200 ///\brief \ref namedfuncparam "Named parameter" 1203 1201 ///for setting \ref PredMap object. 1204 1202 /// 1205 ///\ref named templparam "Named parameter"1203 ///\ref namedfuncparam "Named parameter" 1206 1204 ///for setting \ref PredMap object. 1207 1205 template<class T> … … 1210 1208 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); 1211 1209 return DijkstraWizard<SetPredMapBase<T> >(*this); 1210 } 1211 1212 template<class T> 1213 struct SetDistMapBase : public Base { 1214 typedef T DistMap; 1215 static DistMap *createDistMap(const Digraph &) { return 0; }; 1216 SetDistMapBase(const TR &b) : TR(b) {} 1217 }; 1218 ///\brief \ref namedfuncparam "Named parameter" 1219 ///for setting \ref DistMap object. 1220 /// 1221 ///\ref namedfuncparam "Named parameter" 1222 ///for setting \ref DistMap object. 1223 template<class T> 1224 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) 1225 { 1226 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1227 return DijkstraWizard<SetDistMapBase<T> >(*this); 1212 1228 } 1213 1229 … … 1218 1234 SetProcessedMapBase(const TR &b) : TR(b) {} 1219 1235 }; 1220 ///\brief \ref named templparam "Named parameter"1236 ///\brief \ref namedfuncparam "Named parameter" 1221 1237 ///for setting \ref ProcessedMap object. 1222 1238 /// 1223 /// \ref named templparam "Named parameter"1239 /// \ref namedfuncparam "Named parameter" 1224 1240 ///for setting \ref ProcessedMap object. 1225 1241 template<class T> … … 1231 1247 1232 1248 template<class T> 1233 struct SetDistMapBase : public Base { 1234 typedef T DistMap; 1235 static DistMap *createDistMap(const Digraph &) { return 0; }; 1236 SetDistMapBase(const TR &b) : TR(b) {} 1237 }; 1238 ///\brief \ref namedtemplparam "Named parameter" 1239 ///for setting \ref DistMap object. 1240 /// 1241 ///\ref namedtemplparam "Named parameter" 1242 ///for setting \ref DistMap object. 1249 struct SetPathBase : public Base { 1250 typedef T Path; 1251 SetPathBase(const TR &b) : TR(b) {} 1252 }; 1253 ///\brief \ref namedfuncparam "Named parameter" 1254 ///for getting the shortest path to the target node. 1255 /// 1256 ///\ref namedfuncparam "Named parameter" 1257 ///for getting the shortest path to the target node. 1243 1258 template<class T> 1244 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t) 1245 { 1246 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); 1247 return DijkstraWizard<SetDistMapBase<T> >(*this); 1259 DijkstraWizard<SetPathBase<T> > path(const T &t) 1260 { 1261 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t)); 1262 return DijkstraWizard<SetPathBase<T> >(*this); 1263 } 1264 1265 ///\brief \ref namedfuncparam "Named parameter" 1266 ///for getting the distance of the target node. 1267 /// 1268 ///\ref namedfuncparam "Named parameter" 1269 ///for getting the distance of the target node. 1270 DijkstraWizard dist(const Value &d) 1271 { 1272 Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d)); 1273 return *this; 1248 1274 } 1249 1275 1250 1276 }; 1251 1277 1252 ///Function 1278 ///Functiontype interface for Dijkstra algorithm. 1253 1279 1254 1280 /// \ingroup shortest_path 1255 ///Function 1281 ///Functiontype interface for Dijkstra algorithm. 1256 1282 /// 1257 ///This function also has several 1258 ///\ref namedtemplfuncparam "named parameters", 1283 ///This function also has several \ref namedfuncparam "named parameters", 1259 1284 ///they are declared as the members of class \ref DijkstraWizard. 1260 ///The following 1261 ///example shows how to use these parameters. 1285 ///The following examples show how to use these parameters. 1262 1286 ///\code 1263 /// dijkstra(g,length,source).predMap(preds).run(); 1287 /// // Compute shortest path from node s to each node 1288 /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); 1289 /// 1290 /// // Compute shortest path from s to t 1291 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); 1264 1292 ///\endcode 1265 1293 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" … … 1269 1297 template<class GR, class LM> 1270 1298 DijkstraWizard<DijkstraWizardBase<GR,LM> > 1271 dijkstra(const GR & g,const LM &l,typename GR::Node s=INVALID)1299 dijkstra(const GR &digraph, const LM &length) 1272 1300 { 1273 return DijkstraWizard<DijkstraWizardBase<GR,LM> >( g,l,s);1301 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length); 1274 1302 } 1275 1303
Note: See TracChangeset
for help on using the changeset viewer.