equal
deleted
inserted
replaced
134 template <typename GR=ListDigraph, |
134 template <typename GR=ListDigraph, |
135 typename TR=DfsDefaultTraits<GR> > |
135 typename TR=DfsDefaultTraits<GR> > |
136 #endif |
136 #endif |
137 class Dfs { |
137 class Dfs { |
138 public: |
138 public: |
139 ///\ref Exception for uninitialized parameters. |
|
140 |
|
141 ///This error represents problems in the initialization of the |
|
142 ///parameters of the algorithm. |
|
143 class UninitializedParameter : public lemon::UninitializedParameter { |
|
144 public: |
|
145 virtual const char* what() const throw() { |
|
146 return "lemon::Dfs::UninitializedParameter"; |
|
147 } |
|
148 }; |
|
149 |
139 |
150 ///The type of the digraph the algorithm runs on. |
140 ///The type of the digraph the algorithm runs on. |
151 typedef typename TR::Digraph Digraph; |
141 typedef typename TR::Digraph Digraph; |
152 |
142 |
153 ///\brief The type of the map that stores the predecessor arcs of the |
143 ///\brief The type of the map that stores the predecessor arcs of the |
230 template <class T> |
220 template <class T> |
231 struct SetPredMapTraits : public Traits { |
221 struct SetPredMapTraits : public Traits { |
232 typedef T PredMap; |
222 typedef T PredMap; |
233 static PredMap *createPredMap(const Digraph &) |
223 static PredMap *createPredMap(const Digraph &) |
234 { |
224 { |
235 throw UninitializedParameter(); |
225 LEMON_ASSERT(false, "PredMap is not initialized"); |
|
226 return 0; // ignore warnings |
236 } |
227 } |
237 }; |
228 }; |
238 ///\brief \ref named-templ-param "Named parameter" for setting |
229 ///\brief \ref named-templ-param "Named parameter" for setting |
239 ///\ref PredMap type. |
230 ///\ref PredMap type. |
240 /// |
231 /// |
248 template <class T> |
239 template <class T> |
249 struct SetDistMapTraits : public Traits { |
240 struct SetDistMapTraits : public Traits { |
250 typedef T DistMap; |
241 typedef T DistMap; |
251 static DistMap *createDistMap(const Digraph &) |
242 static DistMap *createDistMap(const Digraph &) |
252 { |
243 { |
253 throw UninitializedParameter(); |
244 LEMON_ASSERT(false, "DistMap is not initialized"); |
|
245 return 0; // ignore warnings |
254 } |
246 } |
255 }; |
247 }; |
256 ///\brief \ref named-templ-param "Named parameter" for setting |
248 ///\brief \ref named-templ-param "Named parameter" for setting |
257 ///\ref DistMap type. |
249 ///\ref DistMap type. |
258 /// |
250 /// |
266 template <class T> |
258 template <class T> |
267 struct SetReachedMapTraits : public Traits { |
259 struct SetReachedMapTraits : public Traits { |
268 typedef T ReachedMap; |
260 typedef T ReachedMap; |
269 static ReachedMap *createReachedMap(const Digraph &) |
261 static ReachedMap *createReachedMap(const Digraph &) |
270 { |
262 { |
271 throw UninitializedParameter(); |
263 LEMON_ASSERT(false, "ReachedMap is not initialized"); |
|
264 return 0; // ignore warnings |
272 } |
265 } |
273 }; |
266 }; |
274 ///\brief \ref named-templ-param "Named parameter" for setting |
267 ///\brief \ref named-templ-param "Named parameter" for setting |
275 ///\ref ReachedMap type. |
268 ///\ref ReachedMap type. |
276 /// |
269 /// |
284 template <class T> |
277 template <class T> |
285 struct SetProcessedMapTraits : public Traits { |
278 struct SetProcessedMapTraits : public Traits { |
286 typedef T ProcessedMap; |
279 typedef T ProcessedMap; |
287 static ProcessedMap *createProcessedMap(const Digraph &) |
280 static ProcessedMap *createProcessedMap(const Digraph &) |
288 { |
281 { |
289 throw UninitializedParameter(); |
282 LEMON_ASSERT(false, "ProcessedMap is not initialized"); |
|
283 return 0; // ignore warnings |
290 } |
284 } |
291 }; |
285 }; |
292 ///\brief \ref named-templ-param "Named parameter" for setting |
286 ///\brief \ref named-templ-param "Named parameter" for setting |
293 ///\ref ProcessedMap type. |
287 ///\ref ProcessedMap type. |
294 /// |
288 /// |
972 ///(it stops searching when \c t is processed). |
966 ///(it stops searching when \c t is processed). |
973 /// |
967 /// |
974 ///\return \c true if \c t is reachable form \c s. |
968 ///\return \c true if \c t is reachable form \c s. |
975 bool run(Node s, Node t) |
969 bool run(Node s, Node t) |
976 { |
970 { |
977 if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
978 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
971 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
979 if (Base::_pred) |
972 if (Base::_pred) |
980 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
973 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
981 if (Base::_dist) |
974 if (Base::_dist) |
982 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
975 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
1268 typename _Traits = DfsDefaultTraits<_Digraph> > |
1261 typename _Traits = DfsDefaultTraits<_Digraph> > |
1269 #endif |
1262 #endif |
1270 class DfsVisit { |
1263 class DfsVisit { |
1271 public: |
1264 public: |
1272 |
1265 |
1273 /// \brief \ref Exception for uninitialized parameters. |
|
1274 /// |
|
1275 /// This error represents problems in the initialization |
|
1276 /// of the parameters of the algorithm. |
|
1277 class UninitializedParameter : public lemon::UninitializedParameter { |
|
1278 public: |
|
1279 virtual const char* what() const throw() |
|
1280 { |
|
1281 return "lemon::DfsVisit::UninitializedParameter"; |
|
1282 } |
|
1283 }; |
|
1284 |
|
1285 ///The traits class. |
1266 ///The traits class. |
1286 typedef _Traits Traits; |
1267 typedef _Traits Traits; |
1287 |
1268 |
1288 ///The type of the digraph the algorithm runs on. |
1269 ///The type of the digraph the algorithm runs on. |
1289 typedef typename Traits::Digraph Digraph; |
1270 typedef typename Traits::Digraph Digraph; |
1334 ///@{ |
1315 ///@{ |
1335 template <class T> |
1316 template <class T> |
1336 struct SetReachedMapTraits : public Traits { |
1317 struct SetReachedMapTraits : public Traits { |
1337 typedef T ReachedMap; |
1318 typedef T ReachedMap; |
1338 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1319 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1339 throw UninitializedParameter(); |
1320 LEMON_ASSERT(false, "ReachedMap is not initialized"); |
|
1321 return 0; // ignore warnings |
1340 } |
1322 } |
1341 }; |
1323 }; |
1342 /// \brief \ref named-templ-param "Named parameter" for setting |
1324 /// \brief \ref named-templ-param "Named parameter" for setting |
1343 /// ReachedMap type. |
1325 /// ReachedMap type. |
1344 /// |
1326 /// |