LEMON/LEMON-main Changeset - r405:6b9057cdcd8b

Repositories » LEMON » LEMON-main

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

Changeset - r405:6b9057cdcd8b

« 395:0c5dd7

408:69f33e »

r405:6b9057cdcd8b

Sun, 30 Nov 2008 19:17:51

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Doc improvements for Bfs, Dfs, Dijkstra (#185) - More precise references to overloaded member functions. - Hide the doc of the traits class parameters. - Better doc for named groups. - More precise doc for the case of multiple sources in Dfs.

0 3 0

default

3 files changed with 276 insertions and 269 deletions:

lemon/bfs.h

lemon/dfs.h

102

104

lemon/dijkstra.h

↑ Collapse diff ↑

lemon/bfs.h

Show inline comments

@@ -77,13 +77,14 @@
+		    {
 		      return new ProcessedMap();
+		    }
 		    ///The type of the map that indicates which nodes are reached.
-		    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    ///The type of the map that indicates which nodes are reached.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template NodeMap<bool> ReachedMap;
 		    ///Instantiates a ReachedMap.
 		    ///This function instantiates a ReachedMap.
 		    ///\param g is the digraph, to which
 		    ///we would like to define the ReachedMap.
@@ -115,19 +116,13 @@
 		  ///
 		  ///There is also a \ref bfs() "function-type interface" for the BFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///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>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=BfsDefaultTraits<GR> >
@@ -147,13 +142,13 @@
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
+		    ///The \ref BfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
@@ -209,13 +204,13 @@
 		    Bfs() {}
 		  public:
 		    typedef Bfs Create;
-		    ///\name Named template parameters
+		    ///\name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetPredMapTraits : public Traits {
 		      typedef T PredMap;
@@ -227,12 +222,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
 		      typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -246,12 +242,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -265,12 +262,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -284,12 +282,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
@@ -336,15 +335,16 @@
 		      if(local_processed) delete _processed;
+		    }
 		    ///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)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
@@ -353,15 +353,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
@@ -370,15 +371,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
@@ -388,15 +390,16 @@
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by
 		    ///the algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///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)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
@@ -404,28 +407,25 @@
 		      _dist = &m;
 		      return *this;
+		    }
 		  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();
 		      _queue.resize(countNodes(*G));
 		      _queue_head=_queue_tail=0;
 		      _curr_dist=1;
@@ -553,22 +553,22 @@
 		    ///is empty.
 		    Node nextNode() const
+		    {
 		      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.
 		    ///Executes the algorithm.
 		    ///
@@ -727,93 +727,94 @@
+		      }
+		    }
 		    ///@}
 		    ///\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.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
-		    ///\warning \c t should be reachable from the root(s).
+		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///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]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    /// distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reachable from the root(s).
+		    ///Checks if a node is reached from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\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]; }
 		    ///@}
 		  };
@@ -953,14 +954,14 @@
 		  };
 		  /// Auxiliary class for the function-type interface of BFS algorithm.
 		  /// This auxiliary class is created to implement the
 		  /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
 		  /// It does not have own \ref run() method, it uses the functions
 		  /// 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.
 		  template<class TR>
 		  class BfsWizard : public TR
+		  {
@@ -1174,13 +1175,13 @@
 		  ///  // Compute shortest path from node s to each node
 		  ///  bfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // Compute shortest path from s to t
 		  ///  bool reached = bfs(g).path(p).dist(d).run(s,t);
 		  ///\endcode
 		  ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
+		  ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
 		  ///to the end of the parameter list.
 		  ///\sa BfsWizard
 		  ///\sa Bfs
 		  template<class GR>
 		  BfsWizard<BfsWizardBase<GR> >
 		  bfs(const GR &digraph)
@@ -1360,13 +1361,13 @@
 		    BfsVisit() {}
 		  public:
 		    typedef BfsVisit Create;
-		    /// \name Named template parameters
+		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
@@ -1402,37 +1403,35 @@
 		      if(local_reached) delete _reached;
+		    }
 		    /// \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) {
 		        delete _reached;
 		        local_reached = false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  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.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
@@ -1726,23 +1725,24 @@
+		      }
+		    }
 		    ///@}
 		    /// \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]; }
 		    ///@}
 		  };

lemon/dfs.h

Show inline comments

@@ -116,19 +116,13 @@
 		  ///
 		  ///There is also a \ref dfs() "function-type interface" for the DFS
 		  ///algorithm, which is convenient in the simplier cases and it can be
 		  ///used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph. The value of GR is not used
 		  ///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>
 		#else
 		  template <typename GR=ListDigraph,
 		            typename TR=DfsDefaultTraits<GR> >
