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