LEMON/LEMON-official Changeset - r424:69f33ef03334

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r424:69f33ef03334

« 421:6b9057
« 423:e22fc1

429:d8b87e »

r424:69f33ef03334

Tue, 02 Dec 2008 11:31:20

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 3 0

merge default

1 file changed with 277 insertions and 270 deletions:

lemon/bfs.h

lemon/dfs.h

102

104

lemon/dijkstra.h

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

@@ -53,3 +53,3 @@
-		    ///This function instantiates a PredMap.
 		    ///This function instantiates a PredMap.
 		    ///\param g is the digraph, to which we would like to define the
@@ -82,3 +82,4 @@
-		    ///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;
@@ -120,9 +121,3 @@
 		  ///\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
@@ -152,3 +147,3 @@
 		    ///The traits class.
+		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
@@ -214,3 +209,3 @@
-		    ///\name Named template parameters
+		    ///\name Named Template Parameters
@@ -232,2 +227,3 @@
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -251,2 +247,3 @@
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -270,2 +267,3 @@
 		    ///ReachedMap type.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
@@ -289,2 +287,3 @@
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -341,5 +340,6 @@
 		    ///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>
@@ -358,5 +358,6 @@
 		    ///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>
@@ -375,5 +376,6 @@
 		    ///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>
@@ -393,5 +395,6 @@
 		    ///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>
@@ -409,11 +412,9 @@
 		    ///\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.
@@ -421,6 +422,5 @@
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
@@ -558,7 +558,6 @@
 		    ///\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; }
@@ -567,3 +566,4 @@
-		    ///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; }
@@ -732,6 +732,6 @@
 		    ///\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.
@@ -743,6 +743,6 @@
 		    ///
-		    ///\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); }
@@ -753,7 +753,7 @@
 		    ///
-		    ///\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]; }
@@ -764,4 +764,4 @@
 		    ///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.
 		    ///
@@ -770,4 +770,4 @@
 		    ///
 		    ///\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];}
@@ -778,4 +778,4 @@
 		    ///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.
 		    ///
@@ -784,4 +784,4 @@
 		    ///
 		    ///\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:
@@ -795,3 +795,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -805,3 +805,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -809,6 +809,7 @@
-		    ///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.
@@ -958,4 +959,4 @@
 		  /// \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.
 		  ///
@@ -1179,3 +1180,3 @@
 		  ///\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.
@@ -1365,3 +1366,3 @@
-		    /// \name Named template parameters
+		    /// \name Named Template Parameters
@@ -1407,5 +1408,6 @@
 		    /// 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>
@@ -1422,12 +1424,9 @@
 		    /// \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.
@@ -1731,13 +1730,14 @@
 		    /// \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.

lemon/dfs.h

Show inline comments

@@ -121,9 +121,3 @@
 		  ///\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
@@ -153,3 +147,3 @@
 		    ///The traits class.
+		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
@@ -232,2 +226,3 @@
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -251,2 +246,3 @@
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -270,2 +266,3 @@
 		    ///ReachedMap type.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
@@ -289,2 +286,3 @@
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -340,5 +338,6 @@
 		    ///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>
@@ -357,5 +356,6 @@
 		    ///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>
@@ -374,5 +374,6 @@
 		    ///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>
@@ -392,5 +393,6 @@
 		    ///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>
@@ -408,11 +410,10 @@
 		    ///\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.
@@ -420,6 +421,5 @@
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
@@ -440,7 +440,6 @@
 		    ///
 		    ///\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)
@@ -508,7 +507,6 @@
 		    ///\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; }
@@ -517,3 +515,4 @@
-		    ///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; }
@@ -639,4 +638,4 @@
 		    ///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.
 		    ///
@@ -665,6 +664,6 @@
 		    ///\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.
@@ -676,17 +675,17 @@
 		    ///
-		    ///\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]; }
@@ -696,5 +695,5 @@
 		    ///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.
 		    ///
@@ -703,4 +702,4 @@
 		    ///
 		    ///\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];}
@@ -711,4 +710,4 @@
 		    ///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.
 		    ///
@@ -717,4 +716,4 @@
 		    ///
 		    ///\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:
@@ -728,3 +727,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -738,3 +737,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -742,6 +741,7 @@
-		    ///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.
@@ -891,4 +891,4 @@
 		  /// \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.
 		  ///
@@ -1112,4 +1112,3 @@
 		  ///\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.
@@ -1311,3 +1310,3 @@
-		    /// \name Named template parameters
+		    /// \name Named Template Parameters
@@ -1353,5 +1352,6 @@
 		    /// 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>
@@ -1368,12 +1368,10 @@
 		    /// \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.
@@ -1393,11 +1391,10 @@
 		    ///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)
@@ -1591,4 +1588,4 @@
 		    /// 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.
 		    ///
@@ -1617,13 +1614,14 @@
 		    /// \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.

lemon/dijkstra.h

Show inline comments

@@ -181,16 +181,9 @@
 		  ///\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
@@ -228,3 +221,3 @@
 		    ///The traits class.
+		    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
@@ -310,2 +303,3 @@
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -330,2 +324,3 @@
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -350,2 +345,3 @@
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
@@ -390,6 +386,10 @@
 		    ///\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> >
@@ -413,8 +413,14 @@
 		    ///\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> >
@@ -488,5 +494,6 @@
 		    ///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>
@@ -505,5 +512,6 @@
 		    ///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>
@@ -523,5 +531,6 @@
 		    ///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>
@@ -540,5 +549,7 @@
 		    ///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>
@@ -569,11 +580,9 @@
 		    ///\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.
@@ -581,6 +590,5 @@
 		    ///\brief Initializes the internal data structures.
 		    ///
 		    ///Initializes the internal data structures.
 		    ///Initializes the internal data structures.
 		    ///
 		    void init()
@@ -660,13 +668,12 @@
 		    ///\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(); }
@@ -791,7 +798,6 @@
 		    ///\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.
@@ -803,6 +809,6 @@
 		    ///
-		    ///\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); }
@@ -813,7 +819,7 @@
 		    ///
-		    ///\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]; }
@@ -824,4 +830,4 @@
 		    ///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.
 		    ///
@@ -830,4 +836,4 @@
 		    ///
 		    ///\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]; }
@@ -838,4 +844,4 @@
 		    ///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.
 		    ///
@@ -844,4 +850,4 @@
 		    ///
 		    ///\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:
@@ -855,3 +861,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -865,3 +871,3 @@
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
@@ -869,6 +875,7 @@
-		    ///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.
@@ -881,3 +888,4 @@
 		    ///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.
@@ -890,3 +898,4 @@
 		    ///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
@@ -1073,4 +1082,4 @@
 		  /// \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.
 		  ///
@@ -1269,3 +1278,3 @@
 		  ///\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.

0 comments (0 inline)

RhodeCode

Login to your account