alpar@255: // -*- C++ -*- alpar@255: #ifndef HUGO_DIJKSTRA_H alpar@255: #define HUGO_DIJKSTRA_H alpar@255: alpar@758: ///\ingroup flowalgs alpar@255: ///\file alpar@255: ///\brief Dijkstra algorithm. alpar@255: ladanyi@542: #include ladanyi@542: #include alpar@255: alpar@255: namespace hugo { jacint@385: alpar@758: /// \addtogroup flowalgs alpar@430: /// @{ alpar@430: alpar@255: ///%Dijkstra algorithm class. alpar@255: alpar@255: ///This class provides an efficient implementation of %Dijkstra algorithm. alpar@255: ///The edge lengths are passed to the algorithm using a alpar@880: ///\ref skeleton::ReadMap "ReadMap", alpar@255: ///so it is easy to change it to any kind of length. alpar@255: /// alpar@880: ///The type of the length is determined by the alpar@880: ///\ref skeleton::ReadMap::ValueType "ValueType" of the length map. alpar@255: /// alpar@255: ///It is also possible to change the underlying priority heap. alpar@255: /// alpar@584: ///\param GR The graph type the algorithm runs on. alpar@584: ///\param LM This read-only jacint@385: ///EdgeMap jacint@385: ///determines the jacint@385: ///lengths of the edges. It is read once for each edge, so the map jacint@385: ///may involve in relatively time consuming process to compute the edge jacint@385: ///length if it is necessary. The default map type is alpar@880: ///\ref skeleton::StaticGraph::EdgeMap "Graph::EdgeMap" jacint@385: ///\param Heap The heap type used by the %Dijkstra jacint@385: ///algorithm. The default jacint@385: ///is using \ref BinHeap "binary heap". alpar@456: /// alpar@689: ///\author Jacint Szabo and Alpar Juttner alpar@693: ///\todo We need a typedef-names should be standardized. (-: alpar@734: ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap alpar@734: ///should not be fixed. (Problematic to solve). alpar@584: alpar@255: #ifdef DOXYGEN alpar@584: template alpar@255: #else alpar@584: template , alpar@532: template class Heap = BinHeap > alpar@255: #endif alpar@255: class Dijkstra{ alpar@255: public: alpar@584: ///The type of the underlying graph. alpar@584: typedef GR Graph; alpar@802: ///. alpar@255: typedef typename Graph::Node Node; alpar@802: ///. alpar@255: typedef typename Graph::NodeIt NodeIt; alpar@802: ///. alpar@255: typedef typename Graph::Edge Edge; alpar@802: ///. alpar@255: typedef typename Graph::OutEdgeIt OutEdgeIt; alpar@255: alpar@584: ///The type of the length of the edges. alpar@584: typedef typename LM::ValueType ValueType; alpar@693: ///The type of the map that stores the edge lengths. alpar@584: typedef LM LengthMap; alpar@693: ///\brief The type of the map that stores the last alpar@584: ///edges of the shortest paths. marci@433: typedef typename Graph::template NodeMap PredMap; alpar@693: ///\brief The type of the map that stores the last but one alpar@584: ///nodes of the shortest paths. marci@433: typedef typename Graph::template NodeMap PredNodeMap; alpar@693: ///The type of the map that stores the dists of the nodes. marci@433: typedef typename Graph::template NodeMap DistMap; alpar@255: alpar@255: private: alpar@802: /// Pointer to the underlying graph. alpar@688: const Graph *G; alpar@802: /// Pointer to the length map alpar@688: const LM *length; alpar@802: ///Pointer to the map of predecessors edges. alpar@688: PredMap *predecessor; alpar@802: ///Indicates if \ref predecessor is locally allocated (\c true) or not. alpar@688: bool local_predecessor; alpar@802: ///Pointer to the map of predecessors nodes. alpar@688: PredNodeMap *pred_node; alpar@802: ///Indicates if \ref pred_node is locally allocated (\c true) or not. alpar@688: bool local_pred_node; alpar@802: ///Pointer to the map of distances. alpar@688: DistMap *distance; alpar@802: ///Indicates if \ref distance is locally allocated (\c true) or not. alpar@688: bool local_distance; alpar@688: alpar@802: ///The source node of the last execution. alpar@774: Node source; alpar@774: alpar@785: ///Initializes the maps. alpar@688: alpar@694: ///\todo Error if \c G or are \c NULL. What about \c length? alpar@688: ///\todo Better memory allocation (instead of new). alpar@688: void init_maps() alpar@688: { alpar@688: if(!predecessor) { alpar@688: local_predecessor = true; alpar@688: predecessor = new PredMap(*G); alpar@688: } alpar@688: if(!pred_node) { alpar@688: local_pred_node = true; alpar@688: pred_node = new PredNodeMap(*G); alpar@688: } alpar@688: if(!distance) { alpar@688: local_distance = true; alpar@688: distance = new DistMap(*G); alpar@688: } alpar@688: } alpar@255: alpar@255: public : alpar@802: ///Constructor. alpar@255: alpar@802: ///\param _G the graph the algorithm will run on. alpar@802: ///\param _length the length map used by the algorithm. alpar@584: Dijkstra(const Graph& _G, const LM& _length) : alpar@688: G(&_G), length(&_length), alpar@707: predecessor(NULL), local_predecessor(false), alpar@707: pred_node(NULL), local_pred_node(false), alpar@707: distance(NULL), local_distance(false) alpar@688: { } alpar@688: alpar@802: ///Destructor. alpar@688: ~Dijkstra() alpar@688: { alpar@688: if(local_predecessor) delete predecessor; alpar@688: if(local_pred_node) delete pred_node; alpar@688: if(local_distance) delete distance; alpar@688: } alpar@688: alpar@688: ///Sets the length map. alpar@688: alpar@688: ///Sets the length map. alpar@688: ///\return (*this) alpar@688: Dijkstra &setLengthMap(const LM &m) alpar@688: { alpar@688: length = &m; alpar@688: return *this; alpar@688: } alpar@688: alpar@688: ///Sets the map storing the predecessor edges. alpar@688: alpar@688: ///Sets the map storing the predecessor edges. alpar@688: ///If you don't use this function before calling \ref run(), alpar@688: ///it will allocate one. The destuctor deallocates this alpar@688: ///automatically allocated map, of course. alpar@688: ///\return (*this) alpar@688: Dijkstra &setPredMap(PredMap &m) alpar@688: { alpar@688: if(local_predecessor) { alpar@688: delete predecessor; alpar@688: local_predecessor=false; alpar@688: } alpar@688: predecessor = &m; alpar@688: return *this; alpar@688: } alpar@688: alpar@688: ///Sets the map storing the predecessor nodes. alpar@688: alpar@688: ///Sets the map storing the predecessor nodes. alpar@688: ///If you don't use this function before calling \ref run(), alpar@688: ///it will allocate one. The destuctor deallocates this alpar@688: ///automatically allocated map, of course. alpar@688: ///\return (*this) alpar@688: Dijkstra &setPredNodeMap(PredNodeMap &m) alpar@688: { alpar@688: if(local_pred_node) { alpar@688: delete pred_node; alpar@688: local_pred_node=false; alpar@688: } alpar@688: pred_node = &m; alpar@688: return *this; alpar@688: } alpar@688: alpar@688: ///Sets the map storing the distances calculated by the algorithm. alpar@688: alpar@688: ///Sets the map storing the distances calculated by the algorithm. alpar@688: ///If you don't use this function before calling \ref run(), alpar@688: ///it will allocate one. The destuctor deallocates this alpar@688: ///automatically allocated map, of course. alpar@688: ///\return (*this) alpar@688: Dijkstra &setDistMap(DistMap &m) alpar@688: { alpar@688: if(local_distance) { alpar@688: delete distance; alpar@688: local_distance=false; alpar@688: } alpar@688: distance = &m; alpar@688: return *this; alpar@688: } alpar@255: alpar@694: ///Runs %Dijkstra algorithm from node \c s. alpar@694: alpar@694: ///This method runs the %Dijkstra algorithm from a root node \c s alpar@694: ///in order to alpar@694: ///compute the alpar@694: ///shortest path to each node. The algorithm computes alpar@694: ///- The shortest path tree. alpar@694: ///- The distance of each node from the root. alpar@694: alpar@694: void run(Node s) { alpar@694: alpar@694: init_maps(); alpar@694: alpar@774: source = s; alpar@774: alpar@774: for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { alpar@694: predecessor->set(u,INVALID); alpar@694: pred_node->set(u,INVALID); alpar@694: } alpar@694: alpar@694: typename GR::template NodeMap heap_map(*G,-1); alpar@694: alpar@694: typedef Heap, alpar@694: std::less > alpar@694: HeapType; alpar@694: alpar@694: HeapType heap(heap_map); alpar@694: alpar@694: heap.push(s,0); alpar@694: alpar@694: while ( !heap.empty() ) { alpar@694: alpar@694: Node v=heap.top(); alpar@694: ValueType oldvalue=heap[v]; alpar@694: heap.pop(); alpar@694: distance->set(v, oldvalue); alpar@694: alpar@694: alpar@774: for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { alpar@774: Node w=G->head(e); alpar@694: switch(heap.state(w)) { alpar@694: case HeapType::PRE_HEAP: alpar@694: heap.push(w,oldvalue+(*length)[e]); alpar@694: predecessor->set(w,e); alpar@694: pred_node->set(w,v); alpar@694: break; alpar@694: case HeapType::IN_HEAP: alpar@694: if ( oldvalue+(*length)[e] < heap[w] ) { alpar@694: heap.decrease(w, oldvalue+(*length)[e]); alpar@694: predecessor->set(w,e); alpar@694: pred_node->set(w,v); alpar@694: } alpar@694: break; alpar@694: case HeapType::POST_HEAP: alpar@694: break; alpar@694: } alpar@694: } alpar@694: } alpar@694: } alpar@255: jacint@385: ///The distance of a node from the root. alpar@255: jacint@385: ///Returns the distance of a node from the root. alpar@255: ///\pre \ref run() must be called before using this function. jacint@385: ///\warning If node \c v in unreachable from the root the return value alpar@255: ///of this funcion is undefined. alpar@688: ValueType dist(Node v) const { return (*distance)[v]; } jacint@373: alpar@584: ///Returns the 'previous edge' of the shortest path tree. alpar@255: alpar@584: ///For a node \c v it returns the 'previous edge' of the shortest path tree, alpar@785: ///i.e. it returns the last edge of a shortest path from the root to \c alpar@688: ///v. It is \ref INVALID alpar@688: ///if \c v is unreachable from the root or if \c v=s. The jacint@385: ///shortest path tree used here is equal to the shortest path tree used in jacint@385: ///\ref predNode(Node v). \pre \ref run() must be called before using jacint@385: ///this function. alpar@780: ///\todo predEdge could be a better name. alpar@688: Edge pred(Node v) const { return (*predecessor)[v]; } jacint@373: alpar@584: ///Returns the 'previous node' of the shortest path tree. alpar@255: alpar@584: ///For a node \c v it returns the 'previous node' of the shortest path tree, jacint@385: ///i.e. it returns the last but one node from a shortest path from the jacint@385: ///root to \c /v. It is INVALID if \c v is unreachable from the root or if jacint@385: ///\c v=s. The shortest path tree used here is equal to the shortest path jacint@385: ///tree used in \ref pred(Node v). \pre \ref run() must be called before jacint@385: ///using this function. alpar@688: Node predNode(Node v) const { return (*pred_node)[v]; } alpar@255: alpar@255: ///Returns a reference to the NodeMap of distances. alpar@255: jacint@385: ///Returns a reference to the NodeMap of distances. \pre \ref run() must jacint@385: ///be called before using this function. alpar@688: const DistMap &distMap() const { return *distance;} jacint@385: alpar@255: ///Returns a reference to the shortest path tree map. alpar@255: alpar@255: ///Returns a reference to the NodeMap of the edges of the alpar@255: ///shortest path tree. alpar@255: ///\pre \ref run() must be called before using this function. alpar@688: const PredMap &predMap() const { return *predecessor;} jacint@385: jacint@385: ///Returns a reference to the map of nodes of shortest paths. alpar@255: alpar@255: ///Returns a reference to the NodeMap of the last but one nodes of the jacint@385: ///shortest path tree. alpar@255: ///\pre \ref run() must be called before using this function. alpar@688: const PredNodeMap &predNodeMap() const { return *pred_node;} alpar@255: jacint@385: ///Checks if a node is reachable from the root. alpar@255: jacint@385: ///Returns \c true if \c v is reachable from the root. alpar@802: ///\note The root node is reported to be reached! alpar@255: ///\pre \ref run() must be called before using this function. jacint@385: /// alpar@780: bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; } alpar@255: alpar@255: }; alpar@255: alpar@430: /// @} alpar@255: alpar@255: } //END OF NAMESPACE HUGO alpar@255: alpar@255: #endif alpar@255: alpar@255: