diff -r d8863141824d -r fb261e3a9a0f src/hugo/dijkstra.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/dijkstra.h Thu May 06 13:21:24 2004 +0000 @@ -0,0 +1,208 @@ +// -*- C++ -*- +#ifndef HUGO_DIJKSTRA_H +#define HUGO_DIJKSTRA_H + +///\ingroup galgs +///\file +///\brief Dijkstra algorithm. + +#include +#include + +namespace hugo { + +/// \addtogroup galgs +/// @{ + + ///%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", + ///so it is easy to change it to any kind of length. + /// + ///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 + ///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" + ///\param Heap The heap type used by the %Dijkstra + ///algorithm. The default + ///is using \ref BinHeap "binary heap". + /// + ///\author Jacint Szabo +#ifdef DOXYGEN + template +#else + template , + template class Heap = BinHeap > +#endif + class Dijkstra{ + public: + typedef typename Graph::Node Node; + typedef typename Graph::NodeIt NodeIt; + typedef typename Graph::Edge Edge; + typedef typename Graph::OutEdgeIt OutEdgeIt; + + typedef typename LengthMap::ValueType ValueType; + typedef typename Graph::template NodeMap PredMap; + typedef typename Graph::template NodeMap PredNodeMap; + typedef typename Graph::template NodeMap DistMap; + + private: + const Graph& G; + const LengthMap& length; + PredMap predecessor; + PredNodeMap pred_node; + DistMap distance; + + public : + + Dijkstra(const Graph& _G, const LengthMap& _length) : + G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { } + + 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 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 class Heap > + void Dijkstra::run(Node s) { + + NodeIt u; + for ( G.first(u) ; G.valid(u) ; G.next(u) ) { + predecessor.set(u,INVALID); + pred_node.set(u,INVALID); + } + + typename Graph::template NodeMap heap_map(G,-1); + + typedef Heap, + std::less > + 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); + + { //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.bNode(e); + + switch(heap.state(w)) { + case HeapType::PRE_HEAP: + heap.push(w,oldvalue+length[e]); + predecessor.set(w,e); + pred_node.set(w,v); + break; + case HeapType::IN_HEAP: + if ( oldvalue+length[e] < heap[w] ) { + heap.decrease(w, oldvalue+length[e]); + predecessor.set(w,e); + pred_node.set(w,v); + } + break; + case HeapType::POST_HEAP: + break; + } + } + } //FIXME tis bracket + } + } + +/// @} + +} //END OF NAMESPACE HUGO + +#endif + +