1.1 --- a/lemon/bfs.h Sat Sep 26 07:16:22 2009 +0200
1.2 +++ b/lemon/bfs.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 shortest 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 @@ -225,7 +226,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 Bfs< Digraph, SetPredMapTraits<T> > {
1.48 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
1.49 @@ -245,7 +246,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 Bfs< Digraph, SetDistMapTraits<T> > {
1.57 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
1.58 @@ -265,7 +266,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 Bfs< Digraph, SetReachedMapTraits<T> > {
1.66 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
1.67 @@ -285,7 +286,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 Bfs< Digraph, SetProcessedMapTraits<T> > {
1.75 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
1.76 @@ -413,8 +414,8 @@
1.77 ///\name Execution Control
1.78 ///The simplest way to execute the BFS 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 several source nodes with
1.82 + ///If you need better control on the execution, you have to call
1.83 + ///\ref init() first, then you can add several source nodes with
1.84 ///\ref addSource(). Finally the actual path computation can be
1.85 ///performed with one of the \ref start() functions.
1.86
1.87 @@ -737,9 +738,9 @@
1.88
1.89 ///@{
1.90
1.91 - ///The shortest path to a node.
1.92 + ///The shortest path to the given node.
1.93
1.94 - ///Returns the shortest path to a node.
1.95 + ///Returns the shortest 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 @@ -747,9 +748,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 @@ -758,29 +759,31 @@
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 shortest path tree for a node.
1.116 -
1.117 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.118 + ///the given node.
1.119 + ///
1.120 ///This function returns the 'previous arc' of the shortest path
1.121 ///tree for the node \c v, i.e. it returns the last arc of a
1.122 ///shortest path from a root to \c v. It is \c INVALID if \c v
1.123 ///is not reached from the root(s) or if \c v is a root.
1.124 ///
1.125 ///The shortest path tree used here is equal to the shortest path
1.126 - ///tree used in \ref predNode().
1.127 + ///tree used in \ref predNode() and \ref predMap().
1.128 ///
1.129 ///\pre Either \ref run(Node) "run()" or \ref init()
1.130 ///must be called before using this function.
1.131 Arc predArc(Node v) const { return (*_pred)[v];}
1.132
1.133 - ///Returns the 'previous node' of the shortest path tree for a node.
1.134 -
1.135 + ///\brief Returns the 'previous node' of the shortest path tree for
1.136 + ///the given node.
1.137 + ///
1.138 ///This function returns the 'previous node' of the shortest path
1.139 ///tree for the node \c v, i.e. it returns the last but one node
1.140 - ///from a shortest path from a root to \c v. It is \c INVALID
1.141 + ///of a shortest path from a root to \c v. It is \c INVALID
1.142 ///if \c v is not reached from the root(s) or if \c v is a root.
1.143 ///
1.144 ///The shortest path tree used here is equal to the shortest path
1.145 - ///tree used in \ref predArc().
1.146 + ///tree used in \ref predArc() and \ref predMap().
1.147 ///
1.148 ///\pre Either \ref run(Node) "run()" or \ref init()
1.149 ///must be called before using this function.
1.150 @@ -801,13 +804,13 @@
1.151 ///predecessor arcs.
1.152 ///
1.153 ///Returns a const reference to the node map that stores the predecessor
1.154 - ///arcs, which form the shortest path tree.
1.155 + ///arcs, which form the shortest path tree (forest).
1.156 ///
1.157 ///\pre Either \ref run(Node) "run()" or \ref init()
1.158 ///must be called before using this function.
1.159 const PredMap &predMap() const { return *_pred;}
1.160
1.161 - ///Checks if a node is reached from the root(s).
1.162 + ///Checks if the given node is reached from the root(s).
1.163
1.164 ///Returns \c true if \c v is reached from the root(s).
1.165 ///
1.166 @@ -833,7 +836,7 @@
1.167 ///
1.168 ///The type of the map that stores the predecessor
1.169 ///arcs of the shortest paths.
1.170 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.171 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.172 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.173 ///Instantiates a PredMap.
1.174
1.175 @@ -848,7 +851,7 @@
1.176 ///The type of the map that indicates which nodes are processed.
1.177
1.178 ///The type of the map that indicates which nodes are processed.
1.179 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.180 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.181 ///By default it is a NullMap.
1.182 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.183 ///Instantiates a ProcessedMap.
1.184 @@ -868,7 +871,7 @@
1.185 ///The type of the map that indicates which nodes are reached.
1.186
1.187 ///The type of the map that indicates which nodes are reached.
1.188 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.189 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.190 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.191 ///Instantiates a ReachedMap.
1.192
1.193 @@ -883,7 +886,7 @@
1.194 ///The type of the map that stores the distances of the nodes.
1.195
1.196 ///The type of the map that stores the distances of the nodes.
1.197 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.198 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.199 typedef typename Digraph::template NodeMap<int> DistMap;
1.200 ///Instantiates a DistMap.
1.201
1.202 @@ -898,18 +901,14 @@
1.203 ///The type of the shortest paths.
1.204
1.205 ///The type of the shortest paths.
1.206 - ///It must meet the \ref concepts::Path "Path" concept.
1.207 + ///It must conform to the \ref concepts::Path "Path" concept.
1.208 typedef lemon::Path<Digraph> Path;
1.209 };
1.210
1.211 /// Default traits class used by BfsWizard
1.212
1.213 - /// To make it easier to use Bfs algorithm
1.214 - /// we have created a wizard class.
1.215 - /// This \ref BfsWizard class needs default traits,
1.216 - /// as well as the \ref Bfs class.
1.217 - /// The \ref BfsWizardBase is a class to be the default traits of the
1.218 - /// \ref BfsWizard class.
1.219 + /// Default traits class used by BfsWizard.
1.220 + /// \tparam GR The type of the digraph.
1.221 template<class GR>
1.222 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
1.223 {
1.224 @@ -937,7 +936,7 @@
1.225 public:
1.226 /// Constructor.
1.227
1.228 - /// This constructor does not require parameters, therefore it initiates
1.229 + /// This constructor does not require parameters, it initiates
1.230 /// all of the attributes to \c 0.
1.231 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.232 _dist(0), _path(0), _di(0) {}
1.233 @@ -967,7 +966,6 @@
1.234 {
1.235 typedef TR Base;
1.236
1.237 - ///The type of the digraph the algorithm runs on.
1.238 typedef typename TR::Digraph Digraph;
1.239
1.240 typedef typename Digraph::Node Node;
1.241 @@ -975,16 +973,10 @@
1.242 typedef typename Digraph::Arc Arc;
1.243 typedef typename Digraph::OutArcIt OutArcIt;
1.244
1.245 - ///\brief The type of the map that stores the predecessor
1.246 - ///arcs of the shortest paths.
1.247 typedef typename TR::PredMap PredMap;
1.248 - ///\brief The type of the map that stores the distances of the nodes.
1.249 typedef typename TR::DistMap DistMap;
1.250 - ///\brief The type of the map that indicates which nodes are reached.
1.251 typedef typename TR::ReachedMap ReachedMap;
1.252 - ///\brief The type of the map that indicates which nodes are processed.
1.253 typedef typename TR::ProcessedMap ProcessedMap;
1.254 - ///The type of the shortest paths
1.255 typedef typename TR::Path Path;
1.256
1.257 public:
1.258 @@ -1067,11 +1059,12 @@
1.259 static PredMap *createPredMap(const Digraph &) { return 0; };
1.260 SetPredMapBase(const TR &b) : TR(b) {}
1.261 };
1.262 - ///\brief \ref named-func-param "Named parameter"
1.263 - ///for setting PredMap object.
1.264 +
1.265 + ///\brief \ref named-templ-param "Named parameter" for setting
1.266 + ///the predecessor map.
1.267 ///
1.268 - ///\ref named-func-param "Named parameter"
1.269 - ///for setting PredMap object.
1.270 + ///\ref named-templ-param "Named parameter" function for setting
1.271 + ///the map that stores the predecessor arcs of the nodes.
1.272 template<class T>
1.273 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.274 {
1.275 @@ -1085,11 +1078,12 @@
1.276 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.277 SetReachedMapBase(const TR &b) : TR(b) {}
1.278 };
1.279 - ///\brief \ref named-func-param "Named parameter"
1.280 - ///for setting ReachedMap object.
1.281 +
1.282 + ///\brief \ref named-templ-param "Named parameter" for setting
1.283 + ///the reached map.
1.284 ///
1.285 - /// \ref named-func-param "Named parameter"
1.286 - ///for setting ReachedMap object.
1.287 + ///\ref named-templ-param "Named parameter" function for setting
1.288 + ///the map that indicates which nodes are reached.
1.289 template<class T>
1.290 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.291 {
1.292 @@ -1103,11 +1097,13 @@
1.293 static DistMap *createDistMap(const Digraph &) { return 0; };
1.294 SetDistMapBase(const TR &b) : TR(b) {}
1.295 };
1.296 - ///\brief \ref named-func-param "Named parameter"
1.297 - ///for setting DistMap object.
1.298 +
1.299 + ///\brief \ref named-templ-param "Named parameter" for setting
1.300 + ///the distance map.
1.301 ///
1.302 - /// \ref named-func-param "Named parameter"
1.303 - ///for setting DistMap object.
1.304 + ///\ref named-templ-param "Named parameter" function for setting
1.305 + ///the map that stores the distances of the nodes calculated
1.306 + ///by the algorithm.
1.307 template<class T>
1.308 BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.309 {
1.310 @@ -1121,11 +1117,12 @@
1.311 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.312 SetProcessedMapBase(const TR &b) : TR(b) {}
1.313 };
1.314 - ///\brief \ref named-func-param "Named parameter"
1.315 - ///for setting ProcessedMap object.
1.316 +
1.317 + ///\brief \ref named-func-param "Named parameter" for setting
1.318 + ///the processed map.
1.319 ///
1.320 - /// \ref named-func-param "Named parameter"
1.321 - ///for setting ProcessedMap object.
1.322 + ///\ref named-templ-param "Named parameter" function for setting
1.323 + ///the map that indicates which nodes are processed.
1.324 template<class T>
1.325 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.326 {
1.327 @@ -1264,7 +1261,7 @@
1.328 /// \brief The type of the map that indicates which nodes are reached.
1.329 ///
1.330 /// The type of the map that indicates which nodes are reached.
1.331 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.332 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.333 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.334
1.335 /// \brief Instantiates a ReachedMap.
1.336 @@ -1425,8 +1422,8 @@
1.337 /// \name Execution Control
1.338 /// The simplest way to execute the BFS algorithm is to use one of the
1.339 /// member functions called \ref run(Node) "run()".\n
1.340 - /// If you need more control on the execution, first you have to call
1.341 - /// \ref init(), then you can add several source nodes with
1.342 + /// If you need better control on the execution, you have to call
1.343 + /// \ref init() first, then you can add several source nodes with
1.344 /// \ref addSource(). Finally the actual path computation can be
1.345 /// performed with one of the \ref start() functions.
1.346
1.347 @@ -1735,7 +1732,7 @@
1.348
1.349 ///@{
1.350
1.351 - /// \brief Checks if a node is reached from the root(s).
1.352 + /// \brief Checks if the given node is reached from the root(s).
1.353 ///
1.354 /// Returns \c true if \c v is reached from the root(s).
1.355 ///