lemon/bfs.h
changeset 629 70a356a461a5
parent 440 88ed40ad0d4f
child 713 4ac30454f1c1
child 716 f47b6c94577e
child 975 b873350e6258
equal deleted inserted replaced
23:d3d83066113d 24:27de417382be
    47     ///
    47     ///
    48     ///The type of the map that stores the predecessor
    48     ///The type of the map that stores the predecessor
    49     ///arcs of the shortest paths.
    49     ///arcs of the shortest paths.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    50     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    51     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    51     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    52     ///Instantiates a PredMap.
    52     ///Instantiates a \c PredMap.
    53 
    53 
    54     ///This function instantiates a PredMap.
    54     ///This function instantiates a \ref PredMap.
    55     ///\param g is the digraph, to which we would like to define the
    55     ///\param g is the digraph, to which we would like to define the
    56     ///PredMap.
    56     ///\ref PredMap.
    57     static PredMap *createPredMap(const Digraph &g)
    57     static PredMap *createPredMap(const Digraph &g)
    58     {
    58     {
    59       return new PredMap(g);
    59       return new PredMap(g);
    60     }
    60     }
    61 
    61 
    62     ///The type of the map that indicates which nodes are processed.
    62     ///The type of the map that indicates which nodes are processed.
    63 
    63 
    64     ///The type of the map that indicates which nodes are processed.
    64     ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    65     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    66     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    66     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    67     ///Instantiates a ProcessedMap.
    67     ///Instantiates a \c ProcessedMap.
    68 
    68 
    69     ///This function instantiates a ProcessedMap.
    69     ///This function instantiates a \ref ProcessedMap.
    70     ///\param g is the digraph, to which
    70     ///\param g is the digraph, to which
    71     ///we would like to define the ProcessedMap
    71     ///we would like to define the \ref ProcessedMap
    72 #ifdef DOXYGEN
    72 #ifdef DOXYGEN
    73     static ProcessedMap *createProcessedMap(const Digraph &g)
    73     static ProcessedMap *createProcessedMap(const Digraph &g)
    74 #else
    74 #else
    75     static ProcessedMap *createProcessedMap(const Digraph &)
    75     static ProcessedMap *createProcessedMap(const Digraph &)
    76 #endif
    76 #endif
    81     ///The type of the map that indicates which nodes are reached.
    81     ///The type of the map that indicates which nodes are reached.
    82 
    82 
    83     ///The type of the map that indicates which nodes are reached.
    83     ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    85     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    85     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    86     ///Instantiates a ReachedMap.
    86     ///Instantiates a \c ReachedMap.
    87 
    87 
    88     ///This function instantiates a ReachedMap.
    88     ///This function instantiates a \ref ReachedMap.
    89     ///\param g is the digraph, to which
    89     ///\param g is the digraph, to which
    90     ///we would like to define the ReachedMap.
    90     ///we would like to define the \ref ReachedMap.
    91     static ReachedMap *createReachedMap(const Digraph &g)
    91     static ReachedMap *createReachedMap(const Digraph &g)
    92     {
    92     {
    93       return new ReachedMap(g);
    93       return new ReachedMap(g);
    94     }
    94     }
    95 
    95 
    96     ///The type of the map that stores the distances of the nodes.
    96     ///The type of the map that stores the distances of the nodes.
    97 
    97 
    98     ///The type of the map that stores the distances of the nodes.
    98     ///The type of the map that stores the distances of the nodes.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    99     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   100     typedef typename Digraph::template NodeMap<int> DistMap;
   100     typedef typename Digraph::template NodeMap<int> DistMap;
   101     ///Instantiates a DistMap.
   101     ///Instantiates a \c DistMap.
   102 
   102 
   103     ///This function instantiates a DistMap.
   103     ///This function instantiates a \ref DistMap.
   104     ///\param g is the digraph, to which we would like to define the
   104     ///\param g is the digraph, to which we would like to define the
   105     ///DistMap.
   105     ///\ref DistMap.
   106     static DistMap *createDistMap(const Digraph &g)
   106     static DistMap *createDistMap(const Digraph &g)
   107     {
   107     {
   108       return new DistMap(g);
   108       return new DistMap(g);
   109     }
   109     }
   110   };
   110   };
   219         LEMON_ASSERT(false, "PredMap is not initialized");
   219         LEMON_ASSERT(false, "PredMap is not initialized");
   220         return 0; // ignore warnings
   220         return 0; // ignore warnings
   221       }
   221       }
   222     };
   222     };
   223     ///\brief \ref named-templ-param "Named parameter" for setting
   223     ///\brief \ref named-templ-param "Named parameter" for setting
   224     ///PredMap type.
   224     ///\c PredMap type.
   225     ///
   225     ///
   226     ///\ref named-templ-param "Named parameter" for setting
   226     ///\ref named-templ-param "Named parameter" for setting
   227     ///PredMap type.
   227     ///\c PredMap type.
   228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   228     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   229     template <class T>
   229     template <class T>
   230     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
   230     struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
   231       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
   231       typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
   232     };
   232     };
   239         LEMON_ASSERT(false, "DistMap is not initialized");
   239         LEMON_ASSERT(false, "DistMap is not initialized");
   240         return 0; // ignore warnings
   240         return 0; // ignore warnings
   241       }
   241       }
   242     };
   242     };
   243     ///\brief \ref named-templ-param "Named parameter" for setting
   243     ///\brief \ref named-templ-param "Named parameter" for setting
   244     ///DistMap type.
   244     ///\c DistMap type.
   245     ///
   245     ///
   246     ///\ref named-templ-param "Named parameter" for setting
   246     ///\ref named-templ-param "Named parameter" for setting
   247     ///DistMap type.
   247     ///\c DistMap type.
   248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   248     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   249     template <class T>
   249     template <class T>
   250     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
   250     struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
   251       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
   251       typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
   252     };
   252     };
   259         LEMON_ASSERT(false, "ReachedMap is not initialized");
   259         LEMON_ASSERT(false, "ReachedMap is not initialized");
   260         return 0; // ignore warnings
   260         return 0; // ignore warnings
   261       }
   261       }
   262     };
   262     };
   263     ///\brief \ref named-templ-param "Named parameter" for setting
   263     ///\brief \ref named-templ-param "Named parameter" for setting
   264     ///ReachedMap type.
   264     ///\c ReachedMap type.
   265     ///
   265     ///
   266     ///\ref named-templ-param "Named parameter" for setting
   266     ///\ref named-templ-param "Named parameter" for setting
   267     ///ReachedMap type.
   267     ///\c ReachedMap type.
   268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   268     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   269     template <class T>
   269     template <class T>
   270     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   270     struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
   271       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
   271       typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
   272     };
   272     };
   279         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   279         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   280         return 0; // ignore warnings
   280         return 0; // ignore warnings
   281       }
   281       }
   282     };
   282     };
   283     ///\brief \ref named-templ-param "Named parameter" for setting
   283     ///\brief \ref named-templ-param "Named parameter" for setting
   284     ///ProcessedMap type.
   284     ///\c ProcessedMap type.
   285     ///
   285     ///
   286     ///\ref named-templ-param "Named parameter" for setting
   286     ///\ref named-templ-param "Named parameter" for setting
   287     ///ProcessedMap type.
   287     ///\c ProcessedMap type.
   288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   288     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   289     template <class T>
   289     template <class T>
   290     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   290     struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
   291       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
   291       typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
   292     };
   292     };
   298         return new ProcessedMap(g);
   298         return new ProcessedMap(g);
   299         return 0; // ignore warnings
   299         return 0; // ignore warnings
   300       }
   300       }
   301     };
   301     };
   302     ///\brief \ref named-templ-param "Named parameter" for setting
   302     ///\brief \ref named-templ-param "Named parameter" for setting
   303     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   303     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   304     ///
   304     ///
   305     ///\ref named-templ-param "Named parameter" for setting
   305     ///\ref named-templ-param "Named parameter" for setting
   306     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   306     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   307     ///If you don't set it explicitly, it will be automatically allocated.
   307     ///If you don't set it explicitly, it will be automatically allocated.
   308     struct SetStandardProcessedMap :
   308     struct SetStandardProcessedMap :
   309       public Bfs< Digraph, SetStandardProcessedMapTraits > {
   309       public Bfs< Digraph, SetStandardProcessedMapTraits > {
   310       typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
   310       typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
   311     };
   311     };
  1192 #ifdef DOXYGEN
  1192 #ifdef DOXYGEN
  1193   /// \brief Visitor class for BFS.
  1193   /// \brief Visitor class for BFS.
  1194   ///
  1194   ///
  1195   /// This class defines the interface of the BfsVisit events, and
  1195   /// This class defines the interface of the BfsVisit events, and
  1196   /// it could be the base of a real visitor class.
  1196   /// it could be the base of a real visitor class.
  1197   template <typename _Digraph>
  1197   template <typename GR>
  1198   struct BfsVisitor {
  1198   struct BfsVisitor {
  1199     typedef _Digraph Digraph;
  1199     typedef GR Digraph;
  1200     typedef typename Digraph::Arc Arc;
  1200     typedef typename Digraph::Arc Arc;
  1201     typedef typename Digraph::Node Node;
  1201     typedef typename Digraph::Node Node;
  1202     /// \brief Called for the source node(s) of the BFS.
  1202     /// \brief Called for the source node(s) of the BFS.
  1203     ///
  1203     ///
  1204     /// This function is called for the source node(s) of the BFS.
  1204     /// This function is called for the source node(s) of the BFS.
  1222     /// This function is called when an arc is examined but its target node is
  1222     /// This function is called when an arc is examined but its target node is
  1223     /// already discovered.
  1223     /// already discovered.
  1224     void examine(const Arc& arc) {}
  1224     void examine(const Arc& arc) {}
  1225   };
  1225   };
  1226 #else
  1226 #else
  1227   template <typename _Digraph>
  1227   template <typename GR>
  1228   struct BfsVisitor {
  1228   struct BfsVisitor {
  1229     typedef _Digraph Digraph;
  1229     typedef GR Digraph;
  1230     typedef typename Digraph::Arc Arc;
  1230     typedef typename Digraph::Arc Arc;
  1231     typedef typename Digraph::Node Node;
  1231     typedef typename Digraph::Node Node;
  1232     void start(const Node&) {}
  1232     void start(const Node&) {}
  1233     void reach(const Node&) {}
  1233     void reach(const Node&) {}
  1234     void process(const Node&) {}
  1234     void process(const Node&) {}
  1252 #endif
  1252 #endif
  1253 
  1253 
  1254   /// \brief Default traits class of BfsVisit class.
  1254   /// \brief Default traits class of BfsVisit class.
  1255   ///
  1255   ///
  1256   /// Default traits class of BfsVisit class.
  1256   /// Default traits class of BfsVisit class.
  1257   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1257   /// \tparam GR The type of the digraph the algorithm runs on.
  1258   template<class _Digraph>
  1258   template<class GR>
  1259   struct BfsVisitDefaultTraits {
  1259   struct BfsVisitDefaultTraits {
  1260 
  1260 
  1261     /// \brief The type of the digraph the algorithm runs on.
  1261     /// \brief The type of the digraph the algorithm runs on.
  1262     typedef _Digraph Digraph;
  1262     typedef GR Digraph;
  1263 
  1263 
  1264     /// \brief The type of the map that indicates which nodes are reached.
  1264     /// \brief The type of the map that indicates which nodes are reached.
  1265     ///
  1265     ///
  1266     /// The type of the map that indicates which nodes are reached.
  1266     /// The type of the map that indicates which nodes are reached.
  1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1267     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1278 
  1278 
  1279   };
  1279   };
  1280 
  1280 
  1281   /// \ingroup search
  1281   /// \ingroup search
  1282   ///
  1282   ///
  1283   /// \brief %BFS algorithm class with visitor interface.
  1283   /// \brief BFS algorithm class with visitor interface.
  1284   ///
  1284   ///
  1285   /// This class provides an efficient implementation of the %BFS algorithm
  1285   /// This class provides an efficient implementation of the BFS algorithm
  1286   /// with visitor interface.
  1286   /// with visitor interface.
  1287   ///
  1287   ///
  1288   /// The %BfsVisit class provides an alternative interface to the Bfs
  1288   /// The BfsVisit class provides an alternative interface to the Bfs
  1289   /// class. It works with callback mechanism, the BfsVisit object calls
  1289   /// class. It works with callback mechanism, the BfsVisit object calls
  1290   /// the member functions of the \c Visitor class on every BFS event.
  1290   /// the member functions of the \c Visitor class on every BFS event.
  1291   ///
  1291   ///
  1292   /// This interface of the BFS algorithm should be used in special cases
  1292   /// This interface of the BFS algorithm should be used in special cases
  1293   /// when extra actions have to be performed in connection with certain
  1293   /// when extra actions have to be performed in connection with certain
  1294   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
  1294   /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
  1295   /// instead.
  1295   /// instead.
  1296   ///
  1296   ///
  1297   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1297   /// \tparam GR The type of the digraph the algorithm runs on.
  1298   /// The default value is
  1298   /// The default type is \ref ListDigraph.
  1299   /// \ref ListDigraph. The value of _Digraph is not used directly by
  1299   /// The value of GR is not used directly by \ref BfsVisit,
  1300   /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
  1300   /// it is only passed to \ref BfsVisitDefaultTraits.
  1301   /// \tparam _Visitor The Visitor type that is used by the algorithm.
  1301   /// \tparam VS The Visitor type that is used by the algorithm.
  1302   /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
  1302   /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
  1303   /// does not observe the BFS events. If you want to observe the BFS
  1303   /// does not observe the BFS events. If you want to observe the BFS
  1304   /// events, you should implement your own visitor class.
  1304   /// events, you should implement your own visitor class.
  1305   /// \tparam _Traits Traits class to set various data types used by the
  1305   /// \tparam TR Traits class to set various data types used by the
  1306   /// algorithm. The default traits class is
  1306   /// algorithm. The default traits class is
  1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
  1307   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
  1308   /// See \ref BfsVisitDefaultTraits for the documentation of
  1308   /// See \ref BfsVisitDefaultTraits for the documentation of
  1309   /// a BFS visit traits class.
  1309   /// a BFS visit traits class.
  1310 #ifdef DOXYGEN
  1310 #ifdef DOXYGEN
  1311   template <typename _Digraph, typename _Visitor, typename _Traits>
  1311   template <typename GR, typename VS, typename TR>
  1312 #else
  1312 #else
  1313   template <typename _Digraph = ListDigraph,
  1313   template <typename GR = ListDigraph,
  1314             typename _Visitor = BfsVisitor<_Digraph>,
  1314             typename VS = BfsVisitor<GR>,
  1315             typename _Traits = BfsVisitDefaultTraits<_Digraph> >
  1315             typename TR = BfsVisitDefaultTraits<GR> >
  1316 #endif
  1316 #endif
  1317   class BfsVisit {
  1317   class BfsVisit {
  1318   public:
  1318   public:
  1319 
  1319 
  1320     ///The traits class.
  1320     ///The traits class.
  1321     typedef _Traits Traits;
  1321     typedef TR Traits;
  1322 
  1322 
  1323     ///The type of the digraph the algorithm runs on.
  1323     ///The type of the digraph the algorithm runs on.
  1324     typedef typename Traits::Digraph Digraph;
  1324     typedef typename Traits::Digraph Digraph;
  1325 
  1325 
  1326     ///The visitor type used by the algorithm.
  1326     ///The visitor type used by the algorithm.
  1327     typedef _Visitor Visitor;
  1327     typedef VS Visitor;
  1328 
  1328 
  1329     ///The type of the map that indicates which nodes are reached.
  1329     ///The type of the map that indicates which nodes are reached.
  1330     typedef typename Traits::ReachedMap ReachedMap;
  1330     typedef typename Traits::ReachedMap ReachedMap;
  1331 
  1331 
  1332   private:
  1332   private: