1.1 --- a/lemon/bfs.h Thu Sep 11 11:10:44 2008 +0100
1.2 +++ b/lemon/bfs.h Mon Sep 22 15:33:23 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 @@ -115,7 +116,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 @@ -841,26 +842,23 @@
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 ///\todo The digraph alone may be insufficient to initialize
1.32 -#ifdef DOXYGEN
1.33 static PredMap *createPredMap(const Digraph &g)
1.34 -#else
1.35 - static PredMap *createPredMap(const Digraph &)
1.36 -#endif
1.37 {
1.38 - return new PredMap();
1.39 + return new PredMap(g);
1.40 }
1.41
1.42 ///The type of the map that indicates which nodes are processed.
1.43
1.44 ///The type of the map that indicates which nodes are processed.
1.45 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.46 + ///By default it is a NullMap.
1.47 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.48 ///Instantiates a \ref ProcessedMap.
1.49
1.50 @@ -895,21 +893,22 @@
1.51
1.52 ///The type of the map that stores the distances of the nodes.
1.53 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.54 - ///
1.55 - typedef NullMap<typename Digraph::Node,int> DistMap;
1.56 + typedef typename Digraph::template NodeMap<int> DistMap;
1.57 ///Instantiates a \ref DistMap.
1.58
1.59 ///This function instantiates a \ref DistMap.
1.60 ///\param g is the digraph, to which we would like to define
1.61 ///the \ref DistMap
1.62 -#ifdef DOXYGEN
1.63 static DistMap *createDistMap(const Digraph &g)
1.64 -#else
1.65 - static DistMap *createDistMap(const Digraph &)
1.66 -#endif
1.67 {
1.68 - return new DistMap();
1.69 + return new DistMap(g);
1.70 }
1.71 +
1.72 + ///The type of the shortest paths.
1.73 +
1.74 + ///The type of the shortest paths.
1.75 + ///It must meet the \ref concepts::Path "Path" concept.
1.76 + typedef lemon::Path<Digraph> Path;
1.77 };
1.78
1.79 /// Default traits class used by \ref BfsWizard
1.80 @@ -939,51 +938,39 @@
1.81 void *_pred;
1.82 //Pointer to the map of distances.
1.83 void *_dist;
1.84 - //Pointer to the source node.
1.85 - Node _source;
1.86 + //Pointer to the shortest path to the target node.
1.87 + void *_path;
1.88 + //Pointer to the distance of the target node.
1.89 + int *_di;
1.90
1.91 public:
1.92 /// Constructor.
1.93
1.94 /// This constructor does not require parameters, therefore it initiates
1.95 - /// all of the attributes to default values (0, INVALID).
1.96 + /// all of the attributes to \c 0.
1.97 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.98 - _dist(0), _source(INVALID) {}
1.99 + _dist(0), _path(0), _di(0) {}
1.100
1.101 /// Constructor.
1.102
1.103 - /// This constructor requires some parameters,
1.104 - /// listed in the parameters list.
1.105 - /// Others are initiated to 0.
1.106 + /// This constructor requires one parameter,
1.107 + /// others are initiated to \c 0.
1.108 /// \param g The digraph the algorithm runs on.
1.109 - /// \param s The source node.
1.110 - BfsWizardBase(const GR &g, Node s=INVALID) :
1.111 + BfsWizardBase(const GR &g) :
1.112 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.113 - _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.114 + _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.115
1.116 };
1.117
1.118 - /// Auxiliary class for the function type interface of BFS algorithm.
1.119 + /// Auxiliary class for the function-type interface of BFS algorithm.
1.120
1.121 - /// This auxiliary class is created to implement the function type
1.122 - /// interface of \ref Bfs algorithm. It uses the functions and features
1.123 - /// of the plain \ref Bfs, but it is much simpler to use it.
1.124 - /// It should only be used through the \ref bfs() function, which makes
1.125 - /// it easier to use the algorithm.
1.126 + /// This auxiliary class is created to implement the
1.127 + /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
1.128 + /// It does not have own \ref run() method, it uses the functions
1.129 + /// and features of the plain \ref Bfs.
1.130 ///
1.131 - /// Simplicity means that the way to change the types defined
1.132 - /// in the traits class is based on functions that returns the new class
1.133 - /// and not on templatable built-in classes.
1.134 - /// When using the plain \ref Bfs
1.135 - /// the new class with the modified type comes from
1.136 - /// the original class by using the ::
1.137 - /// operator. In the case of \ref BfsWizard only
1.138 - /// a function have to be called, and it will
1.139 - /// return the needed class.
1.140 - ///
1.141 - /// It does not have own \ref run() method. When its \ref run() method
1.142 - /// is called, it initiates a plain \ref Bfs object, and calls the
1.143 - /// \ref Bfs::run() method of it.
1.144 + /// This class should only be used through the \ref bfs() function,
1.145 + /// which makes it easier to use the algorithm.
1.146 template<class TR>
1.147 class BfsWizard : public TR
1.148 {
1.149 @@ -1006,6 +993,8 @@
1.150 typedef typename TR::ReachedMap ReachedMap;
1.151 ///\brief The type of the map that indicates which nodes are processed.
1.152 typedef typename TR::ProcessedMap ProcessedMap;
1.153 + ///The type of the shortest paths
1.154 + typedef typename TR::Path Path;
1.155
1.156 public:
1.157
1.158 @@ -1016,51 +1005,70 @@
1.159
1.160 /// Constructor that requires parameters.
1.161 /// These parameters will be the default values for the traits class.
1.162 - BfsWizard(const Digraph &g, Node s=INVALID) :
1.163 - TR(g,s) {}
1.164 + /// \param g The digraph the algorithm runs on.
1.165 + BfsWizard(const Digraph &g) :
1.166 + TR(g) {}
1.167
1.168 ///Copy constructor
1.169 BfsWizard(const TR &b) : TR(b) {}
1.170
1.171 ~BfsWizard() {}
1.172
1.173 - ///Runs BFS algorithm from a source node.
1.174 + ///Runs BFS algorithm from the given source node.
1.175
1.176 - ///Runs BFS algorithm from a source node.
1.177 - ///The node can be given with the \ref source() function.
1.178 + ///This method runs BFS algorithm from node \c s
1.179 + ///in order to compute the shortest path to each node.
1.180 + void run(Node s)
1.181 + {
1.182 + Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.183 + if (Base::_pred)
1.184 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.185 + if (Base::_dist)
1.186 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.187 + if (Base::_reached)
1.188 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.189 + if (Base::_processed)
1.190 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.191 + if (s!=INVALID)
1.192 + alg.run(s);
1.193 + else
1.194 + alg.run();
1.195 + }
1.196 +
1.197 + ///Finds the shortest path between \c s and \c t.
1.198 +
1.199 + ///This method runs BFS algorithm from node \c s
1.200 + ///in order to compute the shortest path to node \c t
1.201 + ///(it stops searching when \c t is processed).
1.202 + ///
1.203 + ///\return \c true if \c t is reachable form \c s.
1.204 + bool run(Node s, Node t)
1.205 + {
1.206 + if (s==INVALID || t==INVALID) throw UninitializedParameter();
1.207 + Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.208 + if (Base::_pred)
1.209 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.210 + if (Base::_dist)
1.211 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.212 + if (Base::_reached)
1.213 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.214 + if (Base::_processed)
1.215 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.216 + alg.run(s,t);
1.217 + if (Base::_path)
1.218 + *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
1.219 + if (Base::_di)
1.220 + *Base::_di = alg.dist(t);
1.221 + return alg.reached(t);
1.222 + }
1.223 +
1.224 + ///Runs BFS algorithm to visit all nodes in the digraph.
1.225 +
1.226 + ///This method runs BFS algorithm in order to compute
1.227 + ///the shortest path to each node.
1.228 void run()
1.229 {
1.230 - if(Base::_source==INVALID) throw UninitializedParameter();
1.231 - Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.232 - if(Base::_reached)
1.233 - alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.234 - if(Base::_processed)
1.235 - alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.236 - if(Base::_pred)
1.237 - alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.238 - if(Base::_dist)
1.239 - alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.240 - alg.run(Base::_source);
1.241 - }
1.242 -
1.243 - ///Runs BFS algorithm from the given node.
1.244 -
1.245 - ///Runs BFS algorithm from the given node.
1.246 - ///\param s is the given source.
1.247 - void run(Node s)
1.248 - {
1.249 - Base::_source=s;
1.250 - run();
1.251 - }
1.252 -
1.253 - /// Sets the source node, from which the Bfs algorithm runs.
1.254 -
1.255 - /// Sets the source node, from which the Bfs algorithm runs.
1.256 - /// \param s is the source node.
1.257 - BfsWizard<TR> &source(Node s)
1.258 - {
1.259 - Base::_source=s;
1.260 - return *this;
1.261 + run(INVALID);
1.262 }
1.263
1.264 template<class T>
1.265 @@ -1069,10 +1077,10 @@
1.266 static PredMap *createPredMap(const Digraph &) { return 0; };
1.267 SetPredMapBase(const TR &b) : TR(b) {}
1.268 };
1.269 - ///\brief \ref named-templ-param "Named parameter"
1.270 + ///\brief \ref named-func-param "Named parameter"
1.271 ///for setting \ref PredMap object.
1.272 ///
1.273 - /// \ref named-templ-param "Named parameter"
1.274 + ///\ref named-func-param "Named parameter"
1.275 ///for setting \ref PredMap object.
1.276 template<class T>
1.277 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.278 @@ -1087,10 +1095,10 @@
1.279 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.280 SetReachedMapBase(const TR &b) : TR(b) {}
1.281 };
1.282 - ///\brief \ref named-templ-param "Named parameter"
1.283 + ///\brief \ref named-func-param "Named parameter"
1.284 ///for setting \ref ReachedMap object.
1.285 ///
1.286 - /// \ref named-templ-param "Named parameter"
1.287 + /// \ref named-func-param "Named parameter"
1.288 ///for setting \ref ReachedMap object.
1.289 template<class T>
1.290 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.291 @@ -1100,15 +1108,33 @@
1.292 }
1.293
1.294 template<class T>
1.295 + struct SetDistMapBase : public Base {
1.296 + typedef T DistMap;
1.297 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.298 + SetDistMapBase(const TR &b) : TR(b) {}
1.299 + };
1.300 + ///\brief \ref named-func-param "Named parameter"
1.301 + ///for setting \ref DistMap object.
1.302 + ///
1.303 + /// \ref named-func-param "Named parameter"
1.304 + ///for setting \ref DistMap object.
1.305 + template<class T>
1.306 + BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.307 + {
1.308 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.309 + return BfsWizard<SetDistMapBase<T> >(*this);
1.310 + }
1.311 +
1.312 + template<class T>
1.313 struct SetProcessedMapBase : public Base {
1.314 typedef T ProcessedMap;
1.315 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.316 SetProcessedMapBase(const TR &b) : TR(b) {}
1.317 };
1.318 - ///\brief \ref named-templ-param "Named parameter"
1.319 + ///\brief \ref named-func-param "Named parameter"
1.320 ///for setting \ref ProcessedMap object.
1.321 ///
1.322 - /// \ref named-templ-param "Named parameter"
1.323 + /// \ref named-func-param "Named parameter"
1.324 ///for setting \ref ProcessedMap object.
1.325 template<class T>
1.326 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.327 @@ -1118,37 +1144,49 @@
1.328 }
1.329
1.330 template<class T>
1.331 - struct SetDistMapBase : public Base {
1.332 - typedef T DistMap;
1.333 - static DistMap *createDistMap(const Digraph &) { return 0; };
1.334 - SetDistMapBase(const TR &b) : TR(b) {}
1.335 + struct SetPathBase : public Base {
1.336 + typedef T Path;
1.337 + SetPathBase(const TR &b) : TR(b) {}
1.338 };
1.339 - ///\brief \ref named-templ-param "Named parameter"
1.340 - ///for setting \ref DistMap object.
1.341 + ///\brief \ref named-func-param "Named parameter"
1.342 + ///for getting the shortest path to the target node.
1.343 ///
1.344 - /// \ref named-templ-param "Named parameter"
1.345 - ///for setting \ref DistMap object.
1.346 + ///\ref named-func-param "Named parameter"
1.347 + ///for getting the shortest path to the target node.
1.348 template<class T>
1.349 - BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.350 + BfsWizard<SetPathBase<T> > path(const T &t)
1.351 {
1.352 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.353 - return BfsWizard<SetDistMapBase<T> >(*this);
1.354 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1.355 + return BfsWizard<SetPathBase<T> >(*this);
1.356 + }
1.357 +
1.358 + ///\brief \ref named-func-param "Named parameter"
1.359 + ///for getting the distance of the target node.
1.360 + ///
1.361 + ///\ref named-func-param "Named parameter"
1.362 + ///for getting the distance of the target node.
1.363 + BfsWizard dist(const int &d)
1.364 + {
1.365 + Base::_di=const_cast<int*>(&d);
1.366 + return *this;
1.367 }
1.368
1.369 };
1.370
1.371 - ///Function type interface for Bfs algorithm.
1.372 + ///Function-type interface for BFS algorithm.
1.373
1.374 /// \ingroup search
1.375 - ///Function type interface for Bfs algorithm.
1.376 + ///Function-type interface for BFS algorithm.
1.377 ///
1.378 - ///This function also has several
1.379 - ///\ref named-templ-func-param "named parameters",
1.380 + ///This function also has several \ref named-func-param "named parameters",
1.381 ///they are declared as the members of class \ref BfsWizard.
1.382 - ///The following
1.383 - ///example shows how to use these parameters.
1.384 + ///The following examples show how to use these parameters.
1.385 ///\code
1.386 - /// bfs(g,source).predMap(preds).run();
1.387 + /// // Compute shortest path from node s to each node
1.388 + /// bfs(g).predMap(preds).distMap(dists).run(s);
1.389 + ///
1.390 + /// // Compute shortest path from s to t
1.391 + /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1.392 ///\endcode
1.393 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.394 ///to the end of the parameter list.
1.395 @@ -1156,9 +1194,9 @@
1.396 ///\sa Bfs
1.397 template<class GR>
1.398 BfsWizard<BfsWizardBase<GR> >
1.399 - bfs(const GR &g,typename GR::Node s=INVALID)
1.400 + bfs(const GR &digraph)
1.401 {
1.402 - return BfsWizard<BfsWizardBase<GR> >(g,s);
1.403 + return BfsWizard<BfsWizardBase<GR> >(digraph);
1.404 }
1.405
1.406 #ifdef DOXYGEN
2.1 --- a/lemon/concepts/path.h Thu Sep 11 11:10:44 2008 +0100
2.2 +++ b/lemon/concepts/path.h Mon Sep 22 15:33:23 2008 +0200
2.3 @@ -66,7 +66,10 @@
2.4
2.5 /// \brief Template assigment
2.6 template <typename CPath>
2.7 - Path& operator=(const CPath& cpath) {}
2.8 + Path& operator=(const CPath& cpath) {
2.9 + ignore_unused_variable_warning(cpath);
2.10 + return *this;
2.11 + }
2.12
2.13 /// Length of the path ie. the number of arcs in the path.
2.14 int length() const { return 0;}
3.1 --- a/lemon/dfs.h Thu Sep 11 11:10:44 2008 +0100
3.2 +++ b/lemon/dfs.h Mon Sep 22 15:33:23 2008 +0200
3.3 @@ -29,6 +29,7 @@
3.4 #include <lemon/error.h>
3.5 #include <lemon/assert.h>
3.6 #include <lemon/maps.h>
3.7 +#include <lemon/path.h>
3.8
3.9 namespace lemon {
3.10
3.11 @@ -116,7 +117,7 @@
3.12 ///\ingroup search
3.13 ///This class provides an efficient implementation of the %DFS algorithm.
3.14 ///
3.15 - ///There is also a \ref dfs() "function type interface" for the DFS
3.16 + ///There is also a \ref dfs() "function-type interface" for the DFS
3.17 ///algorithm, which is convenient in the simplier cases and it can be
3.18 ///used easier.
3.19 ///
3.20 @@ -775,27 +776,23 @@
3.21 ///The type of the map that stores the predecessor
3.22 ///arcs of the %DFS paths.
3.23 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.24 - ///
3.25 - typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
3.26 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
3.27 ///Instantiates a \ref PredMap.
3.28
3.29 ///This function instantiates a \ref PredMap.
3.30 ///\param g is the digraph, to which we would like to define the
3.31 ///\ref PredMap.
3.32 ///\todo The digraph alone may be insufficient to initialize
3.33 -#ifdef DOXYGEN
3.34 static PredMap *createPredMap(const Digraph &g)
3.35 -#else
3.36 - static PredMap *createPredMap(const Digraph &)
3.37 -#endif
3.38 {
3.39 - return new PredMap();
3.40 + return new PredMap(g);
3.41 }
3.42
3.43 ///The type of the map that indicates which nodes are processed.
3.44
3.45 ///The type of the map that indicates which nodes are processed.
3.46 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.47 + ///By default it is a NullMap.
3.48 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
3.49 ///Instantiates a \ref ProcessedMap.
3.50
3.51 @@ -830,21 +827,22 @@
3.52
3.53 ///The type of the map that stores the distances of the nodes.
3.54 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.55 - ///
3.56 - typedef NullMap<typename Digraph::Node,int> DistMap;
3.57 + typedef typename Digraph::template NodeMap<int> DistMap;
3.58 ///Instantiates a \ref DistMap.
3.59
3.60 ///This function instantiates a \ref DistMap.
3.61 ///\param g is the digraph, to which we would like to define
3.62 ///the \ref DistMap
3.63 -#ifdef DOXYGEN
3.64 static DistMap *createDistMap(const Digraph &g)
3.65 -#else
3.66 - static DistMap *createDistMap(const Digraph &)
3.67 -#endif
3.68 {
3.69 - return new DistMap();
3.70 + return new DistMap(g);
3.71 }
3.72 +
3.73 + ///The type of the DFS paths.
3.74 +
3.75 + ///The type of the DFS paths.
3.76 + ///It must meet the \ref concepts::Path "Path" concept.
3.77 + typedef lemon::Path<Digraph> Path;
3.78 };
3.79
3.80 /// Default traits class used by \ref DfsWizard
3.81 @@ -874,51 +872,39 @@
3.82 void *_pred;
3.83 //Pointer to the map of distances.
3.84 void *_dist;
3.85 - //Pointer to the source node.
3.86 - Node _source;
3.87 + //Pointer to the DFS path to the target node.
3.88 + void *_path;
3.89 + //Pointer to the distance of the target node.
3.90 + int *_di;
3.91
3.92 public:
3.93 /// Constructor.
3.94
3.95 /// This constructor does not require parameters, therefore it initiates
3.96 - /// all of the attributes to default values (0, INVALID).
3.97 + /// all of the attributes to \c 0.
3.98 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
3.99 - _dist(0), _source(INVALID) {}
3.100 + _dist(0), _path(0), _di(0) {}
3.101
3.102 /// Constructor.
3.103
3.104 - /// This constructor requires some parameters,
3.105 - /// listed in the parameters list.
3.106 - /// Others are initiated to 0.
3.107 + /// This constructor requires one parameter,
3.108 + /// others are initiated to \c 0.
3.109 /// \param g The digraph the algorithm runs on.
3.110 - /// \param s The source node.
3.111 - DfsWizardBase(const GR &g, Node s=INVALID) :
3.112 + DfsWizardBase(const GR &g) :
3.113 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
3.114 - _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
3.115 + _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
3.116
3.117 };
3.118
3.119 - /// Auxiliary class for the function type interface of DFS algorithm.
3.120 + /// Auxiliary class for the function-type interface of DFS algorithm.
3.121
3.122 - /// This auxiliary class is created to implement the function type
3.123 - /// interface of \ref Dfs algorithm. It uses the functions and features
3.124 - /// of the plain \ref Dfs, but it is much simpler to use it.
3.125 - /// It should only be used through the \ref dfs() function, which makes
3.126 - /// it easier to use the algorithm.
3.127 + /// This auxiliary class is created to implement the
3.128 + /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
3.129 + /// It does not have own \ref run() method, it uses the functions
3.130 + /// and features of the plain \ref Dfs.
3.131 ///
3.132 - /// Simplicity means that the way to change the types defined
3.133 - /// in the traits class is based on functions that returns the new class
3.134 - /// and not on templatable built-in classes.
3.135 - /// When using the plain \ref Dfs
3.136 - /// the new class with the modified type comes from
3.137 - /// the original class by using the ::
3.138 - /// operator. In the case of \ref DfsWizard only
3.139 - /// a function have to be called, and it will
3.140 - /// return the needed class.
3.141 - ///
3.142 - /// It does not have own \ref run() method. When its \ref run() method
3.143 - /// is called, it initiates a plain \ref Dfs object, and calls the
3.144 - /// \ref Dfs::run() method of it.
3.145 + /// This class should only be used through the \ref dfs() function,
3.146 + /// which makes it easier to use the algorithm.
3.147 template<class TR>
3.148 class DfsWizard : public TR
3.149 {
3.150 @@ -933,7 +919,7 @@
3.151 typedef typename Digraph::OutArcIt OutArcIt;
3.152
3.153 ///\brief The type of the map that stores the predecessor
3.154 - ///arcs of the shortest paths.
3.155 + ///arcs of the DFS paths.
3.156 typedef typename TR::PredMap PredMap;
3.157 ///\brief The type of the map that stores the distances of the nodes.
3.158 typedef typename TR::DistMap DistMap;
3.159 @@ -941,6 +927,8 @@
3.160 typedef typename TR::ReachedMap ReachedMap;
3.161 ///\brief The type of the map that indicates which nodes are processed.
3.162 typedef typename TR::ProcessedMap ProcessedMap;
3.163 + ///The type of the DFS paths
3.164 + typedef typename TR::Path Path;
3.165
3.166 public:
3.167
3.168 @@ -951,51 +939,70 @@
3.169
3.170 /// Constructor that requires parameters.
3.171 /// These parameters will be the default values for the traits class.
3.172 - DfsWizard(const Digraph &g, Node s=INVALID) :
3.173 - TR(g,s) {}
3.174 + /// \param g The digraph the algorithm runs on.
3.175 + DfsWizard(const Digraph &g) :
3.176 + TR(g) {}
3.177
3.178 ///Copy constructor
3.179 DfsWizard(const TR &b) : TR(b) {}
3.180
3.181 ~DfsWizard() {}
3.182
3.183 - ///Runs DFS algorithm from a source node.
3.184 + ///Runs DFS algorithm from the given source node.
3.185
3.186 - ///Runs DFS algorithm from a source node.
3.187 - ///The node can be given with the \ref source() function.
3.188 + ///This method runs DFS algorithm from node \c s
3.189 + ///in order to compute the DFS path to each node.
3.190 + void run(Node s)
3.191 + {
3.192 + Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
3.193 + if (Base::_pred)
3.194 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
3.195 + if (Base::_dist)
3.196 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
3.197 + if (Base::_reached)
3.198 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
3.199 + if (Base::_processed)
3.200 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
3.201 + if (s!=INVALID)
3.202 + alg.run(s);
3.203 + else
3.204 + alg.run();
3.205 + }
3.206 +
3.207 + ///Finds the DFS path between \c s and \c t.
3.208 +
3.209 + ///This method runs DFS algorithm from node \c s
3.210 + ///in order to compute the DFS path to node \c t
3.211 + ///(it stops searching when \c t is processed).
3.212 + ///
3.213 + ///\return \c true if \c t is reachable form \c s.
3.214 + bool run(Node s, Node t)
3.215 + {
3.216 + if (s==INVALID || t==INVALID) throw UninitializedParameter();
3.217 + Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
3.218 + if (Base::_pred)
3.219 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
3.220 + if (Base::_dist)
3.221 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
3.222 + if (Base::_reached)
3.223 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
3.224 + if (Base::_processed)
3.225 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
3.226 + alg.run(s,t);
3.227 + if (Base::_path)
3.228 + *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
3.229 + if (Base::_di)
3.230 + *Base::_di = alg.dist(t);
3.231 + return alg.reached(t);
3.232 + }
3.233 +
3.234 + ///Runs DFS algorithm to visit all nodes in the digraph.
3.235 +
3.236 + ///This method runs DFS algorithm in order to compute
3.237 + ///the DFS path to each node.
3.238 void run()
3.239 {
3.240 - if(Base::_source==INVALID) throw UninitializedParameter();
3.241 - Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
3.242 - if(Base::_reached)
3.243 - alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
3.244 - if(Base::_processed)
3.245 - alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
3.246 - if(Base::_pred)
3.247 - alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
3.248 - if(Base::_dist)
3.249 - alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
3.250 - alg.run(Base::_source);
3.251 - }
3.252 -
3.253 - ///Runs DFS algorithm from the given node.
3.254 -
3.255 - ///Runs DFS algorithm from the given node.
3.256 - ///\param s is the given source.
3.257 - void run(Node s)
3.258 - {
3.259 - Base::_source=s;
3.260 - run();
3.261 - }
3.262 -
3.263 - /// Sets the source node, from which the Dfs algorithm runs.
3.264 -
3.265 - /// Sets the source node, from which the Dfs algorithm runs.
3.266 - /// \param s is the source node.
3.267 - DfsWizard<TR> &source(Node s)
3.268 - {
3.269 - Base::_source=s;
3.270 - return *this;
3.271 + run(INVALID);
3.272 }
3.273
3.274 template<class T>
3.275 @@ -1004,10 +1011,10 @@
3.276 static PredMap *createPredMap(const Digraph &) { return 0; };
3.277 SetPredMapBase(const TR &b) : TR(b) {}
3.278 };
3.279 - ///\brief \ref named-templ-param "Named parameter"
3.280 + ///\brief \ref named-func-param "Named parameter"
3.281 ///for setting \ref PredMap object.
3.282 ///
3.283 - ///\ref named-templ-param "Named parameter"
3.284 + ///\ref named-func-param "Named parameter"
3.285 ///for setting \ref PredMap object.
3.286 template<class T>
3.287 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
3.288 @@ -1022,10 +1029,10 @@
3.289 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
3.290 SetReachedMapBase(const TR &b) : TR(b) {}
3.291 };
3.292 - ///\brief \ref named-templ-param "Named parameter"
3.293 + ///\brief \ref named-func-param "Named parameter"
3.294 ///for setting \ref ReachedMap object.
3.295 ///
3.296 - /// \ref named-templ-param "Named parameter"
3.297 + /// \ref named-func-param "Named parameter"
3.298 ///for setting \ref ReachedMap object.
3.299 template<class T>
3.300 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
3.301 @@ -1035,15 +1042,33 @@
3.302 }
3.303
3.304 template<class T>
3.305 + struct SetDistMapBase : public Base {
3.306 + typedef T DistMap;
3.307 + static DistMap *createDistMap(const Digraph &) { return 0; };
3.308 + SetDistMapBase(const TR &b) : TR(b) {}
3.309 + };
3.310 + ///\brief \ref named-func-param "Named parameter"
3.311 + ///for setting \ref DistMap object.
3.312 + ///
3.313 + /// \ref named-func-param "Named parameter"
3.314 + ///for setting \ref DistMap object.
3.315 + template<class T>
3.316 + DfsWizard<SetDistMapBase<T> > distMap(const T &t)
3.317 + {
3.318 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
3.319 + return DfsWizard<SetDistMapBase<T> >(*this);
3.320 + }
3.321 +
3.322 + template<class T>
3.323 struct SetProcessedMapBase : public Base {
3.324 typedef T ProcessedMap;
3.325 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
3.326 SetProcessedMapBase(const TR &b) : TR(b) {}
3.327 };
3.328 - ///\brief \ref named-templ-param "Named parameter"
3.329 + ///\brief \ref named-func-param "Named parameter"
3.330 ///for setting \ref ProcessedMap object.
3.331 ///
3.332 - /// \ref named-templ-param "Named parameter"
3.333 + /// \ref named-func-param "Named parameter"
3.334 ///for setting \ref ProcessedMap object.
3.335 template<class T>
3.336 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
3.337 @@ -1053,47 +1078,60 @@
3.338 }
3.339
3.340 template<class T>
3.341 - struct SetDistMapBase : public Base {
3.342 - typedef T DistMap;
3.343 - static DistMap *createDistMap(const Digraph &) { return 0; };
3.344 - SetDistMapBase(const TR &b) : TR(b) {}
3.345 + struct SetPathBase : public Base {
3.346 + typedef T Path;
3.347 + SetPathBase(const TR &b) : TR(b) {}
3.348 };
3.349 - ///\brief \ref named-templ-param "Named parameter"
3.350 - ///for setting \ref DistMap object.
3.351 + ///\brief \ref named-func-param "Named parameter"
3.352 + ///for getting the DFS path to the target node.
3.353 ///
3.354 - ///\ref named-templ-param "Named parameter"
3.355 - ///for setting \ref DistMap object.
3.356 + ///\ref named-func-param "Named parameter"
3.357 + ///for getting the DFS path to the target node.
3.358 template<class T>
3.359 - DfsWizard<SetDistMapBase<T> > distMap(const T &t)
3.360 + DfsWizard<SetPathBase<T> > path(const T &t)
3.361 {
3.362 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
3.363 - return DfsWizard<SetDistMapBase<T> >(*this);
3.364 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
3.365 + return DfsWizard<SetPathBase<T> >(*this);
3.366 + }
3.367 +
3.368 + ///\brief \ref named-func-param "Named parameter"
3.369 + ///for getting the distance of the target node.
3.370 + ///
3.371 + ///\ref named-func-param "Named parameter"
3.372 + ///for getting the distance of the target node.
3.373 + DfsWizard dist(const int &d)
3.374 + {
3.375 + Base::_di=const_cast<int*>(&d);
3.376 + return *this;
3.377 }
3.378
3.379 };
3.380
3.381 - ///Function type interface for Dfs algorithm.
3.382 + ///Function-type interface for DFS algorithm.
3.383
3.384 ///\ingroup search
3.385 - ///Function type interface for Dfs algorithm.
3.386 + ///Function-type interface for DFS algorithm.
3.387 ///
3.388 - ///This function also has several
3.389 - ///\ref named-templ-func-param "named parameters",
3.390 + ///This function also has several \ref named-func-param "named parameters",
3.391 ///they are declared as the members of class \ref DfsWizard.
3.392 - ///The following
3.393 - ///example shows how to use these parameters.
3.394 + ///The following examples show how to use these parameters.
3.395 ///\code
3.396 - /// dfs(g,source).predMap(preds).run();
3.397 + /// // Compute the DFS tree
3.398 + /// dfs(g).predMap(preds).distMap(dists).run(s);
3.399 + ///
3.400 + /// // Compute the DFS path from s to t
3.401 + /// bool reached = dfs(g).path(p).dist(d).run(s,t);
3.402 ///\endcode
3.403 +
3.404 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
3.405 ///to the end of the parameter list.
3.406 ///\sa DfsWizard
3.407 ///\sa Dfs
3.408 template<class GR>
3.409 DfsWizard<DfsWizardBase<GR> >
3.410 - dfs(const GR &g,typename GR::Node s=INVALID)
3.411 + dfs(const GR &digraph)
3.412 {
3.413 - return DfsWizard<DfsWizardBase<GR> >(g,s);
3.414 + return DfsWizard<DfsWizardBase<GR> >(digraph);
3.415 }
3.416
3.417 #ifdef DOXYGEN
4.1 --- a/lemon/dijkstra.h Thu Sep 11 11:10:44 2008 +0100
4.2 +++ b/lemon/dijkstra.h Mon Sep 22 15:33:23 2008 +0200
4.3 @@ -30,6 +30,7 @@
4.4 #include <lemon/core.h>
4.5 #include <lemon/error.h>
4.6 #include <lemon/maps.h>
4.7 +#include <lemon/path.h>
4.8
4.9 namespace lemon {
4.10
4.11 @@ -199,7 +200,7 @@
4.12 ///\ref concepts::ReadMap::Value "Value" of the length map.
4.13 ///It is also possible to change the underlying priority heap.
4.14 ///
4.15 - ///There is also a \ref dijkstra() "function type interface" for the
4.16 + ///There is also a \ref dijkstra() "function-type interface" for the
4.17 ///%Dijkstra algorithm, which is convenient in the simplier cases and
4.18 ///it can be used easier.
4.19 ///
4.20 @@ -987,20 +988,16 @@
4.21 ///The type of the map that stores the predecessor
4.22 ///arcs of the shortest paths.
4.23 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
4.24 - typedef NullMap <typename Digraph::Node,typename Digraph::Arc> PredMap;
4.25 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
4.26 ///Instantiates a \ref PredMap.
4.27
4.28 ///This function instantiates a \ref PredMap.
4.29 ///\param g is the digraph, to which we would like to define the
4.30 ///\ref PredMap.
4.31 ///\todo The digraph alone may be insufficient to initialize
4.32 -#ifdef DOXYGEN
4.33 static PredMap *createPredMap(const Digraph &g)
4.34 -#else
4.35 - static PredMap *createPredMap(const Digraph &)
4.36 -#endif
4.37 {
4.38 - return new PredMap();
4.39 + return new PredMap(g);
4.40 }
4.41
4.42 ///The type of the map that indicates which nodes are processed.
4.43 @@ -1030,20 +1027,22 @@
4.44
4.45 ///The type of the map that stores the distances of the nodes.
4.46 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
4.47 - typedef NullMap<typename Digraph::Node,Value> DistMap;
4.48 + typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
4.49 ///Instantiates a \ref DistMap.
4.50
4.51 ///This function instantiates a \ref DistMap.
4.52 ///\param g is the digraph, to which we would like to define
4.53 ///the \ref DistMap
4.54 -#ifdef DOXYGEN
4.55 static DistMap *createDistMap(const Digraph &g)
4.56 -#else
4.57 - static DistMap *createDistMap(const Digraph &)
4.58 -#endif
4.59 {
4.60 - return new DistMap();
4.61 + return new DistMap(g);
4.62 }
4.63 +
4.64 + ///The type of the shortest paths.
4.65 +
4.66 + ///The type of the shortest paths.
4.67 + ///It must meet the \ref concepts::Path "Path" concept.
4.68 + typedef lemon::Path<Digraph> Path;
4.69 };
4.70
4.71 /// Default traits class used by \ref DijkstraWizard
4.72 @@ -1065,7 +1064,7 @@
4.73
4.74 //Pointer to the digraph the algorithm runs on.
4.75 void *_g;
4.76 - //Pointer to the length map
4.77 + //Pointer to the length map.
4.78 void *_length;
4.79 //Pointer to the map of processed nodes.
4.80 void *_processed;
4.81 @@ -1073,53 +1072,41 @@
4.82 void *_pred;
4.83 //Pointer to the map of distances.
4.84 void *_dist;
4.85 - //Pointer to the source node.
4.86 - Node _source;
4.87 + //Pointer to the shortest path to the target node.
4.88 + void *_path;
4.89 + //Pointer to the distance of the target node.
4.90 + void *_di;
4.91
4.92 public:
4.93 /// Constructor.
4.94
4.95 /// This constructor does not require parameters, therefore it initiates
4.96 - /// all of the attributes to default values (0, INVALID).
4.97 + /// all of the attributes to \c 0.
4.98 DijkstraWizardBase() : _g(0), _length(0), _processed(0), _pred(0),
4.99 - _dist(0), _source(INVALID) {}
4.100 + _dist(0), _path(0), _di(0) {}
4.101
4.102 /// Constructor.
4.103
4.104 - /// This constructor requires some parameters,
4.105 - /// listed in the parameters list.
4.106 - /// Others are initiated to 0.
4.107 + /// This constructor requires two parameters,
4.108 + /// others are initiated to \c 0.
4.109 /// \param g The digraph the algorithm runs on.
4.110 /// \param l The length map.
4.111 - /// \param s The source node.
4.112 - DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
4.113 + DijkstraWizardBase(const GR &g,const LM &l) :
4.114 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
4.115 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
4.116 - _processed(0), _pred(0), _dist(0), _source(s) {}
4.117 + _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
4.118
4.119 };
4.120
4.121 - /// Auxiliary class for the function type interface of Dijkstra algorithm.
4.122 + /// Auxiliary class for the function-type interface of Dijkstra algorithm.
4.123
4.124 - /// This auxiliary class is created to implement the function type
4.125 - /// interface of \ref Dijkstra algorithm. It uses the functions and features
4.126 - /// of the plain \ref Dijkstra, but it is much simpler to use it.
4.127 - /// It should only be used through the \ref dijkstra() function, which makes
4.128 - /// it easier to use the algorithm.
4.129 + /// This auxiliary class is created to implement the
4.130 + /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
4.131 + /// It does not have own \ref run() method, it uses the functions
4.132 + /// and features of the plain \ref Dijkstra.
4.133 ///
4.134 - /// Simplicity means that the way to change the types defined
4.135 - /// in the traits class is based on functions that returns the new class
4.136 - /// and not on templatable built-in classes.
4.137 - /// When using the plain \ref Dijkstra
4.138 - /// the new class with the modified type comes from
4.139 - /// the original class by using the ::
4.140 - /// operator. In the case of \ref DijkstraWizard only
4.141 - /// a function have to be called, and it will
4.142 - /// return the needed class.
4.143 - ///
4.144 - /// It does not have own \ref run() method. When its \ref run() method
4.145 - /// is called, it initiates a plain \ref Dijkstra object, and calls the
4.146 - /// \ref Dijkstra::run() method of it.
4.147 + /// This class should only be used through the \ref dijkstra() function,
4.148 + /// which makes it easier to use the algorithm.
4.149 template<class TR>
4.150 class DijkstraWizard : public TR
4.151 {
4.152 @@ -1144,6 +1131,8 @@
4.153 typedef typename TR::DistMap DistMap;
4.154 ///The type of the map that indicates which nodes are processed.
4.155 typedef typename TR::ProcessedMap ProcessedMap;
4.156 + ///The type of the shortest paths
4.157 + typedef typename TR::Path Path;
4.158 ///The heap type used by the dijkstra algorithm.
4.159 typedef typename TR::Heap Heap;
4.160
4.161 @@ -1156,51 +1145,60 @@
4.162
4.163 /// Constructor that requires parameters.
4.164 /// These parameters will be the default values for the traits class.
4.165 - DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
4.166 - TR(g,l,s) {}
4.167 + /// \param g The digraph the algorithm runs on.
4.168 + /// \param l The length map.
4.169 + DijkstraWizard(const Digraph &g, const LengthMap &l) :
4.170 + TR(g,l) {}
4.171
4.172 ///Copy constructor
4.173 DijkstraWizard(const TR &b) : TR(b) {}
4.174
4.175 ~DijkstraWizard() {}
4.176
4.177 - ///Runs Dijkstra algorithm from a source node.
4.178 + ///Runs Dijkstra algorithm from the given source node.
4.179
4.180 - ///Runs Dijkstra algorithm from a source node.
4.181 - ///The node can be given with the \ref source() function.
4.182 - void run()
4.183 + ///This method runs %Dijkstra algorithm from the given source node
4.184 + ///in order to compute the shortest path to each node.
4.185 + void run(Node s)
4.186 {
4.187 - if(Base::_source==INVALID) throw UninitializedParameter();
4.188 + if (s==INVALID) throw UninitializedParameter();
4.189 Dijkstra<Digraph,LengthMap,TR>
4.190 - dij(*reinterpret_cast<const Digraph*>(Base::_g),
4.191 - *reinterpret_cast<const LengthMap*>(Base::_length));
4.192 - if(Base::_processed)
4.193 - dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
4.194 - if(Base::_pred)
4.195 - dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
4.196 - if(Base::_dist)
4.197 - dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
4.198 - dij.run(Base::_source);
4.199 + dijk(*reinterpret_cast<const Digraph*>(Base::_g),
4.200 + *reinterpret_cast<const LengthMap*>(Base::_length));
4.201 + if (Base::_pred)
4.202 + dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
4.203 + if (Base::_dist)
4.204 + dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
4.205 + if (Base::_processed)
4.206 + dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
4.207 + dijk.run(s);
4.208 }
4.209
4.210 - ///Runs Dijkstra algorithm from the given node.
4.211 + ///Finds the shortest path between \c s and \c t.
4.212
4.213 - ///Runs Dijkstra algorithm from the given node.
4.214 - ///\param s is the given source.
4.215 - void run(Node s)
4.216 + ///This method runs the %Dijkstra algorithm from node \c s
4.217 + ///in order to compute the shortest path to node \c t
4.218 + ///(it stops searching when \c t is processed).
4.219 + ///
4.220 + ///\return \c true if \c t is reachable form \c s.
4.221 + bool run(Node s, Node t)
4.222 {
4.223 - Base::_source=s;
4.224 - run();
4.225 - }
4.226 -
4.227 - /// Sets the source node, from which the Dijkstra algorithm runs.
4.228 -
4.229 - /// Sets the source node, from which the Dijkstra algorithm runs.
4.230 - /// \param s is the source node.
4.231 - DijkstraWizard<TR> &source(Node s)
4.232 - {
4.233 - Base::_source=s;
4.234 - return *this;
4.235 + if (s==INVALID || t==INVALID) throw UninitializedParameter();
4.236 + Dijkstra<Digraph,LengthMap,TR>
4.237 + dijk(*reinterpret_cast<const Digraph*>(Base::_g),
4.238 + *reinterpret_cast<const LengthMap*>(Base::_length));
4.239 + if (Base::_pred)
4.240 + dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
4.241 + if (Base::_dist)
4.242 + dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
4.243 + if (Base::_processed)
4.244 + dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
4.245 + dijk.run(s,t);
4.246 + if (Base::_path)
4.247 + *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
4.248 + if (Base::_di)
4.249 + *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
4.250 + return dijk.reached(t);
4.251 }
4.252
4.253 template<class T>
4.254 @@ -1209,10 +1207,10 @@
4.255 static PredMap *createPredMap(const Digraph &) { return 0; };
4.256 SetPredMapBase(const TR &b) : TR(b) {}
4.257 };
4.258 - ///\brief \ref named-templ-param "Named parameter"
4.259 + ///\brief \ref named-func-param "Named parameter"
4.260 ///for setting \ref PredMap object.
4.261 ///
4.262 - ///\ref named-templ-param "Named parameter"
4.263 + ///\ref named-func-param "Named parameter"
4.264 ///for setting \ref PredMap object.
4.265 template<class T>
4.266 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
4.267 @@ -1222,15 +1220,33 @@
4.268 }
4.269
4.270 template<class T>
4.271 + struct SetDistMapBase : public Base {
4.272 + typedef T DistMap;
4.273 + static DistMap *createDistMap(const Digraph &) { return 0; };
4.274 + SetDistMapBase(const TR &b) : TR(b) {}
4.275 + };
4.276 + ///\brief \ref named-func-param "Named parameter"
4.277 + ///for setting \ref DistMap object.
4.278 + ///
4.279 + ///\ref named-func-param "Named parameter"
4.280 + ///for setting \ref DistMap object.
4.281 + template<class T>
4.282 + DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
4.283 + {
4.284 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
4.285 + return DijkstraWizard<SetDistMapBase<T> >(*this);
4.286 + }
4.287 +
4.288 + template<class T>
4.289 struct SetProcessedMapBase : public Base {
4.290 typedef T ProcessedMap;
4.291 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
4.292 SetProcessedMapBase(const TR &b) : TR(b) {}
4.293 };
4.294 - ///\brief \ref named-templ-param "Named parameter"
4.295 + ///\brief \ref named-func-param "Named parameter"
4.296 ///for setting \ref ProcessedMap object.
4.297 ///
4.298 - /// \ref named-templ-param "Named parameter"
4.299 + /// \ref named-func-param "Named parameter"
4.300 ///for setting \ref ProcessedMap object.
4.301 template<class T>
4.302 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
4.303 @@ -1240,37 +1256,49 @@
4.304 }
4.305
4.306 template<class T>
4.307 - struct SetDistMapBase : public Base {
4.308 - typedef T DistMap;
4.309 - static DistMap *createDistMap(const Digraph &) { return 0; };
4.310 - SetDistMapBase(const TR &b) : TR(b) {}
4.311 + struct SetPathBase : public Base {
4.312 + typedef T Path;
4.313 + SetPathBase(const TR &b) : TR(b) {}
4.314 };
4.315 - ///\brief \ref named-templ-param "Named parameter"
4.316 - ///for setting \ref DistMap object.
4.317 + ///\brief \ref named-func-param "Named parameter"
4.318 + ///for getting the shortest path to the target node.
4.319 ///
4.320 - ///\ref named-templ-param "Named parameter"
4.321 - ///for setting \ref DistMap object.
4.322 + ///\ref named-func-param "Named parameter"
4.323 + ///for getting the shortest path to the target node.
4.324 template<class T>
4.325 - DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
4.326 + DijkstraWizard<SetPathBase<T> > path(const T &t)
4.327 {
4.328 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
4.329 - return DijkstraWizard<SetDistMapBase<T> >(*this);
4.330 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
4.331 + return DijkstraWizard<SetPathBase<T> >(*this);
4.332 + }
4.333 +
4.334 + ///\brief \ref named-func-param "Named parameter"
4.335 + ///for getting the distance of the target node.
4.336 + ///
4.337 + ///\ref named-func-param "Named parameter"
4.338 + ///for getting the distance of the target node.
4.339 + DijkstraWizard dist(const Value &d)
4.340 + {
4.341 + Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
4.342 + return *this;
4.343 }
4.344
4.345 };
4.346
4.347 - ///Function type interface for Dijkstra algorithm.
4.348 + ///Function-type interface for Dijkstra algorithm.
4.349
4.350 /// \ingroup shortest_path
4.351 - ///Function type interface for Dijkstra algorithm.
4.352 + ///Function-type interface for Dijkstra algorithm.
4.353 ///
4.354 - ///This function also has several
4.355 - ///\ref named-templ-func-param "named parameters",
4.356 + ///This function also has several \ref named-func-param "named parameters",
4.357 ///they are declared as the members of class \ref DijkstraWizard.
4.358 - ///The following
4.359 - ///example shows how to use these parameters.
4.360 + ///The following examples show how to use these parameters.
4.361 ///\code
4.362 - /// dijkstra(g,length,source).predMap(preds).run();
4.363 + /// // Compute shortest path from node s to each node
4.364 + /// dijkstra(g,length).predMap(preds).distMap(dists).run(s);
4.365 + ///
4.366 + /// // Compute shortest path from s to t
4.367 + /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
4.368 ///\endcode
4.369 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
4.370 ///to the end of the parameter list.
4.371 @@ -1278,9 +1306,9 @@
4.372 ///\sa Dijkstra
4.373 template<class GR, class LM>
4.374 DijkstraWizard<DijkstraWizardBase<GR,LM> >
4.375 - dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
4.376 + dijkstra(const GR &digraph, const LM &length)
4.377 {
4.378 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
4.379 + return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
4.380 }
4.381
4.382 } //END OF NAMESPACE LEMON
5.1 --- a/test/bfs_test.cc Thu Sep 11 11:10:44 2008 +0100
5.2 +++ b/test/bfs_test.cc Mon Sep 22 15:33:23 2008 +0200
5.3 @@ -62,7 +62,6 @@
5.4 bool b;
5.5 BType::DistMap d(G);
5.6 BType::PredMap p(G);
5.7 - // BType::PredNodeMap pn(G);
5.8
5.9 BType bfs_test(G);
5.10
5.11 @@ -72,9 +71,7 @@
5.12 e = bfs_test.predArc(n);
5.13 n = bfs_test.predNode(n);
5.14 d = bfs_test.distMap();
5.15 -
5.16 p = bfs_test.predMap();
5.17 - // pn = bfs_test.predNodeMap();
5.18 b = bfs_test.reached(n);
5.19
5.20 Path<Digraph> pp = bfs_test.path(n);
5.21 @@ -88,14 +85,30 @@
5.22 typedef Digraph::Node Node;
5.23
5.24 Digraph g;
5.25 - bfs(g,Node()).run();
5.26 - bfs(g).source(Node()).run();
5.27 + bool b;
5.28 + bfs(g).run(Node());
5.29 + b=bfs(g).run(Node(),Node());
5.30 + bfs(g).run();
5.31 bfs(g)
5.32 - .predMap(concepts::WriteMap<Node,Arc>())
5.33 - .distMap(concepts::WriteMap<Node,VType>())
5.34 + .predMap(concepts::ReadWriteMap<Node,Arc>())
5.35 + .distMap(concepts::ReadWriteMap<Node,VType>())
5.36 .reachedMap(concepts::ReadWriteMap<Node,bool>())
5.37 .processedMap(concepts::WriteMap<Node,bool>())
5.38 .run(Node());
5.39 + b=bfs(g)
5.40 + .predMap(concepts::ReadWriteMap<Node,Arc>())
5.41 + .distMap(concepts::ReadWriteMap<Node,VType>())
5.42 + .reachedMap(concepts::ReadWriteMap<Node,bool>())
5.43 + .processedMap(concepts::WriteMap<Node,bool>())
5.44 + .path(concepts::Path<Digraph>())
5.45 + .dist(VType())
5.46 + .run(Node(),Node());
5.47 + bfs(g)
5.48 + .predMap(concepts::ReadWriteMap<Node,Arc>())
5.49 + .distMap(concepts::ReadWriteMap<Node,VType>())
5.50 + .reachedMap(concepts::ReadWriteMap<Node,bool>())
5.51 + .processedMap(concepts::WriteMap<Node,bool>())
5.52 + .run();
5.53 }
5.54
5.55 template <class Digraph>
5.56 @@ -114,7 +127,7 @@
5.57 Bfs<Digraph> bfs_test(G);
5.58 bfs_test.run(s);
5.59
5.60 - check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t));
5.61 + check(bfs_test.dist(t)==2,"Bfs found a wrong path.");
5.62
5.63 Path<Digraph> p = bfs_test.path(t);
5.64 check(p.length()==2,"path() found a wrong path.");
5.65 @@ -128,7 +141,7 @@
5.66 Node v=G.target(a);
5.67 check( !bfs_test.reached(u) ||
5.68 (bfs_test.dist(v) <= bfs_test.dist(u)+1),
5.69 - "Wrong output." << G.id(v) << ' ' << G.id(u));
5.70 + "Wrong output. " << G.id(u) << "->" << G.id(v));
5.71 }
5.72
5.73 for(NodeIt v(G); v!=INVALID; ++v) {
5.74 @@ -140,11 +153,15 @@
5.75 check(u==bfs_test.predNode(v),"Wrong tree.");
5.76 check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
5.77 "Wrong distance. Difference: "
5.78 - << std::abs(bfs_test.dist(v) - bfs_test.dist(u)
5.79 - - 1));
5.80 + << std::abs(bfs_test.dist(v) - bfs_test.dist(u) - 1));
5.81 }
5.82 }
5.83 }
5.84 +
5.85 + {
5.86 + NullMap<Node,Arc> myPredMap;
5.87 + bfs(G).predMap(myPredMap).run(s);
5.88 + }
5.89 }
5.90
5.91 int main()
6.1 --- a/test/dfs_test.cc Thu Sep 11 11:10:44 2008 +0100
6.2 +++ b/test/dfs_test.cc Mon Sep 22 15:33:23 2008 +0200
6.3 @@ -20,7 +20,6 @@
6.4 #include <lemon/smart_graph.h>
6.5 #include <lemon/list_graph.h>
6.6 #include <lemon/lgf_reader.h>
6.7 -
6.8 #include <lemon/dfs.h>
6.9 #include <lemon/path.h>
6.10
6.11 @@ -88,14 +87,30 @@
6.12 typedef Digraph::Node Node;
6.13
6.14 Digraph g;
6.15 - dfs(g,Node()).run();
6.16 - dfs(g).source(Node()).run();
6.17 + bool b;
6.18 + dfs(g).run(Node());
6.19 + b=dfs(g).run(Node(),Node());
6.20 + dfs(g).run();
6.21 dfs(g)
6.22 - .predMap(concepts::WriteMap<Node,Arc>())
6.23 - .distMap(concepts::WriteMap<Node,VType>())
6.24 + .predMap(concepts::ReadWriteMap<Node,Arc>())
6.25 + .distMap(concepts::ReadWriteMap<Node,VType>())
6.26 .reachedMap(concepts::ReadWriteMap<Node,bool>())
6.27 .processedMap(concepts::WriteMap<Node,bool>())
6.28 .run(Node());
6.29 + b=dfs(g)
6.30 + .predMap(concepts::ReadWriteMap<Node,Arc>())
6.31 + .distMap(concepts::ReadWriteMap<Node,VType>())
6.32 + .reachedMap(concepts::ReadWriteMap<Node,bool>())
6.33 + .processedMap(concepts::WriteMap<Node,bool>())
6.34 + .path(concepts::Path<Digraph>())
6.35 + .dist(VType())
6.36 + .run(Node(),Node());
6.37 + dfs(g)
6.38 + .predMap(concepts::ReadWriteMap<Node,Arc>())
6.39 + .distMap(concepts::ReadWriteMap<Node,VType>())
6.40 + .reachedMap(concepts::ReadWriteMap<Node,bool>())
6.41 + .processedMap(concepts::WriteMap<Node,bool>())
6.42 + .run();
6.43 }
6.44
6.45 template <class Digraph>
6.46 @@ -129,10 +144,15 @@
6.47 check(u==dfs_test.predNode(v),"Wrong tree.");
6.48 check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
6.49 "Wrong distance. (" << dfs_test.dist(u) << "->"
6.50 - <<dfs_test.dist(v) << ')');
6.51 + << dfs_test.dist(v) << ")");
6.52 }
6.53 }
6.54 }
6.55 +
6.56 + {
6.57 + NullMap<Node,Arc> myPredMap;
6.58 + dfs(G).predMap(myPredMap).run(s);
6.59 + }
6.60 }
6.61
6.62 int main()
7.1 --- a/test/dijkstra_test.cc Thu Sep 11 11:10:44 2008 +0100
7.2 +++ b/test/dijkstra_test.cc Mon Sep 22 15:33:23 2008 +0200
7.3 @@ -20,7 +20,6 @@
7.4 #include <lemon/smart_graph.h>
7.5 #include <lemon/list_graph.h>
7.6 #include <lemon/lgf_reader.h>
7.7 -
7.8 #include <lemon/dijkstra.h>
7.9 #include <lemon/path.h>
7.10
7.11 @@ -64,7 +63,6 @@
7.12 bool b;
7.13 DType::DistMap d(G);
7.14 DType::PredMap p(G);
7.15 - // DType::PredNodeMap pn(G);
7.16 LengthMap length;
7.17
7.18 DType dijkstra_test(G,length);
7.19 @@ -76,7 +74,6 @@
7.20 n = dijkstra_test.predNode(n);
7.21 d = dijkstra_test.distMap();
7.22 p = dijkstra_test.predMap();
7.23 - // pn = dijkstra_test.predNodeMap();
7.24 b = dijkstra_test.reached(n);
7.25
7.26 Path<Digraph> pp = dijkstra_test.path(n);
7.27 @@ -91,12 +88,21 @@
7.28 typedef concepts::ReadMap<Digraph::Arc,VType> LengthMap;
7.29
7.30 Digraph g;
7.31 - dijkstra(g,LengthMap(),Node()).run();
7.32 - dijkstra(g,LengthMap()).source(Node()).run();
7.33 + bool b;
7.34 + dijkstra(g,LengthMap()).run(Node());
7.35 + b=dijkstra(g,LengthMap()).run(Node(),Node());
7.36 dijkstra(g,LengthMap())
7.37 - .predMap(concepts::WriteMap<Node,Arc>())
7.38 - .distMap(concepts::WriteMap<Node,VType>())
7.39 + .predMap(concepts::ReadWriteMap<Node,Arc>())
7.40 + .distMap(concepts::ReadWriteMap<Node,VType>())
7.41 + .processedMap(concepts::WriteMap<Node,bool>())
7.42 .run(Node());
7.43 + b=dijkstra(g,LengthMap())
7.44 + .predMap(concepts::ReadWriteMap<Node,Arc>())
7.45 + .distMap(concepts::ReadWriteMap<Node,VType>())
7.46 + .processedMap(concepts::WriteMap<Node,bool>())
7.47 + .path(concepts::Path<Digraph>())
7.48 + .dist(VType())
7.49 + .run(Node(),Node());
7.50 }
7.51
7.52 template <class Digraph>
7.53 @@ -122,7 +128,7 @@
7.54 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path.");
7.55
7.56 Path<Digraph> p = dijkstra_test.path(t);
7.57 - check(p.length()==3,"getPath() found a wrong path.");
7.58 + check(p.length()==3,"path() found a wrong path.");
7.59 check(checkPath(G, p),"path() found a wrong path.");
7.60 check(pathSource(G, p) == s,"path() found a wrong path.");
7.61 check(pathTarget(G, p) == t,"path() found a wrong path.");
7.62 @@ -132,7 +138,7 @@
7.63 Node v=G.target(e);
7.64 check( !dijkstra_test.reached(u) ||
7.65 (dijkstra_test.dist(v) - dijkstra_test.dist(u) <= length[e]),
7.66 - "dist(target)-dist(source)-arc_length= " <<
7.67 + "Wrong output. dist(target)-dist(source)-arc_length=" <<
7.68 dijkstra_test.dist(v) - dijkstra_test.dist(u) - length[e]);
7.69 }
7.70