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