lemon/dfs.h
changeset 579 d11bf7998905
parent 440 88ed40ad0d4f
child 584 33c6b6e755cd
equal deleted inserted replaced
26:00e7509217fa 27:73030d4e18d6
    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 %DFS paths.
    49     ///arcs of the %DFS 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   };
   218         LEMON_ASSERT(false, "PredMap is not initialized");
   218         LEMON_ASSERT(false, "PredMap is not initialized");
   219         return 0; // ignore warnings
   219         return 0; // ignore warnings
   220       }
   220       }
   221     };
   221     };
   222     ///\brief \ref named-templ-param "Named parameter" for setting
   222     ///\brief \ref named-templ-param "Named parameter" for setting
   223     ///PredMap type.
   223     ///\c PredMap type.
   224     ///
   224     ///
   225     ///\ref named-templ-param "Named parameter" for setting
   225     ///\ref named-templ-param "Named parameter" for setting
   226     ///PredMap type.
   226     ///\c PredMap type.
   227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   227     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   228     template <class T>
   228     template <class T>
   229     struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
   229     struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
   230       typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
   230       typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
   231     };
   231     };
   238         LEMON_ASSERT(false, "DistMap is not initialized");
   238         LEMON_ASSERT(false, "DistMap is not initialized");
   239         return 0; // ignore warnings
   239         return 0; // ignore warnings
   240       }
   240       }
   241     };
   241     };
   242     ///\brief \ref named-templ-param "Named parameter" for setting
   242     ///\brief \ref named-templ-param "Named parameter" for setting
   243     ///DistMap type.
   243     ///\c DistMap type.
   244     ///
   244     ///
   245     ///\ref named-templ-param "Named parameter" for setting
   245     ///\ref named-templ-param "Named parameter" for setting
   246     ///DistMap type.
   246     ///\c DistMap type.
   247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   247     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   248     template <class T>
   248     template <class T>
   249     struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
   249     struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
   250       typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
   250       typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
   251     };
   251     };
   258         LEMON_ASSERT(false, "ReachedMap is not initialized");
   258         LEMON_ASSERT(false, "ReachedMap is not initialized");
   259         return 0; // ignore warnings
   259         return 0; // ignore warnings
   260       }
   260       }
   261     };
   261     };
   262     ///\brief \ref named-templ-param "Named parameter" for setting
   262     ///\brief \ref named-templ-param "Named parameter" for setting
   263     ///ReachedMap type.
   263     ///\c ReachedMap type.
   264     ///
   264     ///
   265     ///\ref named-templ-param "Named parameter" for setting
   265     ///\ref named-templ-param "Named parameter" for setting
   266     ///ReachedMap type.
   266     ///\c ReachedMap type.
   267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   267     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   268     template <class T>
   268     template <class T>
   269     struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
   269     struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
   270       typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
   270       typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
   271     };
   271     };
   278         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   278         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   279         return 0; // ignore warnings
   279         return 0; // ignore warnings
   280       }
   280       }
   281     };
   281     };
   282     ///\brief \ref named-templ-param "Named parameter" for setting
   282     ///\brief \ref named-templ-param "Named parameter" for setting
   283     ///ProcessedMap type.
   283     ///\c ProcessedMap type.
   284     ///
   284     ///
   285     ///\ref named-templ-param "Named parameter" for setting
   285     ///\ref named-templ-param "Named parameter" for setting
   286     ///ProcessedMap type.
   286     ///\c ProcessedMap type.
   287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   287     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   288     template <class T>
   288     template <class T>
   289     struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
   289     struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
   290       typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
   290       typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
   291     };
   291     };
   296       {
   296       {
   297         return new ProcessedMap(g);
   297         return new ProcessedMap(g);
   298       }
   298       }
   299     };
   299     };
   300     ///\brief \ref named-templ-param "Named parameter" for setting
   300     ///\brief \ref named-templ-param "Named parameter" for setting
   301     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   301     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   302     ///
   302     ///
   303     ///\ref named-templ-param "Named parameter" for setting
   303     ///\ref named-templ-param "Named parameter" for setting
   304     ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   304     ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   305     ///If you don't set it explicitly, it will be automatically allocated.
   305     ///If you don't set it explicitly, it will be automatically allocated.
   306     struct SetStandardProcessedMap :
   306     struct SetStandardProcessedMap :
   307       public Dfs< Digraph, SetStandardProcessedMapTraits > {
   307       public Dfs< Digraph, SetStandardProcessedMapTraits > {
   308       typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
   308       typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
   309     };
   309     };
  1124 #ifdef DOXYGEN
  1124 #ifdef DOXYGEN
  1125   /// \brief Visitor class for DFS.
  1125   /// \brief Visitor class for DFS.
  1126   ///
  1126   ///
  1127   /// This class defines the interface of the DfsVisit events, and
  1127   /// This class defines the interface of the DfsVisit events, and
  1128   /// it could be the base of a real visitor class.
  1128   /// it could be the base of a real visitor class.
  1129   template <typename _Digraph>
  1129   template <typename GR>
  1130   struct DfsVisitor {
  1130   struct DfsVisitor {
  1131     typedef _Digraph Digraph;
  1131     typedef GR Digraph;
  1132     typedef typename Digraph::Arc Arc;
  1132     typedef typename Digraph::Arc Arc;
  1133     typedef typename Digraph::Node Node;
  1133     typedef typename Digraph::Node Node;
  1134     /// \brief Called for the source node of the DFS.
  1134     /// \brief Called for the source node of the DFS.
  1135     ///
  1135     ///
  1136     /// This function is called for the source node of the DFS.
  1136     /// This function is called for the source node of the DFS.
  1162     ///
  1162     ///
  1163     /// This function is called when the DFS steps back on an arc.
  1163     /// This function is called when the DFS steps back on an arc.
  1164     void backtrack(const Arc& arc) {}
  1164     void backtrack(const Arc& arc) {}
  1165   };
  1165   };
  1166 #else
  1166 #else
  1167   template <typename _Digraph>
  1167   template <typename GR>
  1168   struct DfsVisitor {
  1168   struct DfsVisitor {
  1169     typedef _Digraph Digraph;
  1169     typedef GR Digraph;
  1170     typedef typename Digraph::Arc Arc;
  1170     typedef typename Digraph::Arc Arc;
  1171     typedef typename Digraph::Node Node;
  1171     typedef typename Digraph::Node Node;
  1172     void start(const Node&) {}
  1172     void start(const Node&) {}
  1173     void stop(const Node&) {}
  1173     void stop(const Node&) {}
  1174     void reach(const Node&) {}
  1174     void reach(const Node&) {}
  1197 
  1197 
  1198   /// \brief Default traits class of DfsVisit class.
  1198   /// \brief Default traits class of DfsVisit class.
  1199   ///
  1199   ///
  1200   /// Default traits class of DfsVisit class.
  1200   /// Default traits class of DfsVisit class.
  1201   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1201   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1202   template<class _Digraph>
  1202   template<class GR>
  1203   struct DfsVisitDefaultTraits {
  1203   struct DfsVisitDefaultTraits {
  1204 
  1204 
  1205     /// \brief The type of the digraph the algorithm runs on.
  1205     /// \brief The type of the digraph the algorithm runs on.
  1206     typedef _Digraph Digraph;
  1206     typedef GR Digraph;
  1207 
  1207 
  1208     /// \brief The type of the map that indicates which nodes are reached.
  1208     /// \brief The type of the map that indicates which nodes are reached.
  1209     ///
  1209     ///
  1210     /// The type of the map that indicates which nodes are reached.
  1210     /// The type of the map that indicates which nodes are reached.
  1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1211     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1222 
  1222 
  1223   };
  1223   };
  1224 
  1224 
  1225   /// \ingroup search
  1225   /// \ingroup search
  1226   ///
  1226   ///
  1227   /// \brief %DFS algorithm class with visitor interface.
  1227   /// \brief DFS algorithm class with visitor interface.
  1228   ///
  1228   ///
  1229   /// This class provides an efficient implementation of the %DFS algorithm
  1229   /// This class provides an efficient implementation of the DFS algorithm
  1230   /// with visitor interface.
  1230   /// with visitor interface.
  1231   ///
  1231   ///
  1232   /// The %DfsVisit class provides an alternative interface to the Dfs
  1232   /// The DfsVisit class provides an alternative interface to the Dfs
  1233   /// class. It works with callback mechanism, the DfsVisit object calls
  1233   /// class. It works with callback mechanism, the DfsVisit object calls
  1234   /// the member functions of the \c Visitor class on every DFS event.
  1234   /// the member functions of the \c Visitor class on every DFS event.
  1235   ///
  1235   ///
  1236   /// This interface of the DFS algorithm should be used in special cases
  1236   /// This interface of the DFS algorithm should be used in special cases
  1237   /// when extra actions have to be performed in connection with certain
  1237   /// when extra actions have to be performed in connection with certain
  1238   /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
  1238   /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
  1239   /// instead.
  1239   /// instead.
  1240   ///
  1240   ///
  1241   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1241   /// \tparam GR The type of the digraph the algorithm runs on.
  1242   /// The default value is
  1242   /// The default type is \ref ListDigraph.
  1243   /// \ref ListDigraph. The value of _Digraph is not used directly by
  1243   /// The value of GR is not used directly by \ref DfsVisit,
  1244   /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
  1244   /// it is only passed to \ref DfsVisitDefaultTraits.
  1245   /// \tparam _Visitor The Visitor type that is used by the algorithm.
  1245   /// \tparam VS The Visitor type that is used by the algorithm.
  1246   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
  1246   /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
  1247   /// does not observe the DFS events. If you want to observe the DFS
  1247   /// does not observe the DFS events. If you want to observe the DFS
  1248   /// events, you should implement your own visitor class.
  1248   /// events, you should implement your own visitor class.
  1249   /// \tparam _Traits Traits class to set various data types used by the
  1249   /// \tparam TR Traits class to set various data types used by the
  1250   /// algorithm. The default traits class is
  1250   /// algorithm. The default traits class is
  1251   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
  1251   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
  1252   /// See \ref DfsVisitDefaultTraits for the documentation of
  1252   /// See \ref DfsVisitDefaultTraits for the documentation of
  1253   /// a DFS visit traits class.
  1253   /// a DFS visit traits class.
  1254 #ifdef DOXYGEN
  1254 #ifdef DOXYGEN
  1255   template <typename _Digraph, typename _Visitor, typename _Traits>
  1255   template <typename GR, typename VS, typename TR>
  1256 #else
  1256 #else
  1257   template <typename _Digraph = ListDigraph,
  1257   template <typename GR = ListDigraph,
  1258             typename _Visitor = DfsVisitor<_Digraph>,
  1258             typename VS = DfsVisitor<GR>,
  1259             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
  1259             typename TR = DfsVisitDefaultTraits<GR> >
  1260 #endif
  1260 #endif
  1261   class DfsVisit {
  1261   class DfsVisit {
  1262   public:
  1262   public:
  1263 
  1263 
  1264     ///The traits class.
  1264     ///The traits class.
  1265     typedef _Traits Traits;
  1265     typedef TR Traits;
  1266 
  1266 
  1267     ///The type of the digraph the algorithm runs on.
  1267     ///The type of the digraph the algorithm runs on.
  1268     typedef typename Traits::Digraph Digraph;
  1268     typedef typename Traits::Digraph Digraph;
  1269 
  1269 
  1270     ///The visitor type used by the algorithm.
  1270     ///The visitor type used by the algorithm.
  1271     typedef _Visitor Visitor;
  1271     typedef VS Visitor;
  1272 
  1272 
  1273     ///The type of the map that indicates which nodes are reached.
  1273     ///The type of the map that indicates which nodes are reached.
  1274     typedef typename Traits::ReachedMap ReachedMap;
  1274     typedef typename Traits::ReachedMap ReachedMap;
  1275 
  1275 
  1276   private:
  1276   private: