diff --git a/lemon/dijkstra.h b/lemon/dijkstra.h --- a/lemon/dijkstra.h +++ b/lemon/dijkstra.h @@ -30,6 +30,7 @@ #include #include #include +#include namespace lemon { @@ -199,7 +200,7 @@ ///\ref concepts::ReadMap::Value "Value" of the length map. ///It is also possible to change the underlying priority heap. /// - ///There is also a \ref dijkstra() "function type interface" for the + ///There is also a \ref dijkstra() "function-type interface" for the ///%Dijkstra algorithm, which is convenient in the simplier cases and ///it can be used easier. /// @@ -987,20 +988,16 @@ ///The type of the map that stores the predecessor ///arcs of the shortest paths. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef NullMap PredMap; + typedef typename Digraph::template NodeMap PredMap; ///Instantiates a \ref PredMap. ///This function instantiates a \ref PredMap. ///\param g is the digraph, to which we would like to define the ///\ref PredMap. ///\todo The digraph alone may be insufficient to initialize -#ifdef DOXYGEN static PredMap *createPredMap(const Digraph &g) -#else - static PredMap *createPredMap(const Digraph &) -#endif { - return new PredMap(); + return new PredMap(g); } ///The type of the map that indicates which nodes are processed. @@ -1030,20 +1027,22 @@ ///The type of the map that stores the distances of the nodes. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. - typedef NullMap DistMap; + typedef typename Digraph::template NodeMap DistMap; ///Instantiates a \ref DistMap. ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define ///the \ref DistMap -#ifdef DOXYGEN static DistMap *createDistMap(const Digraph &g) -#else - static DistMap *createDistMap(const Digraph &) -#endif { - return new DistMap(); + return new DistMap(g); } + + ///The type of the shortest paths. + + ///The type of the shortest paths. + ///It must meet the \ref concepts::Path "Path" concept. + typedef lemon::Path Path; }; /// Default traits class used by \ref DijkstraWizard @@ -1065,7 +1064,7 @@ //Pointer to the digraph the algorithm runs on. void *_g; - //Pointer to the length map + //Pointer to the length map. void *_length; //Pointer to the map of processed nodes. void *_processed; @@ -1073,53 +1072,41 @@ void *_pred; //Pointer to the map of distances. void *_dist; - //Pointer to the source node. - Node _source; + //Pointer to the shortest path to the target node. + void *_path; + //Pointer to the distance of the target node. + void *_di; public: /// Constructor. /// This constructor does not require parameters, therefore it initiates - /// all of the attributes to default values (0, INVALID). + /// all of the attributes to \c 0. DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0), - _dist(0), _source(INVALID) {} + _dist(0), _path(0), _di(0) {} /// Constructor. - /// This constructor requires some parameters, - /// listed in the parameters list. - /// Others are initiated to 0. + /// This constructor requires two parameters, + /// others are initiated to \c 0. /// \param g The digraph the algorithm runs on. /// \param l The length map. - /// \param s The source node. - DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) : + DijkstraWizardBase(const GR &g,const LM &l) : _g(reinterpret_cast(const_cast(&g))), _length(reinterpret_cast(const_cast(&l))), - _processed(0), _pred(0), _dist(0), _source(s) {} + _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} }; - /// Auxiliary class for the function type interface of Dijkstra algorithm. + /// Auxiliary class for the function-type interface of Dijkstra algorithm. - /// This auxiliary class is created to implement the function type - /// interface of \ref Dijkstra algorithm. It uses the functions and features - /// of the plain \ref Dijkstra, but it is much simpler to use it. - /// It should only be used through the \ref dijkstra() function, which makes - /// it easier to use the algorithm. + /// 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. /// - /// Simplicity means that the way to change the types defined - /// in the traits class is based on functions that returns the new class - /// and not on templatable built-in classes. - /// When using the plain \ref Dijkstra - /// the new class with the modified type comes from - /// the original class by using the :: - /// operator. In the case of \ref DijkstraWizard only - /// a function have to be called, and it will - /// return the needed class. - /// - /// It does not have own \ref run() method. When its \ref run() method - /// is called, it initiates a plain \ref Dijkstra object, and calls the - /// \ref Dijkstra::run() method of it. + /// This class should only be used through the \ref dijkstra() function, + /// which makes it easier to use the algorithm. template class DijkstraWizard : public TR { @@ -1144,6 +1131,8 @@ 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; @@ -1156,51 +1145,60 @@ /// Constructor that requires parameters. /// These parameters will be the default values for the traits class. - DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) : - TR(g,l,s) {} + /// \param g The digraph the algorithm runs on. + /// \param l The length map. + DijkstraWizard(const Digraph &g, const LengthMap &l) : + TR(g,l) {} ///Copy constructor DijkstraWizard(const TR &b) : TR(b) {} ~DijkstraWizard() {} - ///Runs Dijkstra algorithm from a source node. + ///Runs Dijkstra algorithm from the given source node. - ///Runs Dijkstra algorithm from a source node. - ///The node can be given with the \ref source() function. - void run() + ///This method runs %Dijkstra algorithm from the given source node + ///in order to compute the shortest path to each node. + void run(Node s) { - if(Base::_source==INVALID) throw UninitializedParameter(); + if (s==INVALID) throw UninitializedParameter(); Dijkstra - dij(*reinterpret_cast(Base::_g), - *reinterpret_cast(Base::_length)); - if(Base::_processed) - dij.processedMap(*reinterpret_cast(Base::_processed)); - if(Base::_pred) - dij.predMap(*reinterpret_cast(Base::_pred)); - if(Base::_dist) - dij.distMap(*reinterpret_cast(Base::_dist)); - dij.run(Base::_source); + dijk(*reinterpret_cast(Base::_g), + *reinterpret_cast(Base::_length)); + if (Base::_pred) + dijk.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + dijk.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_processed) + dijk.processedMap(*reinterpret_cast(Base::_processed)); + dijk.run(s); } - ///Runs Dijkstra algorithm from the given node. + ///Finds the shortest path between \c s and \c t. - ///Runs Dijkstra algorithm from the given node. - ///\param s is the given source. - void run(Node s) + ///This method runs the %Dijkstra algorithm from node \c s + ///in order to compute the shortest path to node \c t + ///(it stops searching when \c t is processed). + /// + ///\return \c true if \c t is reachable form \c s. + bool run(Node s, Node t) { - Base::_source=s; - run(); - } - - /// Sets the source node, from which the Dijkstra algorithm runs. - - /// Sets the source node, from which the Dijkstra algorithm runs. - /// \param s is the source node. - DijkstraWizard &source(Node s) - { - Base::_source=s; - return *this; + if (s==INVALID || t==INVALID) throw UninitializedParameter(); + Dijkstra + dijk(*reinterpret_cast(Base::_g), + *reinterpret_cast(Base::_length)); + if (Base::_pred) + dijk.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + dijk.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_processed) + dijk.processedMap(*reinterpret_cast(Base::_processed)); + dijk.run(s,t); + if (Base::_path) + *reinterpret_cast(Base::_path) = dijk.path(t); + if (Base::_di) + *reinterpret_cast(Base::_di) = dijk.dist(t); + return dijk.reached(t); } template @@ -1209,10 +1207,10 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" + ///\brief \ref named-func-param "Named parameter" ///for setting \ref PredMap object. /// - ///\ref named-templ-param "Named parameter" + ///\ref named-func-param "Named parameter" ///for setting \ref PredMap object. template DijkstraWizard > predMap(const T &t) @@ -1222,15 +1220,33 @@ } template + struct SetDistMapBase : public Base { + typedef T DistMap; + static DistMap *createDistMap(const Digraph &) { return 0; }; + SetDistMapBase(const TR &b) : TR(b) {} + }; + ///\brief \ref named-func-param "Named parameter" + ///for setting \ref DistMap object. + /// + ///\ref named-func-param "Named parameter" + ///for setting \ref DistMap object. + template + DijkstraWizard > distMap(const T &t) + { + Base::_dist=reinterpret_cast(const_cast(&t)); + return DijkstraWizard >(*this); + } + + template struct SetProcessedMapBase : public Base { typedef T ProcessedMap; static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" + ///\brief \ref named-func-param "Named parameter" ///for setting \ref ProcessedMap object. /// - /// \ref named-templ-param "Named parameter" + /// \ref named-func-param "Named parameter" ///for setting \ref ProcessedMap object. template DijkstraWizard > processedMap(const T &t) @@ -1240,37 +1256,49 @@ } template - struct SetDistMapBase : public Base { - typedef T DistMap; - static DistMap *createDistMap(const Digraph &) { return 0; }; - SetDistMapBase(const TR &b) : TR(b) {} + struct SetPathBase : public Base { + typedef T Path; + SetPathBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" - ///for setting \ref DistMap object. + ///\brief \ref named-func-param "Named parameter" + ///for getting the shortest path to the target node. /// - ///\ref named-templ-param "Named parameter" - ///for setting \ref DistMap object. + ///\ref named-func-param "Named parameter" + ///for getting the shortest path to the target node. template - DijkstraWizard > distMap(const T &t) + DijkstraWizard > path(const T &t) { - Base::_dist=reinterpret_cast(const_cast(&t)); - return DijkstraWizard >(*this); + Base::_path=reinterpret_cast(const_cast(&t)); + return DijkstraWizard >(*this); + } + + ///\brief \ref named-func-param "Named parameter" + ///for getting the distance of the target node. + /// + ///\ref named-func-param "Named parameter" + ///for getting the distance of the target node. + DijkstraWizard dist(const Value &d) + { + Base::_di=reinterpret_cast(const_cast(&d)); + return *this; } }; - ///Function type interface for Dijkstra algorithm. + ///Function-type interface for Dijkstra algorithm. /// \ingroup shortest_path - ///Function type interface for Dijkstra algorithm. + ///Function-type interface for Dijkstra algorithm. /// - ///This function also has several - ///\ref named-templ-func-param "named parameters", + ///This function also has several \ref named-func-param "named parameters", ///they are declared as the members of class \ref DijkstraWizard. - ///The following - ///example shows how to use these parameters. + ///The following examples show how to use these parameters. ///\code - /// dijkstra(g,length,source).predMap(preds).run(); + /// // Compute shortest path from node s to each node + /// dijkstra(g,length).predMap(preds).distMap(dists).run(s); + /// + /// // 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()" ///to the end of the parameter list. @@ -1278,9 +1306,9 @@ ///\sa Dijkstra template DijkstraWizard > - dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID) + dijkstra(const GR &digraph, const LM &length) { - return DijkstraWizard >(g,l,s); + return DijkstraWizard >(digraph,length); } } //END OF NAMESPACE LEMON