diff -r 47ef467ccf70 -r 425731cb66de src/lemon/dijkstra.h --- a/src/lemon/dijkstra.h Sun Feb 06 20:00:56 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,344 +0,0 @@ -/* -*- 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 - -namespace lemon { - -/// \addtogroup flowalgs -/// @{ - - ///%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. - ///\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" - ///\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. (-: - ///\todo Type of \c PredMap, \c PredNodeMap and \c DistMap - ///should not be fixed. (Problematic to solve). - -#ifdef DOXYGEN - template -#else - template , - template class Heap = BinHeap > -#endif - class Dijkstra{ - public: - ///The type of the underlying graph. - typedef GR 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 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: - /// Pointer to the underlying graph. - const Graph *G; - /// Pointer to the length map - const LM *length; - ///Pointer to the map of predecessors edges. - PredMap *predecessor; - ///Indicates if \ref predecessor is locally allocated (\c true) or not. - bool local_predecessor; - ///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; - - ///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(!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 : - ///Constructor. - - ///\param _G the graph the algorithm will run on. - ///\param _length the length map used by the algorithm. - Dijkstra(const Graph& _G, const LM& _length) : - G(&_G), length(&_length), - predecessor(NULL), local_predecessor(false), - pred_node(NULL), local_pred_node(false), - distance(NULL), local_distance(false) - { } - - ///Destructor. - ~Dijkstra() - { - if(local_predecessor) delete predecessor; - if(local_pred_node) delete pred_node; - if(local_distance) delete distance; - } - - ///Sets the length map. - - ///Sets the length map. - ///\return (*this) - Dijkstra &setLengthMap(const LM &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 &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(); - - source = s; - - for ( NodeIt u(*G) ; u!=INVALID ; ++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); e!=INVALID; ++e) { - Node w=G->target(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 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 (*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. - ///\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 || (*predecessor)[v]!=INVALID; } - - }; - -/// @} - -} //END OF NAMESPACE LEMON - -#endif - -