lemon: comparison lemon/dijkstra.h

equal deleted inserted replaced

-:1c84deb82bea
+:fd0f0a7c7fc6
 typedef GR Digraph;
 ///The type of the map that stores the arc lengths.
 ///The type of the map that stores the arc lengths.
-///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 typedef LEN LengthMap;
-///The type of the length of the arcs.
+///The type of the arc lengths.
 typedef typename LEN::Value Value;
 /// Operation traits for %Dijkstra algorithm.
 /// This class defines the operations that are used in the algorithm.
 ///\brief The type of the map that stores the predecessor
 ///arcs of the shortest paths.
 ///
 ///The type of the map that stores the predecessor
 ///arcs of the shortest paths.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 ///Instantiates a \c PredMap.
 ///This function instantiates a \ref PredMap.
 ///\param g is the digraph, to which we would like to define the
 }
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that indicates which nodes are processed.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 ///By default it is a NullMap.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a \c ProcessedMap.
 ///This function instantiates a \ref ProcessedMap.
 }
 ///The type of the map that stores the distances of the nodes.
 ///The type of the map that stores the distances of the nodes.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 ///Instantiates a \c DistMap.
 ///This function instantiates a \ref DistMap.
 ///\param g is the digraph, to which we would like to define
 ///%Dijkstra algorithm class.
 /// \ingroup shortest_path
 ///This class provides an efficient implementation of the %Dijkstra algorithm.
+///
+///The %Dijkstra algorithm solves the single-source shortest path problem
+///when all arc lengths are non-negative. If there are negative lengths,
+///the BellmanFord algorithm should be used instead.
 ///
 ///The arc lengths are passed to the algorithm using a
 ///\ref concepts::ReadMap "ReadMap",
 ///so it is easy to change it to any kind of length.
 ///The type of the length is determined by the
 public:
 ///The type of the digraph the algorithm runs on.
 typedef typename TR::Digraph Digraph;
-///The type of the length of the arcs.
+///The type of the arc lengths.
 typedef typename TR::LengthMap::Value Value;
 ///The type of the map that stores the arc lengths.
 typedef typename TR::LengthMap LengthMap;
 ///\brief The type of the map that stores the predecessor arcs of the
 ///shortest paths.
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///\c PredMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c PredMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetPredMap
 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///\c DistMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c DistMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetDistMap
 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///\c ProcessedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c ProcessedMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetProcessedMap
 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
 typedef Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > Create;
 };
 /// \brief \ref named-templ-param "Named parameter" for setting
 ///\c OperationTraits type
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c OperationTraits type.
+/// For more information see \ref DijkstraDefaultOperationTraits.
 template <class T>
 struct SetOperationTraits
 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
 typedef Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> >
 Create;
 ///@}
 ///\name Query Functions
 ///The results of the %Dijkstra algorithm can be obtained using these
 ///functions.\n
-///Either \ref run(Node) "run()" or \ref start() should be called
+///Either \ref run(Node) "run()" or \ref init() should be called
 ///before using them.
 ///@{
-///The shortest path to a node.
+///The shortest path to the given node.
-///Returns the shortest path to a node.
+///Returns the shortest path to the given node from the root(s).
 ///
 ///\warning \c t should be reached from the root(s).
 ///
 ///\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).
+///The distance of the given node from the root(s).
-///Returns the distance of a node from the root(s).
+///Returns the distance of the given node from the root(s).
 ///
 ///\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(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.
+///\brief Returns the 'previous arc' of the shortest path tree for
+///the given 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 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().
+///tree used in \ref predNode() and \ref predMap().
 ///
 ///\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.
+///\brief Returns the 'previous node' of the shortest path tree for
+///the given 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 a root to \c v. It is \c INVALID
+///of 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().
+///tree used in \ref predArc() and \ref predMap().
 ///
 ///\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
 ///predecessor arcs.
 ///
 ///Returns a const reference to the node map that stores the predecessor
-///arcs, which form the shortest path tree.
+///arcs, which form the shortest path tree (forest).
 ///
 ///\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 reached from the root(s).
+///Checks if the given node is reached from the root(s).
 ///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.
 ///\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).
+///The current distance of the given node from the root(s).
-///Returns the current distance of a node from the root(s).
+///Returns the current distance of the given node from the root(s).
 ///It may be decreased in the following processes.
 ///
 ///\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.
 ///The type of the digraph the algorithm runs on.
 typedef GR Digraph;
 ///The type of the map that stores the arc lengths.
 ///The type of the map that stores the arc lengths.
-///It must meet the \ref concepts::ReadMap "ReadMap" concept.
+///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
 typedef LEN LengthMap;
