diff -r ee5959aa4410 -r c280de819a73 src/work/deba/dijkstra.h --- a/src/work/deba/dijkstra.h Sun Apr 17 18:57:22 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,329 +0,0 @@ -// -*- C++ -*- -#ifndef LEMON_DIJKSTRA_H -#define LEMON_DIJKSTRA_H - -///\ingroup galgs -///\file -///\brief Dijkstra algorithm. - -#include -#include - -namespace lemon { - -/// \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 ReadMap "readable map", - ///so it is easy to change it to any kind of length. - /// - ///The type of the length is determined by the \c Value of the length map. - /// - ///It is also possible to change the underlying priority heap. - /// - ///\param GR The graph type the algorithm runs on. - ///\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 Graph::EdgeMap "Graph::EdgeMap" - ///\param Heap The heap type used by the %Dijkstra - ///algorithm. The default - ///is using \ref BinHeap "binary heap". - /// - ///\author Jacint Szabo and Alpar Juttner - ///\todo We need a typedef-names should be standardized. (-: - -#ifdef DOXYGEN - template -#else - template , - template class Heap = BinHeap > -#endif - class Dijkstra{ - public: - ///The type of the underlying graph. - typedef GR Graph; - typedef typename Graph::Node Node; - typedef typename Graph::NodeIt NodeIt; - typedef typename Graph::Edge Edge; - typedef typename Graph::OutEdgeIt OutEdgeIt; - - ///The type of the length of the edges. - typedef typename LM::Value Value; - ///The type of the map that stores the edge lengths. - typedef LM LengthMap; - ///\brief The type of the map that stores the last - ///edges of the shortest paths. - typedef typename Graph::template NodeMap PredMap; - ///\brief The type of the map that stores the last but one - ///nodes of the shortest paths. - typedef typename Graph::template NodeMap PredNodeMap; - ///The type of the map that stores the dists of the nodes. - typedef typename Graph::template NodeMap DistMap; - - private: - const Graph *G; - const LM *length; - // bool local_length; - PredMap *predecessor; - bool local_predecessor; - PredNodeMap *pred_node; - bool local_pred_node; - DistMap *distance; - bool local_distance; - - ///Initialize 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(!length) { -// local_length = true; -// length = new LM(G); -// } - if(!predecessor) { - local_predecessor = true; - predecessor = new PredMap(*G); - } - if(!pred_node) { - local_pred_node = true; - pred_node = new PredNodeMap(*G); - } - if(!distance) { - local_distance = true; - distance = new DistMap(*G); - } - } - - public : - - Dijkstra(const Graph& _G, const LM& _length) : - G(&_G), length(&_length), - predecessor(NULL), pred_node(NULL), distance(NULL), - local_predecessor(false), local_pred_node(false), local_distance(false) - { } - - ~Dijkstra() - { - // if(local_length) delete length; - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///Sets the graph the algorithm will run on. - - ///Sets the graph the algorithm will run on. - ///\return (*this) - Dijkstra &setGraph(const Graph &_G) - { - G = &_G; - return *this; - } - ///Sets the length map. - - ///Sets the length map. - ///\return (*this) - Dijkstra &setLengthMap(const LM &m) - { -// if(local_length) { -// delete length; -// local_length=false; -// } - 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 &setPredMap(PredMap &m) - { - if(local_predecessor) { - delete predecessor; - local_predecessor=false; - } - predecessor = &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 &setPredNodeMap(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 &setDistMap(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. - - void run(Node s) { - - init_maps(); - - for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) { - predecessor->set(u,INVALID); - pred_node->set(u,INVALID); - } - - typename GR::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(); - Value oldvalue=heap[v]; - heap.pop(); - distance->set(v, oldvalue); - - - for(OutEdgeIt e(*G,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; - } - } - } - } - - ///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 from 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. - 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 - // ********************************************************************** - -/// @} - -} //END OF NAMESPACE LEMON - -#endif - -