Changeset 287:bb40b6db0a58 in lemon for lemon/dijkstra.h

Timestamp:

09/27/08 14:33:28 (16 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

288:47b3a3b67837, 290:f6899946c1ac

Parents:

286:da414906fe21 (diff), 285:d8dc5acf739b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Phase:

public

Message:

Merge

Files:

• lemon/dijkstra.h (modified) (6 diffs)
• lemon/dijkstra.h (modified) (7 diffs)

lemon/dijkstra.h

@@ -725 +725 @@
     }
 
-    ///Executes the algorithm until the given target node is reached.
-
-    ///Executes the algorithm until the given target node is reached.
+    ///Executes the algorithm until the given target node is processed.
+
+    ///Executes the algorithm until the given target node is processed.
     ///
     ///This method runs the %Dijkstra algorithm from the root node(s)
-    ///in order to compute the shortest path to \c dest.
+    ///in order to compute the shortest path to \c t.
     ///
     ///The algorithm computes
-    ///- the shortest path to \c dest,
-    ///- the distance of \c dest from the root(s).
+    ///- the shortest path to \c t,
+    ///- the distance of \c t from the root(s).
     ///
     ///\pre init() must be called and at least one root node should be
     ///added with addSource() before using this function.
-    void start(Node dest)
-    {
-      while ( !_heap->empty() && _heap->top()!=dest ) processNextNode();
-      if ( !_heap->empty() ) finalizeNodeData(_heap->top(),_heap->prio());
+    void start(Node t)
+    {
+      while ( !_heap->empty() && _heap->top()!=t ) processNextNode();
+      if ( !_heap->empty() ) {
+        finalizeNodeData(_heap->top(),_heap->prio());
+        _heap->pop();
+      }
     }
 
@@ -769 +772 @@
     }
 
-    ///Runs the algorithm from the given node.
+    ///Runs the algorithm from the given source node.
 
     ///This method runs the %Dijkstra algorithm from node \c s
@@ -793 +796 @@
 
     ///This method runs the %Dijkstra algorithm from node \c s
-    ///in order to compute the shortest path to \c t.
-    ///
-    ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
-    ///if \c t is reachable form \c s, \c 0 otherwise.
+    ///in order to compute the shortest path to node \c t
+    ///(it stops searching when \c t is processed).
+    ///
+    ///\return \c true if \c t is reachable form \c s.
     ///
     ///\note Apart from the return value, <tt>d.run(s,t)</tt> is just a
@@ -805 +808 @@
     ///  d.start(t);
     ///\endcode
-    Value run(Node s,Node t) {
+    bool run(Node s,Node t) {
       init();
       addSource(s);
       start(t);
-      return (*_pred)[t]==INVALID?OperationTraits::zero():(*_dist)[t];
+      return (*_heap_cross_ref)[t] == Heap::POST_HEAP;
     }
 
@@ -905 +908 @@
     ///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 start()
+    ///\pre Either \ref run() or \ref init()
     ///must be called before using this function.
     bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
@@ -914 +917 @@
     ///Returns the current distance of a node from the root(s).
     ///It may be decreased in the following processes.
-    ///\pre \c v should be reached but not processed.
-    Value currentDist(Node v) const { return (*_heap)[v]; }
+    ///\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.
+    Value currentDist(Node v) const {
+      return processed(v) ? (*_dist)[v] : (*_heap)[v];
+    }
 
     ///@}

lemon/dijkstra.h

@@ -145 +145 @@
     ///\param g is the digraph, to which we would like to define the
     ///\ref PredMap.
-    ///\todo The digraph alone may be insufficient for the initialization
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -156 +155 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
-    ///\todo If it is set to a real map,
-    ///Dijkstra::processed() should read this.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \ref ProcessedMap.
@@ -298 +295 @@
     bool local_heap;
 
-    ///Creates the maps if necessary.
-    ///\todo Better memory allocation (instead of new).
+    //Creates the maps if necessary.
     void create_maps()
     {
@@ -966 +962 @@
     /// \param g is the digraph, to which we would like to define the
     /// HeapCrossRef.
-    /// \todo The digraph alone may be insufficient for the initialization
     static HeapCrossRef *createHeapCrossRef(const Digraph &g)
     {
@@ -1002 +997 @@
     ///\param g is the digraph, to which we would like to define the
     ///\ref PredMap.
-    ///\todo The digraph alone may be insufficient to initialize
     static PredMap *createPredMap(const Digraph &g)
     {
@@ -1013 +1007 @@
     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
     ///By default it is a NullMap.
-    ///\todo If it is set to a real map,
-    ///Dijkstra::processed() should read this.
-    ///\todo named parameter to set this type, function to read and write.
     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
     ///Instantiates a \ref ProcessedMap.
@@ -1061 +1052 @@
   /// The \ref DijkstraWizardBase is a class to be the default traits of the
   /// \ref DijkstraWizard class.
-  /// \todo More named parameters are required...
   template<class GR,class LM>
   class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>