1.1 --- a/lemon/dfs.h Sat Sep 26 07:16:22 2009 +0200
1.2 +++ b/lemon/dfs.h Sat Sep 26 07:21:54 2009 +0200
1.3 @@ -47,7 +47,7 @@
1.4 ///
1.5 ///The type of the map that stores the predecessor
1.6 ///arcs of the %DFS paths.
1.7 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.8 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.9 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.10 ///Instantiates a \c PredMap.
1.11
1.12 @@ -62,7 +62,8 @@
1.13 ///The type of the map that indicates which nodes are processed.
1.14
1.15 ///The type of the map that indicates which nodes are processed.
1.16 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.17 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.18 + ///By default it is a NullMap.
1.19 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.20 ///Instantiates a \c ProcessedMap.
1.21
1.22 @@ -81,7 +82,7 @@
1.23 ///The type of the map that indicates which nodes are reached.
1.24
1.25 ///The type of the map that indicates which nodes are reached.
1.26 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.27 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.28 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.29 ///Instantiates a \c ReachedMap.
1.30
1.31 @@ -96,7 +97,7 @@
1.32 ///The type of the map that stores the distances of the nodes.
1.33
1.34 ///The type of the map that stores the distances of the nodes.
1.35 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.36 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.37 typedef typename Digraph::template NodeMap<int> DistMap;
1.38 ///Instantiates a \c DistMap.
1.39
1.40 @@ -224,7 +225,7 @@
1.41 ///
1.42 ///\ref named-templ-param "Named parameter" for setting
1.43 ///\c PredMap type.
1.44 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.45 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.46 template <class T>
1.47 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
1.48 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
1.49 @@ -244,7 +245,7 @@
1.50 ///
1.51 ///\ref named-templ-param "Named parameter" for setting
1.52 ///\c DistMap type.
1.53 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.54 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.55 template <class T>
1.56 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
1.57 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
1.58 @@ -264,7 +265,7 @@
1.59 ///
1.60 ///\ref named-templ-param "Named parameter" for setting
1.61 ///\c ReachedMap type.
1.62 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.63 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.64 template <class T>
1.65 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
1.66 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
1.67 @@ -284,7 +285,7 @@
1.68 ///
1.69 ///\ref named-templ-param "Named parameter" for setting
1.70 ///\c ProcessedMap type.
1.71 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.72 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.73 template <class T>
1.74 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
1.75 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
1.76 @@ -411,8 +412,8 @@
1.77 ///\name Execution Control
1.78 ///The simplest way to execute the DFS algorithm is to use one of the
1.79 ///member functions called \ref run(Node) "run()".\n
1.80 - ///If you need more control on the execution, first you have to call
1.81 - ///\ref init(), then you can add a source node with \ref addSource()
1.82 + ///If you need better control on the execution, you have to call
1.83 + ///\ref init() first, then you can add a source node with \ref addSource()
1.84 ///and perform the actual computation with \ref start().
1.85 ///This procedure can be repeated if there are nodes that have not
1.86 ///been reached.
1.87 @@ -669,9 +670,9 @@
1.88
1.89 ///@{
1.90
1.91 - ///The DFS path to a node.
1.92 + ///The DFS path to the given node.
1.93
1.94 - ///Returns the DFS path to a node.
1.95 + ///Returns the DFS path to the given node from the root(s).
1.96 ///
1.97 ///\warning \c t should be reached from the root(s).
1.98 ///
1.99 @@ -679,9 +680,9 @@
1.100 ///must be called before using this function.
1.101 Path path(Node t) const { return Path(*G, *_pred, t); }
1.102
1.103 - ///The distance of a node from the root(s).
1.104 + ///The distance of the given node from the root(s).
1.105
1.106 - ///Returns the distance of a node from the root(s).
1.107 + ///Returns the distance of the given node from the root(s).
1.108 ///
1.109 ///\warning If node \c v is not reached from the root(s), then
1.110 ///the return value of this function is undefined.
1.111 @@ -690,7 +691,7 @@
1.112 ///must be called before using this function.
1.113 int dist(Node v) const { return (*_dist)[v]; }
1.114
1.115 - ///Returns the 'previous arc' of the %DFS tree for a node.
1.116 + ///Returns the 'previous arc' of the %DFS tree for the given node.
1.117
1.118 ///This function returns the 'previous arc' of the %DFS tree for the
1.119 ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.120 @@ -698,21 +699,21 @@
1.121 ///root(s) or if \c v is a root.
1.122 ///
1.123 ///The %DFS tree used here is equal to the %DFS tree used in
1.124 - ///\ref predNode().
1.125 + ///\ref predNode() and \ref predMap().
1.126 ///
1.127 ///\pre Either \ref run(Node) "run()" or \ref init()
1.128 ///must be called before using this function.
1.129 Arc predArc(Node v) const { return (*_pred)[v];}
1.130
1.131 - ///Returns the 'previous node' of the %DFS tree.
1.132 + ///Returns the 'previous node' of the %DFS tree for the given node.
1.133
1.134 ///This function returns the 'previous node' of the %DFS
1.135 ///tree for the node \c v, i.e. it returns the last but one node
1.136 - ///from a %DFS path from a root to \c v. It is \c INVALID
1.137 + ///of a %DFS path from a root to \c v. It is \c INVALID
1.138 ///if \c v is not reached from the root(s) or if \c v is a root.
1.139 ///
1.140 ///The %DFS tree used here is equal to the %DFS tree used in
1.141 - ///\ref predArc().
1.142 + ///\ref predArc() and \ref predMap().
1.143 ///
1.144 ///\pre Either \ref run(Node) "run()" or \ref init()
1.145 ///must be called before using this function.
1.146 @@ -733,13 +734,13 @@
1.147 ///predecessor arcs.
1.148 ///
1.149 ///Returns a const reference to the node map that stores the predecessor
1.150 - ///arcs, which form the DFS tree.
1.151 + ///arcs, which form the DFS tree (forest).
1.152 ///
1.153 ///\pre Either \ref run(Node) "run()" or \ref init()
1.154 ///must be called before using this function.
1.155 const PredMap &predMap() const { return *_pred;}
1.156
1.157 - ///Checks if a node is reached from the root(s).
1.158 + ///Checks if the given node. node is reached from the root(s).
1.159
1.160 ///Returns \c true if \c v is reached from the root(s).
1.161 ///
1.162 @@ -765,7 +766,7 @@
1.163 ///
1.164 ///The type of the map that stores the predecessor
1.165 ///arcs of the %DFS paths.
1.166 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.167 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.168 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.169 ///Instantiates a PredMap.
1.170
1.171 @@ -780,7 +781,7 @@
1.172 ///The type of the map that indicates which nodes are processed.
1.173
1.174 ///The type of the map that indicates which nodes are processed.
1.175 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.176 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.177 ///By default it is a NullMap.
1.178 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.179 ///Instantiates a ProcessedMap.
1.180 @@ -800,7 +801,7 @@
1.181 ///The type of the map that indicates which nodes are reached.
1.182
1.183 ///The type of the map that indicates which nodes are reached.
1.184 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.185 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.186 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.187 ///Instantiates a ReachedMap.
1.188
1.189 @@ -815,7 +816,7 @@
1.190 ///The type of the map that stores the distances of the nodes.
1.191
1.192 ///The type of the map that stores the distances of the nodes.
1.193 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.194 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.195 typedef typename Digraph::template NodeMap<int> DistMap;
1.196 ///Instantiates a DistMap.
1.197
1.198 @@ -830,18 +831,14 @@
1.199 ///The type of the DFS paths.
1.200
1.201 ///The type of the DFS paths.
1.202 - ///It must meet the \ref concepts::Path "Path" concept.
1.203 + ///It must conform to the \ref concepts::Path "Path" concept.
1.204 typedef lemon::Path<Digraph> Path;
1.205 };
1.206
1.207 /// Default traits class used by DfsWizard
1.208
1.209 - /// To make it easier to use Dfs algorithm
1.210 - /// we have created a wizard class.
1.211 - /// This \ref DfsWizard class needs default traits,
1.212 - /// as well as the \ref Dfs class.
1.213 - /// The \ref DfsWizardBase is a class to be the default traits of the
1.214 - /// \ref DfsWizard class.
1.215 + /// Default traits class used by DfsWizard.
1.216 + /// \tparam GR The type of the digraph.
1.217 template<class GR>
1.218 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.219 {
1.220 @@ -869,7 +866,7 @@
1.221 public:
1.222 /// Constructor.
1.223
1.224 - /// This constructor does not require parameters, therefore it initiates
1.225 + /// This constructor does not require parameters, it initiates
1.226 /// all of the attributes to \c 0.
1.227 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.228 _dist(0), _path(0), _di(0) {}
1.229 @@ -899,7 +896,6 @@
1.230 {
1.231 typedef TR Base;
1.232
1.233 - ///The type of the digraph the algorithm runs on.
1.234 typedef typename TR::Digraph Digraph;
1.235
1.236 typedef typename Digraph::Node Node;
1.237 @@ -907,16 +903,10 @@
1.238 typedef typename Digraph::Arc Arc;
1.239 typedef typename Digraph::OutArcIt OutArcIt;
1.240
1.241 - ///\brief The type of the map that stores the predecessor
1.242 - ///arcs of the DFS paths.
1.243 typedef typename TR::PredMap PredMap;
1.244 - ///\brief The type of the map that stores the distances of the nodes.
1.245 typedef typename TR::DistMap DistMap;
1.246 - ///\brief The type of the map that indicates which nodes are reached.
1.247 typedef typename TR::ReachedMap ReachedMap;
1.248 - ///\brief The type of the map that indicates which nodes are processed.
1.249 typedef typename TR::ProcessedMap ProcessedMap;
1.250 - ///The type of the DFS paths
1.251 typedef typename TR::Path Path;
1.252
1.253 public:
1.254 @@ -999,11 +989,12 @@
1.255 static PredMap *createPredMap(const Digraph &) { return 0; };
1.256 SetPredMapBase(const TR &b) : TR(b) {}
1.257 };
1.258 - ///\brief \ref named-func-param "Named parameter"
1.259 - ///for setting PredMap object.
1.260 +
1.261 + ///\brief \ref named-templ-param "Named parameter" for setting
1.262 + ///the predecessor map.
1.263 ///
1.264 - ///\ref named-func-param "Named parameter"
1.265 - ///for setting PredMap object.
1.266 + ///\ref named-templ-param "Named parameter" function for setting
1.267 + ///the map that stores the predecessor arcs of the nodes.
1.268 template<class T>
1.269 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.270 {
1.271 @@ -1017,11 +1008,12 @@
1.272 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.273 SetReachedMapBase(const TR &b) : TR(b) {}
1.274 };
1.275 - ///\brief \ref named-func-param "Named parameter"
1.276 - ///for setting ReachedMap object.
1.277 +
1.278 + ///\brief \ref named-templ-param "Named parameter" for setting
1.279 + ///the reached map.
1.280 ///
1.281 - /// \ref named-func-param "Named parameter"
1.282 - ///for setting ReachedMap object.
1.283 + ///\ref named-templ-param "Named parameter" function for setting
1.284 + ///the map that indicates which nodes are reached.
1.285 template<class T>
1.286 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.287 {
1.288 @@ -1035,11 +1027,13 @@
1.289 static DistMap *createDistMap(const Digraph &) { return 0; };
1.290 SetDistMapBase(const TR &b) : TR(b) {}
1.291 };
1.292 - ///\brief \ref named-func-param "Named parameter"
1.293 - ///for setting DistMap object.
1.294 +
1.295 + ///\brief \ref named-templ-param "Named parameter" for setting
1.296 + ///the distance map.
1.297 ///
1.298 - /// \ref named-func-param "Named parameter"
1.299 - ///for setting DistMap object.
1.300 + ///\ref named-templ-param "Named parameter" function for setting
1.301 + ///the map that stores the distances of the nodes calculated
1.302 + ///by the algorithm.
1.303 template<class T>
1.304 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.305 {
1.306 @@ -1053,11 +1047,12 @@
1.307 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.308 SetProcessedMapBase(const TR &b) : TR(b) {}
1.309 };
1.310 - ///\brief \ref named-func-param "Named parameter"
1.311 - ///for setting ProcessedMap object.
1.312 +
1.313 + ///\brief \ref named-func-param "Named parameter" for setting
1.314 + ///the processed map.
1.315 ///
1.316 - /// \ref named-func-param "Named parameter"
1.317 - ///for setting ProcessedMap object.
1.318 + ///\ref named-templ-param "Named parameter" function for setting
1.319 + ///the map that indicates which nodes are processed.
1.320 template<class T>
1.321 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.322 {
1.323 @@ -1208,7 +1203,7 @@
1.324 /// \brief The type of the map that indicates which nodes are reached.
1.325 ///
1.326 /// The type of the map that indicates which nodes are reached.
1.327 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.328 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.329 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.330
1.331 /// \brief Instantiates a ReachedMap.
1.332 @@ -1369,8 +1364,8 @@
1.333 /// \name Execution Control
1.334 /// The simplest way to execute the DFS algorithm is to use one of the
1.335 /// member functions called \ref run(Node) "run()".\n
1.336 - /// If you need more control on the execution, first you have to call
1.337 - /// \ref init(), then you can add a source node with \ref addSource()
1.338 + /// If you need better control on the execution, you have to call
1.339 + /// \ref init() first, then you can add a source node with \ref addSource()
1.340 /// and perform the actual computation with \ref start().
1.341 /// This procedure can be repeated if there are nodes that have not
1.342 /// been reached.
1.343 @@ -1620,7 +1615,7 @@
1.344
1.345 ///@{
1.346
1.347 - /// \brief Checks if a node is reached from the root(s).
1.348 + /// \brief Checks if the given node is reached from the root(s).
1.349 ///
1.350 /// Returns \c true if \c v is reached from the root(s).
1.351 ///