1.1 --- a/lemon/bfs.h Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/lemon/bfs.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -47,13 +47,13 @@
1.13 ///
1.14 ///The type of the map that stores the predecessor
1.15 ///arcs of the shortest paths.
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 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.19 - ///Instantiates a PredMap.
1.20 + ///Instantiates a \c PredMap.
1.21
1.22 - ///This function instantiates a PredMap.
1.23 + ///This function instantiates a \ref PredMap.
1.24 ///\param g is the digraph, to which we would like to define the
1.25 - ///PredMap.
1.26 + ///\ref PredMap.
1.27 static PredMap *createPredMap(const Digraph &g)
1.28 {
1.29 return new PredMap(g);
1.30 @@ -62,13 +62,14 @@
1.31 ///The type of the map that indicates which nodes are processed.
1.32
1.33 ///The type of the map that indicates which nodes are processed.
1.34 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.35 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.36 + ///By default it is a NullMap.
1.37 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.38 - ///Instantiates a ProcessedMap.
1.39 + ///Instantiates a \c ProcessedMap.
1.40
1.41 - ///This function instantiates a ProcessedMap.
1.42 + ///This function instantiates a \ref ProcessedMap.
1.43 ///\param g is the digraph, to which
1.44 - ///we would like to define the ProcessedMap
1.45 + ///we would like to define the \ref ProcessedMap
1.46 #ifdef DOXYGEN
1.47 static ProcessedMap *createProcessedMap(const Digraph &g)
1.48 #else
1.49 @@ -81,13 +82,13 @@
1.50 ///The type of the map that indicates which nodes are reached.
1.51
1.52 ///The type of the map that indicates which nodes are reached.
1.53 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.54 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.55 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.56 - ///Instantiates a ReachedMap.
1.57 + ///Instantiates a \c ReachedMap.
1.58
1.59 - ///This function instantiates a ReachedMap.
1.60 + ///This function instantiates a \ref ReachedMap.
1.61 ///\param g is the digraph, to which
1.62 - ///we would like to define the ReachedMap.
1.63 + ///we would like to define the \ref ReachedMap.
1.64 static ReachedMap *createReachedMap(const Digraph &g)
1.65 {
1.66 return new ReachedMap(g);
1.67 @@ -96,13 +97,13 @@
1.68 ///The type of the map that stores the distances of the nodes.
1.69
1.70 ///The type of the map that stores the distances of the nodes.
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 typedef typename Digraph::template NodeMap<int> DistMap;
1.74 - ///Instantiates a DistMap.
1.75 + ///Instantiates a \c DistMap.
1.76
1.77 - ///This function instantiates a DistMap.
1.78 + ///This function instantiates a \ref DistMap.
1.79 ///\param g is the digraph, to which we would like to define the
1.80 - ///DistMap.
1.81 + ///\ref DistMap.
1.82 static DistMap *createDistMap(const Digraph &g)
1.83 {
1.84 return new DistMap(g);
1.85 @@ -119,13 +120,7 @@
1.86 ///used easier.
1.87 ///
1.88 ///\tparam GR The type of the digraph the algorithm runs on.
1.89 - ///The default value is \ref ListDigraph. The value of GR is not used
1.90 - ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
1.91 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.92 - ///The default traits class is
1.93 - ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.94 - ///See \ref BfsDefaultTraits for the documentation of
1.95 - ///a Bfs traits class.
1.96 + ///The default type is \ref ListDigraph.
1.97 #ifdef DOXYGEN
1.98 template <typename GR,
1.99 typename TR>
1.100 @@ -151,7 +146,7 @@
1.101 ///The type of the paths.
1.102 typedef PredMapPath<Digraph, PredMap> Path;
1.103
1.104 - ///The traits class.
1.105 + ///The \ref BfsDefaultTraits "traits class" of the algorithm.
1.106 typedef TR Traits;
1.107
1.108 private:
1.109 @@ -213,7 +208,7 @@
1.110
1.111 typedef Bfs Create;
1.112
1.113 - ///\name Named template parameters
1.114 + ///\name Named Template Parameters
1.115
1.116 ///@{
1.117
1.118 @@ -227,10 +222,11 @@
1.119 }
1.120 };
1.121 ///\brief \ref named-templ-param "Named parameter" for setting
1.122 - ///PredMap type.
1.123 + ///\c PredMap type.
1.124 ///
1.125 ///\ref named-templ-param "Named parameter" for setting
1.126 - ///PredMap type.
1.127 + ///\c PredMap type.
1.128 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.129 template <class T>
1.130 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.131 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
1.132 @@ -246,10 +242,11 @@
1.133 }
1.134 };
1.135 ///\brief \ref named-templ-param "Named parameter" for setting
1.136 - ///DistMap type.
1.137 + ///\c DistMap type.
1.138 ///
1.139 ///\ref named-templ-param "Named parameter" for setting
1.140 - ///DistMap type.
1.141 + ///\c DistMap type.
1.142 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.143 template <class T>
1.144 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.145 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
1.146 @@ -265,10 +262,11 @@
1.147 }
1.148 };
1.149 ///\brief \ref named-templ-param "Named parameter" for setting
1.150 - ///ReachedMap type.
1.151 + ///\c ReachedMap type.
1.152 ///
1.153 ///\ref named-templ-param "Named parameter" for setting
1.154 - ///ReachedMap type.
1.155 + ///\c ReachedMap type.
1.156 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.157 template <class T>
1.158 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.159 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
1.160 @@ -284,10 +282,11 @@
1.161 }
1.162 };
1.163 ///\brief \ref named-templ-param "Named parameter" for setting
1.164 - ///ProcessedMap type.
1.165 + ///\c ProcessedMap type.
1.166 ///
1.167 ///\ref named-templ-param "Named parameter" for setting
1.168 - ///ProcessedMap type.
1.169 + ///\c ProcessedMap type.
1.170 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.171 template <class T>
1.172 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.173 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
1.174 @@ -302,10 +301,10 @@
1.175 }
1.176 };
1.177 ///\brief \ref named-templ-param "Named parameter" for setting
1.178 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.179 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.180 ///
1.181 ///\ref named-templ-param "Named parameter" for setting
1.182 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.183 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.184 ///If you don't set it explicitly, it will be automatically allocated.
1.185 struct SetStandardProcessedMap :
1.186 public Bfs< Digraph, SetStandardProcessedMapTraits > {
1.187 @@ -340,9 +339,10 @@
1.188 ///Sets the map that stores the predecessor arcs.
1.189
1.190 ///Sets the map that stores the predecessor arcs.
1.191 - ///If you don't use this function before calling \ref run(),
1.192 - ///it will allocate one. The destructor deallocates this
1.193 - ///automatically allocated map, of course.
1.194 + ///If you don't use this function before calling \ref run(Node) "run()"
1.195 + ///or \ref init(), an instance will be allocated automatically.
1.196 + ///The destructor deallocates this automatically allocated map,
1.197 + ///of course.
1.198 ///\return <tt> (*this) </tt>
1.199 Bfs &predMap(PredMap &m)
1.200 {
1.201 @@ -357,9 +357,10 @@
1.202 ///Sets the map that indicates which nodes are reached.
1.203
1.204 ///Sets the map that indicates which nodes are reached.
1.205 - ///If you don't use this function before calling \ref run(),
1.206 - ///it will allocate one. The destructor deallocates this
1.207 - ///automatically allocated map, of course.
1.208 + ///If you don't use this function before calling \ref run(Node) "run()"
1.209 + ///or \ref init(), an instance will be allocated automatically.
1.210 + ///The destructor deallocates this automatically allocated map,
1.211 + ///of course.
1.212 ///\return <tt> (*this) </tt>
1.213 Bfs &reachedMap(ReachedMap &m)
1.214 {
1.215 @@ -374,9 +375,10 @@
1.216 ///Sets the map that indicates which nodes are processed.
1.217
1.218 ///Sets the map that indicates which nodes are processed.
1.219 - ///If you don't use this function before calling \ref run(),
1.220 - ///it will allocate one. The destructor deallocates this
1.221 - ///automatically allocated map, of course.
1.222 + ///If you don't use this function before calling \ref run(Node) "run()"
1.223 + ///or \ref init(), an instance will be allocated automatically.
1.224 + ///The destructor deallocates this automatically allocated map,
1.225 + ///of course.
1.226 ///\return <tt> (*this) </tt>
1.227 Bfs &processedMap(ProcessedMap &m)
1.228 {
1.229 @@ -392,9 +394,10 @@
1.230
1.231 ///Sets the map that stores the distances of the nodes calculated by
1.232 ///the algorithm.
1.233 - ///If you don't use this function before calling \ref run(),
1.234 - ///it will allocate one. The destructor deallocates this
1.235 - ///automatically allocated map, of course.
1.236 + ///If you don't use this function before calling \ref run(Node) "run()"
1.237 + ///or \ref init(), an instance will be allocated automatically.
1.238 + ///The destructor deallocates this automatically allocated map,
1.239 + ///of course.
1.240 ///\return <tt> (*this) </tt>
1.241 Bfs &distMap(DistMap &m)
1.242 {
1.243 @@ -408,22 +411,19 @@
1.244
1.245 public:
1.246
1.247 - ///\name Execution control
1.248 - ///The simplest way to execute the algorithm is to use
1.249 - ///one of the member functions called \ref lemon::Bfs::run() "run()".
1.250 - ///\n
1.251 - ///If you need more control on the execution, first you must call
1.252 - ///\ref lemon::Bfs::init() "init()", then you can add several source
1.253 - ///nodes with \ref lemon::Bfs::addSource() "addSource()".
1.254 - ///Finally \ref lemon::Bfs::start() "start()" will perform the
1.255 - ///actual path computation.
1.256 + ///\name Execution Control
1.257 + ///The simplest way to execute the BFS algorithm is to use one of the
1.258 + ///member functions called \ref run(Node) "run()".\n
1.259 + ///If you need better control on the execution, you have to call
1.260 + ///\ref init() first, then you can add several source nodes with
1.261 + ///\ref addSource(). Finally the actual path computation can be
1.262 + ///performed with one of the \ref start() functions.
1.263
1.264 ///@{
1.265
1.266 + ///\brief Initializes the internal data structures.
1.267 + ///
1.268 ///Initializes the internal data structures.
1.269 -
1.270 - ///Initializes the internal data structures.
1.271 - ///
1.272 void init()
1.273 {
1.274 create_maps();
1.275 @@ -557,16 +557,16 @@
1.276 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.277 }
1.278
1.279 - ///\brief Returns \c false if there are nodes
1.280 - ///to be processed.
1.281 - ///
1.282 - ///Returns \c false if there are nodes
1.283 - ///to be processed in the queue.
1.284 + ///Returns \c false if there are nodes to be processed.
1.285 +
1.286 + ///Returns \c false if there are nodes to be processed
1.287 + ///in the queue.
1.288 bool emptyQueue() const { return _queue_tail==_queue_head; }
1.289
1.290 ///Returns the number of the nodes to be processed.
1.291
1.292 - ///Returns the number of the nodes to be processed in the queue.
1.293 + ///Returns the number of the nodes to be processed
1.294 + ///in the queue.
1.295 int queueSize() const { return _queue_head-_queue_tail; }
1.296
1.297 ///Executes the algorithm.
1.298 @@ -731,60 +731,62 @@
1.299 ///@}
1.300
1.301 ///\name Query Functions
1.302 - ///The result of the %BFS algorithm can be obtained using these
1.303 + ///The results of the BFS algorithm can be obtained using these
1.304 ///functions.\n
1.305 - ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
1.306 - ///"start()" must be called before using them.
1.307 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.308 + ///before using them.
1.309
1.310 ///@{
1.311
1.312 - ///The shortest path to a node.
1.313 + ///The shortest path to the given node.
1.314
1.315 - ///Returns the shortest path to a node.
1.316 + ///Returns the shortest path to the given node from the root(s).
1.317 ///
1.318 - ///\warning \c t should be reachable from the root(s).
1.319 + ///\warning \c t should be reached from the root(s).
1.320 ///
1.321 - ///\pre Either \ref run() or \ref start() must be called before
1.322 - ///using this function.
1.323 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.324 + ///must be called before using this function.
1.325 Path path(Node t) const { return Path(*G, *_pred, t); }
1.326
1.327 - ///The distance of a node from the root(s).
1.328 + ///The distance of the given node from the root(s).
1.329
1.330 - ///Returns the distance of a node from the root(s).
1.331 + ///Returns the distance of the given node from the root(s).
1.332 ///
1.333 - ///\warning If node \c v is not reachable from the root(s), then
1.334 + ///\warning If node \c v is not reached from the root(s), then
1.335 ///the return value of this function is undefined.
1.336 ///
1.337 - ///\pre Either \ref run() or \ref start() must be called before
1.338 - ///using this function.
1.339 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.340 + ///must be called before using this function.
1.341 int dist(Node v) const { return (*_dist)[v]; }
1.342
1.343 - ///Returns the 'previous arc' of the shortest path tree for a node.
1.344 -
1.345 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.346 + ///the given node.
1.347 + ///
1.348 ///This function returns the 'previous arc' of the shortest path
1.349 ///tree for the node \c v, i.e. it returns the last arc of a
1.350 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.351 - ///is not reachable from the root(s) or if \c v is a root.
1.352 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.353 + ///is not reached from the root(s) or if \c v is a root.
1.354 ///
1.355 ///The shortest path tree used here is equal to the shortest path
1.356 - ///tree used in \ref predNode().
1.357 + ///tree used in \ref predNode() and \ref predMap().
1.358 ///
1.359 - ///\pre Either \ref run() or \ref start() must be called before
1.360 - ///using this function.
1.361 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.362 + ///must be called before using this function.
1.363 Arc predArc(Node v) const { return (*_pred)[v];}
1.364
1.365 - ///Returns the 'previous node' of the shortest path tree for a node.
1.366 -
1.367 + ///\brief Returns the 'previous node' of the shortest path tree for
1.368 + ///the given node.
1.369 + ///
1.370 ///This function returns the 'previous node' of the shortest path
1.371 ///tree for the node \c v, i.e. it returns the last but one node
1.372 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.373 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.374 + ///of a shortest path from a root to \c v. It is \c INVALID
1.375 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.376 ///
1.377 ///The shortest path tree used here is equal to the shortest path
1.378 - ///tree used in \ref predArc().
1.379 + ///tree used in \ref predArc() and \ref predMap().
1.380 ///
1.381 - ///\pre Either \ref run() or \ref start() must be called before
1.382 - ///using this function.
1.383 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.384 + ///must be called before using this function.
1.385 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.386 G->source((*_pred)[v]); }
1.387
1.388 @@ -794,7 +796,7 @@
1.389 ///Returns a const reference to the node map that stores the distances
1.390 ///of the nodes calculated by the algorithm.
1.391 ///
1.392 - ///\pre Either \ref run() or \ref init()
1.393 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.394 ///must be called before using this function.
1.395 const DistMap &distMap() const { return *_dist;}
1.396
1.397 @@ -802,16 +804,17 @@
1.398 ///predecessor arcs.
1.399 ///
1.400 ///Returns a const reference to the node map that stores the predecessor
1.401 - ///arcs, which form the shortest path tree.
1.402 + ///arcs, which form the shortest path tree (forest).
1.403 ///
1.404 - ///\pre Either \ref run() or \ref init()
1.405 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.406 ///must be called before using this function.
1.407 const PredMap &predMap() const { return *_pred;}
1.408
1.409 - ///Checks if a node is reachable from the root(s).
1.410 + ///Checks if the given node is reached from the root(s).
1.411
1.412 - ///Returns \c true if \c v is reachable from the root(s).
1.413 - ///\pre Either \ref run() or \ref start()
1.414 + ///Returns \c true if \c v is reached from the root(s).
1.415 + ///
1.416 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.417 ///must be called before using this function.
1.418 bool reached(Node v) const { return (*_reached)[v]; }
1.419
1.420 @@ -833,7 +836,7 @@
1.421 ///
1.422 ///The type of the map that stores the predecessor
1.423 ///arcs of the shortest paths.
1.424 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.425 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.426 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.427 ///Instantiates a PredMap.
1.428
1.429 @@ -848,7 +851,7 @@
1.430 ///The type of the map that indicates which nodes are processed.
1.431
1.432 ///The type of the map that indicates which nodes are processed.
1.433 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.434 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.435 ///By default it is a NullMap.
1.436 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.437 ///Instantiates a ProcessedMap.
1.438 @@ -868,7 +871,7 @@
1.439 ///The type of the map that indicates which nodes are reached.
1.440
1.441 ///The type of the map that indicates which nodes are reached.
1.442 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.443 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.444 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.445 ///Instantiates a ReachedMap.
1.446
1.447 @@ -883,7 +886,7 @@
1.448 ///The type of the map that stores the distances of the nodes.
1.449
1.450 ///The type of the map that stores the distances of the nodes.
1.451 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.452 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.453 typedef typename Digraph::template NodeMap<int> DistMap;
1.454 ///Instantiates a DistMap.
1.455
1.456 @@ -898,18 +901,14 @@
1.457 ///The type of the shortest paths.
1.458
1.459 ///The type of the shortest paths.
1.460 - ///It must meet the \ref concepts::Path "Path" concept.
1.461 + ///It must conform to the \ref concepts::Path "Path" concept.
1.462 typedef lemon::Path<Digraph> Path;
1.463 };
1.464
1.465 /// Default traits class used by BfsWizard
1.466
1.467 - /// To make it easier to use Bfs algorithm
1.468 - /// we have created a wizard class.
1.469 - /// This \ref BfsWizard class needs default traits,
1.470 - /// as well as the \ref Bfs class.
1.471 - /// The \ref BfsWizardBase is a class to be the default traits of the
1.472 - /// \ref BfsWizard class.
1.473 + /// Default traits class used by BfsWizard.
1.474 + /// \tparam GR The type of the digraph.
1.475 template<class GR>
1.476 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
1.477 {
1.478 @@ -937,7 +936,7 @@
1.479 public:
1.480 /// Constructor.
1.481
1.482 - /// This constructor does not require parameters, therefore it initiates
1.483 + /// This constructor does not require parameters, it initiates
1.484 /// all of the attributes to \c 0.
1.485 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.486 _dist(0), _path(0), _di(0) {}
1.487 @@ -957,8 +956,8 @@
1.488
1.489 /// This auxiliary class is created to implement the
1.490 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
1.491 - /// It does not have own \ref run() method, it uses the functions
1.492 - /// and features of the plain \ref Bfs.
1.493 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.494 + /// functions and features of the plain \ref Bfs.
1.495 ///
1.496 /// This class should only be used through the \ref bfs() function,
1.497 /// which makes it easier to use the algorithm.
1.498 @@ -967,7 +966,6 @@
1.499 {
1.500 typedef TR Base;
1.501
1.502 - ///The type of the digraph the algorithm runs on.
1.503 typedef typename TR::Digraph Digraph;
1.504
1.505 typedef typename Digraph::Node Node;
1.506 @@ -975,16 +973,10 @@
1.507 typedef typename Digraph::Arc Arc;
1.508 typedef typename Digraph::OutArcIt OutArcIt;
1.509
1.510 - ///\brief The type of the map that stores the predecessor
1.511 - ///arcs of the shortest paths.
1.512 typedef typename TR::PredMap PredMap;
1.513 - ///\brief The type of the map that stores the distances of the nodes.
1.514 typedef typename TR::DistMap DistMap;
1.515 - ///\brief The type of the map that indicates which nodes are reached.
1.516 typedef typename TR::ReachedMap ReachedMap;
1.517 - ///\brief The type of the map that indicates which nodes are processed.
1.518 typedef typename TR::ProcessedMap ProcessedMap;
1.519 - ///The type of the shortest paths
1.520 typedef typename TR::Path Path;
1.521
1.522 public:
1.523 @@ -1067,11 +1059,12 @@
1.524 static PredMap *createPredMap(const Digraph &) { return 0; };
1.525 SetPredMapBase(const TR &b) : TR(b) {}
1.526 };
1.527 - ///\brief \ref named-func-param "Named parameter"
1.528 - ///for setting PredMap object.
1.529 +
1.530 + ///\brief \ref named-templ-param "Named parameter" for setting
1.531 + ///the predecessor map.
1.532 ///
1.533 - ///\ref named-func-param "Named parameter"
1.534 - ///for setting PredMap object.
1.535 + ///\ref named-templ-param "Named parameter" function for setting
1.536 + ///the map that stores the predecessor arcs of the nodes.
1.537 template<class T>
1.538 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.539 {
1.540 @@ -1085,11 +1078,12 @@
1.541 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.542 SetReachedMapBase(const TR &b) : TR(b) {}
1.543 };
1.544 - ///\brief \ref named-func-param "Named parameter"
1.545 - ///for setting ReachedMap object.
1.546 +
1.547 + ///\brief \ref named-templ-param "Named parameter" for setting
1.548 + ///the reached map.
1.549 ///
1.550 - /// \ref named-func-param "Named parameter"
1.551 - ///for setting ReachedMap object.
1.552 + ///\ref named-templ-param "Named parameter" function for setting
1.553 + ///the map that indicates which nodes are reached.
1.554 template<class T>
1.555 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.556 {
1.557 @@ -1103,11 +1097,13 @@
1.558 static DistMap *createDistMap(const Digraph &) { return 0; };
1.559 SetDistMapBase(const TR &b) : TR(b) {}
1.560 };
1.561 - ///\brief \ref named-func-param "Named parameter"
1.562 - ///for setting DistMap object.
1.563 +
1.564 + ///\brief \ref named-templ-param "Named parameter" for setting
1.565 + ///the distance map.
1.566 ///
1.567 - /// \ref named-func-param "Named parameter"
1.568 - ///for setting DistMap object.
1.569 + ///\ref named-templ-param "Named parameter" function for setting
1.570 + ///the map that stores the distances of the nodes calculated
1.571 + ///by the algorithm.
1.572 template<class T>
1.573 BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.574 {
1.575 @@ -1121,11 +1117,12 @@
1.576 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.577 SetProcessedMapBase(const TR &b) : TR(b) {}
1.578 };
1.579 - ///\brief \ref named-func-param "Named parameter"
1.580 - ///for setting ProcessedMap object.
1.581 +
1.582 + ///\brief \ref named-func-param "Named parameter" for setting
1.583 + ///the processed map.
1.584 ///
1.585 - /// \ref named-func-param "Named parameter"
1.586 - ///for setting ProcessedMap object.
1.587 + ///\ref named-templ-param "Named parameter" function for setting
1.588 + ///the map that indicates which nodes are processed.
1.589 template<class T>
1.590 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.591 {
1.592 @@ -1178,7 +1175,7 @@
1.593 /// // Compute shortest path from s to t
1.594 /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1.595 ///\endcode
1.596 - ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.597 + ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1.598 ///to the end of the parameter list.
1.599 ///\sa BfsWizard
1.600 ///\sa Bfs
1.601 @@ -1194,9 +1191,9 @@
1.602 ///
1.603 /// This class defines the interface of the BfsVisit events, and
1.604 /// it could be the base of a real visitor class.
1.605 - template <typename _Digraph>
1.606 + template <typename GR>
1.607 struct BfsVisitor {
1.608 - typedef _Digraph Digraph;
1.609 + typedef GR Digraph;
1.610 typedef typename Digraph::Arc Arc;
1.611 typedef typename Digraph::Node Node;
1.612 /// \brief Called for the source node(s) of the BFS.
1.613 @@ -1224,9 +1221,9 @@
1.614 void examine(const Arc& arc) {}
1.615 };
1.616 #else
1.617 - template <typename _Digraph>
1.618 + template <typename GR>
1.619 struct BfsVisitor {
1.620 - typedef _Digraph Digraph;
1.621 + typedef GR Digraph;
1.622 typedef typename Digraph::Arc Arc;
1.623 typedef typename Digraph::Node Node;
1.624 void start(const Node&) {}
1.625 @@ -1254,17 +1251,17 @@
1.626 /// \brief Default traits class of BfsVisit class.
1.627 ///
1.628 /// Default traits class of BfsVisit class.
1.629 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.630 - template<class _Digraph>
1.631 + /// \tparam GR The type of the digraph the algorithm runs on.
1.632 + template<class GR>
1.633 struct BfsVisitDefaultTraits {
1.634
1.635 /// \brief The type of the digraph the algorithm runs on.
1.636 - typedef _Digraph Digraph;
1.637 + typedef GR Digraph;
1.638
1.639 /// \brief The type of the map that indicates which nodes are reached.
1.640 ///
1.641 /// The type of the map that indicates which nodes are reached.
1.642 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.643 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.644 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.645
1.646 /// \brief Instantiates a ReachedMap.
1.647 @@ -1280,12 +1277,12 @@
1.648
1.649 /// \ingroup search
1.650 ///
1.651 - /// \brief %BFS algorithm class with visitor interface.
1.652 + /// \brief BFS algorithm class with visitor interface.
1.653 ///
1.654 - /// This class provides an efficient implementation of the %BFS algorithm
1.655 + /// This class provides an efficient implementation of the BFS algorithm
1.656 /// with visitor interface.
1.657 ///
1.658 - /// The %BfsVisit class provides an alternative interface to the Bfs
1.659 + /// The BfsVisit class provides an alternative interface to the Bfs
1.660 /// class. It works with callback mechanism, the BfsVisit object calls
1.661 /// the member functions of the \c Visitor class on every BFS event.
1.662 ///
1.663 @@ -1294,37 +1291,37 @@
1.664 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1.665 /// instead.
1.666 ///
1.667 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.668 - /// The default value is
1.669 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.670 - /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1.671 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.672 - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1.673 + /// \tparam GR The type of the digraph the algorithm runs on.
1.674 + /// The default type is \ref ListDigraph.
1.675 + /// The value of GR is not used directly by \ref BfsVisit,
1.676 + /// it is only passed to \ref BfsVisitDefaultTraits.
1.677 + /// \tparam VS The Visitor type that is used by the algorithm.
1.678 + /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1.679 /// does not observe the BFS events. If you want to observe the BFS
1.680 /// events, you should implement your own visitor class.
1.681 - /// \tparam _Traits Traits class to set various data types used by the
1.682 + /// \tparam TR Traits class to set various data types used by the
1.683 /// algorithm. The default traits class is
1.684 - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.685 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
1.686 /// See \ref BfsVisitDefaultTraits for the documentation of
1.687 /// a BFS visit traits class.
1.688 #ifdef DOXYGEN
1.689 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.690 + template <typename GR, typename VS, typename TR>
1.691 #else
1.692 - template <typename _Digraph = ListDigraph,
1.693 - typename _Visitor = BfsVisitor<_Digraph>,
1.694 - typename _Traits = BfsVisitDefaultTraits<_Digraph> >
1.695 + template <typename GR = ListDigraph,
1.696 + typename VS = BfsVisitor<GR>,
1.697 + typename TR = BfsVisitDefaultTraits<GR> >
1.698 #endif
1.699 class BfsVisit {
1.700 public:
1.701
1.702 ///The traits class.
1.703 - typedef _Traits Traits;
1.704 + typedef TR Traits;
1.705
1.706 ///The type of the digraph the algorithm runs on.
1.707 typedef typename Traits::Digraph Digraph;
1.708
1.709 ///The visitor type used by the algorithm.
1.710 - typedef _Visitor Visitor;
1.711 + typedef VS Visitor;
1.712
1.713 ///The type of the map that indicates which nodes are reached.
1.714 typedef typename Traits::ReachedMap ReachedMap;
1.715 @@ -1364,7 +1361,7 @@
1.716
1.717 typedef BfsVisit Create;
1.718
1.719 - /// \name Named template parameters
1.720 + /// \name Named Template Parameters
1.721
1.722 ///@{
1.723 template <class T>
1.724 @@ -1406,9 +1403,10 @@
1.725 /// \brief Sets the map that indicates which nodes are reached.
1.726 ///
1.727 /// Sets the map that indicates which nodes are reached.
1.728 - /// If you don't use this function before calling \ref run(),
1.729 - /// it will allocate one. The destructor deallocates this
1.730 - /// automatically allocated map, of course.
1.731 + /// If you don't use this function before calling \ref run(Node) "run()"
1.732 + /// or \ref init(), an instance will be allocated automatically.
1.733 + /// The destructor deallocates this automatically allocated map,
1.734 + /// of course.
1.735 /// \return <tt> (*this) </tt>
1.736 BfsVisit &reachedMap(ReachedMap &m) {
1.737 if(local_reached) {
1.738 @@ -1421,16 +1419,13 @@
1.739
1.740 public:
1.741
1.742 - /// \name Execution control
1.743 - /// The simplest way to execute the algorithm is to use
1.744 - /// one of the member functions called \ref lemon::BfsVisit::run()
1.745 - /// "run()".
1.746 - /// \n
1.747 - /// If you need more control on the execution, first you must call
1.748 - /// \ref lemon::BfsVisit::init() "init()", then you can add several
1.749 - /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1.750 - /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1.751 - /// actual path computation.
1.752 + /// \name Execution Control
1.753 + /// The simplest way to execute the BFS algorithm is to use one of the
1.754 + /// member functions called \ref run(Node) "run()".\n
1.755 + /// If you need better control on the execution, you have to call
1.756 + /// \ref init() first, then you can add several source nodes with
1.757 + /// \ref addSource(). Finally the actual path computation can be
1.758 + /// performed with one of the \ref start() functions.
1.759
1.760 /// @{
1.761
1.762 @@ -1730,19 +1725,20 @@
1.763 ///@}
1.764
1.765 /// \name Query Functions
1.766 - /// The result of the %BFS algorithm can be obtained using these
1.767 + /// The results of the BFS algorithm can be obtained using these
1.768 /// functions.\n
1.769 - /// Either \ref lemon::BfsVisit::run() "run()" or
1.770 - /// \ref lemon::BfsVisit::start() "start()" must be called before
1.771 - /// using them.
1.772 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.773 + /// before using them.
1.774 +
1.775 ///@{
1.776
1.777 - /// \brief Checks if a node is reachable from the root(s).
1.778 + /// \brief Checks if the given node is reached from the root(s).
1.779 ///
1.780 - /// Returns \c true if \c v is reachable from the root(s).
1.781 - /// \pre Either \ref run() or \ref start()
1.782 + /// Returns \c true if \c v is reached from the root(s).
1.783 + ///
1.784 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.785 /// must be called before using this function.
1.786 - bool reached(Node v) { return (*_reached)[v]; }
1.787 + bool reached(Node v) const { return (*_reached)[v]; }
1.788
1.789 ///@}
1.790