lemon/dijkstra.h
changeset 770 432c54cec63c
parent 716 f47b6c94577e
parent 713 4ac30454f1c1
child 786 e20173729589
child 787 c2230649a493
     1.1 --- a/lemon/dijkstra.h	Tue Aug 18 10:08:28 2009 +0200
     1.2 +++ b/lemon/dijkstra.h	Thu Nov 05 08:39:49 2009 +0100
     1.3 @@ -70,9 +70,9 @@
     1.4      ///The type of the map that stores the arc lengths.
     1.5  
     1.6      ///The type of the map that stores the arc lengths.
     1.7 -    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
     1.8 +    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
     1.9      typedef LEN LengthMap;
    1.10 -    ///The type of the length of the arcs.
    1.11 +    ///The type of the arc lengths.
    1.12      typedef typename LEN::Value Value;
    1.13  
    1.14      /// Operation traits for %Dijkstra algorithm.
    1.15 @@ -116,7 +116,7 @@
    1.16      ///
    1.17      ///The type of the map that stores the predecessor
    1.18      ///arcs of the shortest paths.
    1.19 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.20 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.21      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    1.22      ///Instantiates a \c PredMap.
    1.23  
    1.24 @@ -131,7 +131,7 @@
    1.25      ///The type of the map that indicates which nodes are processed.
    1.26  
    1.27      ///The type of the map that indicates which nodes are processed.
    1.28 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.29 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.30      ///By default it is a NullMap.
    1.31      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    1.32      ///Instantiates a \c ProcessedMap.
    1.33 @@ -151,7 +151,7 @@
    1.34      ///The type of the map that stores the distances of the nodes.
    1.35  
    1.36      ///The type of the map that stores the distances of the nodes.
    1.37 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.38 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.39      typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
    1.40      ///Instantiates a \c DistMap.
    1.41  
    1.42 @@ -169,6 +169,10 @@
    1.43    /// \ingroup shortest_path
    1.44    ///This class provides an efficient implementation of the %Dijkstra algorithm.
    1.45    ///
    1.46 +  ///The %Dijkstra algorithm solves the single-source shortest path problem
    1.47 +  ///when all arc lengths are non-negative. If there are negative lengths,
    1.48 +  ///the BellmanFord algorithm should be used instead.
    1.49 +  ///
    1.50    ///The arc lengths are passed to the algorithm using a
    1.51    ///\ref concepts::ReadMap "ReadMap",
    1.52    ///so it is easy to change it to any kind of length.
    1.53 @@ -201,7 +205,7 @@
    1.54      ///The type of the digraph the algorithm runs on.
    1.55      typedef typename TR::Digraph Digraph;
    1.56  
    1.57 -    ///The type of the length of the arcs.
    1.58 +    ///The type of the arc lengths.
    1.59      typedef typename TR::LengthMap::Value Value;
    1.60      ///The type of the map that stores the arc lengths.
    1.61      typedef typename TR::LengthMap LengthMap;
    1.62 @@ -304,7 +308,7 @@
    1.63      ///
    1.64      ///\ref named-templ-param "Named parameter" for setting
    1.65      ///\c PredMap type.
    1.66 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.67 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.68      template <class T>
    1.69      struct SetPredMap
    1.70        : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
    1.71 @@ -325,7 +329,7 @@
    1.72      ///
    1.73      ///\ref named-templ-param "Named parameter" for setting
    1.74      ///\c DistMap type.
    1.75 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.76 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.77      template <class T>
    1.78      struct SetDistMap
    1.79        : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
    1.80 @@ -346,7 +350,7 @@
    1.81      ///
    1.82      ///\ref named-templ-param "Named parameter" for setting
    1.83      ///\c ProcessedMap type.
    1.84 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.85 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
    1.86      template <class T>
    1.87      struct SetProcessedMap
    1.88        : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
    1.89 @@ -443,6 +447,7 @@
    1.90      ///
    1.91      ///\ref named-templ-param "Named parameter" for setting
    1.92      ///\c OperationTraits type.
    1.93 +    /// For more information see \ref DijkstraDefaultOperationTraits.
    1.94      template <class T>
    1.95      struct SetOperationTraits
    1.96        : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
    1.97 @@ -584,8 +589,8 @@
    1.98      ///\name Execution Control
    1.99      ///The simplest way to execute the %Dijkstra algorithm is to use
   1.100      ///one of the member functions called \ref run(Node) "run()".\n
   1.101 -    ///If you need more control on the execution, first you have to call
   1.102 -    ///\ref init(), then you can add several source nodes with
   1.103 +    ///If you need better control on the execution, you have to call
   1.104 +    ///\ref init() first, then you can add several source nodes with
   1.105      ///\ref addSource(). Finally the actual path computation can be
   1.106      ///performed with one of the \ref start() functions.
   1.107  
   1.108 @@ -801,14 +806,14 @@
   1.109      ///\name Query Functions
   1.110      ///The results of the %Dijkstra algorithm can be obtained using these
   1.111      ///functions.\n
   1.112 -    ///Either \ref run(Node) "run()" or \ref start() should be called
   1.113 +    ///Either \ref run(Node) "run()" or \ref init() should be called
   1.114      ///before using them.
   1.115  
   1.116      ///@{
   1.117  
   1.118 -    ///The shortest path to a node.
   1.119 +    ///The shortest path to the given node.
   1.120  
   1.121 -    ///Returns the shortest path to a node.
   1.122 +    ///Returns the shortest path to the given node from the root(s).
   1.123      ///
   1.124      ///\warning \c t should be reached from the root(s).
   1.125      ///
   1.126 @@ -816,9 +821,9 @@
   1.127      ///must be called before using this function.
   1.128      Path path(Node t) const { return Path(*G, *_pred, t); }
   1.129  
   1.130 -    ///The distance of a node from the root(s).
   1.131 +    ///The distance of the given node from the root(s).
   1.132  
   1.133 -    ///Returns the distance of a node from the root(s).
   1.134 +    ///Returns the distance of the given node from the root(s).
   1.135      ///
   1.136      ///\warning If node \c v is not reached from the root(s), then
   1.137      ///the return value of this function is undefined.
   1.138 @@ -827,29 +832,31 @@
   1.139      ///must be called before using this function.
   1.140      Value dist(Node v) const { return (*_dist)[v]; }
   1.141  
   1.142 -    ///Returns the 'previous arc' of the shortest path tree for a node.
   1.143 -
   1.144 +    ///\brief Returns the 'previous arc' of the shortest path tree for
   1.145 +    ///the given node.
   1.146 +    ///
   1.147      ///This function returns the 'previous arc' of the shortest path
   1.148      ///tree for the node \c v, i.e. it returns the last arc of a
   1.149      ///shortest path from a root to \c v. It is \c INVALID if \c v
   1.150      ///is not reached from the root(s) or if \c v is a root.
   1.151      ///
   1.152      ///The shortest path tree used here is equal to the shortest path
   1.153 -    ///tree used in \ref predNode().
   1.154 +    ///tree used in \ref predNode() and \ref predMap().
   1.155      ///
   1.156      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.157      ///must be called before using this function.
   1.158      Arc predArc(Node v) const { return (*_pred)[v]; }
   1.159  
   1.160 -    ///Returns the 'previous node' of the shortest path tree for a node.
   1.161 -
   1.162 +    ///\brief Returns the 'previous node' of the shortest path tree for
   1.163 +    ///the given node.
   1.164 +    ///
   1.165      ///This function returns the 'previous node' of the shortest path
   1.166      ///tree for the node \c v, i.e. it returns the last but one node
   1.167 -    ///from a shortest path from a root to \c v. It is \c INVALID
   1.168 +    ///of a shortest path from a root to \c v. It is \c INVALID
   1.169      ///if \c v is not reached from the root(s) or if \c v is a root.
   1.170      ///
   1.171      ///The shortest path tree used here is equal to the shortest path
   1.172 -    ///tree used in \ref predArc().
   1.173 +    ///tree used in \ref predArc() and \ref predMap().
   1.174      ///
   1.175      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.176      ///must be called before using this function.
   1.177 @@ -870,13 +877,13 @@
   1.178      ///predecessor arcs.
   1.179      ///
   1.180      ///Returns a const reference to the node map that stores the predecessor
   1.181 -    ///arcs, which form the shortest path tree.
   1.182 +    ///arcs, which form the shortest path tree (forest).
   1.183      ///
   1.184      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.185      ///must be called before using this function.
   1.186      const PredMap &predMap() const { return *_pred;}
   1.187  
   1.188 -    ///Checks if a node is reached from the root(s).
   1.189 +    ///Checks if the given node is reached from the root(s).
   1.190  
   1.191      ///Returns \c true if \c v is reached from the root(s).
   1.192      ///
   1.193 @@ -895,9 +902,9 @@
   1.194      bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
   1.195                                            Heap::POST_HEAP; }
   1.196  
   1.197 -    ///The current distance of a node from the root(s).
   1.198 +    ///The current distance of the given node from the root(s).
   1.199  
   1.200 -    ///Returns the current distance of a node from the root(s).
   1.201 +    ///Returns the current distance of the given node from the root(s).
   1.202      ///It may be decreased in the following processes.
   1.203      ///
   1.204      ///\pre Either \ref run(Node) "run()" or \ref init()
   1.205 @@ -924,9 +931,9 @@
   1.206      ///The type of the map that stores the arc lengths.
   1.207  
   1.208      ///The type of the map that stores the arc lengths.
   1.209 -    ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
   1.210 +    ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
   1.211      typedef LEN LengthMap;
   1.212 -    ///The type of the length of the arcs.
   1.213 +    ///The type of the arc lengths.
   1.214      typedef typename LEN::Value Value;
   1.215  
   1.216      /// Operation traits for Dijkstra algorithm.
   1.217 @@ -973,7 +980,7 @@
   1.218      ///
   1.219      ///The type of the map that stores the predecessor
   1.220      ///arcs of the shortest paths.
   1.221 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.222 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.223      typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   1.224      ///Instantiates a PredMap.
   1.225  
   1.226 @@ -988,7 +995,7 @@
   1.227      ///The type of the map that indicates which nodes are processed.
   1.228  
   1.229      ///The type of the map that indicates which nodes are processed.
   1.230 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.231 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.232      ///By default it is a NullMap.
   1.233      typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   1.234      ///Instantiates a ProcessedMap.
   1.235 @@ -1008,7 +1015,7 @@
   1.236      ///The type of the map that stores the distances of the nodes.
   1.237  
   1.238      ///The type of the map that stores the distances of the nodes.
   1.239 -    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.240 +    ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
   1.241      typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
   1.242      ///Instantiates a DistMap.
   1.243  
   1.244 @@ -1023,18 +1030,15 @@
   1.245      ///The type of the shortest paths.
   1.246  
   1.247      ///The type of the shortest paths.
   1.248 -    ///It must meet the \ref concepts::Path "Path" concept.
   1.249 +    ///It must conform to the \ref concepts::Path "Path" concept.
   1.250      typedef lemon::Path<Digraph> Path;
   1.251    };
   1.252  
   1.253    /// Default traits class used by DijkstraWizard
   1.254  
   1.255 -  /// To make it easier to use Dijkstra algorithm
   1.256 -  /// we have created a wizard class.
   1.257 -  /// This \ref DijkstraWizard class needs default traits,
   1.258 -  /// as well as the \ref Dijkstra class.
   1.259 -  /// The \ref DijkstraWizardBase is a class to be the default traits of the
   1.260 -  /// \ref DijkstraWizard class.
   1.261 +  /// Default traits class used by DijkstraWizard.
   1.262 +  /// \tparam GR The type of the digraph.
   1.263 +  /// \tparam LEN The type of the length map.
   1.264    template<typename GR, typename LEN>
   1.265    class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
   1.266    {
   1.267 @@ -1093,7 +1097,6 @@
   1.268    {
   1.269      typedef TR Base;
   1.270  
   1.271 -    ///The type of the digraph the algorithm runs on.
   1.272      typedef typename TR::Digraph Digraph;
   1.273  
   1.274      typedef typename Digraph::Node Node;
   1.275 @@ -1101,20 +1104,12 @@
   1.276      typedef typename Digraph::Arc Arc;
   1.277      typedef typename Digraph::OutArcIt OutArcIt;
   1.278  
   1.279 -    ///The type of the map that stores the arc lengths.
   1.280      typedef typename TR::LengthMap LengthMap;
   1.281 -    ///The type of the length of the arcs.
   1.282      typedef typename LengthMap::Value Value;
   1.283 -    ///\brief The type of the map that stores the predecessor
   1.284 -    ///arcs of the shortest paths.
   1.285      typedef typename TR::PredMap PredMap;
   1.286 -    ///The type of the map that stores the distances of the nodes.
   1.287      typedef typename TR::DistMap DistMap;
   1.288 -    ///The type of the map that indicates which nodes are processed.
   1.289      typedef typename TR::ProcessedMap ProcessedMap;
   1.290 -    ///The type of the shortest paths
   1.291      typedef typename TR::Path Path;
   1.292 -    ///The heap type used by the dijkstra algorithm.
   1.293      typedef typename TR::Heap Heap;
   1.294  
   1.295    public:
   1.296 @@ -1186,11 +1181,12 @@
   1.297        static PredMap *createPredMap(const Digraph &) { return 0; };
   1.298        SetPredMapBase(const TR &b) : TR(b) {}
   1.299      };
   1.300 -    ///\brief \ref named-func-param "Named parameter"
   1.301 -    ///for setting PredMap object.
   1.302 +
   1.303 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.304 +    ///the predecessor map.
   1.305      ///
   1.306 -    ///\ref named-func-param "Named parameter"
   1.307 -    ///for setting PredMap object.
   1.308 +    ///\ref named-templ-param "Named parameter" function for setting
   1.309 +    ///the map that stores the predecessor arcs of the nodes.
   1.310      template<class T>
   1.311      DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
   1.312      {
   1.313 @@ -1204,11 +1200,13 @@
   1.314        static DistMap *createDistMap(const Digraph &) { return 0; };
   1.315        SetDistMapBase(const TR &b) : TR(b) {}
   1.316      };
   1.317 -    ///\brief \ref named-func-param "Named parameter"
   1.318 -    ///for setting DistMap object.
   1.319 +
   1.320 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.321 +    ///the distance map.
   1.322      ///
   1.323 -    ///\ref named-func-param "Named parameter"
   1.324 -    ///for setting DistMap object.
   1.325 +    ///\ref named-templ-param "Named parameter" function for setting
   1.326 +    ///the map that stores the distances of the nodes calculated
   1.327 +    ///by the algorithm.
   1.328      template<class T>
   1.329      DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
   1.330      {
   1.331 @@ -1222,11 +1220,12 @@
   1.332        static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
   1.333        SetProcessedMapBase(const TR &b) : TR(b) {}
   1.334      };
   1.335 -    ///\brief \ref named-func-param "Named parameter"
   1.336 -    ///for setting ProcessedMap object.
   1.337 +
   1.338 +    ///\brief \ref named-func-param "Named parameter" for setting
   1.339 +    ///the processed map.
   1.340      ///
   1.341 -    /// \ref named-func-param "Named parameter"
   1.342 -    ///for setting ProcessedMap object.
   1.343 +    ///\ref named-templ-param "Named parameter" function for setting
   1.344 +    ///the map that indicates which nodes are processed.
   1.345      template<class T>
   1.346      DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
   1.347      {
   1.348 @@ -1239,6 +1238,7 @@
   1.349        typedef T Path;
   1.350        SetPathBase(const TR &b) : TR(b) {}
   1.351      };
   1.352 +
   1.353      ///\brief \ref named-func-param "Named parameter"
   1.354      ///for getting the shortest path to the target node.
   1.355      ///