diff --git a/lemon/bfs.h b/lemon/bfs.h --- a/lemon/bfs.h +++ b/lemon/bfs.h @@ -28,6 +28,7 @@ #include #include #include +#include namespace lemon { @@ -115,7 +116,7 @@ ///\ingroup search ///This class provides an efficient implementation of the %BFS algorithm. /// - ///There is also a \ref bfs() "function type interface" for the BFS + ///There is also a \ref bfs() "function-type interface" for the BFS ///algorithm, which is convenient in the simplier cases and it can be ///used easier. /// @@ -841,26 +842,23 @@ ///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. ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \ref ProcessedMap. @@ -895,21 +893,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 BfsWizard @@ -939,51 +938,39 @@ 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. + int *_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. BfsWizardBase() : _g(0), _reached(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 one parameter, + /// others are initiated to \c 0. /// \param g The digraph the algorithm runs on. - /// \param s The source node. - BfsWizardBase(const GR &g, Node s=INVALID) : + BfsWizardBase(const GR &g) : _g(reinterpret_cast(const_cast(&g))), - _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} + _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} }; - /// Auxiliary class for the function type interface of BFS algorithm. + /// Auxiliary class for the function-type interface of BFS algorithm. - /// This auxiliary class is created to implement the function type - /// interface of \ref Bfs algorithm. It uses the functions and features - /// of the plain \ref Bfs, but it is much simpler to use it. - /// It should only be used through the \ref bfs() function, which makes - /// it easier to use the algorithm. + /// This auxiliary class is created to implement the + /// \ref bfs() "function-type interface" of \ref Bfs algorithm. + /// It does not have own \ref run() method, it uses the functions + /// and features of the plain \ref Bfs. /// - /// 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 Bfs - /// the new class with the modified type comes from - /// the original class by using the :: - /// operator. In the case of \ref BfsWizard 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 Bfs object, and calls the - /// \ref Bfs::run() method of it. + /// This class should only be used through the \ref bfs() function, + /// which makes it easier to use the algorithm. template class BfsWizard : public TR { @@ -1006,6 +993,8 @@ typedef typename TR::ReachedMap ReachedMap; ///\brief 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; public: @@ -1016,51 +1005,70 @@ /// Constructor that requires parameters. /// These parameters will be the default values for the traits class. - BfsWizard(const Digraph &g, Node s=INVALID) : - TR(g,s) {} + /// \param g The digraph the algorithm runs on. + BfsWizard(const Digraph &g) : + TR(g) {} ///Copy constructor BfsWizard(const TR &b) : TR(b) {} ~BfsWizard() {} - ///Runs BFS algorithm from a source node. + ///Runs BFS algorithm from the given source node. - ///Runs BFS algorithm from a source node. - ///The node can be given with the \ref source() function. + ///This method runs BFS algorithm from node \c s + ///in order to compute the shortest path to each node. + void run(Node s) + { + Bfs alg(*reinterpret_cast(Base::_g)); + if (Base::_pred) + alg.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + alg.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_reached) + alg.reachedMap(*reinterpret_cast(Base::_reached)); + if (Base::_processed) + alg.processedMap(*reinterpret_cast(Base::_processed)); + if (s!=INVALID) + alg.run(s); + else + alg.run(); + } + + ///Finds the shortest path between \c s and \c t. + + ///This method runs BFS 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) + { + if (s==INVALID || t==INVALID) throw UninitializedParameter(); + Bfs alg(*reinterpret_cast(Base::_g)); + if (Base::_pred) + alg.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + alg.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_reached) + alg.reachedMap(*reinterpret_cast(Base::_reached)); + if (Base::_processed) + alg.processedMap(*reinterpret_cast(Base::_processed)); + alg.run(s,t); + if (Base::_path) + *reinterpret_cast(Base::_path) = alg.path(t); + if (Base::_di) + *Base::_di = alg.dist(t); + return alg.reached(t); + } + + ///Runs BFS algorithm to visit all nodes in the digraph. + + ///This method runs BFS algorithm in order to compute + ///the shortest path to each node. void run() { - if(Base::_source==INVALID) throw UninitializedParameter(); - Bfs alg(*reinterpret_cast(Base::_g)); - if(Base::_reached) - alg.reachedMap(*reinterpret_cast(Base::_reached)); - if(Base::_processed) - alg.processedMap(*reinterpret_cast(Base::_processed)); - if(Base::_pred) - alg.predMap(*reinterpret_cast(Base::_pred)); - if(Base::_dist) - alg.distMap(*reinterpret_cast(Base::_dist)); - alg.run(Base::_source); - } - - ///Runs BFS algorithm from the given node. - - ///Runs BFS algorithm from the given node. - ///\param s is the given source. - void run(Node s) - { - Base::_source=s; - run(); - } - - /// Sets the source node, from which the Bfs algorithm runs. - - /// Sets the source node, from which the Bfs algorithm runs. - /// \param s is the source node. - BfsWizard &source(Node s) - { - Base::_source=s; - return *this; + run(INVALID); } template @@ -1069,10 +1077,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 BfsWizard > predMap(const T &t) @@ -1087,10 +1095,10 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" + ///\brief \ref named-func-param "Named parameter" ///for setting \ref ReachedMap object. /// - /// \ref named-templ-param "Named parameter" + /// \ref named-func-param "Named parameter" ///for setting \ref ReachedMap object. template BfsWizard > reachedMap(const T &t) @@ -1100,15 +1108,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 + BfsWizard > distMap(const T &t) + { + Base::_dist=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*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 BfsWizard > processedMap(const T &t) @@ -1118,37 +1144,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 - BfsWizard > distMap(const T &t) + BfsWizard > path(const T &t) { - Base::_dist=reinterpret_cast(const_cast(&t)); - return BfsWizard >(*this); + Base::_path=reinterpret_cast(const_cast(&t)); + return BfsWizard >(*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. + BfsWizard dist(const int &d) + { + Base::_di=const_cast(&d); + return *this; } }; - ///Function type interface for Bfs algorithm. + ///Function-type interface for BFS algorithm. /// \ingroup search - ///Function type interface for Bfs algorithm. + ///Function-type interface for BFS 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 BfsWizard. - ///The following - ///example shows how to use these parameters. + ///The following examples show how to use these parameters. ///\code - /// bfs(g,source).predMap(preds).run(); + /// // Compute shortest path from node s to each node + /// bfs(g).predMap(preds).distMap(dists).run(s); + /// + /// // Compute shortest path from s to t + /// bool reached = bfs(g).path(p).dist(d).run(s,t); ///\endcode ///\warning Don't forget to put the \ref BfsWizard::run() "run()" ///to the end of the parameter list. @@ -1156,9 +1194,9 @@ ///\sa Bfs template BfsWizard > - bfs(const GR &g,typename GR::Node s=INVALID) + bfs(const GR &digraph) { - return BfsWizard >(g,s); + return BfsWizard >(digraph); } #ifdef DOXYGEN diff --git a/lemon/concepts/path.h b/lemon/concepts/path.h --- a/lemon/concepts/path.h +++ b/lemon/concepts/path.h @@ -66,7 +66,10 @@ /// \brief Template assigment template - Path& operator=(const CPath& cpath) {} + Path& operator=(const CPath& cpath) { + ignore_unused_variable_warning(cpath); + return *this; + } /// Length of the path ie. the number of arcs in the path. int length() const { return 0;} diff --git a/lemon/dfs.h b/lemon/dfs.h --- a/lemon/dfs.h +++ b/lemon/dfs.h @@ -29,6 +29,7 @@ #include #include #include +#include namespace lemon { @@ -116,7 +117,7 @@ ///\ingroup search ///This class provides an efficient implementation of the %DFS algorithm. /// - ///There is also a \ref dfs() "function type interface" for the DFS + ///There is also a \ref dfs() "function-type interface" for the DFS ///algorithm, which is convenient in the simplier cases and it can be ///used easier. /// @@ -775,27 +776,23 @@ ///The type of the map that stores the predecessor ///arcs of the %DFS 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. ///The type of the map that indicates which nodes are processed. ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \ref ProcessedMap. @@ -830,21 +827,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 DFS paths. + + ///The type of the DFS paths. + ///It must meet the \ref concepts::Path "Path" concept. + typedef lemon::Path Path; }; /// Default traits class used by \ref DfsWizard @@ -874,51 +872,39 @@ void *_pred; //Pointer to the map of distances. void *_dist; - //Pointer to the source node. - Node _source; + //Pointer to the DFS path to the target node. + void *_path; + //Pointer to the distance of the target node. + int *_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. DfsWizardBase() : _g(0), _reached(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 one parameter, + /// others are initiated to \c 0. /// \param g The digraph the algorithm runs on. - /// \param s The source node. - DfsWizardBase(const GR &g, Node s=INVALID) : + DfsWizardBase(const GR &g) : _g(reinterpret_cast(const_cast(&g))), - _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} + _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} }; - /// Auxiliary class for the function type interface of DFS algorithm. + /// Auxiliary class for the function-type interface of DFS algorithm. - /// This auxiliary class is created to implement the function type - /// interface of \ref Dfs algorithm. It uses the functions and features - /// of the plain \ref Dfs, but it is much simpler to use it. - /// It should only be used through the \ref dfs() function, which makes - /// it easier to use the algorithm. + /// This auxiliary class is created to implement the + /// \ref dfs() "function-type interface" of \ref Dfs algorithm. + /// It does not have own \ref run() method, it uses the functions + /// and features of the plain \ref Dfs. /// - /// 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 Dfs - /// the new class with the modified type comes from - /// the original class by using the :: - /// operator. In the case of \ref DfsWizard 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 Dfs object, and calls the - /// \ref Dfs::run() method of it. + /// This class should only be used through the \ref dfs() function, + /// which makes it easier to use the algorithm. template class DfsWizard : public TR { @@ -933,7 +919,7 @@ typedef typename Digraph::OutArcIt OutArcIt; ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. + ///arcs of the DFS paths. typedef typename TR::PredMap PredMap; ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; @@ -941,6 +927,8 @@ typedef typename TR::ReachedMap ReachedMap; ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; + ///The type of the DFS paths + typedef typename TR::Path Path; public: @@ -951,51 +939,70 @@ /// Constructor that requires parameters. /// These parameters will be the default values for the traits class. - DfsWizard(const Digraph &g, Node s=INVALID) : - TR(g,s) {} + /// \param g The digraph the algorithm runs on. + DfsWizard(const Digraph &g) : + TR(g) {} ///Copy constructor DfsWizard(const TR &b) : TR(b) {} ~DfsWizard() {} - ///Runs DFS algorithm from a source node. + ///Runs DFS algorithm from the given source node. - ///Runs DFS algorithm from a source node. - ///The node can be given with the \ref source() function. + ///This method runs DFS algorithm from node \c s + ///in order to compute the DFS path to each node. + void run(Node s) + { + Dfs alg(*reinterpret_cast(Base::_g)); + if (Base::_pred) + alg.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + alg.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_reached) + alg.reachedMap(*reinterpret_cast(Base::_reached)); + if (Base::_processed) + alg.processedMap(*reinterpret_cast(Base::_processed)); + if (s!=INVALID) + alg.run(s); + else + alg.run(); + } + + ///Finds the DFS path between \c s and \c t. + + ///This method runs DFS algorithm from node \c s + ///in order to compute the DFS 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) + { + if (s==INVALID || t==INVALID) throw UninitializedParameter(); + Dfs alg(*reinterpret_cast(Base::_g)); + if (Base::_pred) + alg.predMap(*reinterpret_cast(Base::_pred)); + if (Base::_dist) + alg.distMap(*reinterpret_cast(Base::_dist)); + if (Base::_reached) + alg.reachedMap(*reinterpret_cast(Base::_reached)); + if (Base::_processed) + alg.processedMap(*reinterpret_cast(Base::_processed)); + alg.run(s,t); + if (Base::_path) + *reinterpret_cast(Base::_path) = alg.path(t); + if (Base::_di) + *Base::_di = alg.dist(t); + return alg.reached(t); + } + + ///Runs DFS algorithm to visit all nodes in the digraph. + + ///This method runs DFS algorithm in order to compute + ///the DFS path to each node. void run() { - if(Base::_source==INVALID) throw UninitializedParameter(); - Dfs alg(*reinterpret_cast(Base::_g)); - if(Base::_reached) - alg.reachedMap(*reinterpret_cast(Base::_reached)); - if(Base::_processed) - alg.processedMap(*reinterpret_cast(Base::_processed)); - if(Base::_pred) - alg.predMap(*reinterpret_cast(Base::_pred)); - if(Base::_dist) - alg.distMap(*reinterpret_cast(Base::_dist)); - alg.run(Base::_source); - } - - ///Runs DFS algorithm from the given node. - - ///Runs DFS algorithm from the given node. - ///\param s is the given source. - void run(Node s) - { - Base::_source=s; - run(); - } - - /// Sets the source node, from which the Dfs algorithm runs. - - /// Sets the source node, from which the Dfs algorithm runs. - /// \param s is the source node. - DfsWizard &source(Node s) - { - Base::_source=s; - return *this; + run(INVALID); } template @@ -1004,10 +1011,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 DfsWizard > predMap(const T &t) @@ -1022,10 +1029,10 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-templ-param "Named parameter" + ///\brief \ref named-func-param "Named parameter" ///for setting \ref ReachedMap object. /// - /// \ref named-templ-param "Named parameter" + /// \ref named-func-param "Named parameter" ///for setting \ref ReachedMap object. template DfsWizard > reachedMap(const T &t) @@ -1035,15 +1042,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 + DfsWizard > distMap(const T &t) + { + Base::_dist=reinterpret_cast(const_cast(&t)); + return DfsWizard >(*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 DfsWizard > processedMap(const T &t) @@ -1053,47 +1078,60 @@ } 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 DFS 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 DFS path to the target node. template - DfsWizard > distMap(const T &t) + DfsWizard > path(const T &t) { - Base::_dist=reinterpret_cast(const_cast(&t)); - return DfsWizard >(*this); + Base::_path=reinterpret_cast(const_cast(&t)); + return DfsWizard >(*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. + DfsWizard dist(const int &d) + { + Base::_di=const_cast(&d); + return *this; } }; - ///Function type interface for Dfs algorithm. + ///Function-type interface for DFS algorithm. ///\ingroup search - ///Function type interface for Dfs algorithm. + ///Function-type interface for DFS 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 DfsWizard. - ///The following - ///example shows how to use these parameters. + ///The following examples show how to use these parameters. ///\code - /// dfs(g,source).predMap(preds).run(); + /// // Compute the DFS tree + /// dfs(g).predMap(preds).distMap(dists).run(s); + /// + /// // Compute the DFS path from s to t + /// bool reached = dfs(g).path(p).dist(d).run(s,t); ///\endcode + ///\warning Don't forget to put the \ref DfsWizard::run() "run()" ///to the end of the parameter list. ///\sa DfsWizard ///\sa Dfs template DfsWizard > - dfs(const GR &g,typename GR::Node s=INVALID) + dfs(const GR &digraph) { - return DfsWizard >(g,s); + return DfsWizard >(digraph); } #ifdef DOXYGEN 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 diff --git a/test/bfs_test.cc b/test/bfs_test.cc --- a/test/bfs_test.cc +++ b/test/bfs_test.cc @@ -62,7 +62,6 @@ bool b; BType::DistMap d(G); BType::PredMap p(G); - // BType::PredNodeMap pn(G); BType bfs_test(G); @@ -72,9 +71,7 @@ e = bfs_test.predArc(n); n = bfs_test.predNode(n); d = bfs_test.distMap(); - p = bfs_test.predMap(); - // pn = bfs_test.predNodeMap(); b = bfs_test.reached(n); Path pp = bfs_test.path(n); @@ -88,14 +85,30 @@ typedef Digraph::Node Node; Digraph g; - bfs(g,Node()).run(); - bfs(g).source(Node()).run(); + bool b; + bfs(g).run(Node()); + b=bfs(g).run(Node(),Node()); + bfs(g).run(); bfs(g) - .predMap(concepts::WriteMap()) - .distMap(concepts::WriteMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) .reachedMap(concepts::ReadWriteMap()) .processedMap(concepts::WriteMap()) .run(Node()); + b=bfs(g) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .reachedMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) + .path(concepts::Path()) + .dist(VType()) + .run(Node(),Node()); + bfs(g) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .reachedMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) + .run(); } template @@ -114,7 +127,7 @@ Bfs bfs_test(G); bfs_test.run(s); - check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); + check(bfs_test.dist(t)==2,"Bfs found a wrong path."); Path p = bfs_test.path(t); check(p.length()==2,"path() found a wrong path."); @@ -128,7 +141,7 @@ Node v=G.target(a); check( !bfs_test.reached(u) || (bfs_test.dist(v) <= bfs_test.dist(u)+1), - "Wrong output." << G.id(v) << ' ' << G.id(u)); + "Wrong output. " << G.id(u) << "->" << G.id(v)); } for(NodeIt v(G); v!=INVALID; ++v) { @@ -140,11 +153,15 @@ check(u==bfs_test.predNode(v),"Wrong tree."); check(bfs_test.dist(v) - bfs_test.dist(u) == 1, "Wrong distance. Difference: " - << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - - 1)); + << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1)); } } } + + { + NullMap myPredMap; + bfs(G).predMap(myPredMap).run(s); + } } int main() diff --git a/test/dfs_test.cc b/test/dfs_test.cc --- a/test/dfs_test.cc +++ b/test/dfs_test.cc @@ -20,7 +20,6 @@ #include #include #include - #include #include @@ -88,14 +87,30 @@ typedef Digraph::Node Node; Digraph g; - dfs(g,Node()).run(); - dfs(g).source(Node()).run(); + bool b; + dfs(g).run(Node()); + b=dfs(g).run(Node(),Node()); + dfs(g).run(); dfs(g) - .predMap(concepts::WriteMap()) - .distMap(concepts::WriteMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) .reachedMap(concepts::ReadWriteMap()) .processedMap(concepts::WriteMap()) .run(Node()); + b=dfs(g) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .reachedMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) + .path(concepts::Path()) + .dist(VType()) + .run(Node(),Node()); + dfs(g) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .reachedMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) + .run(); } template @@ -129,10 +144,15 @@ check(u==dfs_test.predNode(v),"Wrong tree."); check(dfs_test.dist(v) - dfs_test.dist(u) == 1, "Wrong distance. (" << dfs_test.dist(u) << "->" - < myPredMap; + dfs(G).predMap(myPredMap).run(s); + } } int main() diff --git a/test/dijkstra_test.cc b/test/dijkstra_test.cc --- a/test/dijkstra_test.cc +++ b/test/dijkstra_test.cc @@ -20,7 +20,6 @@ #include #include #include - #include #include @@ -64,7 +63,6 @@ bool b; DType::DistMap d(G); DType::PredMap p(G); - // DType::PredNodeMap pn(G); LengthMap length; DType dijkstra_test(G,length); @@ -76,7 +74,6 @@ n = dijkstra_test.predNode(n); d = dijkstra_test.distMap(); p = dijkstra_test.predMap(); - // pn = dijkstra_test.predNodeMap(); b = dijkstra_test.reached(n); Path pp = dijkstra_test.path(n); @@ -91,12 +88,21 @@ typedef concepts::ReadMap LengthMap; Digraph g; - dijkstra(g,LengthMap(),Node()).run(); - dijkstra(g,LengthMap()).source(Node()).run(); + bool b; + dijkstra(g,LengthMap()).run(Node()); + b=dijkstra(g,LengthMap()).run(Node(),Node()); dijkstra(g,LengthMap()) - .predMap(concepts::WriteMap()) - .distMap(concepts::WriteMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) .run(Node()); + b=dijkstra(g,LengthMap()) + .predMap(concepts::ReadWriteMap()) + .distMap(concepts::ReadWriteMap()) + .processedMap(concepts::WriteMap()) + .path(concepts::Path()) + .dist(VType()) + .run(Node(),Node()); } template @@ -122,7 +128,7 @@ check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); Path p = dijkstra_test.path(t); - check(p.length()==3,"getPath() found a wrong path."); + check(p.length()==3,"path() found a wrong path."); check(checkPath(G, p),"path() found a wrong path."); check(pathSource(G, p) == s,"path() found a wrong path."); check(pathTarget(G, p) == t,"path() found a wrong path."); @@ -132,7 +138,7 @@ Node v=G.target(e); check( !dijkstra_test.reached(u) || (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]), - "dist(target)-dist(source)-arc_length= " << + "Wrong output. dist(target)-dist(source)-arc_length=" << dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]); }