equal
deleted
inserted
replaced
133 template <typename GR=ListDigraph, |
133 template <typename GR=ListDigraph, |
134 typename TR=BfsDefaultTraits<GR> > |
134 typename TR=BfsDefaultTraits<GR> > |
135 #endif |
135 #endif |
136 class Bfs { |
136 class Bfs { |
137 public: |
137 public: |
138 ///\ref Exception for uninitialized parameters. |
|
139 |
|
140 ///This error represents problems in the initialization of the |
|
141 ///parameters of the algorithm. |
|
142 class UninitializedParameter : public lemon::UninitializedParameter { |
|
143 public: |
|
144 virtual const char* what() const throw() { |
|
145 return "lemon::Bfs::UninitializedParameter"; |
|
146 } |
|
147 }; |
|
148 |
138 |
149 ///The type of the digraph the algorithm runs on. |
139 ///The type of the digraph the algorithm runs on. |
150 typedef typename TR::Digraph Digraph; |
140 typedef typename TR::Digraph Digraph; |
151 |
141 |
152 ///\brief The type of the map that stores the predecessor arcs of the |
142 ///\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 /// |
302 struct SetStandardProcessedMapTraits : public Traits { |
296 struct SetStandardProcessedMapTraits : public Traits { |
303 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
297 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
304 static ProcessedMap *createProcessedMap(const Digraph &g) |
298 static ProcessedMap *createProcessedMap(const Digraph &g) |
305 { |
299 { |
306 return new ProcessedMap(g); |
300 return new ProcessedMap(g); |
|
301 return 0; // ignore warnings |
307 } |
302 } |
308 }; |
303 }; |
309 ///\brief \ref named-templ-param "Named parameter" for setting |
304 ///\brief \ref named-templ-param "Named parameter" for setting |
310 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
305 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>. |
311 /// |
306 /// |
1038 ///(it stops searching when \c t is processed). |
1033 ///(it stops searching when \c t is processed). |
1039 /// |
1034 /// |
1040 ///\return \c true if \c t is reachable form \c s. |
1035 ///\return \c true if \c t is reachable form \c s. |
1041 bool run(Node s, Node t) |
1036 bool run(Node s, Node t) |
1042 { |
1037 { |
1043 if (s==INVALID || t==INVALID) throw UninitializedParameter(); |
|
1044 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
1038 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
1045 if (Base::_pred) |
1039 if (Base::_pred) |
1046 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
1040 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
1047 if (Base::_dist) |
1041 if (Base::_dist) |
1048 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
1042 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
1321 typename _Traits = BfsDefaultTraits<_Digraph> > |
1315 typename _Traits = BfsDefaultTraits<_Digraph> > |
1322 #endif |
1316 #endif |
1323 class BfsVisit { |
1317 class BfsVisit { |
1324 public: |
1318 public: |
1325 |
1319 |
1326 /// \brief \ref Exception for uninitialized parameters. |
|
1327 /// |
|
1328 /// This error represents problems in the initialization |
|
1329 /// of the parameters of the algorithm. |
|
1330 class UninitializedParameter : public lemon::UninitializedParameter { |
|
1331 public: |
|
1332 virtual const char* what() const throw() |
|
1333 { |
|
1334 return "lemon::BfsVisit::UninitializedParameter"; |
|
1335 } |
|
1336 }; |
|
1337 |
|
1338 ///The traits class. |
1320 ///The traits class. |
1339 typedef _Traits Traits; |
1321 typedef _Traits Traits; |
1340 |
1322 |
1341 ///The type of the digraph the algorithm runs on. |
1323 ///The type of the digraph the algorithm runs on. |
1342 typedef typename Traits::Digraph Digraph; |
1324 typedef typename Traits::Digraph Digraph; |
1387 ///@{ |
1369 ///@{ |
1388 template <class T> |
1370 template <class T> |
1389 struct SetReachedMapTraits : public Traits { |
1371 struct SetReachedMapTraits : public Traits { |
1390 typedef T ReachedMap; |
1372 typedef T ReachedMap; |
1391 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1373 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1392 throw UninitializedParameter(); |
1374 LEMON_ASSERT(false, "ReachedMap is not initialized"); |
|
1375 return 0; // ignore warnings |
1393 } |
1376 } |
1394 }; |
1377 }; |
1395 /// \brief \ref named-templ-param "Named parameter" for setting |
1378 /// \brief \ref named-templ-param "Named parameter" for setting |
1396 /// ReachedMap type. |
1379 /// ReachedMap type. |
1397 /// |
1380 /// |