Changeset 373:259ea2d741a2 in lemon-0.x for src/include/dijkstra.h

Timestamp:

04/22/04 16:50:24 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@503

Message:

Changes in the documentation.

File:

• src/include/dijkstra.h (modified) (12 diffs)

src/include/dijkstra.h

@@ -1 +1 @@
 // -*- C++ -*-
-
-/* 
- *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
- *
- *Constructor: 
- *
- *Dijkstra(Graph G, LengthMap length)
- *
- *
- *Methods:
- *
- *void run(Node s)
- *
- *T dist(Node v) : After run(s) was run, it returns the distance from s to v. 
- *   Returns T() if v is not reachable from s.
- *
- *Edge pred(Node v) : After run(s) was run, it returns the last 
- *   edge of a shortest s-v path. It is INVALID for s and for 
- *   the nodes not reachable from s.
- *
- *bool reached(Node v) : After run(s) was run, it is true iff v is 
- *   reachable from s
- *
- */
 
 #ifndef HUGO_DIJKSTRA_H
@@ -37 +13 @@
 namespace hugo {
   
-  //Alpar: Changed the order of the parameters
-  
   ///%Dijkstra algorithm class.
 
@@ -50 +24 @@
   ///It is also possible to change the underlying priority heap.
   ///
-  ///\param Graph The graph type the algorithm runs on.
-  ///\param LengthMap This read-only
-  ///EdgeMap
-  ///determines the
-  ///lengths of the edges. It is read once for each edge, so the map
-  ///may involve in relatively time consuming process to compute the edge
-  ///length if it is necessary. The default map type is
-  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
-  ///\param Heap The heap type used by the %Dijkstra
-  ///algorithm. The default
-  ///is using \ref BinHeap "binary heap".
+  ///\param Graph The graph type the algorithm runs on.  
+  ///\param LengthMap This read-only EdgeMap determines the lengths of
+  ///the edges. It is read once for each edge, so the map may involve
+  ///in relatively time consuming process to compute the edge length
+  ///if it is necessary. The default map type is \ref
+  ///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
+  ///\param Heap The heap type used by the %Dijkstra algorithm. The
+  ///default is using \ref BinHeap "binary heap".
   
 #ifdef DOXYGEN
@@ -104 +75 @@
     ///of this funcion is undefined.
     ValueType dist(Node v) const { return distance[v]; }
+
     ///Returns the edges of the shortest path tree.
 
@@ -111 +83 @@
     ///\pre \ref run() must be called before using this function.
     Edge pred(Node v) const { return predecessor[v]; }
+
     ///Returns the nodes of the shortest paths.
 
@@ -124 +97 @@
     ///
     const DistMap &distMap() const { return distance;}
+    
     ///Returns a reference to the shortest path tree map.
 
@@ -130 +104 @@
     ///\pre \ref run() must be called before using this function.
     const PredMap &predMap() const { return predecessor;}
+    
     ///Returns a reference to the map of nodes of  shortest paths.
 
@@ -143 +118 @@
     ///\todo Is this what we want?
     ///\pre \ref run() must be called before using this function.
-    ///
     bool reached(Node v) { return G.valid(predecessor[v]); }
     
@@ -153 +127 @@
   // **********************************************************************
 
-  ///Runs %Dijkstra algorithm from node the source.
+  ///Runs %Dijkstra algorithm from source node \c s.
 
   ///This method runs the %Dijkstra algorithm from a source node \c s
-  ///in order to
-  ///compute the
-  ///shortest path to each node. The algorithm computes
-  ///- The shortest path tree.
-  ///- The distance of each node from the source.
+  ///in order to compute the shortest path to each node. The algorithm
+  ///computes - The shortest path tree.  - The distance of each node
+  ///from the source.
   template <typename Graph, typename LengthMap,
             template<class,class,class> class Heap >
@@ -169 +141 @@
       predecessor.set(u,INVALID);
       pred_node.set(u,INVALID);
-      // If a node is unreacheable, then why should be the dist=0?
-      // distance.set(u,0);
-      //      reach.set(u,false);
     }
     
@@ -177 +146 @@
     
     Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
-    
     heap.push(s,0); 
     
-      while ( !heap.empty() ) {
+    while ( !heap.empty() ) {
+      
+      Node v=heap.top(); 
+      ValueType oldvalue=heap[v];
+      heap.pop();
+      distance.set(v, oldvalue);
         
-        Node v=heap.top(); 
-        ValueType oldvalue=heap[v];
-        heap.pop();
-        distance.set(v, oldvalue);
-        
-        { //FIXME this bracket is for e to be local
-          OutEdgeIt e;
-        for(G.first(e, v);
-            G.valid(e); G.next(e)) {
+      { //FIXME this bracket is for e to be local
+        OutEdgeIt e;
+        for(G.first(e, v); G.valid(e); G.next(e)) {
           Node w=G.head(e); 
           
@@ -210 +177 @@
           }
         }
-      } //FIXME tis bracket
-      }
+      } //FIXME this bracket
+    }
   }