lemon/bfs.h
changeset 291 d901321d6555
parent 287 bb40b6db0a58
child 292 e7af73f1805e
equal deleted inserted replaced
15:119df1b4c737 17:5dbb5bf3ce33
   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     ///