1.1 --- a/lemon/dfs.h Thu Sep 11 11:10:44 2008 +0100
1.2 +++ b/lemon/dfs.h Mon Sep 22 15:33:23 2008 +0200
1.3 @@ -29,6 +29,7 @@
1.4 #include <lemon/error.h>
1.5 #include <lemon/assert.h>
1.6 #include <lemon/maps.h>
1.7 +#include <lemon/path.h>
1.8
1.9 namespace lemon {
1.10
1.11 @@ -116,7 +117,7 @@
1.12 ///\ingroup search
1.13 ///This class provides an efficient implementation of the %DFS algorithm.
1.14 ///
1.15 - ///There is also a \ref dfs() "function type interface" for the DFS
1.16 + ///There is also a \ref dfs() "function-type interface" for the DFS
1.17 ///algorithm, which is convenient in the simplier cases and it can be
1.18 ///used easier.
1.19 ///
1.20 @@ -775,27 +776,23 @@
1.21 ///The type of the map that stores the predecessor
1.22 ///arcs of the %DFS paths.
1.23 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.24 - ///
1.25 - typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
1.26 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.27 ///Instantiates a \ref PredMap.
1.28
1.29 ///This function instantiates a \ref PredMap.
1.30 ///\param g is the digraph, to which we would like to define the
1.31 ///\ref PredMap.
1.32 ///\todo The digraph alone may be insufficient to initialize
1.33 -#ifdef DOXYGEN
1.34 static PredMap *createPredMap(const Digraph &g)
1.35 -#else
1.36 - static PredMap *createPredMap(const Digraph &)
1.37 -#endif
1.38 {
1.39 - return new PredMap();
1.40 + return new PredMap(g);
1.41 }
1.42
1.43 ///The type of the map that indicates which nodes are processed.
1.44
1.45 ///The type of the map that indicates which nodes are processed.
1.46 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.47 + ///By default it is a NullMap.
1.48 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.49 ///Instantiates a \ref ProcessedMap.
1.50
1.51 @@ -830,21 +827,22 @@
1.52
1.53 ///The type of the map that stores the distances of the nodes.
1.54 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.55 - ///
1.56 - typedef NullMap<typename Digraph::Node,int> DistMap;
1.57 + typedef typename Digraph::template NodeMap<int> DistMap;
1.58 ///Instantiates a \ref DistMap.
1.59
1.60 ///This function instantiates a \ref DistMap.
1.61 ///\param g is the digraph, to which we would like to define
1.62 ///the \ref DistMap
1.63 -#ifdef DOXYGEN
1.64 static DistMap *createDistMap(const Digraph &g)
1.65 -#else
1.66 - static DistMap *createDistMap(const Digraph &)
1.67 -#endif
1.68 {
1.69 - return new DistMap();
1.70 + return new DistMap(g);
1.71 }
1.72 +
1.73 + ///The type of the DFS paths.
1.74 +
1.75 + ///The type of the DFS paths.
1.76 + ///It must meet the \ref concepts::Path "Path" concept.
1.77 + typedef lemon::Path<Digraph> Path;
1.78 };
1.79
1.80 /// Default traits class used by \ref DfsWizard
1.81 @@ -874,51 +872,39 @@
1.82 void *_pred;
1.83 //Pointer to the map of distances.
1.84 void *_dist;
1.85 - //Pointer to the source node.
1.86 - Node _source;
1.87 + //Pointer to the DFS path to the target node.
1.88 + void *_path;
1.89 + //Pointer to the distance of the target node.
1.90 + int *_di;
1.91
1.92 public:
1.93 /// Constructor.
1.94
1.95 /// This constructor does not require parameters, therefore it initiates
1.96 - /// all of the attributes to default values (0, INVALID).
1.97 + /// all of the attributes to \c 0.
1.98 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.99 - _dist(0), _source(INVALID) {}
1.100 + _dist(0), _path(0), _di(0) {}
1.101
1.102 /// Constructor.
1.103
1.104 - /// This constructor requires some parameters,
1.105 - /// listed in the parameters list.
1.106 - /// Others are initiated to 0.
1.107 + /// This constructor requires one parameter,
1.108 + /// others are initiated to \c 0.
1.109 /// \param g The digraph the algorithm runs on.
1.110 - /// \param s The source node.
1.111 - DfsWizardBase(const GR &g, Node s=INVALID) :
1.112 + DfsWizardBase(const GR &g) :
1.113 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.114 - _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.115 + _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.116
1.117 };
1.118
1.119 - /// Auxiliary class for the function type interface of DFS algorithm.
1.120 + /// Auxiliary class for the function-type interface of DFS algorithm.
1.121
1.122 - /// This auxiliary class is created to implement the function type
1.123 - /// interface of \ref Dfs algorithm. It uses the functions and features
1.124 - /// of the plain \ref Dfs, but it is much simpler to use it.
1.125 - /// It should only be used through the \ref dfs() function, which makes
1.126 - /// it easier to use the algorithm.
1.127 + /// This auxiliary class is created to implement the
1.128 + /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
1.129 + /// It does not have own \ref run() method, it uses the functions
1.130 + /// and features of the plain \ref Dfs.
1.131 ///
1.132 - /// Simplicity means that the way to change the types defined
1.133 - /// in the traits class is based on functions that returns the new class
1.134 - /// and not on templatable built-in classes.
1.135 - /// When using the plain \ref Dfs
1.136 - /// the new class with the modified type comes from
1.137 - /// the original class by using the ::
1.138 - /// operator. In the case of \ref DfsWizard only
1.139 - /// a function have to be called, and it will
1.140 - /// return the needed class.
1.141 - ///
1.142 - /// It does not have own \ref run() method. When its \ref run() method
1.143 - /// is called, it initiates a plain \ref Dfs object, and calls the
1.144 - /// \ref Dfs::run() method of it.
1.145 + /// This class should only be used through the \ref dfs() function,
1.146 + /// which makes it easier to use the algorithm.
1.147 template<class TR>
1.148 class DfsWizard : public TR
1.149 {
1.150 @@ -933,7 +919,7 @@
1.151 typedef typename Digraph::OutArcIt OutArcIt;
1.152
1.153 ///\brief The type of the map that stores the predecessor
1.154 - ///arcs of the shortest paths.
1.155 + ///arcs of the DFS paths.
1.156 typedef typename TR::PredMap PredMap;
1.157 ///\brief The type of the map that stores the distances of the nodes.
1.158 typedef typename TR::DistMap DistMap;
1.159 @@ -941,6 +927,8 @@
1.160 typedef typename TR::ReachedMap ReachedMap;
1.161 ///\brief The type of the map that indicates which nodes are processed.
1.162 typedef typename TR::ProcessedMap ProcessedMap;
1.163 + ///The type of the DFS paths
1.164 + typedef typename TR::Path Path;
1.165
1.166 public:
1.167
1.168 @@ -951,51 +939,70 @@
1.169
1.170 /// Constructor that requires parameters.
1.171 /// These parameters will be the default values for the traits class.
1.172 - DfsWizard(const Digraph &g, Node s=INVALID) :
1.173 - TR(g,s) {}
1.174 + /// \param g The digraph the algorithm runs on.
1.175 + DfsWizard(const Digraph &g) :
1.176 + TR(g) {}
1.177
1.178 ///Copy constructor
1.179 DfsWizard(const TR &b) : TR(b) {}
1.180
1.181 ~DfsWizard() {}
1.182
1.183 - ///Runs DFS algorithm from a source node.
1.184 + ///Runs DFS algorithm from the given source node.
1.185
1.186 - ///Runs DFS algorithm from a source node.
1.187 - ///The node can be given with the \ref source() function.
1.188 + ///This method runs DFS algorithm from node \c s
1.189 + ///in order to compute the DFS path to each node.
1.190 + void run(Node s)
1.191 + {
1.192 + Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.193 + if (Base::_pred)
1.194 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.195 + if (Base::_dist)
1.196 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.197 + if (Base::_reached)
1.198 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.199 + if (Base::_processed)
1.200 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.201 + if (s!=INVALID)
1.202 + alg.run(s);
1.203 + else
1.204 + alg.run();
1.205 + }
1.206 +
1.207 + ///Finds the DFS path between \c s and \c t.
1.208 +
1.209 + ///This method runs DFS algorithm from node \c s
1.210 + ///in order to compute the DFS path to node \c t
1.211 + ///(it stops searching when \c t is processed).
1.212 + ///
1.213 + ///\return \c true if \c t is reachable form \c s.
1.214 + bool run(Node s, Node t)
1.215 + {
1.216 + if (s==INVALID || t==INVALID) throw UninitializedParameter();
1.217 + Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.218 + if (Base::_pred)
1.219 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.220 + if (Base::_dist)
1.221 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.222 + if (Base::_reached)
1.223 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.224 + if (Base::_processed)
1.225 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.226 + alg.run(s,t);
1.227 + if (Base::_path)
1.228 + *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
1.229 + if (Base::_di)
1.230 + *Base::_di = alg.dist(t);
1.231 + return alg.reached(t);
1.232 + }
1.233 +
1.234 + ///Runs DFS algorithm to visit all nodes in the digraph.
1.235 +
1.236 + ///This method runs DFS algorithm in order to compute
1.237 + ///the DFS path to each node.
1.238 void run()
1.239 {
1.240 - if(Base::_source==INVALID) throw UninitializedParameter();
1.241 - Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.242 - if(Base::_reached)
1.243 - alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.244 - if(Base::_processed)
1.245 - alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.246 - if(Base::_pred)
1.247 - alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.248 - if(Base::_dist)
1.249 - alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.250 - alg.run(Base::_source);
1.251 - }
1.252 -
1.253 - ///Runs DFS algorithm from the given node.
1.254 -
1.255 - ///Runs DFS algorithm from the given node.
1.256 - ///\param s is the given source.
1.257 - void run(Node s)
1.258 - {
1.259 - Base::_source=s;
1.260 - run();
1.261 - }
1.262 -
1.263 - /// Sets the source node, from which the Dfs algorithm runs.
1.264 -
1.265 - /// Sets the source node, from which the Dfs algorithm runs.
1.266 - /// \param s is the source node.
1.267 - DfsWizard<TR> &source(Node s)
1.268 - {
1.269 - Base::_source=s;
1.270 - return *this;
1.271 + run(INVALID);
1.272 }
1.273
1.274 template<class T>
1.275 @@ -1004,10 +1011,10 @@
1.276 static PredMap *createPredMap(const Digraph &) { return 0; };
1.277 SetPredMapBase(const TR &b) : TR(b) {}
1.278 };
1.279 - ///\brief \ref named-templ-param "Named parameter"
1.280 + ///\brief \ref named-func-param "Named parameter"
1.281 ///for setting \ref PredMap object.
1.282 ///
1.283 - ///\ref named-templ-param "Named parameter"
1.284 + ///\ref named-func-param "Named parameter"
1.285 ///for setting \ref PredMap object.
1.286 template<class T>
1.287 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.288 @@ -1022,10 +1029,10 @@
1.289 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.290 SetReachedMapBase(const TR &b) : TR(b) {}
1.291 };
1.292 - ///\brief \ref named-templ-param "Named parameter"
1.293 + ///\brief \ref named-func-param "Named parameter"
1.294 ///for setting \ref ReachedMap object.
1.295 ///
1.296 - /// \ref named-templ-param "Named parameter"
1.297 + /// \ref named-func-param "Named parameter"
1.298 ///for setting \ref ReachedMap object.
1.299 template<class T>
1.300 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.301 @@ -1035,15 +1042,33 @@
1.302 }
1.303
1.304 template<class T>
1.305 + struct SetDistMapBase : public Base {
1.306 + typedef T DistMap;
1.307 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.308 + SetDistMapBase(const TR &b) : TR(b) {}
1.309 + };
1.310 + ///\brief \ref named-func-param "Named parameter"
1.311 + ///for setting \ref DistMap object.
1.312 + ///
1.313 + /// \ref named-func-param "Named parameter"
1.314 + ///for setting \ref DistMap object.
1.315 + template<class T>
1.316 + DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.317 + {
1.318 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.319 + return DfsWizard<SetDistMapBase<T> >(*this);
1.320 + }
1.321 +
1.322 + template<class T>
1.323 struct SetProcessedMapBase : public Base {
1.324 typedef T ProcessedMap;
1.325 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.326 SetProcessedMapBase(const TR &b) : TR(b) {}
1.327 };
1.328 - ///\brief \ref named-templ-param "Named parameter"
1.329 + ///\brief \ref named-func-param "Named parameter"
1.330 ///for setting \ref ProcessedMap object.
1.331 ///
1.332 - /// \ref named-templ-param "Named parameter"
1.333 + /// \ref named-func-param "Named parameter"
1.334 ///for setting \ref ProcessedMap object.
1.335 template<class T>
1.336 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.337 @@ -1053,47 +1078,60 @@
1.338 }
1.339
1.340 template<class T>
1.341 - struct SetDistMapBase : public Base {
1.342 - typedef T DistMap;
1.343 - static DistMap *createDistMap(const Digraph &) { return 0; };
1.344 - SetDistMapBase(const TR &b) : TR(b) {}
1.345 + struct SetPathBase : public Base {
1.346 + typedef T Path;
1.347 + SetPathBase(const TR &b) : TR(b) {}
1.348 };
1.349 - ///\brief \ref named-templ-param "Named parameter"
1.350 - ///for setting \ref DistMap object.
1.351 + ///\brief \ref named-func-param "Named parameter"
1.352 + ///for getting the DFS path to the target node.
1.353 ///
1.354 - ///\ref named-templ-param "Named parameter"
1.355 - ///for setting \ref DistMap object.
1.356 + ///\ref named-func-param "Named parameter"
1.357 + ///for getting the DFS path to the target node.
1.358 template<class T>
1.359 - DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.360 + DfsWizard<SetPathBase<T> > path(const T &t)
1.361 {
1.362 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.363 - return DfsWizard<SetDistMapBase<T> >(*this);
1.364 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1.365 + return DfsWizard<SetPathBase<T> >(*this);
1.366 + }
1.367 +
1.368 + ///\brief \ref named-func-param "Named parameter"
1.369 + ///for getting the distance of the target node.
1.370 + ///
1.371 + ///\ref named-func-param "Named parameter"
1.372 + ///for getting the distance of the target node.
1.373 + DfsWizard dist(const int &d)
1.374 + {
1.375 + Base::_di=const_cast<int*>(&d);
1.376 + return *this;
1.377 }
1.378
1.379 };
1.380
1.381 - ///Function type interface for Dfs algorithm.
1.382 + ///Function-type interface for DFS algorithm.
1.383
1.384 ///\ingroup search
1.385 - ///Function type interface for Dfs algorithm.
1.386 + ///Function-type interface for DFS algorithm.
1.387 ///
1.388 - ///This function also has several
1.389 - ///\ref named-templ-func-param "named parameters",
1.390 + ///This function also has several \ref named-func-param "named parameters",
1.391 ///they are declared as the members of class \ref DfsWizard.
1.392 - ///The following
1.393 - ///example shows how to use these parameters.
1.394 + ///The following examples show how to use these parameters.
1.395 ///\code
1.396 - /// dfs(g,source).predMap(preds).run();
1.397 + /// // Compute the DFS tree
1.398 + /// dfs(g).predMap(preds).distMap(dists).run(s);
1.399 + ///
1.400 + /// // Compute the DFS path from s to t
1.401 + /// bool reached = dfs(g).path(p).dist(d).run(s,t);
1.402 ///\endcode
1.403 +
1.404 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.405 ///to the end of the parameter list.
1.406 ///\sa DfsWizard
1.407 ///\sa Dfs
1.408 template<class GR>
1.409 DfsWizard<DfsWizardBase<GR> >
1.410 - dfs(const GR &g,typename GR::Node s=INVALID)
1.411 + dfs(const GR &digraph)
1.412 {
1.413 - return DfsWizard<DfsWizardBase<GR> >(g,s);
1.414 + return DfsWizard<DfsWizardBase<GR> >(digraph);
1.415 }
1.416
1.417 #ifdef DOXYGEN