lemon-0.x: comparison src/hugo/dijkstra.h

equal deleted inserted replaced

-:9cd8c9cef167
+:17373302ad14
 DistMap *distance;
 bool local_distance;
 ///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()
 {
 //       if(!length) {
 // 	local_length = true;
 }
 distance = &m;
 return *this;
 }
-void run(Node s);
+///Runs %Dijkstra algorithm from node \c 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.
 ///This method runs the %Dijkstra algorithm from a root 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 root.
-template <typename GR, typename LM,
-	    template<class,class,class,class> class Heap >
+void run(Node s) {
-void Dijkstra<GR,LM,Heap>::run(Node s) {
+init_maps();
-init_maps();
+for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
-for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
+	predecessor->set(u,INVALID);
-predecessor->set(u,INVALID);
+	pred_node->set(u,INVALID);
-pred_node->set(u,INVALID);
+}
-}
+typename GR::template NodeMap<int> heap_map(*G,-1);
-typename GR::template NodeMap<int> heap_map(*G,-1);
+typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
-typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
 std::less<ValueType> >
 HeapType;
 HeapType heap(heap_map);
 heap.push(s,0);
 while ( !heap.empty() ) {
 	Node v=heap.top();
 	ValueType oldvalue=heap[v];
 	heap.pop();
 	distance->set(v, oldvalue);
 	for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
 	  Node w=G->bNode(e);
 	  switch(heap.state(w)) {
 	  case HeapType::PRE_HEAP:
 	  case HeapType::POST_HEAP:
 	    break;
 	  }
 	}
 }
 }
+///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
+// **********************************************************************
 /// @}
 } //END OF NAMESPACE HUGO

changeset 696	48aa9ace1d7d
parent 693	80164e89dcbc
child 707	ec034cfade65