lemon-1.1: comparison lemon/dijkstra.h

equal deleted inserted replaced

-:90e56769e5c9
+:0a499103dbaa
 ///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 default type is \ref ListDigraph.
-///The value of GR is not used directly by \ref Dijkstra, it is only
+///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
-///passed to \ref DijkstraDefaultTraits.
+///the lengths of the arcs.
-///\tparam LM A readable arc map that determines the lengths of the
+///It is read once for each arc, so the map may involve in
-///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>".
+///concepts::Digraph::ArcMap "GR::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>
 #else
 template <typename GR=ListDigraph,
 typename LM=typename GR::template ArcMap<int>,
 ///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;
 ///\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;
 };
 ///\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;
 };
 ///\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;
 };
 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;
 };
 {
 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
+///reference types with automatic allocation.
-///object if the cross reference's constructor waits for the digraph as
+///They should have standard constructor interfaces to be able to
-///parameter and the heap's constructor waits for the cross reference.
+///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;
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dijkstra &predMap(PredMap &m)
 {
 if(local_pred) {
 delete _pred;
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dijkstra &processedMap(ProcessedMap &m)
 {
 if(local_processed) {
 delete _processed;
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dijkstra &distMap(DistMap &m)
 {
 if(local_dist) {
 delete _dist;
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), heap and cross reference instances will be
-///automatically allocated heap and cross reference, of course.
+///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;
 _dist->set(v, dst);
 }
 public:
-///\name Execution control
+///\name Execution Control
-///The simplest way to execute the algorithm is to use one of the
+///The simplest way to execute the %Dijkstra algorithm is to use
-///member functions called \ref lemon::Dijkstra::run() "run()".
+///one of the member functions called \ref run(Node) "run()".\n
-///\n
+///If you need more control on the execution, first you have to call
-///If you need more control on the execution, first you must call
+///\ref init(), then you can add several source nodes with
-///\ref lemon::Dijkstra::init() "init()", then you can add several
+///\ref addSource(). Finally the actual path computation can be
-///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
+///performed with one of the \ref start() functions.
-///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()
 {
 create_maps();
 _heap->clear();
 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
 Node nextNode() const
 {
 return !_heap->empty()?_heap->top():INVALID;
 }
-///\brief Returns \c false if there are nodes
+///Returns \c false if there are nodes to be processed.
-///to be processed.
-///
+///Returns \c false if there are nodes to be processed
-///Returns \c false if there are nodes
+///in the priority heap.
-///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.
 }
 ///@}
 ///\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
+///Either \ref run(Node) "run()" or \ref start() should be called
-///\ref lemon::Dijkstra::start() "start()" must be called before
+///before using them.
-///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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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
+///shortest path from a 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.
+///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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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
+///from a shortest path from a 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.
+///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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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).
+///Returns \c true if \c v is reached from the root(s).
-///\pre Either \ref run() or \ref start()
+///
+///\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];
 }
 /// 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
+/// It does not have own \ref run(Node) "run()" method, it uses the
-/// and features of the plain \ref Dijkstra.
+/// 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
 ///  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> >

changeset 422	62c1ed05e83f
parent 397	62f9787c516c
parent 405	6b9057cdcd8b
child 440	88ed40ad0d4f