lemon-main: comparison lemon/bfs.h

equal deleted inserted replaced

-:c88fa5670f29
+:cba8485be580
 ///arcs of the shortest paths.
 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 ///Instantiates a PredMap.
 ///This function instantiates a PredMap.
 ///\param g is the digraph, to which we would like to define the
 ///PredMap.
 static PredMap *createPredMap(const Digraph &g)
 {
 return new PredMap(g);
 return new ProcessedMap();
 }
 ///The type of the map that indicates which nodes are reached.
-///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+///The type of the map that indicates which nodes are reached.
+///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 typedef typename Digraph::template NodeMap<bool> ReachedMap;
 ///Instantiates a ReachedMap.
 ///This function instantiates a ReachedMap.
 ///\param g is the digraph, to which
 ///There is also a \ref bfs() "function-type interface" for the BFS
 ///algorithm, which is convenient in the simplier cases and it can be
 ///used easier.
 ///
 ///\tparam GR The type of the digraph the algorithm runs on.
-///The default value is \ref ListDigraph. The value of GR is not used
+///The default type is \ref ListDigraph.
-///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
-///\tparam TR Traits class to set various data types used by the algorithm.
-///The default traits class is
-///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
-///See \ref BfsDefaultTraits for the documentation of
-///a Bfs traits class.
 #ifdef DOXYGEN
 template <typename GR,
 typename TR>
 #else
 template <typename GR=ListDigraph,
 ///The type of the map that indicates which nodes are processed.
 typedef typename TR::ProcessedMap ProcessedMap;
 ///The type of the paths.
 typedef PredMapPath<Digraph, PredMap> Path;
-///The traits class.
+///The \ref BfsDefaultTraits "traits class" of the algorithm.
 typedef TR Traits;
 private:
 typedef typename Digraph::Node Node;
 public:
 typedef Bfs Create;
-///\name Named template parameters
+///\name Named Template Parameters
 ///@{
 template <class T>
 struct SetPredMapTraits : public Traits {
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///PredMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///PredMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///DistMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///DistMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ReachedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///ReachedMap type.
+///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 template <class T>
 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ProcessedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///ProcessedMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 };
 }
 ///Sets the map that stores the predecessor arcs.
 ///Sets the map that stores the predecessor arcs.