@@ -148,13 +142,13 @@
 		    typedef typename TR::ReachedMap ReachedMap;
 		    ///The type of the map that indicates which nodes are processed.
 		    typedef typename TR::ProcessedMap ProcessedMap;
 		    ///The type of the paths.
 		    typedef PredMapPath<Digraph, PredMap> Path;
 		    ///The traits class.
+		    ///The \ref DfsDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
@@ -227,12 +221,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 		      typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -246,12 +241,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 		      typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -265,12 +261,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ReachedMap type.
 		    ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    template <class T>
 		    struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 		    };
 		    template <class T>
@@ -284,12 +281,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 		      typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 		    };
 		    struct SetStandardProcessedMapTraits : public Traits {
@@ -335,15 +333,16 @@
 		      if(local_processed) delete _processed;
+		    }
 		    ///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)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
@@ -352,15 +351,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_reached) {
 		        delete _reached;
 		        local_reached=false;
@@ -369,15 +369,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
@@ -387,15 +388,16 @@
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by
 		    ///the algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///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)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
@@ -403,28 +405,26 @@
 		      _dist = &m;
 		      return *this;
+		    }
 		  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();
 		      _stack.resize(countNodes(*G));
 		      _stack_head=-1;
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
@@ -435,17 +435,16 @@
+		    }
 		    ///Adds a new source node.
 		    ///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.");
 		      if(!(*_reached)[s])
+		        {
 		          _reached->set(s,true);
@@ -503,22 +502,22 @@
 		    ///is empty.
 		    OutArcIt nextArc() const
+		    {
 		      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.
 		    ///Executes the algorithm.
 		    ///
@@ -634,14 +633,14 @@
 		    ///Runs the algorithm to visit all nodes in the digraph.
 		    ///This method runs the %DFS algorithm in order to 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
 		    ///  d.init();
 		    ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///    if (!d.reached(n)) {
@@ -660,93 +659,94 @@
+		      }
+		    }
 		    ///@}
 		    ///\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.
 		    ///@{
 		    ///The DFS path to a node.
 		    ///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]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the
 		    ///distances of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the 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]; }
 		    ///@}
 		  };
@@ -886,14 +886,14 @@
 		  };
 		  /// Auxiliary class for the function-type interface of DFS algorithm.
 		  /// 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.
 		  template<class TR>
 		  class DfsWizard : public TR
+		  {
@@ -1107,14 +1107,13 @@
 		  ///  // Compute the DFS tree
 		  ///  dfs(g).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // 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
 		  template<class GR>
 		  DfsWizard<DfsWizardBase<GR> >
 		  dfs(const GR &digraph)
@@ -1306,13 +1305,13 @@
 		    DfsVisit() {}
 		  public:
 		    typedef DfsVisit Create;
-		    /// \name Named template parameters
+		    /// \name Named Template Parameters
 		    ///@{
 		    template <class T>
 		    struct SetReachedMapTraits : public Traits {
 		      typedef T ReachedMap;
 		      static ReachedMap *createReachedMap(const Digraph &digraph) {
@@ -1348,37 +1347,36 @@
 		      if(local_reached) delete _reached;
+		    }
 		    /// \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) {
 		        delete _reached;
 		        local_reached=false;
+		      }
 		      _reached = &m;
 		      return *this;
+		    }
 		  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.
 		    /// @{
 		    /// \brief Initializes the internal data structures.
 		    ///
 		    /// Initializes the internal data structures.
@@ -1388,21 +1386,20 @@
 		      _stack_head = -1;
 		      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 		        _reached->set(u, false);
+		      }
+		    }
 		    ///Adds a new source node.
 		    /// \brief Adds a new source node.
 		    ///
 		    ///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.");
 		      if(!(*_reached)[s]) {
 		          _reached->set(s,true);
 		          _visitor->start(s);
@@ -1586,14 +1583,14 @@
 		    /// \brief Runs the algorithm to visit all nodes in the digraph.
 		    /// This method runs the %DFS algorithm in order to
 		    /// 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
 		    ///   d.init();
 		    ///   for (NodeIt n(digraph); n != INVALID; ++n) {
 		    ///     if (!d.reached(n)) {
@@ -1612,23 +1609,24 @@
+		      }
+		    }
 		    ///@}
 		    /// \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]; }
 		    ///@}
 		  };

lemon/dijkstra.h

Show inline comments

@@ -199,26 +199,19 @@
 		  ///
 		  ///There is also a \ref dijkstra() "function-type interface" for the
 		  ///%Dijkstra algorithm, which is convenient in the simplier cases and
 		  ///it can be used easier.
 		  ///
 		  ///\tparam GR The type of the digraph the algorithm runs on.
 		  ///The default value is \ref ListDigraph.
 		  ///The value of GR is not used 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
 		  template <typename GR=ListDigraph,
 		            typename LM=typename GR::template ArcMap<int>,
 		            typename TR=DijkstraDefaultTraits<GR,LM> >