-///The type of the length of the arcs.
+///The type of the arc lengths.
 typedef typename LEN::Value Value;
 /// Operation traits for Dijkstra algorithm.
 /// This class defines the operations that are used in the algorithm.
 ///\brief The type of the map that stores the predecessor
 ///arcs of the shortest paths.
 ///
 ///The type of the map that stores the predecessor
 ///arcs of the shortest paths.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
 ///Instantiates a PredMap.
 ///This function instantiates a PredMap.
 ///\param g is the digraph, to which we would like to define the
 }
 ///The type of the map that indicates which nodes are processed.
 ///The type of the map that indicates which nodes are processed.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 ///By default it is a NullMap.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a ProcessedMap.
 ///This function instantiates a ProcessedMap.
 }
 ///The type of the map that stores the distances of the nodes.
 ///The type of the map that stores the distances of the nodes.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
 ///Instantiates a DistMap.
 ///This function instantiates a DistMap.
 ///\param g is the digraph, to which we would like to define
 }
 ///The type of the shortest paths.
 ///The type of the shortest paths.
-///It must meet the \ref concepts::Path "Path" concept.
+///It must conform to the \ref concepts::Path "Path" concept.
 typedef lemon::Path<Digraph> Path;
 };
 /// Default traits class used by DijkstraWizard
-/// To make it easier to use Dijkstra algorithm
+/// Default traits class used by DijkstraWizard.
-/// we have created a wizard class.
+/// \tparam GR The type of the digraph.
-/// This \ref DijkstraWizard class needs default traits,
+/// \tparam LEN The type of the length map.
-/// as well as the \ref Dijkstra class.
-/// The \ref DijkstraWizardBase is a class to be the default traits of the
-/// \ref DijkstraWizard class.
 template<typename GR, typename LEN>
 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
 {
 typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
 protected:
 template<class TR>
 class DijkstraWizard : public TR
 {
 typedef TR Base;
-///The type of the digraph the algorithm runs on.
 typedef typename TR::Digraph Digraph;
 typedef typename Digraph::Node Node;
 typedef typename Digraph::NodeIt NodeIt;
 typedef typename Digraph::Arc Arc;
 typedef typename Digraph::OutArcIt OutArcIt;
-///The type of the map that stores the arc lengths.
 typedef typename TR::LengthMap LengthMap;
-///The type of the length of the arcs.
 typedef typename LengthMap::Value Value;
-///\brief The type of the map that stores the predecessor
-///arcs of the shortest paths.
 typedef typename TR::PredMap PredMap;
-///The type of the map that stores the distances of the nodes.
 typedef typename TR::DistMap DistMap;
-///The type of the map that indicates which nodes are processed.
 typedef typename TR::ProcessedMap ProcessedMap;
-///The type of the shortest paths
 typedef typename TR::Path Path;
-///The heap type used by the dijkstra algorithm.
 typedef typename TR::Heap Heap;
 public:
 /// Constructor.
 struct SetPredMapBase : public Base {
 typedef T PredMap;
 static PredMap *createPredMap(const Digraph &) { return 0; };
 SetPredMapBase(const TR &b) : TR(b) {}
 };
-///\brief \ref named-func-param "Named parameter"
-///for setting PredMap object.
+///\brief \ref named-templ-param "Named parameter" for setting
-///
+///the predecessor map.
-///\ref named-func-param "Named parameter"
+///
-///for setting PredMap object.
+///\ref named-templ-param "Named parameter" function for setting
+///the map that stores the predecessor arcs of the nodes.
 template<class T>
 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
 {
 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DijkstraWizard<SetPredMapBase<T> >(*this);
 struct SetDistMapBase : public Base {
 typedef T DistMap;
 static DistMap *createDistMap(const Digraph &) { return 0; };
 SetDistMapBase(const TR &b) : TR(b) {}
 };
-///\brief \ref named-func-param "Named parameter"
-///for setting DistMap object.
+///\brief \ref named-templ-param "Named parameter" for setting
-///
+///the distance map.
-///\ref named-func-param "Named parameter"
+///
-///for setting DistMap object.
+///\ref named-templ-param "Named parameter" function for setting
+///the map that stores the distances of the nodes calculated
+///by the algorithm.
 template<class T>
 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
 {
 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DijkstraWizard<SetDistMapBase<T> >(*this);
 struct SetProcessedMapBase : public Base {
 typedef T ProcessedMap;
 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
 SetProcessedMapBase(const TR &b) : TR(b) {}
 };
-///\brief \ref named-func-param "Named parameter"
-///for setting ProcessedMap object.
+///\brief \ref named-func-param "Named parameter" for setting
-///
+///the processed map.
-/// \ref named-func-param "Named parameter"
+///
-///for setting ProcessedMap object.
+///\ref named-templ-param "Named parameter" function for setting
+///the map that indicates which nodes are processed.
 template<class T>
 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
 {
 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DijkstraWizard<SetProcessedMapBase<T> >(*this);
 template<class T>
 struct SetPathBase : public Base {
 typedef T Path;
 SetPathBase(const TR &b) : TR(b) {}
 };
 ///\brief \ref named-func-param "Named parameter"
 ///for getting the shortest path to the target node.
 ///
 ///\ref named-func-param "Named parameter"
 ///for getting the shortest path to the target node.

changeset 763	f47b6c94577e
parent 631	33c6b6e755cd
child 764	684964884a2e