# HG changeset patch
# User Alpar Juttner <alpar@cs.elte.hu>
# Date 1228213880 0
# Node ID 69f33ef03334de29efc0c02e0716d1071a7f49ea
# Parent e22fc10ab6f129b49787b5854160761656e4b617# Parent 6b9057cdcd8b4407f8f78c8753ceebb829cfbf40
Merge
diff -r e22fc10ab6f1 -r 69f33ef03334 lemon/bfs.h
--- a/lemon/bfs.h Tue Dec 02 10:30:52 2008 +0000
+++ b/lemon/bfs.h Tue Dec 02 10:31:20 2008 +0000
@@ -51,7 +51,7 @@
typedef typename Digraph::template NodeMap<typename Digraph::Arc> 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<bool> 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<GR>".
- ///See \ref BfsDefaultTraits for the documentation of
- ///a Bfs traits class.
+ ///The default type is \ref ListDigraph.
#ifdef DOXYGEN
template <typename GR,
typename TR>
@@ -150,7 +145,7 @@
///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:
@@ -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 <class T>
struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
typedef Bfs< Digraph, SetPredMapTraits<T> > 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 <class T>
struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
typedef Bfs< Digraph, SetDistMapTraits<T> > 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 <class T>
struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
typedef Bfs< Digraph, SetReachedMapTraits<T> > 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 <class T>
struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
typedef Bfs< Digraph, SetProcessedMapTraits<T> > 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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <tt> (*this) </tt>
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 <class T>
@@ -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 <tt> (*this) </tt>
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]; }
diff -r e22fc10ab6f1 -r 69f33ef03334 lemon/dfs.h
--- a/lemon/dfs.h Tue Dec 02 10:30:52 2008 +0000
+++ b/lemon/dfs.h Tue Dec 02 10:31:20 2008 +0000
@@ -119,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 Dfs, it is only passed to \ref DfsDefaultTraits.
- ///\tparam TR Traits class to set various data types used by the algorithm.
- ///The default traits class is
- ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
- ///See \ref DfsDefaultTraits for the documentation of
- ///a Dfs traits class.
+ ///The default type is \ref ListDigraph.
#ifdef DOXYGEN
template <typename GR,
typename TR>
@@ -151,7 +145,7 @@
///The type of the paths.
typedef PredMapPath<Digraph, PredMap> Path;
- ///The traits class.
+ ///The \ref DfsDefaultTraits "traits class" of the algorithm.
typedef TR Traits;
private:
@@ -230,6 +224,7 @@
///
///\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 Dfs<Digraph, SetPredMapTraits<T> > {
typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
@@ -249,6 +244,7 @@
///
///\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 Dfs< Digraph, SetDistMapTraits<T> > {
typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
@@ -268,6 +264,7 @@
///
///\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 Dfs< Digraph, SetReachedMapTraits<T> > {
typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
@@ -287,6 +284,7 @@
///
///\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 Dfs< Digraph, SetProcessedMapTraits<T> > {
typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
@@ -338,9 +336,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 <tt> (*this) </tt>
Dfs &predMap(PredMap &m)
{
@@ -355,9 +354,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 <tt> (*this) </tt>
Dfs &reachedMap(ReachedMap &m)
{
@@ -372,9 +372,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 <tt> (*this) </tt>
Dfs &processedMap(ProcessedMap &m)
{
@@ -390,9 +391,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 <tt> (*this) </tt>
Dfs &distMap(DistMap &m)
{
@@ -406,22 +408,20 @@
public:
- ///\name Execution control
- ///The simplest way to execute the algorithm is to use
- ///one of the member functions called \ref lemon::Dfs::run() "run()".
- ///\n
- ///If you need more control on the execution, first you must call
- ///\ref lemon::Dfs::init() "init()", then you can add a source node
- ///with \ref lemon::Dfs::addSource() "addSource()".
- ///Finally \ref lemon::Dfs::start() "start()" will perform the
- ///actual path computation.
+ ///\name Execution Control
+ ///The simplest way to execute the DFS 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 a source node with \ref addSource()
+ ///and perform the actual computation with \ref start().
+ ///This procedure can be repeated if there are nodes that have not
+ ///been reached.
///@{
+ ///\brief Initializes the internal data structures.
+ ///
///Initializes the internal data structures.
-
- ///Initializes the internal data structures.
- ///
void init()
{
create_maps();
@@ -438,11 +438,10 @@
///Adds a new source node to the set of nodes to be processed.
///
- ///\pre The stack must be empty. (Otherwise the algorithm gives
- ///false results.)
- ///
- ///\warning Distances will be wrong (or at least strange) in case of
- ///multiple sources.
+ ///\pre The stack must be empty. Otherwise the algorithm gives
+ ///wrong results. (One of the outgoing arcs of all the source nodes
+ ///except for the last one will not be visited and distances will
+ ///also be wrong.)
void addSource(Node s)
{
LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
@@ -506,16 +505,16 @@
return _stack_head>=0?_stack[_stack_head]: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 (stack).
+ ///Returns \c false if there are nodes to be processed.
+
+ ///Returns \c false if there are nodes to be processed
+ ///in the queue (stack).
bool emptyQueue() const { return _stack_head<0; }
///Returns the number of the nodes to be processed.
- ///Returns the number of the nodes to be processed in the queue (stack).
+ ///Returns the number of the nodes to be processed
+ ///in the queue (stack).
int queueSize() const { return _stack_head+1; }
///Executes the algorithm.
@@ -637,8 +636,8 @@
///%DFS path to each node.
///
///The algorithm computes
- ///- the %DFS tree,
- ///- the distance of each node from the root in the %DFS tree.
+ ///- the %DFS tree (forest),
+ ///- the distance of each node from the root(s) in the %DFS tree.
///
///\note <tt>d.run()</tt> is just a shortcut of the following code.
///\code
@@ -663,10 +662,10 @@
///@}
///\name Query Functions
- ///The result of the %DFS algorithm can be obtained using these
+ ///The results of the DFS algorithm can be obtained using these
///functions.\n
- ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
- ///"start()" must be called before using them.
+ ///Either \ref run(Node) "run()" or \ref start() should be called
+ ///before using them.
///@{
@@ -674,49 +673,49 @@
///Returns the DFS path to a node.
///
- ///\warning \c t should be reachable from the root.
+ ///\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.
+ ///The distance of a node from the root(s).
- ///Returns the distance of a node from the root.
+ ///Returns the distance of a node from the root(s).
///
- ///\warning If node \c v is not reachable from the root, 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 %DFS tree for a node.
///This function returns the 'previous arc' of the %DFS tree for the
- ///node \c v, i.e. it returns the last arc of a %DFS path from the
- ///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.
+ ///node \c v, i.e. it returns the last arc of a %DFS 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 %DFS tree used here is equal to the %DFS 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 %DFS tree.
///This function returns the 'previous node' of the %DFS
///tree for the node \c v, i.e. it returns the last but one node
- ///from a %DFS path from the 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.
+ ///from a %DFS 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 %DFS tree used here is equal to the %DFS 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]); }
@@ -726,7 +725,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;}
@@ -736,14 +735,15 @@
///Returns a const reference to the node map that stores the predecessor
///arcs, which form the DFS 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]; }
@@ -889,8 +889,8 @@
/// This auxiliary class is created to implement the
/// \ref dfs() "function-type interface" of \ref Dfs algorithm.
- /// It does not have own \ref run() method, it uses the functions
- /// and features of the plain \ref Dfs.
+ /// It does not have own \ref run(Node) "run()" method, it uses the
+ /// functions and features of the plain \ref Dfs.
///
/// This class should only be used through the \ref dfs() function,
/// which makes it easier to use the algorithm.
@@ -1110,8 +1110,7 @@
/// // Compute the DFS path from s to t
/// bool reached = dfs(g).path(p).dist(d).run(s,t);
///\endcode
-
- ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
+ ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
///to the end of the parameter list.
///\sa DfsWizard
///\sa Dfs
@@ -1309,7 +1308,7 @@
typedef DfsVisit Create;
- /// \name Named template parameters
+ /// \name Named Template Parameters
///@{
template <class T>
@@ -1351,9 +1350,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 <tt> (*this) </tt>
DfsVisit &reachedMap(ReachedMap &m) {
if(local_reached) {
@@ -1366,16 +1366,14 @@
public:
- /// \name Execution control
- /// The simplest way to execute the algorithm is to use
- /// one of the member functions called \ref lemon::DfsVisit::run()
- /// "run()".
- /// \n
- /// If you need more control on the execution, first you must call
- /// \ref lemon::DfsVisit::init() "init()", then you can add several
- /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
- /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
- /// actual path computation.
+ /// \name Execution Control
+ /// The simplest way to execute the DFS 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 a source node with \ref addSource()
+ /// and perform the actual computation with \ref start().
+ /// This procedure can be repeated if there are nodes that have not
+ /// been reached.
/// @{
@@ -1391,15 +1389,14 @@
}
}
- ///Adds a new source node.
-
- ///Adds a new source node to the set of nodes to be processed.
+ /// \brief Adds a new source node.
///
- ///\pre The stack must be empty. (Otherwise the algorithm gives
- ///false results.)
+ /// Adds a new source node to the set of nodes to be processed.
///
- ///\warning Distances will be wrong (or at least strange) in case of
- ///multiple sources.
+ /// \pre The stack must be empty. Otherwise the algorithm gives
+ /// wrong results. (One of the outgoing arcs of all the source nodes
+ /// except for the last one will not be visited and distances will
+ /// also be wrong.)
void addSource(Node s)
{
LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
@@ -1589,8 +1586,8 @@
/// compute the %DFS path to each node.
///
/// The algorithm computes
- /// - the %DFS tree,
- /// - the distance of each node from the root in the %DFS tree.
+ /// - the %DFS tree (forest),
+ /// - the distance of each node from the root(s) in the %DFS tree.
///
/// \note <tt>d.run()</tt> is just a shortcut of the following code.
///\code
@@ -1615,17 +1612,18 @@
///@}
/// \name Query Functions
- /// The result of the %DFS algorithm can be obtained using these
+ /// The results of the DFS algorithm can be obtained using these
/// functions.\n
- /// Either \ref lemon::DfsVisit::run() "run()" or
- /// \ref lemon::DfsVisit::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]; }
diff -r e22fc10ab6f1 -r 69f33ef03334 lemon/dijkstra.h
--- a/lemon/dijkstra.h Tue Dec 02 10:30:52 2008 +0000
+++ b/lemon/dijkstra.h Tue Dec 02 10:31:20 2008 +0000
@@ -179,20 +179,13 @@
///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 directly by \ref Dijkstra, it is only
- ///passed to \ref DijkstraDefaultTraits.
- ///\tparam LM A readable arc map that determines the lengths of the
- ///arcs. It is read once for each arc, so the map may involve in
+ ///The default type is \ref ListDigraph.
+ ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
+ ///the lengths of the arcs.
+ ///It is read once for each arc, so the map may involve in
///relatively time consuming process to compute the arc lengths if
///it is necessary. The default map type is \ref
- ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
- ///The value of LM is not used directly by \ref Dijkstra, it is only
- ///passed to \ref DijkstraDefaultTraits.
- ///\tparam TR Traits class to set various data types used by the algorithm.
- ///The default traits class is \ref DijkstraDefaultTraits
- ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
- ///for the documentation of a Dijkstra traits class.
+ ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
#ifdef DOXYGEN
template <typename GR, typename LM, typename TR>
#else
@@ -226,7 +219,7 @@
///The operation traits class.
typedef typename TR::OperationTraits OperationTraits;
- ///The traits class.
+ ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
typedef TR Traits;
private:
@@ -308,6 +301,7 @@
///
///\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 Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
@@ -328,6 +322,7 @@
///
///\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 Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
@@ -348,6 +343,7 @@
///
///\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 Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
@@ -388,10 +384,14 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///heap and cross reference type
+ ///heap and cross reference types
///
///\ref named-templ-param "Named parameter" for setting heap and cross
- ///reference type.
+ ///reference types. If this named parameter is used, then external
+ ///heap and cross reference objects must be passed to the algorithm
+ ///using the \ref heap() function before calling \ref run(Node) "run()"
+ ///or \ref init().
+ ///\sa SetStandardHeap
template <class H, class CR = typename Digraph::template NodeMap<int> >
struct SetHeap
: public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
@@ -411,12 +411,18 @@
}
};
///\brief \ref named-templ-param "Named parameter" for setting
- ///heap and cross reference type with automatic allocation
+ ///heap and cross reference types with automatic allocation
///
///\ref named-templ-param "Named parameter" for setting heap and cross
- ///reference type. It can allocate the heap and the cross reference
- ///object if the cross reference's constructor waits for the digraph as
- ///parameter and the heap's constructor waits for the cross reference.
+ ///reference types with automatic allocation.
+ ///They should have standard constructor interfaces to be able to
+ ///automatically created by the algorithm (i.e. the digraph should be
+ ///passed to the constructor of the cross reference and the cross
+ ///reference should be passed to the constructor of the heap).
+ ///However external heap and cross reference objects could also be
+ ///passed to the algorithm using the \ref heap() function before
+ ///calling \ref run(Node) "run()" or \ref init().
+ ///\sa SetHeap
template <class H, class CR = typename Digraph::template NodeMap<int> >
struct SetStandardHeap
: public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
@@ -486,9 +492,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 <tt> (*this) </tt>
Dijkstra &predMap(PredMap &m)
{
@@ -503,9 +510,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 <tt> (*this) </tt>
Dijkstra &processedMap(ProcessedMap &m)
{
@@ -521,9 +529,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 <tt> (*this) </tt>
Dijkstra &distMap(DistMap &m)
{
@@ -538,9 +547,11 @@
///Sets the heap and the cross reference used by algorithm.
///Sets the heap and the cross reference used by algorithm.
- ///If you don't use this function before calling \ref run(),
- ///it will allocate one. The destructor deallocates this
- ///automatically allocated heap and cross reference, of course.
+ ///If you don't use this function before calling \ref run(Node) "run()"
+ ///or \ref init(), heap and cross reference instances will be
+ ///allocated automatically.
+ ///The destructor deallocates these automatically allocated objects,
+ ///of course.
///\return <tt> (*this) </tt>
Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
{
@@ -567,22 +578,19 @@
public:
- ///\name Execution control
- ///The simplest way to execute the algorithm is to use one of the
- ///member functions called \ref lemon::Dijkstra::run() "run()".
- ///\n
- ///If you need more control on the execution, first you must call
- ///\ref lemon::Dijkstra::init() "init()", then you can add several
- ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
- ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
- ///actual path computation.
+ ///\name Execution Control
+ ///The simplest way to execute the %Dijkstra 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();
@@ -658,17 +666,16 @@
return !_heap->empty()?_heap->top():INVALID;
}
- ///\brief Returns \c false if there are nodes
- ///to be processed.
- ///
- ///Returns \c false if there are nodes
- ///to be processed in the priority heap.
+ ///Returns \c false if there are nodes to be processed.
+
+ ///Returns \c false if there are nodes to be processed
+ ///in the priority heap.
bool emptyQueue() const { return _heap->empty(); }
- ///Returns the number of the nodes to be processed in the priority heap
+ ///Returns the number of the nodes to be processed.
- ///Returns the number of the nodes to be processed in the priority heap.
- ///
+ ///Returns the number of the nodes to be processed
+ ///in the priority heap.
int queueSize() const { return _heap->size(); }
///Executes the algorithm.
@@ -789,11 +796,10 @@
///@}
///\name Query Functions
- ///The result of the %Dijkstra algorithm can be obtained using these
+ ///The results of the %Dijkstra algorithm can be obtained using these
///functions.\n
- ///Either \ref lemon::Dijkstra::run() "run()" or
- ///\ref lemon::Dijkstra::start() "start()" must be called before
- ///using them.
+ ///Either \ref run(Node) "run()" or \ref start() should be called
+ ///before using them.
///@{
@@ -801,49 +807,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.
Value 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]); }
@@ -853,7 +859,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;}
@@ -863,14 +869,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 (*_heap_cross_ref)[v] !=
Heap::PRE_HEAP; }
@@ -879,7 +886,8 @@
///Returns \c true if \c v is processed, i.e. the shortest
///path to \c v has already found.
- ///\pre Either \ref run() or \ref init()
+ ///
+ ///\pre Either \ref run(Node) "run()" or \ref init()
///must be called before using this function.
bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
Heap::POST_HEAP; }
@@ -888,7 +896,8 @@
///Returns the current distance of a node from the root(s).
///It may be decreased in the following processes.
- ///\pre Either \ref run() or \ref init()
+ ///
+ ///\pre Either \ref run(Node) "run()" or \ref init()
///must be called before using this function and
///node \c v must be reached but not necessarily processed.
Value currentDist(Node v) const {
@@ -1071,8 +1080,8 @@
/// This auxiliary class is created to implement the
/// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
- /// It does not have own \ref run() method, it uses the functions
- /// and features of the plain \ref Dijkstra.
+ /// It does not have own \ref run(Node) "run()" method, it uses the
+ /// functions and features of the plain \ref Dijkstra.
///
/// This class should only be used through the \ref dijkstra() function,
/// which makes it easier to use the algorithm.
@@ -1267,7 +1276,7 @@
/// // Compute shortest path from s to t
/// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
///\endcode
- ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
+ ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
///to the end of the parameter list.
///\sa DijkstraWizard
///\sa Dijkstra