diff -r c35afa9e89e7 -r ef88c0a30f85 lemon/bfs.h --- a/lemon/bfs.h Mon Jan 12 23:11:39 2009 +0100 +++ b/lemon/bfs.h Thu Nov 05 15:48:01 2009 +0100 @@ -47,13 +47,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); @@ -62,13 +62,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 @@ -81,13 +82,13 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \c ReachedMap. - ///This function instantiates a ReachedMap. + ///This function instantiates a \ref ReachedMap. ///\param g is the digraph, to which - ///we would like to define the ReachedMap. + ///we would like to define the \ref ReachedMap. static ReachedMap *createReachedMap(const Digraph &g) { return new ReachedMap(g); @@ -96,13 +97,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. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a 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. + ///\ref DistMap. static DistMap *createDistMap(const Digraph &g) { return new DistMap(g); @@ -221,11 +222,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. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///\c PredMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Bfs< Digraph, SetPredMapTraits > { typedef Bfs< Digraph, SetPredMapTraits > Create; @@ -241,11 +242,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. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///\c DistMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Bfs< Digraph, SetDistMapTraits > { typedef Bfs< Digraph, SetDistMapTraits > Create; @@ -261,11 +262,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ReachedMap type. + ///\c ReachedMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///ReachedMap type. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///\c ReachedMap type. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits > { typedef Bfs< Digraph, SetReachedMapTraits > Create; @@ -281,11 +282,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. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///\c ProcessedMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits > { typedef Bfs< Digraph, SetProcessedMapTraits > Create; @@ -300,10 +301,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 Bfs< Digraph, SetStandardProcessedMapTraits > { @@ -413,8 +414,8 @@ ///\name Execution Control ///The simplest way to execute the BFS algorithm is to use one of the ///member functions called \ref run(Node) "run()".\n - ///If you need more control on the execution, first you have to call - ///\ref init(), then you can add several source nodes with + ///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. @@ -737,9 +738,9 @@ ///@{ - ///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 reached from the root(s). /// @@ -747,9 +748,9 @@ ///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 reached from the root(s), then ///the return value of this function is undefined. @@ -758,29 +759,31 @@ ///must be called before using this function. int 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 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(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 a root to \c v. It is \c INVALID + ///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(Node) "run()" or \ref init() ///must be called before using this function. @@ -801,13 +804,13 @@ ///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(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reached from the root(s). + ///Checks if the given node is reached from the root(s). ///Returns \c true if \c v is reached from the root(s). /// @@ -833,7 +836,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. @@ -848,7 +851,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. @@ -868,7 +871,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -883,7 +886,7 @@ ///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. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -898,18 +901,14 @@ ///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 BfsWizard - /// To make it easier to use Bfs algorithm - /// we have created a wizard class. - /// This \ref BfsWizard class needs default traits, - /// as well as the \ref Bfs class. - /// The \ref BfsWizardBase is a class to be the default traits of the - /// \ref BfsWizard class. + /// Default traits class used by BfsWizard. + /// \tparam GR The type of the digraph. template class BfsWizardBase : public BfsWizardDefaultTraits { @@ -937,7 +936,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -967,7 +966,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -975,16 +973,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the shortest paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. 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: @@ -1067,11 +1059,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 BfsWizard > predMap(const T &t) { @@ -1085,11 +1078,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template BfsWizard > reachedMap(const T &t) { @@ -1103,11 +1097,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 BfsWizard > distMap(const T &t) { @@ -1121,11 +1117,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 BfsWizard > processedMap(const T &t) { @@ -1194,9 +1191,9 @@ /// /// This class defines the interface of the BfsVisit events, and /// it could be the base of a real visitor class. - template + template struct BfsVisitor { - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; /// \brief Called for the source node(s) of the BFS. @@ -1224,9 +1221,9 @@ void examine(const Arc& arc) {} }; #else - template + template struct BfsVisitor { - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; void start(const Node&) {} @@ -1254,17 +1251,17 @@ /// \brief Default traits class of BfsVisit class. /// /// Default traits class of BfsVisit class. - /// \tparam _Digraph The type of the digraph the algorithm runs on. - template + /// \tparam GR The type of the digraph the algorithm runs on. + template struct BfsVisitDefaultTraits { /// \brief The type of the digraph the algorithm runs on. - typedef _Digraph Digraph; + typedef GR Digraph; /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1280,12 +1277,12 @@ /// \ingroup search /// - /// \brief %BFS algorithm class with visitor interface. + /// \brief BFS algorithm class with visitor interface. /// - /// This class provides an efficient implementation of the %BFS algorithm + /// This class provides an efficient implementation of the BFS algorithm /// with visitor interface. /// - /// The %BfsVisit class provides an alternative interface to the Bfs + /// The BfsVisit class provides an alternative interface to the Bfs /// class. It works with callback mechanism, the BfsVisit object calls /// the member functions of the \c Visitor class on every BFS event. /// @@ -1294,37 +1291,37 @@ /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs() /// instead. /// - /// \tparam _Digraph The type of the digraph the algorithm runs on. - /// The default value is - /// \ref ListDigraph. The value of _Digraph is not used directly by - /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits. - /// \tparam _Visitor The Visitor type that is used by the algorithm. - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which + /// \tparam GR The type of the digraph the algorithm runs on. + /// The default type is \ref ListDigraph. + /// The value of GR is not used directly by \ref BfsVisit, + /// it is only passed to \ref BfsVisitDefaultTraits. + /// \tparam VS The Visitor type that is used by the algorithm. + /// \ref BfsVisitor "BfsVisitor" is an empty visitor, which /// does not observe the BFS events. If you want to observe the BFS /// events, you should implement your own visitor class. - /// \tparam _Traits Traits class to set various data types used by the + /// \tparam TR Traits class to set various data types used by the /// algorithm. The default traits class is - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits". /// See \ref BfsVisitDefaultTraits for the documentation of /// a BFS visit traits class. #ifdef DOXYGEN - template + template #else - template , - typename _Traits = BfsVisitDefaultTraits<_Digraph> > + template , + typename TR = BfsVisitDefaultTraits > #endif class BfsVisit { public: ///The traits class. - typedef _Traits Traits; + typedef TR Traits; ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; ///The visitor type used by the algorithm. - typedef _Visitor Visitor; + typedef VS Visitor; ///The type of the map that indicates which nodes are reached. typedef typename Traits::ReachedMap ReachedMap; @@ -1425,8 +1422,8 @@ /// \name Execution Control /// The simplest way to execute the BFS algorithm is to use one of the /// member functions called \ref run(Node) "run()".\n - /// If you need more control on the execution, first you have to call - /// \ref init(), then you can add several source nodes with + /// 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. @@ -1735,7 +1732,7 @@ ///@{ - /// \brief Checks if a node is reached from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// /// Returns \c true if \c v is reached from the root(s). ///