@@ -246,13 +239,13 @@
 		    typedef typename TR::HeapCrossRef HeapCrossRef;
 		    ///The heap type used by the algorithm.
 		    typedef typename TR::Heap Heap;
 		    ///The operation traits class.
 		    typedef typename TR::OperationTraits OperationTraits;
 		    ///The traits class.
+		    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		  private:
 		    typedef typename Digraph::Node Node;
 		    typedef typename Digraph::NodeIt NodeIt;
@@ -328,12 +321,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///PredMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetPredMap
 		      : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 		    };
@@ -348,12 +342,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///DistMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetDistMap
 		      : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 		    };
@@ -368,12 +363,13 @@
 		    };
 		    ///\brief \ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///
 		    ///\ref named-templ-param "Named parameter" for setting
 		    ///ProcessedMap type.
 		    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 		    template <class T>
 		    struct SetProcessedMap
 		      : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 		    };
@@ -408,16 +404,20 @@
+		      {
 		        LEMON_ASSERT(false, "Heap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    ///\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> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > Create;
 		    };
@@ -431,18 +431,24 @@
 		      static Heap *createHeap(HeapCrossRef &R)
+		      {
 		        return new Heap(R);
+		      }
 		    };
 		    ///\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> > {
 		      typedef Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> >
 		      Create;
 		    };
@@ -506,15 +512,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_pred) {
 		        delete _pred;
 		        local_pred=false;
@@ -523,15 +530,16 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_processed) {
 		        delete _processed;
 		        local_processed=false;
@@ -541,15 +549,16 @@
+		    }
 		    ///Sets the map that stores the distances of the nodes.
 		    ///Sets the map that stores the distances of the nodes calculated by the
 		    ///algorithm.
 		    ///If you don't use this function before calling \ref run(),
 		    ///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)
+		    {
 		      if(local_dist) {
 		        delete _dist;
 		        local_dist=false;
@@ -558,15 +567,17 @@
 		      return *this;
+		    }
 		    ///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)
+		    {
 		      if(local_heap_cross_ref) {
 		        delete _heap_cross_ref;
 		        local_heap_cross_ref=false;
@@ -587,28 +598,25 @@
 		      _processed->set(v,true);
 		      _dist->set(v, dst);
+		    }
 		  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();
 		      _heap->clear();
 		      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 		        _pred->set(u,INVALID);
@@ -678,23 +686,22 @@
 		    ///priority heap is empty.
 		    Node nextNode() const
+		    {
 		      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.
 		    ///Executes the algorithm.
 		    ///
@@ -809,112 +816,114 @@
 		      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
+		    }
 		    ///@}
 		    ///\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.
 		    ///@{
 		    ///The shortest path to a node.
 		    ///Returns the shortest path to a node.
 		    ///
-		    ///\warning \c t should be reachable from the root(s).
+		    ///\warning \c t should be reached from the root(s).
 		    ///
 		    ///\pre Either \ref run() or \ref start() must be called before
 		    ///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]); }
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///distances of the nodes.
 		    ///
 		    ///Returns a const reference to the node map that stores the distances
 		    ///of the nodes calculated by the algorithm.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const DistMap &distMap() const { return *_dist;}
 		    ///\brief Returns a const reference to the node map that stores the
 		    ///predecessor arcs.
 		    ///
 		    ///Returns a const reference to the node map that stores the predecessor
 		    ///arcs, which form the shortest path tree.
 		    ///
 		    ///\pre Either \ref run() or \ref init()
+		    ///\pre Either \ref run(Node) "run()" or \ref init()
 		    ///must be called before using this function.
 		    const PredMap &predMap() const { return *_pred;}
-		    ///Checks if a node is reachable from the root(s).
+		    ///Checks if a node is reached from the root(s).
 		    ///Returns \c true if \c v is reachable from the root(s).
 		    ///\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; }
 		    ///Checks if a node is processed.
 		    ///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; }
 		    ///The current distance of a node from the root(s).
 		    ///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 {
 		      return processed(v) ? (*_dist)[v] : (*_heap)[v];
+		    }
@@ -1091,14 +1100,14 @@
 		  };
 		  /// Auxiliary class for the function-type interface of Dijkstra algorithm.
 		  /// 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.
 		  template<class TR>
 		  class DijkstraWizard : public TR
+		  {
@@ -1287,13 +1296,13 @@
 		  ///  // Compute shortest path from node s to each node
 		  ///  dijkstra(g,length).predMap(preds).distMap(dists).run(s);
 		  ///
 		  ///  // 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
 		  template<class GR, class LM>
 		  DijkstraWizard<DijkstraWizardBase<GR,LM> >
 		  dijkstra(const GR &digraph, const LM &length)

0 comments (0 inline)

RhodeCode

Login to your account