Changes in lemon/dijkstra.h [440:88ed40ad0d4f:397:62f9787c516c] in lemon-main

File:

• lemon/dijkstra.h (modified) (25 diffs)

lemon/dijkstra.h

@@ -3 +3 @@
  * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2009
+ * Copyright (C) 2003-2008
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -180 +180 @@
   ///
   ///\tparam GR The type of the digraph the algorithm runs on.
-  ///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
+  ///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
   ///relatively time consuming process to compute the arc lengths if
   ///it is necessary. The default map type is \ref
-  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
+  ///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.
 #ifdef DOXYGEN
   template <typename GR, typename LM, typename TR>
@@ -220 +227 @@
     typedef typename TR::OperationTraits OperationTraits;
 
-    ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
+    ///The traits class.
     typedef TR Traits;
 
@@ -302 +309 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///PredMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetPredMap
@@ -323 +329 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///DistMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetDistMap
@@ -344 +349 @@
     ///\ref named-templ-param "Named parameter" for setting
     ///ProcessedMap type.
-    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     template <class T>
     struct SetProcessedMap
@@ -385 +389 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///heap and cross reference types
+    ///heap and cross reference type
     ///
     ///\ref named-templ-param "Named parameter" for setting heap and cross
-    ///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
+    ///reference type.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetHeap
@@ -412 +412 @@
     };
     ///\brief \ref named-templ-param "Named parameter" for setting
-    ///heap and cross reference types with automatic allocation
+    ///heap and cross reference type with automatic allocation
     ///
     ///\ref named-templ-param "Named parameter" for setting heap and cross
-    ///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
+    ///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.
     template <class H, class CR = typename Digraph::template NodeMap<int> >
     struct SetStandardHeap
@@ -493 +487 @@
 
     ///Sets the map that stores the predecessor arcs.
-    ///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.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Dijkstra &predMap(PredMap &m)
@@ -511 +504 @@
 
     ///Sets the map that indicates which nodes are processed.
-    ///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.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Dijkstra &processedMap(ProcessedMap &m)
@@ -530 +522 @@
     ///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(Node) "run()"
-    ///or \ref init(), an instance will be allocated automatically.
-    ///The destructor deallocates this automatically allocated map,
-    ///of course.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destructor deallocates this
+    ///automatically allocated map, of course.
     ///\return <tt> (*this) </tt>
     Dijkstra &distMap(DistMap &m)
@@ -548 +539 @@
 
     ///Sets the heap and the cross reference used by algorithm.
-    ///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.
+    ///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.
     ///\return <tt> (*this) </tt>
     Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
@@ -579 +568 @@
   public:
 
-    ///\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.
+    ///\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.
 
     ///@{
 
-    ///\brief Initializes the internal data structures.
-    ///
     ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
     void init()
     {
@@ -667 +659 @@
     }
 
-    ///Returns \c false if there are nodes to be processed.
-
-    ///Returns \c false if there are nodes to be processed
-    ///in the priority heap.
+    ///\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.
     bool emptyQueue() const { return _heap->empty(); }
 
-    ///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
+
+    ///Returns the number of the nodes to be processed in the priority heap.
+    ///
     int queueSize() const { return _heap->size(); }
 
@@ -797 +790 @@
 
     ///\name Query Functions
-    ///The results of the %Dijkstra algorithm can be obtained using these
+    ///The result of the %Dijkstra algorithm can be obtained using these
     ///functions.\n
-    ///Either \ref run(Node) "run()" or \ref start() should be called
-    ///before using them.
+    ///Either \ref lemon::Dijkstra::run() "run()" or
+    ///\ref lemon::Dijkstra::start() "start()" must be called before
+    ///using them.
 
     ///@{
@@ -808 +802 @@
     ///Returns the shortest path to a node.
     ///
-    ///\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.
+    ///\warning \c t should be reachable from the root(s).
+    ///
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Path path(Node t) const { return Path(*G, *_pred, t); }
 
@@ -818 +812 @@
     ///Returns the distance of a node from the root(s).
     ///
-    ///\warning If node \c v is not reached from the root(s), then
+    ///\warning If node \c v is not reachable 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.
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Value dist(Node v) const { return (*_dist)[v]; }
 
@@ -829 +823 @@
     ///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.
+    ///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.
     ///
     ///The shortest path tree used here is equal to the shortest path
     ///tree used in \ref predNode().
     ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
-    ///must be called before using this function.
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Arc predArc(Node v) const { return (*_pred)[v]; }
 
@@ -843 +837 @@
     ///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
-    ///if \c v is not reached from the root(s) or if \c v is a root.
+    ///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.
     ///
     ///The shortest path tree used here is equal to the shortest path
     ///tree used in \ref predArc().
     ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
-    ///must be called before using this function.
+    ///\pre Either \ref run() or \ref start() must be called before
+    ///using this function.
     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
                                   G->source((*_pred)[v]); }
@@ -860 +854 @@
     ///of the nodes calculated by the algorithm.
     ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///\pre Either \ref run() or \ref init()
     ///must be called before using this function.
     const DistMap &distMap() const { return *_dist;}
@@ -870 +864 @@
     ///arcs, which form the shortest path tree.
     ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///\pre Either \ref 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).
-
-    ///Returns \c true if \c v is reached from the root(s).
-    ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///Checks if a node is reachable from the root(s).
+
+    ///Returns \c true if \c v is reachable from the root(s).
+    ///\pre Either \ref run() or \ref start()
     ///must be called before using this function.
     bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
@@ -887 +880 @@
     ///Returns \c true if \c v is processed, i.e. the shortest
     ///path to \c v has already found.
-    ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///\pre Either \ref run() or \ref init()
     ///must be called before using this function.
     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
@@ -897 +889 @@
     ///Returns the current distance of a node from the root(s).
     ///It may be decreased in the following processes.
-    ///
-    ///\pre Either \ref run(Node) "run()" or \ref init()
+    ///\pre Either \ref run() or \ref init()
     ///must be called before using this function and
     ///node \c v must be reached but not necessarily processed.
@@ -1081 +1072 @@
   /// This auxiliary class is created to implement the
   /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
-  /// It does not have own \ref run(Node) "run()" method, it uses the
-  /// functions and features of the plain \ref Dijkstra.
+  /// It does not have own \ref run() method, it uses the functions
+  /// and features of the plain \ref Dijkstra.
   ///
   /// This class should only be used through the \ref dijkstra() function,
@@ -1277 +1268 @@
   ///  bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
   ///\endcode
-  ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
+  ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
   ///to the end of the parameter list.
   ///\sa DijkstraWizard