diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -38,8 +38,10 @@ /// /// This operation traits class defines all computational operations and /// constants which are used in the Dijkstra algorithm. - template + template struct DijkstraDefaultOperationTraits { + /// \e + typedef V Value; /// \brief Gives back the zero value of the type. static Value zero() { return static_cast(0); @@ -58,8 +60,8 @@ ///Default traits class of Dijkstra class. ///\tparam GR The type of the digraph. - ///\tparam LM The type of the length map. - template + ///\tparam LEN The type of the length map. + template struct DijkstraDefaultTraits { ///The type of the digraph the algorithm runs on. @@ -68,12 +70,12 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef LM LengthMap; - ///The type of the length of the arcs. - typedef typename LM::Value Value; + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef LEN LengthMap; + ///The type of the arc lengths. + typedef typename LEN::Value Value; - /// Operation traits for Dijkstra algorithm. + /// Operation traits for %Dijkstra algorithm. /// This class defines the operations that are used in the algorithm. /// \see DijkstraDefaultOperationTraits @@ -84,7 +86,7 @@ /// The cross reference type used by the heap. /// Usually it is \c Digraph::NodeMap. typedef typename Digraph::template NodeMap HeapCrossRef; - ///Instantiates a \ref HeapCrossRef. + ///Instantiates a \c HeapCrossRef. ///This function instantiates a \ref HeapCrossRef. /// \param g is the digraph, to which we would like to define the @@ -94,14 +96,14 @@ return new HeapCrossRef(g); } - ///The heap type used by the Dijkstra algorithm. + ///The heap type used by the %Dijkstra algorithm. ///The heap type used by the Dijkstra algorithm. /// ///\sa BinHeap ///\sa Dijkstra - typedef BinHeap > Heap; - ///Instantiates a \ref Heap. + typedef BinHeap > Heap; + ///Instantiates a \c Heap. ///This function instantiates a \ref Heap. static Heap *createHeap(HeapCrossRef& r) @@ -114,13 +116,13 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; - ///Instantiates a PredMap. + ///Instantiates a \c PredMap. - ///This function instantiates a PredMap. + ///This function instantiates a \ref PredMap. ///\param g is the digraph, to which we would like to define the - ///PredMap. + ///\ref PredMap. static PredMap *createPredMap(const Digraph &g) { return new PredMap(g); @@ -129,14 +131,14 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \c ProcessedMap. - ///This function instantiates a ProcessedMap. + ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the ProcessedMap + ///we would like to define the \ref ProcessedMap. #ifdef DOXYGEN static ProcessedMap *createProcessedMap(const Digraph &g) #else @@ -149,13 +151,13 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a DistMap. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename Digraph::template NodeMap DistMap; + ///Instantiates a \c DistMap. - ///This function instantiates a DistMap. + ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define - ///the DistMap + ///the \ref DistMap. static DistMap *createDistMap(const Digraph &g) { return new DistMap(g); @@ -167,6 +169,10 @@ /// \ingroup shortest_path ///This class provides an efficient implementation of the %Dijkstra algorithm. /// + ///The %Dijkstra algorithm solves the single-source shortest path problem + ///when all arc lengths are non-negative. If there are negative lengths, + ///the BellmanFord algorithm should be used instead. + /// ///The arc lengths are passed to the algorithm using a ///\ref concepts::ReadMap "ReadMap", ///so it is easy to change it to any kind of length. @@ -179,26 +185,19 @@ ///it can be used easier. /// ///\tparam GR The type of the digraph the algorithm runs on. - ///The default value is \ref ListDigraph. - ///The value of GR is not used directly by \ref Dijkstra, it is only - ///passed to \ref DijkstraDefaultTraits. - ///\tparam LM A readable arc map that determines the lengths of the - ///arcs. It is read once for each arc, so the map may involve in + ///The default type is \ref ListDigraph. + ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies + ///the lengths of the arcs. + ///It is read once for each arc, so the map may involve in ///relatively time consuming process to compute the arc lengths if ///it is necessary. The default map type is \ref - ///concepts::Digraph::ArcMap "Digraph::ArcMap". - ///The value of LM is not used directly by \ref Dijkstra, it is only - ///passed to \ref DijkstraDefaultTraits. - ///\tparam 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. + ///concepts::Digraph::ArcMap "GR::ArcMap". #ifdef DOXYGEN - template + template #else template , - typename TR=DijkstraDefaultTraits > + typename LEN=typename GR::template ArcMap, + typename TR=DijkstraDefaultTraits > #endif class Dijkstra { public: @@ -206,7 +205,7 @@ ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; - ///The type of the length of the arcs. + ///The type of the arc lengths. typedef typename TR::LengthMap::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; @@ -223,10 +222,11 @@ typedef typename TR::HeapCrossRef HeapCrossRef; ///The heap type used by the algorithm. typedef typename TR::Heap Heap; - ///The operation traits class. + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class" + ///of the algorithm. typedef typename TR::OperationTraits OperationTraits; - ///The traits class. + ///The \ref DijkstraDefaultTraits "traits class" of the algorithm. typedef TR Traits; private: @@ -239,7 +239,7 @@ //Pointer to the underlying digraph. const Digraph *G; //Pointer to the length map. - const LengthMap *length; + const LengthMap *_length; //Pointer to the map of predecessors arcs. PredMap *_pred; //Indicates if _pred is locally allocated (true) or not. @@ -290,7 +290,7 @@ typedef Dijkstra Create; - ///\name Named template parameters + ///\name Named Template Parameters ///@{ @@ -304,10 +304,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///PredMap type. + ///\c PredMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///PredMap type. + ///\c PredMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dijkstra< Digraph, LengthMap, SetPredMapTraits > { @@ -324,10 +325,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///DistMap type. + ///\c DistMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///DistMap type. + ///\c DistMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dijkstra< Digraph, LengthMap, SetDistMapTraits > { @@ -344,10 +346,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type. + ///\c ProcessedMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///ProcessedMap type. + ///\c ProcessedMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits > { @@ -362,10 +365,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type to be Digraph::NodeMap. + ///\c ProcessedMap type to be Digraph::NodeMap. /// ///\ref named-templ-param "Named parameter" for setting - ///ProcessedMap type to be Digraph::NodeMap. + ///\c ProcessedMap type to be Digraph::NodeMap. ///If you don't set it explicitly, it will be automatically allocated. struct SetStandardProcessedMap : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > { @@ -388,10 +391,14 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///heap and cross reference type + ///heap and cross reference types /// ///\ref named-templ-param "Named parameter" for setting heap and cross - ///reference type. + ///reference types. If this named parameter is used, then external + ///heap and cross reference objects must be passed to the algorithm + ///using the \ref heap() function before calling \ref run(Node) "run()" + ///or \ref init(). + ///\sa SetStandardHeap template > struct SetHeap : public Dijkstra< Digraph, LengthMap, SetHeapTraits > { @@ -411,12 +418,18 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///heap and cross reference type with automatic allocation + ///heap and cross reference types with automatic allocation /// ///\ref named-templ-param "Named parameter" for setting heap and cross - ///reference type. It can allocate the heap and the cross reference - ///object if the cross reference's constructor waits for the digraph as - ///parameter and the heap's constructor waits for the cross reference. + ///reference types with automatic allocation. + ///They should have standard constructor interfaces to be able to + ///automatically created by the algorithm (i.e. the digraph should be + ///passed to the constructor of the cross reference and the cross + ///reference should be passed to the constructor of the heap). + ///However external heap and cross reference objects could also be + ///passed to the algorithm using the \ref heap() function before + ///calling \ref run(Node) "run()" or \ref init(). + ///\sa SetHeap template > struct SetStandardHeap : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits > { @@ -433,7 +446,8 @@ ///\c OperationTraits type /// ///\ref named-templ-param "Named parameter" for setting - ///\ref OperationTraits type. + ///\c OperationTraits type. + /// For more information see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits : public Dijkstra > { @@ -452,10 +466,10 @@ ///Constructor. ///Constructor. - ///\param _g The digraph the algorithm runs on. - ///\param _length The length map used by the algorithm. - Dijkstra(const Digraph& _g, const LengthMap& _length) : - G(&_g), length(&_length), + ///\param g The digraph the algorithm runs on. + ///\param length The length map used by the algorithm. + Dijkstra(const Digraph& g, const LengthMap& length) : + G(&g), _length(&length), _pred(NULL), local_pred(false), _dist(NULL), local_dist(false), _processed(NULL), local_processed(false), @@ -479,16 +493,17 @@ ///\return (*this) Dijkstra &lengthMap(const LengthMap &m) { - length = &m; + _length = &m; return *this; } ///Sets the map that stores the predecessor arcs. ///Sets the map that stores the predecessor arcs. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dijkstra &predMap(PredMap &m) { @@ -503,9 +518,10 @@ ///Sets the map that indicates which nodes are processed. ///Sets the map that indicates which nodes are processed. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dijkstra &processedMap(ProcessedMap &m) { @@ -521,9 +537,10 @@ ///Sets the map that stores the distances of the nodes calculated by the ///algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dijkstra &distMap(DistMap &m) { @@ -538,9 +555,11 @@ ///Sets the heap and the cross reference used by algorithm. ///Sets the heap and the cross reference used by algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated heap and cross reference, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), heap and cross reference instances will be + ///allocated automatically. + ///The destructor deallocates these automatically allocated objects, + ///of course. ///\return (*this) Dijkstra &heap(Heap& hp, HeapCrossRef &cr) { @@ -567,22 +586,19 @@ public: - ///\name Execution control - ///The simplest way to execute the algorithm is to use one of the - ///member functions called \ref lemon::Dijkstra::run() "run()". - ///\n - ///If you need more control on the execution, first you must call - ///\ref lemon::Dijkstra::init() "init()", then you can add several - ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()". - ///Finally \ref lemon::Dijkstra::start() "start()" will perform the - ///actual path computation. + ///\name Execution Control + ///The simplest way to execute the %Dijkstra algorithm is to use + ///one of the member functions called \ref run(Node) "run()".\n + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add several source nodes with + ///\ref addSource(). Finally the actual path computation can be + ///performed with one of the \ref start() functions. ///@{ + ///\brief Initializes the internal data structures. + /// ///Initializes the internal data structures. - - ///Initializes the internal data structures. - /// void init() { create_maps(); @@ -630,12 +646,12 @@ Node w=G->target(e); switch(_heap->state(w)) { case Heap::PRE_HEAP: - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e])); + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e])); _pred->set(w,e); break; case Heap::IN_HEAP: { - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]); + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]); if ( OperationTraits::less(newvalue, (*_heap)[w]) ) { _heap->decrease(w, newvalue); _pred->set(w,e); @@ -658,17 +674,16 @@ return !_heap->empty()?_heap->top():INVALID; } - ///\brief Returns \c false if there are nodes - ///to be processed. - /// - ///Returns \c false if there are nodes - ///to be processed in the priority heap. + ///Returns \c false if there are nodes to be processed. + + ///Returns \c false if there are nodes to be processed + ///in the priority heap. bool emptyQueue() const { return _heap->empty(); } - ///Returns the number of the nodes to be processed in the priority heap + ///Returns the number of the nodes to be processed. - ///Returns the number of the nodes to be processed in the priority heap. - /// + ///Returns the number of the nodes to be processed + ///in the priority heap. int queueSize() const { return _heap->size(); } ///Executes the algorithm. @@ -789,61 +804,62 @@ ///@} ///\name Query Functions - ///The result of the %Dijkstra algorithm can be obtained using these + ///The results of the %Dijkstra algorithm can be obtained using these ///functions.\n - ///Either \ref lemon::Dijkstra::run() "run()" or - ///\ref lemon::Dijkstra::start() "start()" must be called before - ///using them. + ///Either \ref run(Node) "run()" or \ref init() should be called + ///before using them. ///@{ - ///The shortest path to a node. + ///The shortest path to the given node. - ///Returns the shortest path to a node. + ///Returns the shortest path to the given node from the root(s). /// - ///\warning \c t should be reachable from the root(s). + ///\warning \c t should be reached from the root(s). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root(s). + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root(s). + ///Returns the distance of the given node from the root(s). /// - ///\warning If node \c v is not reachable from the root(s), then + ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Value dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the shortest path tree for a node. - + ///\brief Returns the 'previous arc' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous arc' of the shortest path ///tree for the node \c v, i.e. it returns the last arc of a - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v - ///is not reachable from the root(s) or if \c v is a root. + ///shortest path from a root to \c v. It is \c INVALID if \c v + ///is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predNode(). + ///tree used in \ref predNode() and \ref predMap(). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v]; } - ///Returns the 'previous node' of the shortest path tree for a node. - + ///\brief Returns the 'previous node' of the shortest path tree for + ///the given node. + /// ///This function returns the 'previous node' of the shortest path ///tree for the node \c v, i.e. it returns the last but one node - ///from a shortest path from the root(s) to \c v. It is \c INVALID - ///if \c v is not reachable from the root(s) or if \c v is a root. + ///of a shortest path from a root to \c v. It is \c INVALID + ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The shortest path tree used here is equal to the shortest path - ///tree used in \ref predArc(). + ///tree used in \ref predArc() and \ref predMap(). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } @@ -853,7 +869,7 @@ ///Returns a const reference to the node map that stores the distances ///of the nodes calculated by the algorithm. /// - ///\pre Either \ref run() or \ref init() + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const DistMap &distMap() const { return *_dist;} @@ -861,16 +877,17 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the shortest path tree. + ///arcs, which form the shortest path tree (forest). /// - ///\pre Either \ref run() or \ref init() + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reachable from the root(s). + ///Checks if the given node is reached from the root(s). - ///Returns \c true if \c v is reachable from the root(s). - ///\pre Either \ref run() or \ref start() + ///Returns \c true if \c v is reached from the root(s). + /// + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. bool reached(Node v) const { return (*_heap_cross_ref)[v] != Heap::PRE_HEAP; } @@ -879,16 +896,18 @@ ///Returns \c true if \c v is processed, i.e. the shortest ///path to \c v has already found. - ///\pre Either \ref run() or \ref init() + /// + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. bool processed(Node v) const { return (*_heap_cross_ref)[v] == Heap::POST_HEAP; } - ///The current distance of a node from the root(s). + ///The current distance of the given node from the root(s). - ///Returns the current distance of a node from the root(s). + ///Returns the current distance of the given node from the root(s). ///It may be decreased in the following processes. - ///\pre Either \ref run() or \ref init() + /// + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function and ///node \c v must be reached but not necessarily processed. Value currentDist(Node v) const { @@ -903,8 +922,8 @@ ///Default traits class of dijkstra() function. ///\tparam GR The type of the digraph. - ///\tparam LM The type of the length map. - template + ///\tparam LEN The type of the length map. + template struct DijkstraWizardDefaultTraits { ///The type of the digraph the algorithm runs on. @@ -912,10 +931,10 @@ ///The type of the map that stores the arc lengths. ///The type of the map that stores the arc lengths. - ///It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef LM LengthMap; - ///The type of the length of the arcs. - typedef typename LM::Value Value; + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef LEN LengthMap; + ///The type of the arc lengths. + typedef typename LEN::Value Value; /// Operation traits for Dijkstra algorithm. @@ -961,7 +980,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the shortest paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -976,7 +995,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -996,8 +1015,8 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef typename Digraph::template NodeMap DistMap; + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. ///This function instantiates a DistMap. @@ -1011,22 +1030,19 @@ ///The type of the shortest paths. ///The type of the shortest paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DijkstraWizard - /// To make it easier to use Dijkstra algorithm - /// we have created a wizard class. - /// This \ref DijkstraWizard class needs default traits, - /// as well as the \ref Dijkstra class. - /// The \ref DijkstraWizardBase is a class to be the default traits of the - /// \ref DijkstraWizard class. - template - class DijkstraWizardBase : public DijkstraWizardDefaultTraits + /// Default traits class used by DijkstraWizard. + /// \tparam GR The type of the digraph. + /// \tparam LEN The type of the length map. + template + class DijkstraWizardBase : public DijkstraWizardDefaultTraits { - typedef DijkstraWizardDefaultTraits Base; + typedef DijkstraWizardDefaultTraits Base; protected: //The type of the nodes in the digraph. typedef typename Base::Digraph::Node Node; @@ -1060,9 +1076,9 @@ /// others are initiated to \c 0. /// \param g The digraph the algorithm runs on. /// \param l The length map. - DijkstraWizardBase(const GR &g,const LM &l) : + DijkstraWizardBase(const GR &g,const LEN &l) : _g(reinterpret_cast(const_cast(&g))), - _length(reinterpret_cast(const_cast(&l))), + _length(reinterpret_cast(const_cast(&l))), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} }; @@ -1071,8 +1087,8 @@ /// This auxiliary class is created to implement the /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm. - /// It does not have own \ref run() method, it uses the functions - /// and features of the plain \ref Dijkstra. + /// It does not have own \ref run(Node) "run()" method, it uses the + /// functions and features of the plain \ref Dijkstra. /// /// This class should only be used through the \ref dijkstra() function, /// which makes it easier to use the algorithm. @@ -1081,7 +1097,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -1089,20 +1104,12 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; - ///The type of the length of the arcs. typedef typename LengthMap::Value Value; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the shortest paths typedef typename TR::Path Path; - ///The heap type used by the dijkstra algorithm. typedef typename TR::Heap Heap; public: @@ -1174,11 +1181,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DijkstraWizard > predMap(const T &t) { @@ -1192,11 +1200,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - ///\ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DijkstraWizard > distMap(const T &t) { @@ -1210,11 +1220,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DijkstraWizard > processedMap(const T &t) { @@ -1227,6 +1238,7 @@ typedef T Path; SetPathBase(const TR &b) : TR(b) {} }; + ///\brief \ref named-func-param "Named parameter" ///for getting the shortest path to the target node. /// @@ -1267,15 +1279,15 @@ /// // Compute shortest path from s to t /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t); ///\endcode - ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()" + ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()" ///to the end of the parameter list. ///\sa DijkstraWizard ///\sa Dijkstra - template - DijkstraWizard > - dijkstra(const GR &digraph, const LM &length) + template + DijkstraWizard > + dijkstra(const GR &digraph, const LEN &length) { - return DijkstraWizard >(digraph,length); + return DijkstraWizard >(digraph,length); } } //END OF NAMESPACE LEMON