1.1 --- a/lemon/bfs.h Thu Jan 01 00:00:00 2009 +0100
1.2 +++ b/lemon/bfs.h Mon Feb 23 12:10:26 2009 +0100
1.3 @@ -49,11 +49,11 @@
1.4 ///arcs of the shortest paths.
1.5 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.6 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.7 - ///Instantiates a PredMap.
1.8 + ///Instantiates a \c PredMap.
1.9
1.10 - ///This function instantiates a PredMap.
1.11 + ///This function instantiates a \ref PredMap.
1.12 ///\param g is the digraph, to which we would like to define the
1.13 - ///PredMap.
1.14 + ///\ref PredMap.
1.15 static PredMap *createPredMap(const Digraph &g)
1.16 {
1.17 return new PredMap(g);
1.18 @@ -64,11 +64,11 @@
1.19 ///The type of the map that indicates which nodes are processed.
1.20 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.21 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.22 - ///Instantiates a ProcessedMap.
1.23 + ///Instantiates a \c ProcessedMap.
1.24
1.25 - ///This function instantiates a ProcessedMap.
1.26 + ///This function instantiates a \ref ProcessedMap.
1.27 ///\param g is the digraph, to which
1.28 - ///we would like to define the ProcessedMap
1.29 + ///we would like to define the \ref ProcessedMap
1.30 #ifdef DOXYGEN
1.31 static ProcessedMap *createProcessedMap(const Digraph &g)
1.32 #else
1.33 @@ -83,11 +83,11 @@
1.34 ///The type of the map that indicates which nodes are reached.
1.35 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.36 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.37 - ///Instantiates a ReachedMap.
1.38 + ///Instantiates a \c ReachedMap.
1.39
1.40 - ///This function instantiates a ReachedMap.
1.41 + ///This function instantiates a \ref ReachedMap.
1.42 ///\param g is the digraph, to which
1.43 - ///we would like to define the ReachedMap.
1.44 + ///we would like to define the \ref ReachedMap.
1.45 static ReachedMap *createReachedMap(const Digraph &g)
1.46 {
1.47 return new ReachedMap(g);
1.48 @@ -98,11 +98,11 @@
1.49 ///The type of the map that stores the distances of the nodes.
1.50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.51 typedef typename Digraph::template NodeMap<int> DistMap;
1.52 - ///Instantiates a DistMap.
1.53 + ///Instantiates a \c DistMap.
1.54
1.55 - ///This function instantiates a DistMap.
1.56 + ///This function instantiates a \ref DistMap.
1.57 ///\param g is the digraph, to which we would like to define the
1.58 - ///DistMap.
1.59 + ///\ref DistMap.
1.60 static DistMap *createDistMap(const Digraph &g)
1.61 {
1.62 return new DistMap(g);
1.63 @@ -221,10 +221,10 @@
1.64 }
1.65 };
1.66 ///\brief \ref named-templ-param "Named parameter" for setting
1.67 - ///PredMap type.
1.68 + ///\c PredMap type.
1.69 ///
1.70 ///\ref named-templ-param "Named parameter" for setting
1.71 - ///PredMap type.
1.72 + ///\c PredMap type.
1.73 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.74 template <class T>
1.75 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.76 @@ -241,10 +241,10 @@
1.77 }
1.78 };
1.79 ///\brief \ref named-templ-param "Named parameter" for setting
1.80 - ///DistMap type.
1.81 + ///\c DistMap type.
1.82 ///
1.83 ///\ref named-templ-param "Named parameter" for setting
1.84 - ///DistMap type.
1.85 + ///\c DistMap type.
1.86 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.87 template <class T>
1.88 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.89 @@ -261,10 +261,10 @@
1.90 }
1.91 };
1.92 ///\brief \ref named-templ-param "Named parameter" for setting
1.93 - ///ReachedMap type.
1.94 + ///\c ReachedMap type.
1.95 ///
1.96 ///\ref named-templ-param "Named parameter" for setting
1.97 - ///ReachedMap type.
1.98 + ///\c ReachedMap type.
1.99 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.100 template <class T>
1.101 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.102 @@ -281,10 +281,10 @@
1.103 }
1.104 };
1.105 ///\brief \ref named-templ-param "Named parameter" for setting
1.106 - ///ProcessedMap type.
1.107 + ///\c ProcessedMap type.
1.108 ///
1.109 ///\ref named-templ-param "Named parameter" for setting
1.110 - ///ProcessedMap type.
1.111 + ///\c ProcessedMap type.
1.112 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 template <class T>
1.114 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.115 @@ -300,10 +300,10 @@
1.116 }
1.117 };
1.118 ///\brief \ref named-templ-param "Named parameter" for setting
1.119 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.120 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.121 ///
1.122 ///\ref named-templ-param "Named parameter" for setting
1.123 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.124 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.125 ///If you don't set it explicitly, it will be automatically allocated.
1.126 struct SetStandardProcessedMap :
1.127 public Bfs< Digraph, SetStandardProcessedMapTraits > {
1.128 @@ -1194,9 +1194,9 @@
1.129 ///
1.130 /// This class defines the interface of the BfsVisit events, and
1.131 /// it could be the base of a real visitor class.
1.132 - template <typename _Digraph>
1.133 + template <typename GR>
1.134 struct BfsVisitor {
1.135 - typedef _Digraph Digraph;
1.136 + typedef GR Digraph;
1.137 typedef typename Digraph::Arc Arc;
1.138 typedef typename Digraph::Node Node;
1.139 /// \brief Called for the source node(s) of the BFS.
1.140 @@ -1224,9 +1224,9 @@
1.141 void examine(const Arc& arc) {}
1.142 };
1.143 #else
1.144 - template <typename _Digraph>
1.145 + template <typename GR>
1.146 struct BfsVisitor {
1.147 - typedef _Digraph Digraph;
1.148 + typedef GR Digraph;
1.149 typedef typename Digraph::Arc Arc;
1.150 typedef typename Digraph::Node Node;
1.151 void start(const Node&) {}
1.152 @@ -1254,12 +1254,12 @@
1.153 /// \brief Default traits class of BfsVisit class.
1.154 ///
1.155 /// Default traits class of BfsVisit class.
1.156 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.157 - template<class _Digraph>
1.158 + /// \tparam GR The type of the digraph the algorithm runs on.
1.159 + template<class GR>
1.160 struct BfsVisitDefaultTraits {
1.161
1.162 /// \brief The type of the digraph the algorithm runs on.
1.163 - typedef _Digraph Digraph;
1.164 + typedef GR Digraph;
1.165
1.166 /// \brief The type of the map that indicates which nodes are reached.
1.167 ///
1.168 @@ -1280,12 +1280,12 @@
1.169
1.170 /// \ingroup search
1.171 ///
1.172 - /// \brief %BFS algorithm class with visitor interface.
1.173 + /// \brief BFS algorithm class with visitor interface.
1.174 ///
1.175 - /// This class provides an efficient implementation of the %BFS algorithm
1.176 + /// This class provides an efficient implementation of the BFS algorithm
1.177 /// with visitor interface.
1.178 ///
1.179 - /// The %BfsVisit class provides an alternative interface to the Bfs
1.180 + /// The BfsVisit class provides an alternative interface to the Bfs
1.181 /// class. It works with callback mechanism, the BfsVisit object calls
1.182 /// the member functions of the \c Visitor class on every BFS event.
1.183 ///
1.184 @@ -1294,37 +1294,37 @@
1.185 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1.186 /// instead.
1.187 ///
1.188 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.189 - /// The default value is
1.190 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.191 - /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1.192 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.193 - /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1.194 + /// \tparam GR The type of the digraph the algorithm runs on.
1.195 + /// The default type is \ref ListDigraph.
1.196 + /// The value of GR is not used directly by \ref BfsVisit,
1.197 + /// it is only passed to \ref BfsVisitDefaultTraits.
1.198 + /// \tparam VS The Visitor type that is used by the algorithm.
1.199 + /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1.200 /// does not observe the BFS events. If you want to observe the BFS
1.201 /// events, you should implement your own visitor class.
1.202 - /// \tparam _Traits Traits class to set various data types used by the
1.203 + /// \tparam TR Traits class to set various data types used by the
1.204 /// algorithm. The default traits class is
1.205 - /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.206 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
1.207 /// See \ref BfsVisitDefaultTraits for the documentation of
1.208 /// a BFS visit traits class.
1.209 #ifdef DOXYGEN
1.210 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.211 + template <typename GR, typename VS, typename TR>
1.212 #else
1.213 - template <typename _Digraph = ListDigraph,
1.214 - typename _Visitor = BfsVisitor<_Digraph>,
1.215 - typename _Traits = BfsVisitDefaultTraits<_Digraph> >
1.216 + template <typename GR = ListDigraph,
1.217 + typename VS = BfsVisitor<GR>,
1.218 + typename TR = BfsVisitDefaultTraits<GR> >
1.219 #endif
1.220 class BfsVisit {
1.221 public:
1.222
1.223 ///The traits class.
1.224 - typedef _Traits Traits;
1.225 + typedef TR Traits;
1.226
1.227 ///The type of the digraph the algorithm runs on.
1.228 typedef typename Traits::Digraph Digraph;
1.229
1.230 ///The visitor type used by the algorithm.
1.231 - typedef _Visitor Visitor;
1.232 + typedef VS Visitor;
1.233
1.234 ///The type of the map that indicates which nodes are reached.
1.235 typedef typename Traits::ReachedMap ReachedMap;