-///If you don't use this function before calling \ref run(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Bfs &predMap(PredMap &m)
 {
 if(local_pred) {
 delete _pred;
 }
 ///Sets the map that indicates which nodes are reached.
 ///Sets the map that indicates which nodes are reached.
-///If you don't use this function before calling \ref run(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Bfs &reachedMap(ReachedMap &m)
 {
 if(local_reached) {
 delete _reached;
 }
 ///Sets the map that indicates which nodes are processed.
 ///Sets the map that indicates which nodes are processed.
-///If you don't use this function before calling \ref run(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Bfs &processedMap(ProcessedMap &m)
 {
 if(local_processed) {
 delete _processed;
 ///Sets the map that stores the distances of the nodes.
 ///Sets the map that stores the distances of the nodes calculated by
 ///the algorithm.
-///If you don't use this function before calling \ref run(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Bfs &distMap(DistMap &m)
 {
 if(local_dist) {
 delete _dist;
 return *this;
 }
 public:
-///\name Execution control
+///\name Execution Control
-///The simplest way to execute the algorithm is to use
+///The simplest way to execute the BFS algorithm is to use one of the
-///one of the member functions called \ref lemon::Bfs::run() "run()".
+///member functions called \ref run(Node) "run()".\n
-///\n
+///If you need more control on the execution, first you have to call
-///If you need more control on the execution, first you must call
+///\ref init(), then you can add several source nodes with
-///\ref lemon::Bfs::init() "init()", then you can add several source
+///\ref addSource(). Finally the actual path computation can be
-///nodes with \ref lemon::Bfs::addSource() "addSource()".
+///performed with one of the \ref start() functions.
-///Finally \ref lemon::Bfs::start() "start()" will perform the
-///actual path computation.
 ///@{
+///\brief Initializes the internal data structures.
+///
 ///Initializes the internal data structures.
-///Initializes the internal data structures.
-///
 void init()
 {
 create_maps();
 _queue.resize(countNodes(*G));
 _queue_head=_queue_tail=0;
 Node nextNode() const
 {
 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
 }
-///\brief Returns \c false if there are nodes
+///Returns \c false if there are nodes to be processed.
-///to be processed.
-///
+///Returns \c false if there are nodes to be processed
-///Returns \c false if there are nodes
+///in the queue.
-///to be processed in the queue.
 bool emptyQueue() const { return _queue_tail==_queue_head; }
 ///Returns the number of the nodes to be processed.
-///Returns the number of the nodes to be processed in the queue.
+///Returns the number of the nodes to be processed
+///in the queue.
 int queueSize() const { return _queue_head-_queue_tail; }
 ///Executes the algorithm.
 ///Executes the algorithm.
 }
 ///@}
 ///\name Query Functions
-///The result of the %BFS algorithm can be obtained using these
+///The results of the BFS algorithm can be obtained using these
 ///functions.\n
-///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
+///Either \ref run(Node) "run()" or \ref start() should be called
-///"start()" must be called before using them.
+///before using them.
 ///@{
 ///The shortest path to a node.
 ///Returns the shortest path to a node.
 ///
-///\warning \c t should be reachable from the root(s).
+///\warning \c t should be reached from the root(s).
 ///
-///\pre Either \ref run() or \ref start() must be called before
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///must be called before using this function.
 Path path(Node t) const { return Path(*G, *_pred, t); }
 ///The distance of a node from the root(s).
 ///Returns the distance of a node from the root(s).
 ///
-///\warning If node \c v is not reachable from the root(s), then
+///\warning If node \c v is not reached from the root(s), then
 ///the return value of this function is undefined.
 ///
-///\pre Either \ref run() or \ref start() must be called before
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///must be called before using this function.
 int dist(Node v) const { return (*_dist)[v]; }
 ///Returns the 'previous arc' of the shortest path tree for a node.
 ///This function returns the 'previous arc' of the shortest path
 ///tree for the node \c v, i.e. it returns the last arc of a
-///shortest path from the root(s) to \c v. It is \c INVALID if \c v
+///shortest path from a root to \c v. It is \c INVALID if \c v
-///is not reachable from the root(s) or if \c v is a root.
+///is not reached from the root(s) or if \c v is a root.
 ///
 ///The shortest path tree used here is equal to the shortest path
 ///tree used in \ref predNode().
 ///
-///\pre Either \ref run() or \ref start() must be called before
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///must be called before using this function.
 Arc predArc(Node v) const { return (*_pred)[v];}
 ///Returns the 'previous node' of the shortest path tree for a node.
 ///This function returns the 'previous node' of the shortest path
 ///tree for the node \c v, i.e. it returns the last but one node
-///from a shortest path from the root(s) to \c v. It is \c INVALID
+///from a shortest path from a root to \c v. It is \c INVALID
-///if \c v is not reachable from the root(s) or if \c v is a root.
+///if \c v is not reached from the root(s) or if \c v is a root.
 ///
 ///The shortest path tree used here is equal to the shortest path
 ///tree used in \ref predArc().
 ///
-///\pre Either \ref run() or \ref start() must be called before
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///must be called before using this function.
 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 G->source((*_pred)[v]); }
 ///\brief Returns a const reference to the node map that stores the
 /// distances of the nodes.
 ///
 ///Returns a const reference to the node map that stores the distances
 ///of the nodes calculated by the algorithm.
 ///
-///\pre Either \ref run() or \ref init()
+///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
 const DistMap &distMap() const { return *_dist;}
 ///\brief Returns a const reference to the node map that stores the
 ///predecessor arcs.
 ///
 ///Returns a const reference to the node map that stores the predecessor
 ///arcs, which form the shortest path tree.
 ///
-///\pre Either \ref run() or \ref init()
+///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
 const PredMap &predMap() const { return *_pred;}
-///Checks if a node is reachable from the root(s).
+///Checks if a node is reached from the root(s).
-///Returns \c true if \c v is reachable from the root(s).
+///Returns \c true if \c v is reached from the root(s).
-///\pre Either \ref run() or \ref start()
+///
+///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
 bool reached(Node v) const { return (*_reached)[v]; }
 ///@}
 };
 /// Auxiliary class for the function-type interface of BFS algorithm.
 /// This auxiliary class is created to implement the
 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
-/// It does not have own \ref run() method, it uses the functions
+/// It does not have own \ref run(Node) "run()" method, it uses the
-/// and features of the plain \ref Bfs.
+/// functions and features of the plain \ref Bfs.
 ///
 /// This class should only be used through the \ref bfs() function,
 /// which makes it easier to use the algorithm.
 template<class TR>
 class BfsWizard : public TR
 ///  bfs(g).predMap(preds).distMap(dists).run(s);
 ///
 ///  // Compute shortest path from s to t
 ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
 ///\endcode
-///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
 ///to the end of the parameter list.
 ///\sa BfsWizard
 ///\sa Bfs
 template<class GR>
 BfsWizard<BfsWizardBase<GR> >
 public:
 typedef BfsVisit Create;
-/// \name Named template parameters
+/// \name Named Template Parameters
 ///@{
 template <class T>
 struct SetReachedMapTraits : public Traits {
 typedef T ReachedMap;
 }
 /// \brief Sets the map that indicates which nodes are reached.
 ///
 /// Sets the map that indicates which nodes are reached.
-/// If you don't use this function before calling \ref run(),
+/// If you don't use this function before calling \ref run(Node) "run()"
-/// it will allocate one. The destructor deallocates this
+/// or \ref init(), an instance will be allocated automatically.
-/// automatically allocated map, of course.
+/// The destructor deallocates this automatically allocated map,
+/// of course.
 /// \return <tt> (*this) </tt>
 BfsVisit &reachedMap(ReachedMap &m) {
 if(local_reached) {
 delete _reached;
 local_reached = false;
 return *this;
 }
 public:
-/// \name Execution control
+/// \name Execution Control
-/// The simplest way to execute the algorithm is to use
+/// The simplest way to execute the BFS algorithm is to use one of the
-/// one of the member functions called \ref lemon::BfsVisit::run()
+/// member functions called \ref run(Node) "run()".\n
-/// "run()".
+/// If you need more control on the execution, first you have to call
-/// \n
+/// \ref init(), then you can add several source nodes with
-/// If you need more control on the execution, first you must call
+/// \ref addSource(). Finally the actual path computation can be
-/// \ref lemon::BfsVisit::init() "init()", then you can add several
+/// performed with one of the \ref start() functions.
-/// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
-/// Finally \ref lemon::BfsVisit::start() "start()" will perform the
-/// actual path computation.
 /// @{
 /// \brief Initializes the internal data structures.
 ///
 }
 ///@}
 /// \name Query Functions
-/// The result of the %BFS algorithm can be obtained using these
+/// The results of the BFS algorithm can be obtained using these
 /// functions.\n
-/// Either \ref lemon::BfsVisit::run() "run()" or
+/// Either \ref run(Node) "run()" or \ref start() should be called
-/// \ref lemon::BfsVisit::start() "start()" must be called before
+/// before using them.
-/// using them.
 ///@{
-/// \brief Checks if a node is reachable from the root(s).
+/// \brief Checks if a node is reached from the root(s).
 ///
-/// Returns \c true if \c v is reachable from the root(s).
+/// Returns \c true if \c v is reached from the root(s).
-/// \pre Either \ref run() or \ref start()
+///
+/// \pre Either \ref run(Node) "run()" or \ref init()
 /// must be called before using this function.
 bool reached(Node v) { return (*_reached)[v]; }
 ///@}

changeset 418	ad483acf1654
parent 329	d900fd1e760f
child 420	6a2a33ad261b