1.1 --- a/lemon/dfs.h Fri May 29 17:46:48 2009 +0100
1.2 +++ b/lemon/dfs.h Sun Aug 02 12:40:20 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 @@ -669,9 +670,9 @@
1.77
1.78 ///@{
1.79
1.80 - ///The DFS path to a node.
1.81 + ///The DFS path to the given node.
1.82
1.83 - ///Returns the DFS path to a node.
1.84 + ///Returns the DFS path to the given node from the root(s).
1.85 ///
1.86 ///\warning \c t should be reached from the root(s).
1.87 ///
1.88 @@ -679,9 +680,9 @@
1.89 ///must be called before using this function.
1.90 Path path(Node t) const { return Path(*G, *_pred, t); }
1.91
1.92 - ///The distance of a node from the root(s).
1.93 + ///The distance of the given node from the root(s).
1.94
1.95 - ///Returns the distance of a node from the root(s).
1.96 + ///Returns the distance of the given node from the root(s).
1.97 ///
1.98 ///\warning If node \c v is not reached from the root(s), then
1.99 ///the return value of this function is undefined.
1.100 @@ -690,7 +691,7 @@
1.101 ///must be called before using this function.
1.102 int dist(Node v) const { return (*_dist)[v]; }
1.103
1.104 - ///Returns the 'previous arc' of the %DFS tree for a node.
1.105 + ///Returns the 'previous arc' of the %DFS tree for the given node.
1.106
1.107 ///This function returns the 'previous arc' of the %DFS tree for the
1.108 ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.109 @@ -698,21 +699,21 @@
1.110 ///root(s) or if \c v is a root.
1.111 ///
1.112 ///The %DFS tree used here is equal to the %DFS tree used in
1.113 - ///\ref predNode().
1.114 + ///\ref predNode() and \ref predMap().
1.115 ///
1.116 ///\pre Either \ref run(Node) "run()" or \ref init()
1.117 ///must be called before using this function.
1.118 Arc predArc(Node v) const { return (*_pred)[v];}
1.119
1.120 - ///Returns the 'previous node' of the %DFS tree.
1.121 + ///Returns the 'previous node' of the %DFS tree for the given node.
1.122
1.123 ///This function returns the 'previous node' of the %DFS
1.124 ///tree for the node \c v, i.e. it returns the last but one node
1.125 - ///from a %DFS path from a root to \c v. It is \c INVALID
1.126 + ///of a %DFS path from a root to \c v. It is \c INVALID
1.127 ///if \c v is not reached from the root(s) or if \c v is a root.
1.128 ///
1.129 ///The %DFS tree used here is equal to the %DFS tree used in
1.130 - ///\ref predArc().
1.131 + ///\ref predArc() and \ref predMap().
1.132 ///
1.133 ///\pre Either \ref run(Node) "run()" or \ref init()
1.134 ///must be called before using this function.
1.135 @@ -733,13 +734,13 @@
1.136 ///predecessor arcs.
1.137 ///
1.138 ///Returns a const reference to the node map that stores the predecessor
1.139 - ///arcs, which form the DFS tree.
1.140 + ///arcs, which form the DFS tree (forest).
1.141 ///
1.142 ///\pre Either \ref run(Node) "run()" or \ref init()
1.143 ///must be called before using this function.
1.144 const PredMap &predMap() const { return *_pred;}
1.145
1.146 - ///Checks if a node is reached from the root(s).
1.147 + ///Checks if the given node. node is reached from the root(s).
1.148
1.149 ///Returns \c true if \c v is reached from the root(s).
1.150 ///
1.151 @@ -765,7 +766,7 @@
1.152 ///
1.153 ///The type of the map that stores the predecessor
1.154 ///arcs of the %DFS paths.
1.155 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.156 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.157 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.158 ///Instantiates a PredMap.
1.159
1.160 @@ -780,7 +781,7 @@
1.161 ///The type of the map that indicates which nodes are processed.
1.162
1.163 ///The type of the map that indicates which nodes are processed.
1.164 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.165 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.166 ///By default it is a NullMap.
1.167 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.168 ///Instantiates a ProcessedMap.
1.169 @@ -800,7 +801,7 @@
1.170 ///The type of the map that indicates which nodes are reached.
1.171
1.172 ///The type of the map that indicates which nodes are reached.
1.173 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.174 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.175 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.176 ///Instantiates a ReachedMap.
1.177
1.178 @@ -815,7 +816,7 @@
1.179 ///The type of the map that stores the distances of the nodes.
1.180
1.181 ///The type of the map that stores the distances of the nodes.
1.182 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.183 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.184 typedef typename Digraph::template NodeMap<int> DistMap;
1.185 ///Instantiates a DistMap.
1.186
1.187 @@ -830,18 +831,14 @@
1.188 ///The type of the DFS paths.
1.189
1.190 ///The type of the DFS paths.
1.191 - ///It must meet the \ref concepts::Path "Path" concept.
1.192 + ///It must conform to the \ref concepts::Path "Path" concept.
1.193 typedef lemon::Path<Digraph> Path;
1.194 };
1.195
1.196 /// Default traits class used by DfsWizard
1.197
1.198 - /// To make it easier to use Dfs algorithm
1.199 - /// we have created a wizard class.
1.200 - /// This \ref DfsWizard class needs default traits,
1.201 - /// as well as the \ref Dfs class.
1.202 - /// The \ref DfsWizardBase is a class to be the default traits of the
1.203 - /// \ref DfsWizard class.
1.204 + /// Default traits class used by DfsWizard.
1.205 + /// \tparam GR The type of the digraph.
1.206 template<class GR>
1.207 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.208 {
1.209 @@ -869,7 +866,7 @@
1.210 public:
1.211 /// Constructor.
1.212
1.213 - /// This constructor does not require parameters, therefore it initiates
1.214 + /// This constructor does not require parameters, it initiates
1.215 /// all of the attributes to \c 0.
1.216 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.217 _dist(0), _path(0), _di(0) {}
1.218 @@ -899,7 +896,6 @@
1.219 {
1.220 typedef TR Base;
1.221
1.222 - ///The type of the digraph the algorithm runs on.
1.223 typedef typename TR::Digraph Digraph;
1.224
1.225 typedef typename Digraph::Node Node;
1.226 @@ -907,16 +903,10 @@
1.227 typedef typename Digraph::Arc Arc;
1.228 typedef typename Digraph::OutArcIt OutArcIt;
1.229
1.230 - ///\brief The type of the map that stores the predecessor
1.231 - ///arcs of the DFS paths.
1.232 typedef typename TR::PredMap PredMap;
1.233 - ///\brief The type of the map that stores the distances of the nodes.
1.234 typedef typename TR::DistMap DistMap;
1.235 - ///\brief The type of the map that indicates which nodes are reached.
1.236 typedef typename TR::ReachedMap ReachedMap;
1.237 - ///\brief The type of the map that indicates which nodes are processed.
1.238 typedef typename TR::ProcessedMap ProcessedMap;
1.239 - ///The type of the DFS paths
1.240 typedef typename TR::Path Path;
1.241
1.242 public:
1.243 @@ -999,11 +989,12 @@
1.244 static PredMap *createPredMap(const Digraph &) { return 0; };
1.245 SetPredMapBase(const TR &b) : TR(b) {}
1.246 };
1.247 - ///\brief \ref named-func-param "Named parameter"
1.248 - ///for setting PredMap object.
1.249 +
1.250 + ///\brief \ref named-templ-param "Named parameter" for setting
1.251 + ///the predecessor map.
1.252 ///
1.253 - ///\ref named-func-param "Named parameter"
1.254 - ///for setting PredMap object.
1.255 + ///\ref named-templ-param "Named parameter" function for setting
1.256 + ///the map that stores the predecessor arcs of the nodes.
1.257 template<class T>
1.258 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.259 {
1.260 @@ -1017,11 +1008,12 @@
1.261 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.262 SetReachedMapBase(const TR &b) : TR(b) {}
1.263 };
1.264 - ///\brief \ref named-func-param "Named parameter"
1.265 - ///for setting ReachedMap object.
1.266 +
1.267 + ///\brief \ref named-templ-param "Named parameter" for setting
1.268 + ///the reached map.
1.269 ///
1.270 - /// \ref named-func-param "Named parameter"
1.271 - ///for setting ReachedMap object.
1.272 + ///\ref named-templ-param "Named parameter" function for setting
1.273 + ///the map that indicates which nodes are reached.
1.274 template<class T>
1.275 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.276 {
1.277 @@ -1035,11 +1027,13 @@
1.278 static DistMap *createDistMap(const Digraph &) { return 0; };
1.279 SetDistMapBase(const TR &b) : TR(b) {}
1.280 };
1.281 - ///\brief \ref named-func-param "Named parameter"
1.282 - ///for setting DistMap object.
1.283 +
1.284 + ///\brief \ref named-templ-param "Named parameter" for setting
1.285 + ///the distance map.
1.286 ///
1.287 - /// \ref named-func-param "Named parameter"
1.288 - ///for setting DistMap object.
1.289 + ///\ref named-templ-param "Named parameter" function for setting
1.290 + ///the map that stores the distances of the nodes calculated
1.291 + ///by the algorithm.
1.292 template<class T>
1.293 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.294 {
1.295 @@ -1053,11 +1047,12 @@
1.296 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.297 SetProcessedMapBase(const TR &b) : TR(b) {}
1.298 };
1.299 - ///\brief \ref named-func-param "Named parameter"
1.300 - ///for setting ProcessedMap object.
1.301 +
1.302 + ///\brief \ref named-func-param "Named parameter" for setting
1.303 + ///the processed map.
1.304 ///
1.305 - /// \ref named-func-param "Named parameter"
1.306 - ///for setting ProcessedMap object.
1.307 + ///\ref named-templ-param "Named parameter" function for setting
1.308 + ///the map that indicates which nodes are processed.
1.309 template<class T>
1.310 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.311 {
1.312 @@ -1208,7 +1203,7 @@
1.313 /// \brief The type of the map that indicates which nodes are reached.
1.314 ///
1.315 /// The type of the map that indicates which nodes are reached.
1.316 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.317 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.318 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.319
1.320 /// \brief Instantiates a ReachedMap.
1.321 @@ -1620,7 +1615,7 @@
1.322
1.323 ///@{
1.324
1.325 - /// \brief Checks if a node is reached from the root(s).
1.326 + /// \brief Checks if the given node is reached from the root(s).
1.327 ///
1.328 /// Returns \c true if \c v is reached from the root(s).
1.329 ///