/* -*- C++ -*- * src/lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library * * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Combinatorial Optimization Research Group, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_DIJKSTRA_H #define LEMON_DIJKSTRA_H ///\ingroup flowalgs ///\file ///\brief Dijkstra algorithm. #include #include #include #include #include namespace lemon { class UninitializedData : public LogicError {}; /// \addtogroup flowalgs /// @{ ///Default traits class of Dijkstra class. ///Default traits class of Dijkstra class. ///\param GR Graph type. ///\param LM Type of length map. template struct DijkstraDefaultTraits { ///The graph type the algorithm runs on. typedef GR Graph; ///The type of the map that stores the edge lengths. ///It must meet the \ref concept::ReadMap "ReadMap" concept. /// typedef LM LengthMap; //The type of the length of the edges. typedef typename LM::Value Value; ///The heap type used by Dijkstra algorithm. ///The heap type used by Dijkstra algorithm. /// ///\sa BinHeap ///\sa Dijkstra typedef BinHeap, std::less > Heap; ///\brief The type of the map that stores the last ///edges of the shortest paths. /// ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// typedef typename Graph::template NodeMap PredMap; ///Instantiates a PredMap. ///\todo Please document... ///\todo The graph alone may be insufficient for the initialization static PredMap *createPredMap(const GR &G) { return new PredMap(G); } ///\brief The type of the map that stores the last but one ///nodes of the shortest paths. /// ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// typedef typename Graph::template NodeMap PredNodeMap; ///Instantiates a PredNodeMap. ///\todo Please document... /// static PredNodeMap *createPredNodeMap(const GR &G) { return new PredNodeMap(G); } ///The type of the map that stores whether a nodes is reached. ///It must meet the \ref concept::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///\todo If it is set to a real map, Dijkstra::reached() should read this. ///\todo named parameter to set this type, function to read and write. typedef NullMap ReachedMap; ///Instantiates a ReachedMap. ///\todo Please document... /// static ReachedMap *createReachedMap(const GR &G) { return new ReachedMap(); } ///The type of the map that stores the dists of the nodes. ///It must meet the \ref concept::WriteMap "WriteMap" concept. /// typedef typename Graph::template NodeMap DistMap; ///Instantiates a DistMap. ///\todo Please document... /// static DistMap *createDistMap(const GR &G) { return new DistMap(G); } }; ///%Dijkstra algorithm class. ///This class provides an efficient implementation of %Dijkstra algorithm. ///The edge lengths are passed to the algorithm using a ///\ref concept::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. /// ///The type of the length is determined by the ///\ref concept::ReadMap::Value "Value" of the length map. /// ///It is also possible to change the underlying priority heap. /// ///\param GR The graph type the algorithm runs on. The default value is ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it ///is only passed to \ref DijkstraDefaultTraits. ///\param LM 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 concept::StaticGraph::EdgeMap "Graph::EdgeMap". ///The value of LM is not used directly by Dijkstra, it ///is only passed to \ref DijkstraDefaultTraits. ///\param TR Traits class to set various data types used by the algorithm. ///The default traits class is ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits". ///See \ref DijkstraDefaultTraits for the documentation of ///a Dijkstra traits class. /// ///\author Jacint Szabo and Alpar Juttner ///\todo We need a typedef-names should be standardized. (-: #ifdef DOXYGEN template #else template , typename TR=DijkstraDefaultTraits > #endif class Dijkstra { public: ///Exception thrown by dijkstra. class UninitializedData : public lemon::UninitializedData {}; typedef TR Traits; ///The type of the underlying graph. typedef typename TR::Graph Graph; ///\e typedef typename Graph::Node Node; ///\e typedef typename Graph::NodeIt NodeIt; ///\e typedef typename Graph::Edge Edge; ///\e typedef typename Graph::OutEdgeIt OutEdgeIt; ///The type of the length of the edges. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the edge lengths. typedef typename TR::LengthMap LengthMap; ///\brief The type of the map that stores the last ///edges of the shortest paths. typedef typename TR::PredMap PredMap; ///\brief The type of the map that stores the last but one ///nodes of the shortest paths. typedef typename TR::PredNodeMap PredNodeMap; ///The type of the map indicating if a node is reached. typedef typename TR::ReachedMap ReachedMap; ///The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; private: /// Pointer to the underlying graph. const Graph *G; /// Pointer to the length map const LengthMap *length; ///Pointer to the map of predecessors edges. PredMap *_pred; ///Indicates if \ref _pred is locally allocated (\c true) or not. bool local_pred; ///Pointer to the map of predecessors nodes. PredNodeMap *pred_node; ///Indicates if \ref pred_node is locally allocated (\c true) or not. bool local_pred_node; ///Pointer to the map of distances. DistMap *distance; ///Indicates if \ref distance is locally allocated (\c true) or not. bool local_distance; ///Pointer to the map of reached status of the nodes. ReachedMap *_reached; ///Indicates if \ref _reached is locally allocated (\c true) or not. bool local_reached; ///The source node of the last execution. Node source; ///Initializes the maps. ///\todo Error if \c G or are \c NULL. What about \c length? ///\todo Better memory allocation (instead of new). void init_maps() { if(!_pred) { local_pred = true; _pred = Traits::createPredMap(*G); } if(!pred_node) { local_pred_node = true; pred_node = Traits::createPredNodeMap(*G); } if(!distance) { local_distance = true; distance = Traits::createDistMap(*G); } if(!_reached) { local_reached = true; _reached = Traits::createReachedMap(*G); } } public : template struct DefPredMapTraits : public Traits { typedef T PredMap; ///\todo An exception should be thrown. /// static PredMap *createPredMap(const Graph &G) { throw UninitializedData(); } }; ///\ref named-templ-param "Named parameter" for setting PredMap type ///\ref named-templ-param "Named parameter" for setting PredMap type /// template class DefPredMap : public Dijkstra< Graph, LengthMap, DefPredMapTraits > { }; template struct DefPredNodeMapTraits : public Traits { typedef T PredNodeMap; ///\todo An exception should be thrown. /// static PredNodeMap *createPredNodeMap(const Graph &G) { throw UninitializedData(); } }; ///\ref named-templ-param "Named parameter" for setting PredNodeMap type ///\ref named-templ-param "Named parameter" for setting PredNodeMap type /// template class DefPredNodeMap : public Dijkstra< Graph, LengthMap, DefPredNodeMapTraits > { }; template struct DefDistMapTraits : public Traits { typedef T DistMap; ///\todo An exception should be thrown. /// static DistMap *createDistMap(const Graph &G) { throw UninitializedData(); } }; ///\ref named-templ-param "Named parameter" for setting DistMap type ///\ref named-templ-param "Named parameter" for setting DistMap type /// template class DefDistMap : public Dijkstra< Graph, LengthMap, DefDistMapTraits > { }; ///Constructor. ///\param _G the graph the algorithm will run on. ///\param _length the length map used by the algorithm. Dijkstra(const Graph& _G, const LengthMap& _length) : G(&_G), length(&_length), _pred(NULL), local_pred(false), pred_node(NULL), local_pred_node(false), distance(NULL), local_distance(false), _reached(NULL), local_reached(false) { } ///Destructor. ~Dijkstra() { if(local_pred) delete _pred; if(local_pred_node) delete pred_node; if(local_distance) delete distance; if(local_reached) delete _reached; } ///Sets the length map. ///Sets the length map. ///\return (*this) Dijkstra &lengthMap(const LengthMap &m) { length = &m; return *this; } ///Sets the map storing the predecessor edges. ///Sets the map storing the predecessor edges. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) Dijkstra &predMap(PredMap &m) { if(local_pred) { delete _pred; local_pred=false; } _pred = &m; return *this; } ///Sets the map storing the predecessor nodes. ///Sets the map storing the predecessor nodes. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) Dijkstra &predNodeMap(PredNodeMap &m) { if(local_pred_node) { delete pred_node; local_pred_node=false; } pred_node = &m; return *this; } ///Sets the map storing the distances calculated by the algorithm. ///Sets the map storing the distances calculated by the algorithm. ///If you don't use this function before calling \ref run(), ///it will allocate one. The destuctor deallocates this ///automatically allocated map, of course. ///\return (*this) Dijkstra &distMap(DistMap &m) { if(local_distance) { delete distance; local_distance=false; } distance = &m; return *this; } ///Runs %Dijkstra algorithm from node \c s. ///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. ///\todo heap_map's type could also be in the traits class. void run(Node s) { init_maps(); source = s; for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { _pred->set(u,INVALID); pred_node->set(u,INVALID); ///\todo *_reached is not set to false. } typename Graph::template NodeMap heap_map(*G,-1); Heap heap(heap_map); heap.push(s,0); while ( !heap.empty() ) { Node v=heap.top(); _reached->set(v,true); Value oldvalue=heap[v]; heap.pop(); distance->set(v, oldvalue); for(OutEdgeIt e(*G,v); e!=INVALID; ++e) { Node w=G->target(e); switch(heap.state(w)) { case Heap::PRE_HEAP: heap.push(w,oldvalue+(*length)[e]); _pred->set(w,e); pred_node->set(w,v); break; case Heap::IN_HEAP: if ( oldvalue+(*length)[e] < heap[w] ) { heap.decrease(w, oldvalue+(*length)[e]); _pred->set(w,e); pred_node->set(w,v); } break; case Heap::POST_HEAP: break; } } } } ///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. Value 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 of a shortest path from the root to \c ///v. It is \ref 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. ///\todo predEdge could be a better name. Edge pred(Node v) const { return (*_pred)[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 *_pred;} ///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. ///\note The root node is reported to be reached! ///\pre \ref run() must be called before using this function. /// bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; } }; template class DijkstraWizardBase : public DijkstraDefaultTraits { typedef DijkstraDefaultTraits Base; protected: /// Pointer to the underlying graph. void *_g; /// Pointer to the length map void *_length; ///Pointer to the map of predecessors edges. void *_pred; ///Pointer to the map of predecessors nodes. void *_predNode; ///Pointer to the map of distances. void *_dist; ///Pointer to the source node. void *_source; typedef typename Base::Graph::Node Node; public: DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0), _dist(0), _source(INVALID) {} DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0), _dist(0), _source((void *)&s) {} }; ///\e ///\e /// template class DijkstraWizard : public TR { typedef TR Base; //The type of the underlying graph. typedef typename TR::Graph Graph; //\e typedef typename Graph::Node Node; //\e typedef typename Graph::NodeIt NodeIt; //\e typedef typename Graph::Edge Edge; //\e typedef typename Graph::OutEdgeIt OutEdgeIt; //The type of the map that stores the edge lengths. typedef typename TR::LengthMap LengthMap; //The type of the length of the edges. typedef typename LengthMap::Value Value; //\brief The type of the map that stores the last //edges of the shortest paths. typedef typename TR::PredMap PredMap; //\brief The type of the map that stores the last but one //nodes of the shortest paths. typedef typename TR::PredNodeMap PredNodeMap; //The type of the map that stores the dists of the nodes. typedef typename TR::DistMap DistMap; //The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; public: DijkstraWizard() : TR() {} DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) : TR(g,l,s) {} DijkstraWizard(const TR &b) : TR(b) {} ~DijkstraWizard() {} ///\e void run() { if(_source==0) throw UninitializedData(); Dijkstra Dij(*(Graph*)_g,*(LengthMap*)_length); if(_pred) Dij.predMap(*(PredMap*)_pred); if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode); if(_dist) Dij.distMap(*(DistMap*)_dist); Dij.run(*(Node*)_source); } ///\e void run(Node s) { _source=(void *)&s; run(); } template struct DefPredMapBase : public Base { typedef T PredMap; static PredMap *createPredMap(const Graph &G) { return 0; }; DefPredMapBase(const Base &b) : Base(b) {} }; ///\e template DijkstraWizard > predMap(const T &t) { _pred=(void *)&t; return DijkstraWizard >(*this); } template struct DefPredNodeMapBase : public Base { typedef T PredNodeMap; static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; }; DefPredNodeMapBase(const Base &b) : Base(b) {} }; ///\e template DijkstraWizard > predNodeMap(const T &t) { _predNode=(void *)&t; return DijkstraWizard >(*this); } template struct DefDistMapBase : public Base { typedef T DistMap; static DistMap *createDistMap(const Graph &G) { return 0; }; DefDistMapBase(const Base &b) : Base(b) {} }; ///\e template DijkstraWizard > distMap(const T &t) { _dist=(void *)&t; return DijkstraWizard >(*this); } ///\e DijkstraWizard &source(Node s) { source=(void *)&s; return *this; } }; ///\e ///\todo Please document... /// template DijkstraWizard > dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) { return DijkstraWizard >(g,l,s); } /// @} } //END OF NAMESPACE LEMON #endif