diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -51,7 +51,7 @@ typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. - ///This function 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) @@ -80,7 +80,8 @@ ///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 ReachedMap; ///Instantiates a ReachedMap. @@ -118,13 +119,7 @@ ///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 - ///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". - ///See \ref BfsDefaultTraits for the documentation of - ///a Bfs traits class. + ///The default type is \ref ListDigraph. #ifdef DOXYGEN template @@ -150,7 +145,7 @@ ///The type of the paths. typedef PredMapPath Path; - ///The traits class. + ///The \ref BfsDefaultTraits "traits class" of the algorithm. typedef TR Traits; private: @@ -212,7 +207,7 @@ typedef Bfs Create; - ///\name Named template parameters + ///\name Named Template Parameters ///@{ @@ -230,6 +225,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///PredMap type. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { typedef Bfs< Digraph, SetPredMapTraits > Create; @@ -249,6 +245,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///DistMap type. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { typedef Bfs< Digraph, SetDistMapTraits > Create; @@ -268,6 +265,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///ReachedMap type. + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { typedef Bfs< Digraph, SetReachedMapTraits > Create; @@ -287,6 +285,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///ProcessedMap type. + ///It must meet the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { typedef Bfs< Digraph, SetProcessedMapTraits > Create; @@ -339,9 +338,10 @@ ///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(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Bfs &predMap(PredMap &m) { @@ -356,9 +356,10 @@ ///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(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Bfs &reachedMap(ReachedMap &m) { @@ -373,9 +374,10 @@ ///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(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Bfs &processedMap(ProcessedMap &m) { @@ -391,9 +393,10 @@ ///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(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Bfs &distMap(DistMap &m) { @@ -407,22 +410,19 @@ public: - ///\name Execution control - ///The simplest way to execute the algorithm is to use - ///one of the member functions called \ref lemon::Bfs::run() "run()". - ///\n - ///If you need more control on the execution, first you must call - ///\ref lemon::Bfs::init() "init()", then you can add several source - ///nodes with \ref lemon::Bfs::addSource() "addSource()". - ///Finally \ref lemon::Bfs::start() "start()" will perform the - ///actual path computation. + ///\name Execution Control + ///The simplest way to execute the BFS algorithm is to use one of the + ///member functions called \ref run(Node) "run()".\n + ///If you need more control on the execution, first you have to call + ///\ref init(), then you can add several source nodes with + ///\ref addSource(). Finally the actual path computation can be + ///performed with one of the \ref start() functions. ///@{ + ///\brief Initializes the internal data structures. + /// ///Initializes the internal data structures. - - ///Initializes the internal data structures. - /// void init() { create_maps(); @@ -556,16 +556,16 @@ return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; } - ///\brief Returns \c false if there are nodes - ///to be processed. - /// - ///Returns \c false if there are nodes - ///to be processed in the queue. + ///Returns \c false if there are nodes to be processed. + + ///Returns \c false if there are nodes 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. @@ -730,10 +730,10 @@ ///@} ///\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() - ///"start()" must be called before using them. + ///Either \ref run(Node) "run()" or \ref start() should be called + ///before using them. ///@{ @@ -741,49 +741,49 @@ ///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 - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///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 - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///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 - ///is not reachable from the root(s) or if \c v is a root. + ///shortest path from a root to \c v. It is \c INVALID 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 predNode(). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///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 - ///if \c v is not reachable from the root(s) or if \c v is a root. + ///from a shortest path from a root to \c v. It is \c INVALID + ///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 - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } @@ -793,7 +793,7 @@ ///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;} @@ -803,14 +803,15 @@ ///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). - ///\pre Either \ref run() or \ref start() + ///Returns \c true if \c v is reached from the root(s). + /// + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. bool reached(Node v) const { return (*_reached)[v]; } @@ -956,8 +957,8 @@ /// 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 - /// and features of the plain \ref Bfs. + /// It does not have own \ref run(Node) "run()" method, it uses the + /// 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. @@ -1177,7 +1178,7 @@ /// // 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 @@ -1363,7 +1364,7 @@ typedef BfsVisit Create; - /// \name Named template parameters + /// \name Named Template Parameters ///@{ template @@ -1405,9 +1406,10 @@ /// \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(), - /// it will allocate one. The destructor deallocates this - /// automatically allocated map, of course. + /// If you don't use this function before calling \ref run(Node) "run()" + /// or \ref init(), an instance will be allocated automatically. + /// The destructor deallocates this automatically allocated map, + /// of course. /// \return (*this) BfsVisit &reachedMap(ReachedMap &m) { if(local_reached) { @@ -1420,16 +1422,13 @@ public: - /// \name Execution control - /// The simplest way to execute the algorithm is to use - /// one of the member functions called \ref lemon::BfsVisit::run() - /// "run()". - /// \n - /// If you need more control on the execution, first you must call - /// \ref lemon::BfsVisit::init() "init()", then you can add several - /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()". - /// Finally \ref lemon::BfsVisit::start() "start()" will perform the - /// actual path computation. + /// \name Execution Control + /// The simplest way to execute the BFS algorithm is to use one of the + /// member functions called \ref run(Node) "run()".\n + /// If you need more control on the execution, first you have to call + /// \ref init(), then you can add several source nodes with + /// \ref addSource(). Finally the actual path computation can be + /// performed with one of the \ref start() functions. /// @{ @@ -1729,17 +1728,18 @@ ///@} /// \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 - /// \ref lemon::BfsVisit::start() "start()" must be called before - /// using them. + /// Either \ref run(Node) "run()" or \ref start() should be called + /// before 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). - /// \pre Either \ref run() or \ref start() + /// Returns \c true if \c v is reached from the root(s). + /// + /// \pre Either \ref run(Node) "run()" or \ref init() /// must be called before using this function. bool reached(Node v) { return (*_reached)[v]; }