diff -r d8863141824d -r fb261e3a9a0f src/include/dijkstra.h --- a/src/include/dijkstra.h Thu May 06 09:26:23 2004 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,208 +0,0 @@ -// -*- 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 - -