1.1 --- a/lemon/dijkstra.h Thu Sep 11 11:10:44 2008 +0100
1.2 +++ b/lemon/dijkstra.h Mon Sep 22 15:33:23 2008 +0200
1.3 @@ -30,6 +30,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 @@ -199,7 +200,7 @@
1.12 ///\ref concepts::ReadMap::Value "Value" of the length map.
1.13 ///It is also possible to change the underlying priority heap.
1.14 ///
1.15 - ///There is also a \ref dijkstra() "function type interface" for the
1.16 + ///There is also a \ref dijkstra() "function-type interface" for the
1.17 ///%Dijkstra algorithm, which is convenient in the simplier cases and
1.18 ///it can be used easier.
1.19 ///
1.20 @@ -987,20 +988,16 @@
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 @@ -1030,20 +1027,22 @@
1.44
1.45 ///The type of the map that stores the distances of the nodes.
1.46 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.47 - typedef NullMap<typename Digraph::Node,Value> DistMap;
1.48 + typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.49 ///Instantiates a \ref DistMap.
1.50
1.51 ///This function instantiates a \ref DistMap.
1.52 ///\param g is the digraph, to which we would like to define
1.53 ///the \ref DistMap
1.54 -#ifdef DOXYGEN
1.55 static DistMap *createDistMap(const Digraph &g)
1.56 -#else
1.57 - static DistMap *createDistMap(const Digraph &)
1.58 -#endif
1.59 {
1.60 - return new DistMap();
1.61 + return new DistMap(g);
1.62 }
1.63 +
1.64 + ///The type of the shortest paths.
1.65 +
1.66 + ///The type of the shortest paths.
1.67 + ///It must meet the \ref concepts::Path "Path" concept.
1.68 + typedef lemon::Path<Digraph> Path;
1.69 };
1.70
1.71 /// Default traits class used by \ref DijkstraWizard
1.72 @@ -1065,7 +1064,7 @@
1.73
1.74 //Pointer to the digraph the algorithm runs on.
1.75 void *_g;
1.76 - //Pointer to the length map
1.77 + //Pointer to the length map.
1.78 void *_length;
1.79 //Pointer to the map of processed nodes.
1.80 void *_processed;
1.81 @@ -1073,53 +1072,41 @@
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 shortest path to the target node.
1.88 + void *_path;
1.89 + //Pointer to the distance of the target node.
1.90 + void *_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 DijkstraWizardBase() : _g(0), _length(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 two parameters,
1.108 + /// others are initiated to \c 0.
1.109 /// \param g The digraph the algorithm runs on.
1.110 /// \param l The length map.
1.111 - /// \param s The source node.
1.112 - DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.113 + DijkstraWizardBase(const GR &g,const LM &l) :
1.114 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.115 _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.116 - _processed(0), _pred(0), _dist(0), _source(s) {}
1.117 + _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.118
1.119 };
1.120
1.121 - /// Auxiliary class for the function type interface of Dijkstra algorithm.
1.122 + /// Auxiliary class for the function-type interface of Dijkstra algorithm.
1.123
1.124 - /// This auxiliary class is created to implement the function type
1.125 - /// interface of \ref Dijkstra algorithm. It uses the functions and features
1.126 - /// of the plain \ref Dijkstra, but it is much simpler to use it.
1.127 - /// It should only be used through the \ref dijkstra() function, which makes
1.128 - /// it easier to use the algorithm.
1.129 + /// This auxiliary class is created to implement the
1.130 + /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1.131 + /// It does not have own \ref run() method, it uses the functions
1.132 + /// and features of the plain \ref Dijkstra.
1.133 ///
1.134 - /// Simplicity means that the way to change the types defined
1.135 - /// in the traits class is based on functions that returns the new class
1.136 - /// and not on templatable built-in classes.
1.137 - /// When using the plain \ref Dijkstra
1.138 - /// the new class with the modified type comes from
1.139 - /// the original class by using the ::
1.140 - /// operator. In the case of \ref DijkstraWizard only
1.141 - /// a function have to be called, and it will
1.142 - /// return the needed class.
1.143 - ///
1.144 - /// It does not have own \ref run() method. When its \ref run() method
1.145 - /// is called, it initiates a plain \ref Dijkstra object, and calls the
1.146 - /// \ref Dijkstra::run() method of it.
1.147 + /// This class should only be used through the \ref dijkstra() function,
1.148 + /// which makes it easier to use the algorithm.
1.149 template<class TR>
1.150 class DijkstraWizard : public TR
1.151 {
1.152 @@ -1144,6 +1131,8 @@
1.153 typedef typename TR::DistMap DistMap;
1.154 ///The type of the map that indicates which nodes are processed.
1.155 typedef typename TR::ProcessedMap ProcessedMap;
1.156 + ///The type of the shortest paths
1.157 + typedef typename TR::Path Path;
1.158 ///The heap type used by the dijkstra algorithm.
1.159 typedef typename TR::Heap Heap;
1.160
1.161 @@ -1156,51 +1145,60 @@
1.162
1.163 /// Constructor that requires parameters.
1.164 /// These parameters will be the default values for the traits class.
1.165 - DijkstraWizard(const Digraph &g,const LengthMap &l, Node s=INVALID) :
1.166 - TR(g,l,s) {}
1.167 + /// \param g The digraph the algorithm runs on.
1.168 + /// \param l The length map.
1.169 + DijkstraWizard(const Digraph &g, const LengthMap &l) :
1.170 + TR(g,l) {}
1.171
1.172 ///Copy constructor
1.173 DijkstraWizard(const TR &b) : TR(b) {}
1.174
1.175 ~DijkstraWizard() {}
1.176
1.177 - ///Runs Dijkstra algorithm from a source node.
1.178 + ///Runs Dijkstra algorithm from the given source node.
1.179
1.180 - ///Runs Dijkstra algorithm from a source node.
1.181 - ///The node can be given with the \ref source() function.
1.182 - void run()
1.183 + ///This method runs %Dijkstra algorithm from the given source node
1.184 + ///in order to compute the shortest path to each node.
1.185 + void run(Node s)
1.186 {
1.187 - if(Base::_source==INVALID) throw UninitializedParameter();
1.188 + if (s==INVALID) throw UninitializedParameter();
1.189 Dijkstra<Digraph,LengthMap,TR>
1.190 - dij(*reinterpret_cast<const Digraph*>(Base::_g),
1.191 - *reinterpret_cast<const LengthMap*>(Base::_length));
1.192 - if(Base::_processed)
1.193 - dij.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.194 - if(Base::_pred)
1.195 - dij.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.196 - if(Base::_dist)
1.197 - dij.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.198 - dij.run(Base::_source);
1.199 + dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1.200 + *reinterpret_cast<const LengthMap*>(Base::_length));
1.201 + if (Base::_pred)
1.202 + dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.203 + if (Base::_dist)
1.204 + dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.205 + if (Base::_processed)
1.206 + dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.207 + dijk.run(s);
1.208 }
1.209
1.210 - ///Runs Dijkstra algorithm from the given node.
1.211 + ///Finds the shortest path between \c s and \c t.
1.212
1.213 - ///Runs Dijkstra algorithm from the given node.
1.214 - ///\param s is the given source.
1.215 - void run(Node s)
1.216 + ///This method runs the %Dijkstra algorithm from node \c s
1.217 + ///in order to compute the shortest path to node \c t
1.218 + ///(it stops searching when \c t is processed).
1.219 + ///
1.220 + ///\return \c true if \c t is reachable form \c s.
1.221 + bool run(Node s, Node t)
1.222 {
1.223 - Base::_source=s;
1.224 - run();
1.225 - }
1.226 -
1.227 - /// Sets the source node, from which the Dijkstra algorithm runs.
1.228 -
1.229 - /// Sets the source node, from which the Dijkstra algorithm runs.
1.230 - /// \param s is the source node.
1.231 - DijkstraWizard<TR> &source(Node s)
1.232 - {
1.233 - Base::_source=s;
1.234 - return *this;
1.235 + if (s==INVALID || t==INVALID) throw UninitializedParameter();
1.236 + Dijkstra<Digraph,LengthMap,TR>
1.237 + dijk(*reinterpret_cast<const Digraph*>(Base::_g),
1.238 + *reinterpret_cast<const LengthMap*>(Base::_length));
1.239 + if (Base::_pred)
1.240 + dijk.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.241 + if (Base::_dist)
1.242 + dijk.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.243 + if (Base::_processed)
1.244 + dijk.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.245 + dijk.run(s,t);
1.246 + if (Base::_path)
1.247 + *reinterpret_cast<Path*>(Base::_path) = dijk.path(t);
1.248 + if (Base::_di)
1.249 + *reinterpret_cast<Value*>(Base::_di) = dijk.dist(t);
1.250 + return dijk.reached(t);
1.251 }
1.252
1.253 template<class T>
1.254 @@ -1209,10 +1207,10 @@
1.255 static PredMap *createPredMap(const Digraph &) { return 0; };
1.256 SetPredMapBase(const TR &b) : TR(b) {}
1.257 };
1.258 - ///\brief \ref named-templ-param "Named parameter"
1.259 + ///\brief \ref named-func-param "Named parameter"
1.260 ///for setting \ref PredMap object.
1.261 ///
1.262 - ///\ref named-templ-param "Named parameter"
1.263 + ///\ref named-func-param "Named parameter"
1.264 ///for setting \ref PredMap object.
1.265 template<class T>
1.266 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1.267 @@ -1222,15 +1220,33 @@
1.268 }
1.269
1.270 template<class T>
1.271 + struct SetDistMapBase : public Base {
1.272 + typedef T DistMap;
1.273 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.274 + SetDistMapBase(const TR &b) : TR(b) {}
1.275 + };
1.276 + ///\brief \ref named-func-param "Named parameter"
1.277 + ///for setting \ref DistMap object.
1.278 + ///
1.279 + ///\ref named-func-param "Named parameter"
1.280 + ///for setting \ref DistMap object.
1.281 + template<class T>
1.282 + DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.283 + {
1.284 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.285 + return DijkstraWizard<SetDistMapBase<T> >(*this);
1.286 + }
1.287 +
1.288 + template<class T>
1.289 struct SetProcessedMapBase : public Base {
1.290 typedef T ProcessedMap;
1.291 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.292 SetProcessedMapBase(const TR &b) : TR(b) {}
1.293 };
1.294 - ///\brief \ref named-templ-param "Named parameter"
1.295 + ///\brief \ref named-func-param "Named parameter"
1.296 ///for setting \ref ProcessedMap object.
1.297 ///
1.298 - /// \ref named-templ-param "Named parameter"
1.299 + /// \ref named-func-param "Named parameter"
1.300 ///for setting \ref ProcessedMap object.
1.301 template<class T>
1.302 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.303 @@ -1240,37 +1256,49 @@
1.304 }
1.305
1.306 template<class T>
1.307 - struct SetDistMapBase : public Base {
1.308 - typedef T DistMap;
1.309 - static DistMap *createDistMap(const Digraph &) { return 0; };
1.310 - SetDistMapBase(const TR &b) : TR(b) {}
1.311 + struct SetPathBase : public Base {
1.312 + typedef T Path;
1.313 + SetPathBase(const TR &b) : TR(b) {}
1.314 };
1.315 - ///\brief \ref named-templ-param "Named parameter"
1.316 - ///for setting \ref DistMap object.
1.317 + ///\brief \ref named-func-param "Named parameter"
1.318 + ///for getting the shortest path to the target node.
1.319 ///
1.320 - ///\ref named-templ-param "Named parameter"
1.321 - ///for setting \ref DistMap object.
1.322 + ///\ref named-func-param "Named parameter"
1.323 + ///for getting the shortest path to the target node.
1.324 template<class T>
1.325 - DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.326 + DijkstraWizard<SetPathBase<T> > path(const T &t)
1.327 {
1.328 - Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.329 - return DijkstraWizard<SetDistMapBase<T> >(*this);
1.330 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1.331 + return DijkstraWizard<SetPathBase<T> >(*this);
1.332 + }
1.333 +
1.334 + ///\brief \ref named-func-param "Named parameter"
1.335 + ///for getting the distance of the target node.
1.336 + ///
1.337 + ///\ref named-func-param "Named parameter"
1.338 + ///for getting the distance of the target node.
1.339 + DijkstraWizard dist(const Value &d)
1.340 + {
1.341 + Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1.342 + return *this;
1.343 }
1.344
1.345 };
1.346
1.347 - ///Function type interface for Dijkstra algorithm.
1.348 + ///Function-type interface for Dijkstra algorithm.
1.349
1.350 /// \ingroup shortest_path
1.351 - ///Function type interface for Dijkstra algorithm.
1.352 + ///Function-type interface for Dijkstra algorithm.
1.353 ///
1.354 - ///This function also has several
1.355 - ///\ref named-templ-func-param "named parameters",
1.356 + ///This function also has several \ref named-func-param "named parameters",
1.357 ///they are declared as the members of class \ref DijkstraWizard.
1.358 - ///The following
1.359 - ///example shows how to use these parameters.
1.360 + ///The following examples show how to use these parameters.
1.361 ///\code
1.362 - /// dijkstra(g,length,source).predMap(preds).run();
1.363 + /// // Compute shortest path from node s to each node
1.364 + /// dijkstra(g,length).predMap(preds).distMap(dists).run(s);
1.365 + ///
1.366 + /// // Compute shortest path from s to t
1.367 + /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
1.368 ///\endcode
1.369 ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.370 ///to the end of the parameter list.
1.371 @@ -1278,9 +1306,9 @@
1.372 ///\sa Dijkstra
1.373 template<class GR, class LM>
1.374 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.375 - dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1.376 + dijkstra(const GR &digraph, const LM &length)
1.377 {
1.378 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1.379 + return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
1.380 }
1.381
1.382 } //END OF NAMESPACE LEMON