Changeset 694:2d87cefb35b2 in lemon-0.x

Timestamp:

07/06/04 12:07:48 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

I moved run() into the body of class Dijkstra, because Doxygen handles
external member function definitions very poorly.

File:

• src/hugo/dijkstra.h (modified) (5 diffs)

src/hugo/dijkstra.h

@@ -85 +85 @@
     ///Initialize maps
     
-    ///\todo Error if \c G or are \c NULL. What about \c length
+    ///\todo Error if \c G or are \c NULL. What about \c length?
     ///\todo Better memory allocation (instead of new).
     void init_maps() 
@@ -197 +197 @@
     }
     
-    void run(Node s);
-    
-    ///The distance of a node from the root.
-
-    ///Returns the distance of a node from the root.
-    ///\pre \ref run() must be called before using this function.
-    ///\warning If node \c v in unreachable from the root the return value
-    ///of this funcion is undefined.
-    ValueType dist(Node v) const { return (*distance)[v]; }
-
-    ///Returns the 'previous edge' of the shortest path tree.
-
-    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
-    ///i.e. it returns the last edge from a shortest path from the root to \c
-    ///v. It is \ref INVALID
-    ///if \c v is unreachable from the root or if \c v=s. The
-    ///shortest path tree used here is equal to the shortest path tree used in
-    ///\ref predNode(Node v).  \pre \ref run() must be called before using
-    ///this function.
-    Edge pred(Node v) const { return (*predecessor)[v]; }
-
-    ///Returns the 'previous node' of the shortest path tree.
-
-    ///For a node \c v it returns the 'previous node' of the shortest path tree,
-    ///i.e. it returns the last but one node from a shortest path from the
-    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
-    ///\c v=s. The shortest path tree used here is equal to the shortest path
-    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
-    ///using this function.
-    Node predNode(Node v) const { return (*pred_node)[v]; }
-    
-    ///Returns a reference to the NodeMap of distances.
-
-    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
-    ///be called before using this function.
-    const DistMap &distMap() const { return *distance;}
- 
-    ///Returns a reference to the shortest path tree map.
-
-    ///Returns a reference to the NodeMap of the edges of the
-    ///shortest path tree.
-    ///\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.
-
-    ///Returns a reference to the NodeMap of the last but one nodes of the
-    ///shortest path tree.
-    ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return *pred_node;}
-
-    ///Checks if a node is reachable from the root.
-
-    ///Returns \c true if \c v is reachable from the root.
-    ///\warning the root node is reported to be unreached!
-    ///\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]); }
-    
-  };
-  
-
-  // **********************************************************************
-  //  IMPLEMENTATIONS
-  // **********************************************************************
-
-  ///Runs %Dijkstra algorithm from node the root.
+  ///Runs %Dijkstra algorithm from node \c s.
 
   ///This method runs the %Dijkstra algorithm from a root node \c s
@@ -272 +205 @@
   ///- The shortest path tree.
   ///- The distance of each node from the root.
-  template <typename GR, typename LM,
-            template<class,class,class,class> class Heap >
-  void Dijkstra<GR,LM,Heap>::run(Node s) {
-
-    init_maps();
-
-    for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
-      predecessor->set(u,INVALID);
-      pred_node->set(u,INVALID);
-    }
-    
-    typename GR::template NodeMap<int> heap_map(*G,-1);
-    
-    typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
+    
+    void run(Node s) {
+      
+      init_maps();
+      
+      for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
+        predecessor->set(u,INVALID);
+        pred_node->set(u,INVALID);
+      }
+      
+      typename GR::template NodeMap<int> heap_map(*G,-1);
+      
+      typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
       std::less<ValueType> > 
       HeapType;
-    
-    HeapType heap(heap_map);
-    
-    heap.push(s,0); 
-    
+      
+      HeapType heap(heap_map);
+      
+      heap.push(s,0); 
+      
       while ( !heap.empty() ) {
         
@@ -300 +232 @@
         distance->set(v, oldvalue);
         
-          
+        
         for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
           Node w=G->bNode(e); 
@@ -322 +254 @@
         }
       }
-  }
+    }
+    
+    ///The distance of a node from the root.
+
+    ///Returns the distance of a node from the root.
+    ///\pre \ref run() must be called before using this function.
+    ///\warning If node \c v in unreachable from the root the return value
+    ///of this funcion is undefined.
+    ValueType dist(Node v) const { return (*distance)[v]; }
+
+    ///Returns the 'previous edge' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous edge' of the shortest path tree,
+    ///i.e. it returns the last edge from a shortest path from the root to \c
+    ///v. It is \ref INVALID
+    ///if \c v is unreachable from the root or if \c v=s. The
+    ///shortest path tree used here is equal to the shortest path tree used in
+    ///\ref predNode(Node v).  \pre \ref run() must be called before using
+    ///this function.
+    Edge pred(Node v) const { return (*predecessor)[v]; }
+
+    ///Returns the 'previous node' of the shortest path tree.
+
+    ///For a node \c v it returns the 'previous node' of the shortest path tree,
+    ///i.e. it returns the last but one node from a shortest path from the
+    ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
+    ///\c v=s. The shortest path tree used here is equal to the shortest path
+    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
+    ///using this function.
+    Node predNode(Node v) const { return (*pred_node)[v]; }
+    
+    ///Returns a reference to the NodeMap of distances.
+
+    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
+    ///be called before using this function.
+    const DistMap &distMap() const { return *distance;}
+ 
+    ///Returns a reference to the shortest path tree map.
+
+    ///Returns a reference to the NodeMap of the edges of the
+    ///shortest path tree.
+    ///\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.
+
+    ///Returns a reference to the NodeMap of the last but one nodes of the
+    ///shortest path tree.
+    ///\pre \ref run() must be called before using this function.
+    const PredNodeMap &predNodeMap() const { return *pred_node;}
+
+    ///Checks if a node is reachable from the root.
+
+    ///Returns \c true if \c v is reachable from the root.
+    ///\warning the root node is reported to be unreached!
+    ///\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]); }
+    
+  };
+  
+
+  // **********************************************************************
+  //  IMPLEMENTATIONS
+  // **********************************************************************
 
 /// @}