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

equal deleted inserted replaced

-:32abaed18079
+:e646d4053290
 // -*- 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
 #define HUGO_DIJKSTRA_H
 ///\file
 #include <bin_heap.h>
 #include <invalid.h>
 namespace hugo {
-//Alpar: Changed the order of the parameters
 ///%Dijkstra algorithm class.
 ///This class provides an efficient implementation of %Dijkstra algorithm.
 ///The edge lengths are passed to the algorithm using a
 ///\ref ReadMapSkeleton "readable map",
 ///
 ///The type of the length is determined by the \c ValueType of the length map.
 ///
 ///It is also possible to change the underlying priority heap.
 ///
 ///\param Graph The graph type the algorithm runs on.
-///\param LengthMap This read-only
+///\param LengthMap This read-only EdgeMap determines the lengths of
-///EdgeMap
+///the edges. It is read once for each edge, so the map may involve
-///determines the
+///in relatively time consuming process to compute the edge length
-///lengths of the edges. It is read once for each edge, so the map
+///if it is necessary. The default map type is \ref
-///may involve in relatively time consuming process to compute the edge
+///GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
-///length if it is necessary. The default map type is
+///\param Heap The heap type used by the %Dijkstra algorithm. The
-///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
+///default is using \ref BinHeap "binary heap".
-///\param Heap The heap type used by the %Dijkstra
-///algorithm. The default
-///is using \ref BinHeap "binary heap".
 #ifdef DOXYGEN
 template <typename Graph,
 	    typename LengthMap,
 	    typename Heap>
 ///Returns the distance of a node from the source.
 ///\pre \ref run() must be called before using this function.
 ///\warning If node \c v in unreachable from the source the return value
 ///of this funcion is undefined.
 ValueType dist(Node v) const { return distance[v]; }
 ///Returns the edges of the shortest path tree.
 ///For a node \c v it returns the last edge of the shortest path
 ///from the source to \c v or INVALID if \c v is unreachable
 ///from the source.
 ///\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.
 ///For a node \c v it returns the last but one node of the shortest path
 ///from the source to \c v or INVALID if \c v is unreachable
 ///from the source.
 ///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 paths.
 ///\pre \ref run() must be called before using this function.
 ///Returns \c true if \c v is reachable from the source.
 ///\warning the source 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 source.
+///Runs %Dijkstra algorithm from source node \c s.
 ///This method runs the %Dijkstra algorithm from a source node \c s
-///in order to
+///in order to compute the shortest path to each node. The algorithm
-///compute the
+///computes - The shortest path tree.  - The distance of each node
-///shortest path to each node. The algorithm computes
+///from the source.
-///- The shortest path tree.
-///- The distance of each node from the source.
 template <typename Graph, typename LengthMap,
 	    template<class,class,class> class Heap >
 void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
 NodeIt u;
 for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
 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);
 }
 typename Graph::NodeMap<int> heap_map(G,-1);
 Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
 heap.push(s,0);
 while ( !heap.empty() ) {
+Node v=heap.top();
+ValueType oldvalue=heap[v];
+heap.pop();
+distance.set(v, oldvalue);
-	Node v=heap.top();
+{ //FIXME this bracket is for e to be local
-	ValueType oldvalue=heap[v];
+	OutEdgeIt e;
-	heap.pop();
+	for(G.first(e, v); G.valid(e); G.next(e)) {
-	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)) {
 	  Node w=G.head(e);
 	  switch(heap.state(w)) {
 	  case heap.PRE_HEAP:
 	    heap.push(w,oldvalue+length[e]);
 	    break;
 	  case heap.POST_HEAP:
 	    break;
 	  }
 	}
-} //FIXME tis bracket
+} //FIXME this bracket
 }
 }
 } //END OF NAMESPACE HUGO
 #endif

changeset 376	5c12f3515452
parent 335	999eb3cd7b49
child 385	d7ebbae96025