alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@906: * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@906: * (Egervary Combinatorial Optimization Research Group, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_DIJKSTRA_H alpar@921: #define LEMON_DIJKSTRA_H alpar@255: alpar@758: ///\ingroup flowalgs alpar@255: ///\file alpar@255: ///\brief Dijkstra algorithm. alpar@255: alpar@953: #include alpar@921: #include alpar@921: #include alpar@255: alpar@921: namespace lemon { jacint@385: alpar@758: /// \addtogroup flowalgs alpar@430: /// @{ alpar@430: alpar@954: ///Default traits class of Dijkstra class. alpar@954: alpar@954: ///Default traits class of Dijkstra class. alpar@954: ///\param GR Graph type. alpar@954: ///\param LM Type of length map. alpar@953: template alpar@953: struct DijkstraDefaultTraits alpar@953: { alpar@954: ///The graph type the algorithm runs on. alpar@953: typedef GR Graph; alpar@953: ///The type of the map that stores the edge lengths. alpar@953: alpar@967: ///It must meet the \ref concept::ReadMap "ReadMap" concept. alpar@953: /// alpar@953: typedef LM LengthMap; alpar@954: //The type of the length of the edges. alpar@987: typedef typename LM::Value Value; alpar@954: ///The heap type used by Dijkstra algorithm. alpar@967: alpar@967: ///The heap type used by Dijkstra algorithm. alpar@967: /// alpar@967: ///\sa BinHeap alpar@967: ///\sa Dijkstra alpar@953: typedef BinHeap, alpar@987: std::less > Heap; alpar@953: alpar@953: ///\brief The type of the map that stores the last alpar@953: ///edges of the shortest paths. alpar@953: /// alpar@967: ///It must meet the \ref concept::WriteMap "WriteMap" concept. alpar@953: /// alpar@954: typedef typename Graph::template NodeMap PredMap; alpar@954: ///Instantiates a PredMap. alpar@953: alpar@953: ///\todo Please document... alpar@953: /// alpar@954: static PredMap *createPredMap(const GR &G) alpar@953: { alpar@953: return new PredMap(G); alpar@953: } alpar@953: ///\brief The type of the map that stores the last but one alpar@953: ///nodes of the shortest paths. alpar@953: /// alpar@967: ///It must meet the \ref concept::WriteMap "WriteMap" concept. alpar@953: /// alpar@954: typedef typename Graph::template NodeMap PredNodeMap; alpar@954: ///Instantiates a PredNodeMap. alpar@953: alpar@953: ///\todo Please document... alpar@967: /// alpar@954: static PredNodeMap *createPredNodeMap(const GR &G) alpar@953: { alpar@953: return new PredNodeMap(G); alpar@953: } alpar@953: ///The type of the map that stores the dists of the nodes. alpar@953: alpar@967: ///It must meet the \ref concept::WriteMap "WriteMap" concept. alpar@953: /// alpar@987: typedef typename Graph::template NodeMap DistMap; alpar@954: ///Instantiates a DistMap. alpar@953: alpar@953: ///\todo Please document... alpar@953: /// alpar@954: static DistMap *createDistMap(const GR &G) alpar@953: { alpar@953: return new DistMap(G); alpar@953: } alpar@953: }; alpar@953: 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 klao@959: ///\ref concept::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@987: ///\ref concept::ReadMap::Value "Value" of the length map. alpar@255: /// alpar@255: ///It is also possible to change the underlying priority heap. alpar@255: /// alpar@953: ///\param GR The graph type the algorithm runs on. The default value is alpar@955: ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it alpar@954: ///is only passed to \ref DijkstraDefaultTraits. 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 klao@959: ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap". alpar@955: ///The value of LM is not used directly by Dijkstra, it alpar@954: ///is only passed to \ref DijkstraDefaultTraits. alpar@954: ///\param TR Traits class to set various data types used by the algorithm. alpar@954: ///The default traits class is alpar@955: ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits". alpar@954: ///See \ref DijkstraDefaultTraits for the documentation of alpar@954: ///a Dijkstra traits class. alpar@456: /// alpar@689: ///\author Jacint Szabo and Alpar Juttner alpar@693: ///\todo We need a typedef-names should be standardized. (-: alpar@584: alpar@255: #ifdef DOXYGEN alpar@584: template alpar@255: #else alpar@953: template , alpar@953: typename TR=DijkstraDefaultTraits > alpar@255: #endif alpar@255: class Dijkstra{ alpar@255: public: alpar@953: typedef TR Traits; alpar@584: ///The type of the underlying graph. alpar@954: typedef typename TR::Graph Graph; alpar@911: ///\e alpar@255: typedef typename Graph::Node Node; alpar@911: ///\e alpar@255: typedef typename Graph::NodeIt NodeIt; alpar@911: ///\e alpar@255: typedef typename Graph::Edge Edge; alpar@911: ///\e alpar@255: typedef typename Graph::OutEdgeIt OutEdgeIt; alpar@255: alpar@584: ///The type of the length of the edges. alpar@987: typedef typename TR::LengthMap::Value Value; alpar@693: ///The type of the map that stores the edge lengths. alpar@954: typedef typename TR::LengthMap LengthMap; alpar@693: ///\brief The type of the map that stores the last alpar@584: ///edges of the shortest paths. alpar@953: typedef typename TR::PredMap PredMap; alpar@693: ///\brief The type of the map that stores the last but one alpar@584: ///nodes of the shortest paths. alpar@953: typedef typename TR::PredNodeMap PredNodeMap; alpar@693: ///The type of the map that stores the dists of the nodes. alpar@953: typedef typename TR::DistMap DistMap; alpar@953: ///The heap type used by the dijkstra algorithm. alpar@953: typedef typename TR::Heap Heap; alpar@255: private: alpar@802: /// Pointer to the underlying graph. alpar@688: const Graph *G; alpar@802: /// Pointer to the length map alpar@954: const LengthMap *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@953: predecessor = Traits::createPredMap(*G); alpar@688: } alpar@688: if(!pred_node) { alpar@688: local_pred_node = true; alpar@953: pred_node = Traits::createPredNodeMap(*G); alpar@688: } alpar@688: if(!distance) { alpar@688: local_distance = true; alpar@953: distance = Traits::createDistMap(*G); alpar@688: } alpar@688: } alpar@255: alpar@255: public : alpar@953: alpar@953: template alpar@953: struct SetPredMapTraits : public Traits { alpar@953: typedef T PredMap; alpar@953: ///\todo An exception should be thrown. alpar@953: /// alpar@953: static PredMap *createPredMap(const Graph &G) alpar@953: { alpar@953: std::cerr << __FILE__ ":" << __LINE__ << alpar@953: ": error: Special maps should be manually created" << std::endl; alpar@953: exit(1); alpar@953: } alpar@953: }; alpar@954: ///\ref named-templ-param "Named parameter" for setting PredMap type alpar@954: alpar@967: ///\relates Dijkstra alpar@954: ///\ingroup flowalgs alpar@954: ///\ref named-templ-param "Named parameter" for setting PredMap type alpar@953: template alpar@953: class SetPredMap : public Dijkstra< Graph, alpar@953: LengthMap, alpar@953: SetPredMapTraits > { }; alpar@953: alpar@953: template alpar@953: struct SetPredNodeMapTraits : public Traits { alpar@953: typedef T PredNodeMap; alpar@953: ///\todo An exception should be thrown. alpar@953: /// alpar@953: static PredNodeMap *createPredNodeMap(const Graph &G) alpar@953: { alpar@953: std::cerr << __FILE__ ":" << __LINE__ << alpar@953: ": error: Special maps should be manually created" << std::endl; alpar@953: exit(1); alpar@953: } alpar@953: }; alpar@954: ///\ref named-templ-param "Named parameter" for setting PredNodeMap type alpar@954: alpar@954: ///\ingroup flowalgs alpar@954: ///\ref named-templ-param "Named parameter" for setting PredNodeMap type alpar@953: template alpar@953: class SetPredNodeMap : public Dijkstra< Graph, alpar@953: LengthMap, alpar@953: SetPredNodeMapTraits > { }; alpar@953: alpar@953: template alpar@953: struct SetDistMapTraits : public Traits { alpar@953: typedef T DistMap; alpar@953: ///\todo An exception should be thrown. alpar@953: /// alpar@953: static DistMap *createDistMap(const Graph &G) alpar@953: { alpar@953: std::cerr << __FILE__ ":" << __LINE__ << alpar@953: ": error: Special maps should be manually created" << std::endl; alpar@953: exit(1); alpar@953: } alpar@953: }; alpar@954: ///\ref named-templ-param "Named parameter" for setting DistMap type alpar@954: alpar@954: ///\ingroup flowalgs alpar@954: ///\ref named-templ-param "Named parameter" for setting DistMap type alpar@953: template alpar@953: class SetDistMap : public Dijkstra< Graph, alpar@953: LengthMap, alpar@953: SetDistMapTraits > { }; alpar@953: 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@954: Dijkstra(const Graph& _G, const LengthMap& _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@954: Dijkstra &setLengthMap(const LengthMap &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@954: ///\todo heap_map's type could also be in the traits class. 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@954: typename Graph::template NodeMap heap_map(*G,-1); alpar@694: alpar@953: Heap 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@987: Value 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@986: Node w=G->target(e); alpar@694: switch(heap.state(w)) { alpar@953: case Heap::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@953: case Heap::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@953: case Heap::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@987: Value 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@953: alpar@953: ///\e alpar@953: alpar@953: ///\e alpar@953: /// alpar@953: template alpar@953: class _Dijkstra alpar@953: { alpar@953: typedef TR Traits; alpar@953: alpar@953: ///The type of the underlying graph. alpar@953: typedef typename TR::Graph Graph; alpar@953: ///\e alpar@953: typedef typename Graph::Node Node; alpar@953: ///\e alpar@953: typedef typename Graph::NodeIt NodeIt; alpar@953: ///\e alpar@953: typedef typename Graph::Edge Edge; alpar@953: ///\e alpar@953: typedef typename Graph::OutEdgeIt OutEdgeIt; alpar@953: alpar@953: ///The type of the map that stores the edge lengths. alpar@953: typedef typename TR::LengthMap LengthMap; alpar@953: ///The type of the length of the edges. alpar@987: typedef typename LengthMap::Value Value; alpar@953: ///\brief The type of the map that stores the last alpar@953: ///edges of the shortest paths. alpar@953: typedef typename TR::PredMap PredMap; alpar@953: ///\brief The type of the map that stores the last but one alpar@953: ///nodes of the shortest paths. alpar@953: typedef typename TR::PredNodeMap PredNodeMap; alpar@953: ///The type of the map that stores the dists of the nodes. alpar@953: typedef typename TR::DistMap DistMap; alpar@953: alpar@953: ///The heap type used by the dijkstra algorithm. alpar@953: typedef typename TR::Heap Heap; alpar@953: alpar@953: /// Pointer to the underlying graph. alpar@953: const Graph *G; alpar@953: /// Pointer to the length map alpar@953: const LengthMap *length; alpar@953: ///Pointer to the map of predecessors edges. alpar@953: PredMap *predecessor; alpar@953: ///Pointer to the map of predecessors nodes. alpar@953: PredNodeMap *pred_node; alpar@953: ///Pointer to the map of distances. alpar@953: DistMap *distance; alpar@953: alpar@953: Node source; alpar@953: alpar@953: public: alpar@953: _Dijkstra() : G(0), length(0), predecessor(0), pred_node(0), alpar@953: distance(0), source(INVALID) {} alpar@953: alpar@953: _Dijkstra(const Graph &g,const LengthMap &l, Node s) : alpar@953: G(&g), length(&l), predecessor(0), pred_node(0), alpar@953: distance(0), source(s) {} alpar@953: alpar@953: ~_Dijkstra() alpar@953: { alpar@953: Dijkstra Dij(*G,*length); alpar@953: if(predecessor) Dij.setPredMap(*predecessor); alpar@953: if(pred_node) Dij.setPredNodeMap(*pred_node); alpar@953: if(distance) Dij.setDistMap(*distance); alpar@953: Dij.run(source); alpar@953: } alpar@953: alpar@953: template alpar@953: struct SetPredMapTraits : public Traits {typedef T PredMap;}; alpar@953: alpar@953: ///\e alpar@953: template alpar@953: _Dijkstra > setPredMap(const T &t) alpar@953: { alpar@953: _Dijkstra > r; alpar@953: r.G=G; alpar@953: r.length=length; alpar@953: r.predecessor=&t; alpar@953: r.pred_node=pred_node; alpar@953: r.distance=distance; alpar@953: r.source=source; alpar@953: return r; alpar@953: } alpar@953: alpar@953: template alpar@953: struct SetPredNodeMapTraits :public Traits {typedef T PredNodeMap;}; alpar@953: ///\e alpar@953: template alpar@953: _Dijkstra > setPredNodeMap(const T &t) alpar@953: { alpar@953: _Dijkstra > r; alpar@953: r.G=G; alpar@953: r.length=length; alpar@953: r.predecessor=predecessor; alpar@953: r.pred_node=&t; alpar@953: r.distance=distance; alpar@953: r.source=source; alpar@953: return r; alpar@953: } alpar@953: alpar@953: template alpar@953: struct SetDistMapTraits : public Traits {typedef T DistMap;}; alpar@953: ///\e alpar@953: template alpar@953: _Dijkstra > setDistMap(const T &t) alpar@953: { alpar@953: _Dijkstra > r; alpar@953: r.G=G; alpar@953: r.length=length; alpar@953: r.predecessor=predecessor; alpar@953: r.pred_node=pred_node; alpar@953: r.distance=&t; alpar@953: r.source=source; alpar@953: return r; alpar@953: } alpar@953: alpar@953: ///\e alpar@953: _Dijkstra &setSource(Node s) alpar@953: { alpar@953: source=s; alpar@953: return *this; alpar@953: } alpar@953: alpar@953: }; alpar@255: alpar@953: ///\e alpar@953: alpar@954: ///\todo Please document... alpar@953: /// alpar@953: template alpar@953: _Dijkstra > alpar@953: dijkstra(const GR &g,const LM &l,typename GR::Node s) alpar@953: { alpar@953: return _Dijkstra >(g,l,s); alpar@953: } alpar@953: alpar@430: /// @} alpar@255: alpar@921: } //END OF NAMESPACE LEMON alpar@255: alpar@255: #endif alpar@255: alpar@255: