diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2009 + * Copyright (C) 2003-2010 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -70,9 +70,9 @@ ///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. @@ -116,7 +116,7 @@ /// ///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 PredMap; ///Instantiates a \c PredMap. @@ -131,8 +131,8 @@ ///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. - ///By default it is a NullMap. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. @@ -151,7 +151,7 @@ ///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 DistMap; ///Instantiates a \c DistMap. @@ -169,6 +169,10 @@ /// \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. @@ -188,6 +192,11 @@ ///relatively time consuming process to compute the arc lengths if ///it is necessary. The default map type is \ref ///concepts::Digraph::ArcMap "GR::ArcMap". + ///\tparam TR The traits class that defines various types used by the + ///algorithm. By default, it is \ref DijkstraDefaultTraits + ///"DijkstraDefaultTraits". + ///In most cases, this parameter should not be set directly, + ///consider to use the named template parameters instead. #ifdef DOXYGEN template #else @@ -201,8 +210,8 @@ ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///The type of the length of the arcs. - typedef typename TR::LengthMap::Value Value; + ///The type of the arc lengths. + typedef typename TR::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 @@ -304,7 +313,7 @@ /// ///\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 struct SetPredMap : public Dijkstra< Digraph, LengthMap, SetPredMapTraits > { @@ -325,7 +334,7 @@ /// ///\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 struct SetDistMap : public Dijkstra< Digraph, LengthMap, SetDistMapTraits > { @@ -346,7 +355,7 @@ /// ///\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 struct SetProcessedMap : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits > { @@ -422,7 +431,7 @@ ///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 + ///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 @@ -443,6 +452,7 @@ /// ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. + /// For more information, see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits : public Dijkstra > { @@ -584,8 +594,8 @@ ///\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 + ///If you need better control on the execution, you have to call + ///\ref init() first, 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. @@ -801,14 +811,14 @@ ///\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). /// @@ -816,9 +826,9 @@ ///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. @@ -827,29 +837,31 @@ ///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. @@ -870,13 +882,13 @@ ///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). /// @@ -895,9 +907,9 @@ 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() @@ -924,9 +936,9 @@ ///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. @@ -973,7 +985,7 @@ /// ///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 PredMap; ///Instantiates a PredMap. @@ -988,8 +1000,8 @@ ///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. - ///By default it is a NullMap. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -1008,7 +1020,7 @@ ///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 DistMap; ///Instantiates a DistMap. @@ -1023,18 +1035,15 @@ ///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 Path; }; /// Default traits class used by DijkstraWizard - /// To make it easier to use Dijkstra algorithm - /// we have created a wizard class. - /// This \ref DijkstraWizard class needs default traits, - /// as well as the \ref Dijkstra class. - /// The \ref DijkstraWizardBase is a class to be the default traits of the - /// \ref DijkstraWizard class. + /// Default traits class used by DijkstraWizard. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. template class DijkstraWizardBase : public DijkstraWizardDefaultTraits { @@ -1088,12 +1097,14 @@ /// /// This class should only be used through the \ref dijkstra() function, /// which makes it easier to use the algorithm. + /// + /// \tparam TR The traits class that defines various types used by the + /// algorithm. template 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; @@ -1101,20 +1112,12 @@ 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: @@ -1186,11 +1189,12 @@ 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 DijkstraWizard > predMap(const T &t) { @@ -1204,11 +1208,13 @@ 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 DijkstraWizard > distMap(const T &t) { @@ -1222,11 +1228,12 @@ 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 DijkstraWizard > processedMap(const T &t) { @@ -1239,6 +1246,7 @@ 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. ///