1.1 --- a/lemon/dfs.h Sun Oct 04 10:15:32 2009 +0200
1.2 +++ b/lemon/dfs.h Wed Dec 09 11:14:06 2009 +0100
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 @@ -632,12 +633,8 @@
1.88
1.89 ///Runs the algorithm to visit all nodes in the digraph.
1.90
1.91 - ///This method runs the %DFS algorithm in order to compute the
1.92 - ///%DFS path to each node.
1.93 - ///
1.94 - ///The algorithm computes
1.95 - ///- the %DFS tree (forest),
1.96 - ///- the distance of each node from the root(s) in the %DFS tree.
1.97 + ///This method runs the %DFS algorithm in order to visit all nodes
1.98 + ///in the digraph.
1.99 ///
1.100 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
1.101 ///\code
1.102 @@ -669,9 +666,9 @@
1.103
1.104 ///@{
1.105
1.106 - ///The DFS path to a node.
1.107 + ///The DFS path to the given node.
1.108
1.109 - ///Returns the DFS path to a node.
1.110 + ///Returns the DFS path to the given node from the root(s).
1.111 ///
1.112 ///\warning \c t should be reached from the root(s).
1.113 ///
1.114 @@ -679,9 +676,9 @@
1.115 ///must be called before using this function.
1.116 Path path(Node t) const { return Path(*G, *_pred, t); }
1.117
1.118 - ///The distance of a node from the root(s).
1.119 + ///The distance of the given node from the root(s).
1.120
1.121 - ///Returns the distance of a node from the root(s).
1.122 + ///Returns the distance of the given node from the root(s).
1.123 ///
1.124 ///\warning If node \c v is not reached from the root(s), then
1.125 ///the return value of this function is undefined.
1.126 @@ -690,7 +687,7 @@
1.127 ///must be called before using this function.
1.128 int dist(Node v) const { return (*_dist)[v]; }
1.129
1.130 - ///Returns the 'previous arc' of the %DFS tree for a node.
1.131 + ///Returns the 'previous arc' of the %DFS tree for the given node.
1.132
1.133 ///This function returns the 'previous arc' of the %DFS tree for the
1.134 ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.135 @@ -698,21 +695,21 @@
1.136 ///root(s) or if \c v is a root.
1.137 ///
1.138 ///The %DFS tree used here is equal to the %DFS tree used in
1.139 - ///\ref predNode().
1.140 + ///\ref predNode() and \ref predMap().
1.141 ///
1.142 ///\pre Either \ref run(Node) "run()" or \ref init()
1.143 ///must be called before using this function.
1.144 Arc predArc(Node v) const { return (*_pred)[v];}
1.145
1.146 - ///Returns the 'previous node' of the %DFS tree.
1.147 + ///Returns the 'previous node' of the %DFS tree for the given node.
1.148
1.149 ///This function returns the 'previous node' of the %DFS
1.150 ///tree for the node \c v, i.e. it returns the last but one node
1.151 - ///from a %DFS path from a root to \c v. It is \c INVALID
1.152 + ///of a %DFS path from a root to \c v. It is \c INVALID
1.153 ///if \c v is not reached from the root(s) or if \c v is a root.
1.154 ///
1.155 ///The %DFS tree used here is equal to the %DFS tree used in
1.156 - ///\ref predArc().
1.157 + ///\ref predArc() and \ref predMap().
1.158 ///
1.159 ///\pre Either \ref run(Node) "run()" or \ref init()
1.160 ///must be called before using this function.
1.161 @@ -733,13 +730,13 @@
1.162 ///predecessor arcs.
1.163 ///
1.164 ///Returns a const reference to the node map that stores the predecessor
1.165 - ///arcs, which form the DFS tree.
1.166 + ///arcs, which form the DFS tree (forest).
1.167 ///
1.168 ///\pre Either \ref run(Node) "run()" or \ref init()
1.169 ///must be called before using this function.
1.170 const PredMap &predMap() const { return *_pred;}
1.171
1.172 - ///Checks if a node is reached from the root(s).
1.173 + ///Checks if the given node. node is reached from the root(s).
1.174
1.175 ///Returns \c true if \c v is reached from the root(s).
1.176 ///
1.177 @@ -765,7 +762,7 @@
1.178 ///
1.179 ///The type of the map that stores the predecessor
1.180 ///arcs of the %DFS paths.
1.181 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.182 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.183 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.184 ///Instantiates a PredMap.
1.185
1.186 @@ -780,8 +777,8 @@
1.187 ///The type of the map that indicates which nodes are processed.
1.188
1.189 ///The type of the map that indicates which nodes are processed.
1.190 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.191 - ///By default it is a NullMap.
1.192 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.193 + ///By default, it is a NullMap.
1.194 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.195 ///Instantiates a ProcessedMap.
1.196
1.197 @@ -800,7 +797,7 @@
1.198 ///The type of the map that indicates which nodes are reached.
1.199
1.200 ///The type of the map that indicates which nodes are reached.
1.201 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.202 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.203 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.204 ///Instantiates a ReachedMap.
1.205
1.206 @@ -815,7 +812,7 @@
1.207 ///The type of the map that stores the distances of the nodes.
1.208
1.209 ///The type of the map that stores the distances of the nodes.
1.210 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.211 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.212 typedef typename Digraph::template NodeMap<int> DistMap;
1.213 ///Instantiates a DistMap.
1.214
1.215 @@ -830,18 +827,14 @@
1.216 ///The type of the DFS paths.
1.217
1.218 ///The type of the DFS paths.
1.219 - ///It must meet the \ref concepts::Path "Path" concept.
1.220 + ///It must conform to the \ref concepts::Path "Path" concept.
1.221 typedef lemon::Path<Digraph> Path;
1.222 };
1.223
1.224 /// Default traits class used by DfsWizard
1.225
1.226 - /// To make it easier to use Dfs algorithm
1.227 - /// we have created a wizard class.
1.228 - /// This \ref DfsWizard class needs default traits,
1.229 - /// as well as the \ref Dfs class.
1.230 - /// The \ref DfsWizardBase is a class to be the default traits of the
1.231 - /// \ref DfsWizard class.
1.232 + /// Default traits class used by DfsWizard.
1.233 + /// \tparam GR The type of the digraph.
1.234 template<class GR>
1.235 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.236 {
1.237 @@ -869,7 +862,7 @@
1.238 public:
1.239 /// Constructor.
1.240
1.241 - /// This constructor does not require parameters, therefore it initiates
1.242 + /// This constructor does not require parameters, it initiates
1.243 /// all of the attributes to \c 0.
1.244 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.245 _dist(0), _path(0), _di(0) {}
1.246 @@ -899,7 +892,6 @@
1.247 {
1.248 typedef TR Base;
1.249
1.250 - ///The type of the digraph the algorithm runs on.
1.251 typedef typename TR::Digraph Digraph;
1.252
1.253 typedef typename Digraph::Node Node;
1.254 @@ -907,16 +899,10 @@
1.255 typedef typename Digraph::Arc Arc;
1.256 typedef typename Digraph::OutArcIt OutArcIt;
1.257
1.258 - ///\brief The type of the map that stores the predecessor
1.259 - ///arcs of the DFS paths.
1.260 typedef typename TR::PredMap PredMap;
1.261 - ///\brief The type of the map that stores the distances of the nodes.
1.262 typedef typename TR::DistMap DistMap;
1.263 - ///\brief The type of the map that indicates which nodes are reached.
1.264 typedef typename TR::ReachedMap ReachedMap;
1.265 - ///\brief The type of the map that indicates which nodes are processed.
1.266 typedef typename TR::ProcessedMap ProcessedMap;
1.267 - ///The type of the DFS paths
1.268 typedef typename TR::Path Path;
1.269
1.270 public:
1.271 @@ -986,8 +972,8 @@
1.272
1.273 ///Runs DFS algorithm to visit all nodes in the digraph.
1.274
1.275 - ///This method runs DFS algorithm in order to compute
1.276 - ///the DFS path to each node.
1.277 + ///This method runs DFS algorithm in order to visit all nodes
1.278 + ///in the digraph.
1.279 void run()
1.280 {
1.281 run(INVALID);
1.282 @@ -999,11 +985,12 @@
1.283 static PredMap *createPredMap(const Digraph &) { return 0; };
1.284 SetPredMapBase(const TR &b) : TR(b) {}
1.285 };
1.286 - ///\brief \ref named-func-param "Named parameter"
1.287 - ///for setting PredMap object.
1.288 +
1.289 + ///\brief \ref named-templ-param "Named parameter" for setting
1.290 + ///the predecessor map.
1.291 ///
1.292 - ///\ref named-func-param "Named parameter"
1.293 - ///for setting PredMap object.
1.294 + ///\ref named-templ-param "Named parameter" function for setting
1.295 + ///the map that stores the predecessor arcs of the nodes.
1.296 template<class T>
1.297 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.298 {
1.299 @@ -1017,11 +1004,12 @@
1.300 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.301 SetReachedMapBase(const TR &b) : TR(b) {}
1.302 };
1.303 - ///\brief \ref named-func-param "Named parameter"
1.304 - ///for setting ReachedMap object.
1.305 +
1.306 + ///\brief \ref named-templ-param "Named parameter" for setting
1.307 + ///the reached map.
1.308 ///
1.309 - /// \ref named-func-param "Named parameter"
1.310 - ///for setting ReachedMap object.
1.311 + ///\ref named-templ-param "Named parameter" function for setting
1.312 + ///the map that indicates which nodes are reached.
1.313 template<class T>
1.314 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.315 {
1.316 @@ -1035,11 +1023,13 @@
1.317 static DistMap *createDistMap(const Digraph &) { return 0; };
1.318 SetDistMapBase(const TR &b) : TR(b) {}
1.319 };
1.320 - ///\brief \ref named-func-param "Named parameter"
1.321 - ///for setting DistMap object.
1.322 +
1.323 + ///\brief \ref named-templ-param "Named parameter" for setting
1.324 + ///the distance map.
1.325 ///
1.326 - /// \ref named-func-param "Named parameter"
1.327 - ///for setting DistMap object.
1.328 + ///\ref named-templ-param "Named parameter" function for setting
1.329 + ///the map that stores the distances of the nodes calculated
1.330 + ///by the algorithm.
1.331 template<class T>
1.332 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.333 {
1.334 @@ -1053,11 +1043,12 @@
1.335 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.336 SetProcessedMapBase(const TR &b) : TR(b) {}
1.337 };
1.338 - ///\brief \ref named-func-param "Named parameter"
1.339 - ///for setting ProcessedMap object.
1.340 +
1.341 + ///\brief \ref named-func-param "Named parameter" for setting
1.342 + ///the processed map.
1.343 ///
1.344 - /// \ref named-func-param "Named parameter"
1.345 - ///for setting ProcessedMap object.
1.346 + ///\ref named-templ-param "Named parameter" function for setting
1.347 + ///the map that indicates which nodes are processed.
1.348 template<class T>
1.349 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.350 {
1.351 @@ -1208,7 +1199,7 @@
1.352 /// \brief The type of the map that indicates which nodes are reached.
1.353 ///
1.354 /// The type of the map that indicates which nodes are reached.
1.355 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.356 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.357 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.358
1.359 /// \brief Instantiates a ReachedMap.
1.360 @@ -1369,8 +1360,8 @@
1.361 /// \name Execution Control
1.362 /// The simplest way to execute the DFS algorithm is to use one of the
1.363 /// member functions called \ref run(Node) "run()".\n
1.364 - /// If you need more control on the execution, first you have to call
1.365 - /// \ref init(), then you can add a source node with \ref addSource()
1.366 + /// If you need better control on the execution, you have to call
1.367 + /// \ref init() first, then you can add a source node with \ref addSource()
1.368 /// and perform the actual computation with \ref start().
1.369 /// This procedure can be repeated if there are nodes that have not
1.370 /// been reached.
1.371 @@ -1583,12 +1574,8 @@
1.372
1.373 /// \brief Runs the algorithm to visit all nodes in the digraph.
1.374
1.375 - /// This method runs the %DFS algorithm in order to
1.376 - /// compute the %DFS path to each node.
1.377 - ///
1.378 - /// The algorithm computes
1.379 - /// - the %DFS tree (forest),
1.380 - /// - the distance of each node from the root(s) in the %DFS tree.
1.381 + /// This method runs the %DFS algorithm in order to visit all nodes
1.382 + /// in the digraph.
1.383 ///
1.384 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1.385 ///\code
1.386 @@ -1620,7 +1607,7 @@
1.387
1.388 ///@{
1.389
1.390 - /// \brief Checks if a node is reached from the root(s).
1.391 + /// \brief Checks if the given node is reached from the root(s).
1.392 ///
1.393 /// Returns \c true if \c v is reached from the root(s).
1.394 ///