1.1 --- a/lemon/dfs.h Thu Jan 01 00:00:00 2009 +0100
1.2 +++ b/lemon/dfs.h Mon Feb 23 12:10:26 2009 +0100
1.3 @@ -49,11 +49,11 @@
1.4 ///arcs of the %DFS paths.
1.5 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.6 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.7 - ///Instantiates a PredMap.
1.8 + ///Instantiates a \c PredMap.
1.9
1.10 - ///This function instantiates a PredMap.
1.11 + ///This function instantiates a \ref PredMap.
1.12 ///\param g is the digraph, to which we would like to define the
1.13 - ///PredMap.
1.14 + ///\ref PredMap.
1.15 static PredMap *createPredMap(const Digraph &g)
1.16 {
1.17 return new PredMap(g);
1.18 @@ -64,11 +64,11 @@
1.19 ///The type of the map that indicates which nodes are processed.
1.20 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.21 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.22 - ///Instantiates a ProcessedMap.
1.23 + ///Instantiates a \c ProcessedMap.
1.24
1.25 - ///This function instantiates a ProcessedMap.
1.26 + ///This function instantiates a \ref ProcessedMap.
1.27 ///\param g is the digraph, to which
1.28 - ///we would like to define the ProcessedMap
1.29 + ///we would like to define the \ref ProcessedMap.
1.30 #ifdef DOXYGEN
1.31 static ProcessedMap *createProcessedMap(const Digraph &g)
1.32 #else
1.33 @@ -83,11 +83,11 @@
1.34 ///The type of the map that indicates which nodes are reached.
1.35 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.36 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.37 - ///Instantiates a ReachedMap.
1.38 + ///Instantiates a \c ReachedMap.
1.39
1.40 - ///This function instantiates a ReachedMap.
1.41 + ///This function instantiates a \ref ReachedMap.
1.42 ///\param g is the digraph, to which
1.43 - ///we would like to define the ReachedMap.
1.44 + ///we would like to define the \ref ReachedMap.
1.45 static ReachedMap *createReachedMap(const Digraph &g)
1.46 {
1.47 return new ReachedMap(g);
1.48 @@ -98,11 +98,11 @@
1.49 ///The type of the map that stores the distances of the nodes.
1.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.51 typedef typename Digraph::template NodeMap<int> DistMap;
1.52 - ///Instantiates a DistMap.
1.53 + ///Instantiates a \c DistMap.
1.54
1.55 - ///This function instantiates a DistMap.
1.56 + ///This function instantiates a \ref DistMap.
1.57 ///\param g is the digraph, to which we would like to define the
1.58 - ///DistMap.
1.59 + ///\ref DistMap.
1.60 static DistMap *createDistMap(const Digraph &g)
1.61 {
1.62 return new DistMap(g);
1.63 @@ -220,10 +220,10 @@
1.64 }
1.65 };
1.66 ///\brief \ref named-templ-param "Named parameter" for setting
1.67 - ///PredMap type.
1.68 + ///\c PredMap type.
1.69 ///
1.70 ///\ref named-templ-param "Named parameter" for setting
1.71 - ///PredMap type.
1.72 + ///\c PredMap type.
1.73 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.74 template <class T>
1.75 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
1.76 @@ -240,10 +240,10 @@
1.77 }
1.78 };
1.79 ///\brief \ref named-templ-param "Named parameter" for setting
1.80 - ///DistMap type.
1.81 + ///\c DistMap type.
1.82 ///
1.83 ///\ref named-templ-param "Named parameter" for setting
1.84 - ///DistMap type.
1.85 + ///\c DistMap type.
1.86 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.87 template <class T>
1.88 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
1.89 @@ -260,10 +260,10 @@
1.90 }
1.91 };
1.92 ///\brief \ref named-templ-param "Named parameter" for setting
1.93 - ///ReachedMap type.
1.94 + ///\c ReachedMap type.
1.95 ///
1.96 ///\ref named-templ-param "Named parameter" for setting
1.97 - ///ReachedMap type.
1.98 + ///\c ReachedMap type.
1.99 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.100 template <class T>
1.101 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
1.102 @@ -280,10 +280,10 @@
1.103 }
1.104 };
1.105 ///\brief \ref named-templ-param "Named parameter" for setting
1.106 - ///ProcessedMap type.
1.107 + ///\c ProcessedMap type.
1.108 ///
1.109 ///\ref named-templ-param "Named parameter" for setting
1.110 - ///ProcessedMap type.
1.111 + ///\c ProcessedMap type.
1.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 template <class T>
1.114 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
1.115 @@ -298,10 +298,10 @@
1.116 }
1.117 };
1.118 ///\brief \ref named-templ-param "Named parameter" for setting
1.119 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.120 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.121 ///
1.122 ///\ref named-templ-param "Named parameter" for setting
1.123 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.124 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.125 ///If you don't set it explicitly, it will be automatically allocated.
1.126 struct SetStandardProcessedMap :
1.127 public Dfs< Digraph, SetStandardProcessedMapTraits > {
1.128 @@ -1126,9 +1126,9 @@
1.129 ///
1.130 /// This class defines the interface of the DfsVisit events, and
1.131 /// it could be the base of a real visitor class.
1.132 - template <typename _Digraph>
1.133 + template <typename GR>
1.134 struct DfsVisitor {
1.135 - typedef _Digraph Digraph;
1.136 + typedef GR Digraph;
1.137 typedef typename Digraph::Arc Arc;
1.138 typedef typename Digraph::Node Node;
1.139 /// \brief Called for the source node of the DFS.
1.140 @@ -1164,9 +1164,9 @@
1.141 void backtrack(const Arc& arc) {}
1.142 };
1.143 #else
1.144 - template <typename _Digraph>
1.145 + template <typename GR>
1.146 struct DfsVisitor {
1.147 - typedef _Digraph Digraph;
1.148 + typedef GR Digraph;
1.149 typedef typename Digraph::Arc Arc;
1.150 typedef typename Digraph::Node Node;
1.151 void start(const Node&) {}
1.152 @@ -1199,11 +1199,11 @@
1.153 ///
1.154 /// Default traits class of DfsVisit class.
1.155 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.156 - template<class _Digraph>
1.157 + template<class GR>
1.158 struct DfsVisitDefaultTraits {
1.159
1.160 /// \brief The type of the digraph the algorithm runs on.
1.161 - typedef _Digraph Digraph;
1.162 + typedef GR Digraph;
1.163
1.164 /// \brief The type of the map that indicates which nodes are reached.
1.165 ///
1.166 @@ -1224,12 +1224,12 @@
1.167
1.168 /// \ingroup search
1.169 ///
1.170 - /// \brief %DFS algorithm class with visitor interface.
1.171 + /// \brief DFS algorithm class with visitor interface.
1.172 ///
1.173 - /// This class provides an efficient implementation of the %DFS algorithm
1.174 + /// This class provides an efficient implementation of the DFS algorithm
1.175 /// with visitor interface.
1.176 ///
1.177 - /// The %DfsVisit class provides an alternative interface to the Dfs
1.178 + /// The DfsVisit class provides an alternative interface to the Dfs
1.179 /// class. It works with callback mechanism, the DfsVisit object calls
1.180 /// the member functions of the \c Visitor class on every DFS event.
1.181 ///
1.182 @@ -1238,37 +1238,37 @@
1.183 /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1.184 /// instead.
1.185 ///
1.186 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.187 - /// The default value is
1.188 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.189 - /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1.190 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.191 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1.192 + /// \tparam GR The type of the digraph the algorithm runs on.
1.193 + /// The default type is \ref ListDigraph.
1.194 + /// The value of GR is not used directly by \ref DfsVisit,
1.195 + /// it is only passed to \ref DfsVisitDefaultTraits.
1.196 + /// \tparam VS The Visitor type that is used by the algorithm.
1.197 + /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
1.198 /// does not observe the DFS events. If you want to observe the DFS
1.199 /// events, you should implement your own visitor class.
1.200 - /// \tparam _Traits Traits class to set various data types used by the
1.201 + /// \tparam TR Traits class to set various data types used by the
1.202 /// algorithm. The default traits class is
1.203 - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1.204 + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
1.205 /// See \ref DfsVisitDefaultTraits for the documentation of
1.206 /// a DFS visit traits class.
1.207 #ifdef DOXYGEN
1.208 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.209 + template <typename GR, typename VS, typename TR>
1.210 #else
1.211 - template <typename _Digraph = ListDigraph,
1.212 - typename _Visitor = DfsVisitor<_Digraph>,
1.213 - typename _Traits = DfsVisitDefaultTraits<_Digraph> >
1.214 + template <typename GR = ListDigraph,
1.215 + typename VS = DfsVisitor<GR>,
1.216 + typename TR = DfsVisitDefaultTraits<GR> >
1.217 #endif
1.218 class DfsVisit {
1.219 public:
1.220
1.221 ///The traits class.
1.222 - typedef _Traits Traits;
1.223 + typedef TR Traits;
1.224
1.225 ///The type of the digraph the algorithm runs on.
1.226 typedef typename Traits::Digraph Digraph;
1.227
1.228 ///The visitor type used by the algorithm.
1.229 - typedef _Visitor Visitor;
1.230 + typedef VS Visitor;
1.231
1.232 ///The type of the map that indicates which nodes are reached.
1.233 typedef typename Traits::ReachedMap ReachedMap;