1.1 --- a/lemon/bellman_ford.h Fri Jul 24 23:19:43 2009 +0200
1.2 +++ b/lemon/bellman_ford.h Sun Aug 02 13:24:46 2009 +0200
1.3 @@ -16,18 +16,18 @@
1.4 *
1.5 */
1.6
1.7 -#ifndef LEMON_BELMANN_FORD_H
1.8 -#define LEMON_BELMANN_FORD_H
1.9 +#ifndef LEMON_BELLMAN_FORD_H
1.10 +#define LEMON_BELLMAN_FORD_H
1.11
1.12 /// \ingroup shortest_path
1.13 /// \file
1.14 /// \brief Bellman-Ford algorithm.
1.15 -///
1.16
1.17 #include <lemon/bits/path_dump.h>
1.18 #include <lemon/core.h>
1.19 #include <lemon/error.h>
1.20 #include <lemon/maps.h>
1.21 +#include <lemon/path.h>
1.22
1.23 #include <limits>
1.24
1.25 @@ -35,15 +35,17 @@
1.26
1.27 /// \brief Default OperationTraits for the BellmanFord algorithm class.
1.28 ///
1.29 - /// It defines all computational operations and constants which are
1.30 - /// used in the Bellman-Ford algorithm. The default implementation
1.31 - /// is based on the numeric_limits class. If the numeric type does not
1.32 - /// have infinity value then the maximum value is used as extremal
1.33 - /// infinity value.
1.34 + /// This operation traits class defines all computational operations
1.35 + /// and constants that are used in the Bellman-Ford algorithm.
1.36 + /// The default implementation is based on the \c numeric_limits class.
1.37 + /// If the numeric type does not have infinity value, then the maximum
1.38 + /// value is used as extremal infinity value.
1.39 template <
1.40 - typename Value,
1.41 - bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.42 + typename V,
1.43 + bool has_inf = std::numeric_limits<V>::has_infinity>
1.44 struct BellmanFordDefaultOperationTraits {
1.45 + /// \e
1.46 + typedef V Value;
1.47 /// \brief Gives back the zero value of the type.
1.48 static Value zero() {
1.49 return static_cast<Value>(0);
1.50 @@ -56,14 +58,16 @@
1.51 static Value plus(const Value& left, const Value& right) {
1.52 return left + right;
1.53 }
1.54 - /// \brief Gives back true only if the first value less than the second.
1.55 + /// \brief Gives back \c true only if the first value is less than
1.56 + /// the second.
1.57 static bool less(const Value& left, const Value& right) {
1.58 return left < right;
1.59 }
1.60 };
1.61
1.62 - template <typename Value>
1.63 - struct BellmanFordDefaultOperationTraits<Value, false> {
1.64 + template <typename V>
1.65 + struct BellmanFordDefaultOperationTraits<V, false> {
1.66 + typedef V Value;
1.67 static Value zero() {
1.68 return static_cast<Value>(0);
1.69 }
1.70 @@ -82,26 +86,26 @@
1.71 /// \brief Default traits class of BellmanFord class.
1.72 ///
1.73 /// Default traits class of BellmanFord class.
1.74 - /// \param _Digraph Digraph type.
1.75 - /// \param _LegthMap Type of length map.
1.76 - template<class _Digraph, class _LengthMap>
1.77 + /// \param GR The type of the digraph.
1.78 + /// \param LEN The type of the length map.
1.79 + template<typename GR, typename LEN>
1.80 struct BellmanFordDefaultTraits {
1.81 - /// The digraph type the algorithm runs on.
1.82 - typedef _Digraph Digraph;
1.83 + /// The type of the digraph the algorithm runs on.
1.84 + typedef GR Digraph;
1.85
1.86 /// \brief The type of the map that stores the arc lengths.
1.87 ///
1.88 /// The type of the map that stores the arc lengths.
1.89 - /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.90 - typedef _LengthMap LengthMap;
1.91 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.92 + typedef LEN LengthMap;
1.93
1.94 - // The type of the length of the arcs.
1.95 - typedef typename _LengthMap::Value Value;
1.96 + /// The type of the arc lengths.
1.97 + typedef typename LEN::Value Value;
1.98
1.99 /// \brief Operation traits for Bellman-Ford algorithm.
1.100 ///
1.101 - /// It defines the infinity type on the given Value type
1.102 - /// and the used operation.
1.103 + /// It defines the used operations and the infinity value for the
1.104 + /// given \c Value type.
1.105 /// \see BellmanFordDefaultOperationTraits
1.106 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.107
1.108 @@ -110,33 +114,31 @@
1.109 ///
1.110 /// The type of the map that stores the last
1.111 /// arcs of the shortest paths.
1.112 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 - ///
1.114 - typedef typename Digraph::template NodeMap<typename _Digraph::Arc> PredMap;
1.115 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.116 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.117
1.118 - /// \brief Instantiates a PredMap.
1.119 + /// \brief Instantiates a \c PredMap.
1.120 ///
1.121 /// This function instantiates a \ref PredMap.
1.122 - /// \param digraph is the digraph, to which we would like to define the PredMap.
1.123 - static PredMap *createPredMap(const _Digraph& digraph) {
1.124 - return new PredMap(digraph);
1.125 + /// \param g is the digraph to which we would like to define the
1.126 + /// \ref PredMap.
1.127 + static PredMap *createPredMap(const GR& g) {
1.128 + return new PredMap(g);
1.129 }
1.130
1.131 - /// \brief The type of the map that stores the dists of the nodes.
1.132 + /// \brief The type of the map that stores the distances of the nodes.
1.133 ///
1.134 - /// The type of the map that stores the dists of the nodes.
1.135 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.136 - ///
1.137 - typedef typename Digraph::template NodeMap<typename _LengthMap::Value>
1.138 - DistMap;
1.139 + /// The type of the map that stores the distances of the nodes.
1.140 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.141 + typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
1.142
1.143 - /// \brief Instantiates a DistMap.
1.144 + /// \brief Instantiates a \c DistMap.
1.145 ///
1.146 /// This function instantiates a \ref DistMap.
1.147 - /// \param digraph is the digraph, to which we would like to define the
1.148 - /// \ref DistMap
1.149 - static DistMap *createDistMap(const _Digraph& digraph) {
1.150 - return new DistMap(digraph);
1.151 + /// \param g is the digraph to which we would like to define the
1.152 + /// \ref DistMap.
1.153 + static DistMap *createDistMap(const GR& g) {
1.154 + return new DistMap(g);
1.155 }
1.156
1.157 };
1.158 @@ -144,106 +146,109 @@
1.159 /// \brief %BellmanFord algorithm class.
1.160 ///
1.161 /// \ingroup shortest_path
1.162 - /// This class provides an efficient implementation of \c Bellman-Ford
1.163 - /// algorithm. The arc lengths are passed to the algorithm using a
1.164 + /// This class provides an efficient implementation of the Bellman-Ford
1.165 + /// algorithm. The maximum time complexity of the algorithm is
1.166 + /// <tt>O(ne)</tt>.
1.167 + ///
1.168 + /// The Bellman-Ford algorithm solves the single-source shortest path
1.169 + /// problem when the arcs can have negative lengths, but the digraph
1.170 + /// should not contain directed cycles with negative total length.
1.171 + /// If all arc costs are non-negative, consider to use the Dijkstra
1.172 + /// algorithm instead, since it is more efficient.
1.173 + ///
1.174 + /// The arc lengths are passed to the algorithm using a
1.175 /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
1.176 - /// kind of length.
1.177 + /// kind of length. The type of the length values is determined by the
1.178 + /// \ref concepts::ReadMap::Value "Value" type of the length map.
1.179 ///
1.180 - /// The Bellman-Ford algorithm solves the shortest path from one node
1.181 - /// problem when the arcs can have negative length but the digraph should
1.182 - /// not contain cycles with negative sum of length. If we can assume
1.183 - /// that all arc is non-negative in the digraph then the dijkstra algorithm
1.184 - /// should be used rather.
1.185 + /// There is also a \ref bellmanFord() "function-type interface" for the
1.186 + /// Bellman-Ford algorithm, which is convenient in the simplier cases and
1.187 + /// it can be used easier.
1.188 ///
1.189 - /// The maximal time complexity of the algorithm is \f$ O(ne) \f$.
1.190 - ///
1.191 - /// The type of the length is determined by the
1.192 - /// \ref concepts::ReadMap::Value "Value" of the length map.
1.193 - ///
1.194 - /// \param _Digraph The digraph type the algorithm runs on. The default value
1.195 - /// is \ref ListDigraph. The value of _Digraph is not used directly by
1.196 - /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
1.197 - /// \param _LengthMap This read-only ArcMap determines the lengths of the
1.198 - /// arcs. The default map type is \ref concepts::Digraph::ArcMap
1.199 - /// "Digraph::ArcMap<int>". The value of _LengthMap is not used directly
1.200 - /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
1.201 - /// \param _Traits Traits class to set various data types used by the
1.202 - /// algorithm. The default traits class is \ref BellmanFordDefaultTraits
1.203 - /// "BellmanFordDefaultTraits<_Digraph,_LengthMap>". See \ref
1.204 - /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
1.205 - /// class.
1.206 + /// \tparam GR The type of the digraph the algorithm runs on.
1.207 + /// The default type is \ref ListDigraph.
1.208 + /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
1.209 + /// the lengths of the arcs. The default map type is
1.210 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.211 #ifdef DOXYGEN
1.212 - template <typename _Digraph, typename _LengthMap, typename _Traits>
1.213 + template <typename GR, typename LEN, typename TR>
1.214 #else
1.215 - template <typename _Digraph,
1.216 - typename _LengthMap=typename _Digraph::template ArcMap<int>,
1.217 - typename _Traits=BellmanFordDefaultTraits<_Digraph,_LengthMap> >
1.218 + template <typename GR=ListDigraph,
1.219 + typename LEN=typename GR::template ArcMap<int>,
1.220 + typename TR=BellmanFordDefaultTraits<GR,LEN> >
1.221 #endif
1.222 class BellmanFord {
1.223 public:
1.224
1.225 - typedef _Traits Traits;
1.226 ///The type of the underlying digraph.
1.227 - typedef typename _Traits::Digraph Digraph;
1.228 + typedef typename TR::Digraph Digraph;
1.229 +
1.230 + /// \brief The type of the arc lengths.
1.231 + typedef typename TR::LengthMap::Value Value;
1.232 + /// \brief The type of the map that stores the arc lengths.
1.233 + typedef typename TR::LengthMap LengthMap;
1.234 + /// \brief The type of the map that stores the last
1.235 + /// arcs of the shortest paths.
1.236 + typedef typename TR::PredMap PredMap;
1.237 + /// \brief The type of the map that stores the distances of the nodes.
1.238 + typedef typename TR::DistMap DistMap;
1.239 + /// The type of the paths.
1.240 + typedef PredMapPath<Digraph, PredMap> Path;
1.241 + ///\brief The \ref BellmanFordDefaultOperationTraits
1.242 + /// "operation traits class" of the algorithm.
1.243 + typedef typename TR::OperationTraits OperationTraits;
1.244 +
1.245 + ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
1.246 + typedef TR Traits;
1.247 +
1.248 + private:
1.249
1.250 typedef typename Digraph::Node Node;
1.251 typedef typename Digraph::NodeIt NodeIt;
1.252 typedef typename Digraph::Arc Arc;
1.253 typedef typename Digraph::OutArcIt OutArcIt;
1.254 -
1.255 - /// \brief The type of the length of the arcs.
1.256 - typedef typename _Traits::LengthMap::Value Value;
1.257 - /// \brief The type of the map that stores the arc lengths.
1.258 - typedef typename _Traits::LengthMap LengthMap;
1.259 - /// \brief The type of the map that stores the last
1.260 - /// arcs of the shortest paths.
1.261 - typedef typename _Traits::PredMap PredMap;
1.262 - /// \brief The type of the map that stores the dists of the nodes.
1.263 - typedef typename _Traits::DistMap DistMap;
1.264 - /// \brief The operation traits.
1.265 - typedef typename _Traits::OperationTraits OperationTraits;
1.266 - private:
1.267 - /// Pointer to the underlying digraph.
1.268 - const Digraph *digraph;
1.269 - /// Pointer to the length map
1.270 - const LengthMap *length;
1.271 - ///Pointer to the map of predecessors arcs.
1.272 +
1.273 + // Pointer to the underlying digraph.
1.274 + const Digraph *_gr;
1.275 + // Pointer to the length map
1.276 + const LengthMap *_length;
1.277 + // Pointer to the map of predecessors arcs.
1.278 PredMap *_pred;
1.279 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.280 - bool local_pred;
1.281 - ///Pointer to the map of distances.
1.282 + // Indicates if _pred is locally allocated (true) or not.
1.283 + bool _local_pred;
1.284 + // Pointer to the map of distances.
1.285 DistMap *_dist;
1.286 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.287 - bool local_dist;
1.288 + // Indicates if _dist is locally allocated (true) or not.
1.289 + bool _local_dist;
1.290
1.291 typedef typename Digraph::template NodeMap<bool> MaskMap;
1.292 MaskMap *_mask;
1.293
1.294 std::vector<Node> _process;
1.295
1.296 - /// Creates the maps if necessary.
1.297 + // Creates the maps if necessary.
1.298 void create_maps() {
1.299 if(!_pred) {
1.300 - local_pred = true;
1.301 - _pred = Traits::createPredMap(*digraph);
1.302 + _local_pred = true;
1.303 + _pred = Traits::createPredMap(*_gr);
1.304 }
1.305 if(!_dist) {
1.306 - local_dist = true;
1.307 - _dist = Traits::createDistMap(*digraph);
1.308 + _local_dist = true;
1.309 + _dist = Traits::createDistMap(*_gr);
1.310 }
1.311 - _mask = new MaskMap(*digraph, false);
1.312 + _mask = new MaskMap(*_gr, false);
1.313 }
1.314
1.315 public :
1.316
1.317 typedef BellmanFord Create;
1.318
1.319 - /// \name Named template parameters
1.320 + /// \name Named Template Parameters
1.321
1.322 ///@{
1.323
1.324 template <class T>
1.325 - struct DefPredMapTraits : public Traits {
1.326 + struct SetPredMapTraits : public Traits {
1.327 typedef T PredMap;
1.328 static PredMap *createPredMap(const Digraph&) {
1.329 LEMON_ASSERT(false, "PredMap is not initialized");
1.330 @@ -251,18 +256,20 @@
1.331 }
1.332 };
1.333
1.334 - /// \brief \ref named-templ-param "Named parameter" for setting PredMap
1.335 - /// type
1.336 - /// \ref named-templ-param "Named parameter" for setting PredMap type
1.337 + /// \brief \ref named-templ-param "Named parameter" for setting
1.338 + /// \c PredMap type.
1.339 ///
1.340 + /// \ref named-templ-param "Named parameter" for setting
1.341 + /// \c PredMap type.
1.342 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.343 template <class T>
1.344 struct SetPredMap
1.345 - : public BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > {
1.346 - typedef BellmanFord< Digraph, LengthMap, DefPredMapTraits<T> > Create;
1.347 + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
1.348 + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
1.349 };
1.350
1.351 template <class T>
1.352 - struct DefDistMapTraits : public Traits {
1.353 + struct SetDistMapTraits : public Traits {
1.354 typedef T DistMap;
1.355 static DistMap *createDistMap(const Digraph&) {
1.356 LEMON_ASSERT(false, "DistMap is not initialized");
1.357 @@ -270,31 +277,33 @@
1.358 }
1.359 };
1.360
1.361 - /// \brief \ref named-templ-param "Named parameter" for setting DistMap
1.362 - /// type
1.363 + /// \brief \ref named-templ-param "Named parameter" for setting
1.364 + /// \c DistMap type.
1.365 ///
1.366 - /// \ref named-templ-param "Named parameter" for setting DistMap type
1.367 - ///
1.368 + /// \ref named-templ-param "Named parameter" for setting
1.369 + /// \c DistMap type.
1.370 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.371 template <class T>
1.372 struct SetDistMap
1.373 - : public BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > {
1.374 - typedef BellmanFord< Digraph, LengthMap, DefDistMapTraits<T> > Create;
1.375 + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
1.376 + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
1.377 };
1.378 -
1.379 +
1.380 template <class T>
1.381 - struct DefOperationTraitsTraits : public Traits {
1.382 + struct SetOperationTraitsTraits : public Traits {
1.383 typedef T OperationTraits;
1.384 };
1.385
1.386 /// \brief \ref named-templ-param "Named parameter" for setting
1.387 - /// OperationTraits type
1.388 + /// \c OperationTraits type.
1.389 ///
1.390 - /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.391 - /// type
1.392 + /// \ref named-templ-param "Named parameter" for setting
1.393 + /// \c OperationTraits type.
1.394 + /// For more information see \ref BellmanFordDefaultOperationTraits.
1.395 template <class T>
1.396 struct SetOperationTraits
1.397 - : public BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> > {
1.398 - typedef BellmanFord< Digraph, LengthMap, DefOperationTraitsTraits<T> >
1.399 + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.400 + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
1.401 Create;
1.402 };
1.403
1.404 @@ -308,85 +317,89 @@
1.405
1.406 /// \brief Constructor.
1.407 ///
1.408 - /// \param _graph the digraph the algorithm will run on.
1.409 - /// \param _length the length map used by the algorithm.
1.410 - BellmanFord(const Digraph& _graph, const LengthMap& _length) :
1.411 - digraph(&_graph), length(&_length),
1.412 - _pred(0), local_pred(false),
1.413 - _dist(0), local_dist(false), _mask(0) {}
1.414 + /// Constructor.
1.415 + /// \param g The digraph the algorithm runs on.
1.416 + /// \param length The length map used by the algorithm.
1.417 + BellmanFord(const Digraph& g, const LengthMap& length) :
1.418 + _gr(&g), _length(&length),
1.419 + _pred(0), _local_pred(false),
1.420 + _dist(0), _local_dist(false), _mask(0) {}
1.421
1.422 ///Destructor.
1.423 ~BellmanFord() {
1.424 - if(local_pred) delete _pred;
1.425 - if(local_dist) delete _dist;
1.426 + if(_local_pred) delete _pred;
1.427 + if(_local_dist) delete _dist;
1.428 if(_mask) delete _mask;
1.429 }
1.430
1.431 /// \brief Sets the length map.
1.432 ///
1.433 /// Sets the length map.
1.434 - /// \return \c (*this)
1.435 - BellmanFord &lengthMap(const LengthMap &m) {
1.436 - length = &m;
1.437 + /// \return <tt>(*this)</tt>
1.438 + BellmanFord &lengthMap(const LengthMap &map) {
1.439 + _length = ↦
1.440 return *this;
1.441 }
1.442
1.443 - /// \brief Sets the map storing the predecessor arcs.
1.444 + /// \brief Sets the map that stores the predecessor arcs.
1.445 ///
1.446 - /// Sets the map storing the predecessor arcs.
1.447 - /// If you don't use this function before calling \ref run(),
1.448 - /// it will allocate one. The destuctor deallocates this
1.449 - /// automatically allocated map, of course.
1.450 - /// \return \c (*this)
1.451 - BellmanFord &predMap(PredMap &m) {
1.452 - if(local_pred) {
1.453 + /// Sets the map that stores the predecessor arcs.
1.454 + /// If you don't use this function before calling \ref run()
1.455 + /// or \ref init(), an instance will be allocated automatically.
1.456 + /// The destructor deallocates this automatically allocated map,
1.457 + /// of course.
1.458 + /// \return <tt>(*this)</tt>
1.459 + BellmanFord &predMap(PredMap &map) {
1.460 + if(_local_pred) {
1.461 delete _pred;
1.462 - local_pred=false;
1.463 + _local_pred=false;
1.464 }
1.465 - _pred = &m;
1.466 + _pred = ↦
1.467 return *this;
1.468 }
1.469
1.470 - /// \brief Sets the map storing the distances calculated by the algorithm.
1.471 + /// \brief Sets the map that stores the distances of the nodes.
1.472 ///
1.473 - /// Sets the map storing the distances calculated by the algorithm.
1.474 - /// If you don't use this function before calling \ref run(),
1.475 - /// it will allocate one. The destuctor deallocates this
1.476 - /// automatically allocated map, of course.
1.477 - /// \return \c (*this)
1.478 - BellmanFord &distMap(DistMap &m) {
1.479 - if(local_dist) {
1.480 + /// Sets the map that stores the distances of the nodes calculated
1.481 + /// by the algorithm.
1.482 + /// If you don't use this function before calling \ref run()
1.483 + /// or \ref init(), an instance will be allocated automatically.
1.484 + /// The destructor deallocates this automatically allocated map,
1.485 + /// of course.
1.486 + /// \return <tt>(*this)</tt>
1.487 + BellmanFord &distMap(DistMap &map) {
1.488 + if(_local_dist) {
1.489 delete _dist;
1.490 - local_dist=false;
1.491 + _local_dist=false;
1.492 }
1.493 - _dist = &m;
1.494 + _dist = ↦
1.495 return *this;
1.496 }
1.497
1.498 - /// \name Execution control
1.499 - /// The simplest way to execute the algorithm is to use
1.500 - /// one of the member functions called \c run(...).
1.501 - /// \n
1.502 - /// If you need more control on the execution,
1.503 - /// first you must call \ref init(), then you can add several source nodes
1.504 - /// with \ref addSource().
1.505 - /// Finally \ref start() will perform the actual path
1.506 - /// computation.
1.507 + /// \name Execution Control
1.508 + /// The simplest way to execute the Bellman-Ford algorithm is to use
1.509 + /// one of the member functions called \ref run().\n
1.510 + /// If you need better control on the execution, you have to call
1.511 + /// \ref init() first, then you can add several source nodes
1.512 + /// with \ref addSource(). Finally the actual path computation can be
1.513 + /// performed with \ref start(), \ref checkedStart() or
1.514 + /// \ref limitedStart().
1.515
1.516 ///@{
1.517
1.518 /// \brief Initializes the internal data structures.
1.519 ///
1.520 - /// Initializes the internal data structures.
1.521 + /// Initializes the internal data structures. The optional parameter
1.522 + /// is the initial distance of each node.
1.523 void init(const Value value = OperationTraits::infinity()) {
1.524 create_maps();
1.525 - for (NodeIt it(*digraph); it != INVALID; ++it) {
1.526 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.527 _pred->set(it, INVALID);
1.528 _dist->set(it, value);
1.529 }
1.530 _process.clear();
1.531 if (OperationTraits::less(value, OperationTraits::infinity())) {
1.532 - for (NodeIt it(*digraph); it != INVALID; ++it) {
1.533 + for (NodeIt it(*_gr); it != INVALID; ++it) {
1.534 _process.push_back(it);
1.535 _mask->set(it, true);
1.536 }
1.537 @@ -395,9 +408,8 @@
1.538
1.539 /// \brief Adds a new source node.
1.540 ///
1.541 - /// Adds a new source node. The optional second parameter is the
1.542 - /// initial distance of the node. It just sets the distance of the
1.543 - /// node to the given value.
1.544 + /// This function adds a new source node. The optional second parameter
1.545 + /// is the initial distance of the node.
1.546 void addSource(Node source, Value dst = OperationTraits::zero()) {
1.547 _dist->set(source, dst);
1.548 if (!(*_mask)[source]) {
1.549 @@ -409,19 +421,22 @@
1.550 /// \brief Executes one round from the Bellman-Ford algorithm.
1.551 ///
1.552 /// If the algoritm calculated the distances in the previous round
1.553 - /// exactly for all at most \f$ k \f$ length path lengths then it will
1.554 - /// calculate the distances exactly for all at most \f$ k + 1 \f$
1.555 - /// length path lengths. With \f$ k \f$ iteration this function
1.556 - /// calculates the at most \f$ k \f$ length path lengths.
1.557 + /// exactly for the paths of at most \c k arcs, then this function
1.558 + /// will calculate the distances exactly for the paths of at most
1.559 + /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
1.560 + /// calculates the shortest path distances exactly for the paths
1.561 + /// consisting of at most \c k arcs.
1.562 ///
1.563 /// \warning The paths with limited arc number cannot be retrieved
1.564 - /// easily with \ref path() or \ref predArc() functions. If you
1.565 - /// need the shortest path and not just the distance you should store
1.566 - /// after each iteration the \ref predMap() map and manually build
1.567 - /// the path.
1.568 + /// easily with \ref path() or \ref predArc() functions. If you also
1.569 + /// need the shortest paths and not only the distances, you should
1.570 + /// store the \ref predMap() "predecessor map" after each iteration
1.571 + /// and build the path manually.
1.572 ///
1.573 /// \return \c true when the algorithm have not found more shorter
1.574 /// paths.
1.575 + ///
1.576 + /// \see ActiveIt
1.577 bool processNextRound() {
1.578 for (int i = 0; i < int(_process.size()); ++i) {
1.579 _mask->set(_process[i], false);
1.580 @@ -432,9 +447,9 @@
1.581 values[i] = (*_dist)[_process[i]];
1.582 }
1.583 for (int i = 0; i < int(_process.size()); ++i) {
1.584 - for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
1.585 - Node target = digraph->target(it);
1.586 - Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
1.587 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.588 + Node target = _gr->target(it);
1.589 + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
1.590 if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.591 _pred->set(target, it);
1.592 _dist->set(target, relaxed);
1.593 @@ -451,23 +466,28 @@
1.594
1.595 /// \brief Executes one weak round from the Bellman-Ford algorithm.
1.596 ///
1.597 - /// If the algorithm calculated the distances in the
1.598 - /// previous round at least for all at most k length paths then it will
1.599 - /// calculate the distances at least for all at most k + 1 length paths.
1.600 - /// This function does not make it possible to calculate strictly the
1.601 - /// at most k length minimal paths, this is why it is
1.602 - /// called just weak round.
1.603 - /// \return \c true when the algorithm have not found more shorter paths.
1.604 + /// If the algorithm calculated the distances in the previous round
1.605 + /// at least for the paths of at most \c k arcs, then this function
1.606 + /// will calculate the distances at least for the paths of at most
1.607 + /// <tt>k+1</tt> arcs.
1.608 + /// This function does not make it possible to calculate the shortest
1.609 + /// path distances exactly for paths consisting of at most \c k arcs,
1.610 + /// this is why it is called weak round.
1.611 + ///
1.612 + /// \return \c true when the algorithm have not found more shorter
1.613 + /// paths.
1.614 + ///
1.615 + /// \see ActiveIt
1.616 bool processNextWeakRound() {
1.617 for (int i = 0; i < int(_process.size()); ++i) {
1.618 _mask->set(_process[i], false);
1.619 }
1.620 std::vector<Node> nextProcess;
1.621 for (int i = 0; i < int(_process.size()); ++i) {
1.622 - for (OutArcIt it(*digraph, _process[i]); it != INVALID; ++it) {
1.623 - Node target = digraph->target(it);
1.624 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
1.625 + Node target = _gr->target(it);
1.626 Value relaxed =
1.627 - OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
1.628 + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
1.629 if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.630 _pred->set(target, it);
1.631 _dist->set(target, relaxed);
1.632 @@ -484,16 +504,19 @@
1.633
1.634 /// \brief Executes the algorithm.
1.635 ///
1.636 - /// \pre init() must be called and at least one node should be added
1.637 - /// with addSource() before using this function.
1.638 + /// Executes the algorithm.
1.639 ///
1.640 - /// This method runs the %BellmanFord algorithm from the root node(s)
1.641 - /// in order to compute the shortest path to each node. The algorithm
1.642 - /// computes
1.643 - /// - The shortest path tree.
1.644 - /// - The distance of each node from the root(s).
1.645 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.646 + /// in order to compute the shortest path to each node.
1.647 + ///
1.648 + /// The algorithm computes
1.649 + /// - the shortest path tree (forest),
1.650 + /// - the distance of each node from the root(s).
1.651 + ///
1.652 + /// \pre init() must be called and at least one root node should be
1.653 + /// added with addSource() before using this function.
1.654 void start() {
1.655 - int num = countNodes(*digraph) - 1;
1.656 + int num = countNodes(*_gr) - 1;
1.657 for (int i = 0; i < num; ++i) {
1.658 if (processNextWeakRound()) break;
1.659 }
1.660 @@ -501,83 +524,98 @@
1.661
1.662 /// \brief Executes the algorithm and checks the negative cycles.
1.663 ///
1.664 - /// \pre init() must be called and at least one node should be added
1.665 - /// with addSource() before using this function.
1.666 + /// Executes the algorithm and checks the negative cycles.
1.667 ///
1.668 - /// This method runs the %BellmanFord algorithm from the root node(s)
1.669 - /// in order to compute the shortest path to each node. The algorithm
1.670 - /// computes
1.671 - /// - The shortest path tree.
1.672 - /// - The distance of each node from the root(s).
1.673 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.674 + /// in order to compute the shortest path to each node and also checks
1.675 + /// if the digraph contains cycles with negative total length.
1.676 + ///
1.677 + /// The algorithm computes
1.678 + /// - the shortest path tree (forest),
1.679 + /// - the distance of each node from the root(s).
1.680 ///
1.681 /// \return \c false if there is a negative cycle in the digraph.
1.682 + ///
1.683 + /// \pre init() must be called and at least one root node should be
1.684 + /// added with addSource() before using this function.
1.685 bool checkedStart() {
1.686 - int num = countNodes(*digraph);
1.687 + int num = countNodes(*_gr);
1.688 for (int i = 0; i < num; ++i) {
1.689 if (processNextWeakRound()) return true;
1.690 }
1.691 return _process.empty();
1.692 }
1.693
1.694 - /// \brief Executes the algorithm with path length limit.
1.695 + /// \brief Executes the algorithm with arc number limit.
1.696 ///
1.697 - /// \pre init() must be called and at least one node should be added
1.698 - /// with addSource() before using this function.
1.699 + /// Executes the algorithm with arc number limit.
1.700 ///
1.701 - /// This method runs the %BellmanFord algorithm from the root
1.702 - /// node(s) in order to compute the shortest path lengths with at
1.703 - /// most \c num arc.
1.704 + /// This method runs the Bellman-Ford algorithm from the root node(s)
1.705 + /// in order to compute the shortest path distance for each node
1.706 + /// using only the paths consisting of at most \c num arcs.
1.707 + ///
1.708 + /// The algorithm computes
1.709 + /// - the limited distance of each node from the root(s),
1.710 + /// - the predecessor arc for each node.
1.711 ///
1.712 /// \warning The paths with limited arc number cannot be retrieved
1.713 - /// easily with \ref path() or \ref predArc() functions. If you
1.714 - /// need the shortest path and not just the distance you should store
1.715 - /// after each iteration the \ref predMap() map and manually build
1.716 - /// the path.
1.717 + /// easily with \ref path() or \ref predArc() functions. If you also
1.718 + /// need the shortest paths and not only the distances, you should
1.719 + /// store the \ref predMap() "predecessor map" after each iteration
1.720 + /// and build the path manually.
1.721 ///
1.722 - /// The algorithm computes
1.723 - /// - The predecessor arc from each node.
1.724 - /// - The limited distance of each node from the root(s).
1.725 + /// \pre init() must be called and at least one root node should be
1.726 + /// added with addSource() before using this function.
1.727 void limitedStart(int num) {
1.728 for (int i = 0; i < num; ++i) {
1.729 if (processNextRound()) break;
1.730 }
1.731 }
1.732
1.733 - /// \brief Runs %BellmanFord algorithm from node \c s.
1.734 + /// \brief Runs the algorithm from the given root node.
1.735 ///
1.736 - /// This method runs the %BellmanFord algorithm from a root node \c s
1.737 - /// in order to compute the shortest path to each node. The algorithm
1.738 - /// computes
1.739 - /// - The shortest path tree.
1.740 - /// - The distance of each node from the root.
1.741 + /// This method runs the Bellman-Ford algorithm from the given root
1.742 + /// node \c s in order to compute the shortest path to each node.
1.743 ///
1.744 - /// \note d.run(s) is just a shortcut of the following code.
1.745 - ///\code
1.746 - /// d.init();
1.747 - /// d.addSource(s);
1.748 - /// d.start();
1.749 - ///\endcode
1.750 + /// The algorithm computes
1.751 + /// - the shortest path tree (forest),
1.752 + /// - the distance of each node from the root(s).
1.753 + ///
1.754 + /// \note bf.run(s) is just a shortcut of the following code.
1.755 + /// \code
1.756 + /// bf.init();
1.757 + /// bf.addSource(s);
1.758 + /// bf.start();
1.759 + /// \endcode
1.760 void run(Node s) {
1.761 init();
1.762 addSource(s);
1.763 start();
1.764 }
1.765
1.766 - /// \brief Runs %BellmanFord algorithm with limited path length
1.767 - /// from node \c s.
1.768 + /// \brief Runs the algorithm from the given root node with arc
1.769 + /// number limit.
1.770 ///
1.771 - /// This method runs the %BellmanFord algorithm from a root node \c s
1.772 - /// in order to compute the shortest path with at most \c len arcs
1.773 - /// to each node. The algorithm computes
1.774 - /// - The shortest path tree.
1.775 - /// - The distance of each node from the root.
1.776 + /// This method runs the Bellman-Ford algorithm from the given root
1.777 + /// node \c s in order to compute the shortest path distance for each
1.778 + /// node using only the paths consisting of at most \c num arcs.
1.779 ///
1.780 - /// \note d.run(s, num) is just a shortcut of the following code.
1.781 - ///\code
1.782 - /// d.init();
1.783 - /// d.addSource(s);
1.784 - /// d.limitedStart(num);
1.785 - ///\endcode
1.786 + /// The algorithm computes
1.787 + /// - the limited distance of each node from the root(s),
1.788 + /// - the predecessor arc for each node.
1.789 + ///
1.790 + /// \warning The paths with limited arc number cannot be retrieved
1.791 + /// easily with \ref path() or \ref predArc() functions. If you also
1.792 + /// need the shortest paths and not only the distances, you should
1.793 + /// store the \ref predMap() "predecessor map" after each iteration
1.794 + /// and build the path manually.
1.795 + ///
1.796 + /// \note bf.run(s, num) is just a shortcut of the following code.
1.797 + /// \code
1.798 + /// bf.init();
1.799 + /// bf.addSource(s);
1.800 + /// bf.limitedStart(num);
1.801 + /// \endcode
1.802 void run(Node s, int num) {
1.803 init();
1.804 addSource(s);
1.805 @@ -586,27 +624,19 @@
1.806
1.807 ///@}
1.808
1.809 - /// \name Query Functions
1.810 - /// The result of the %BellmanFord algorithm can be obtained using these
1.811 - /// functions.\n
1.812 - /// Before the use of these functions,
1.813 - /// either run() or start() must be called.
1.814 -
1.815 - ///@{
1.816 -
1.817 - /// \brief Lemon iterator for get the active nodes.
1.818 + /// \brief LEMON iterator for getting the active nodes.
1.819 ///
1.820 - /// Lemon iterator for get the active nodes. This class provides a
1.821 - /// common style lemon iterator which gives back a subset of the
1.822 - /// nodes. The iterated nodes are active in the algorithm after
1.823 - /// the last phase so these should be checked in the next phase to
1.824 - /// find augmenting arcs from these.
1.825 + /// This class provides a common style LEMON iterator that traverses
1.826 + /// the active nodes of the Bellman-Ford algorithm after the last
1.827 + /// phase. These nodes should be checked in the next phase to
1.828 + /// find augmenting arcs outgoing from them.
1.829 class ActiveIt {
1.830 public:
1.831
1.832 /// \brief Constructor.
1.833 ///
1.834 - /// Constructor for get the nodeset of the variable.
1.835 + /// Constructor for getting the active nodes of the given BellmanFord
1.836 + /// instance.
1.837 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
1.838 {
1.839 _index = _algorithm->_process.size() - 1;
1.840 @@ -617,9 +647,9 @@
1.841 /// Invalid constructor.
1.842 ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
1.843
1.844 - /// \brief Conversion to node.
1.845 + /// \brief Conversion to \c Node.
1.846 ///
1.847 - /// Conversion to node.
1.848 + /// Conversion to \c Node.
1.849 operator Node() const {
1.850 return _index >= 0 ? _algorithm->_process[_index] : INVALID;
1.851 }
1.852 @@ -646,394 +676,432 @@
1.853 const BellmanFord* _algorithm;
1.854 int _index;
1.855 };
1.856 +
1.857 + /// \name Query Functions
1.858 + /// The result of the Bellman-Ford algorithm can be obtained using these
1.859 + /// functions.\n
1.860 + /// Either \ref run() or \ref init() should be called before using them.
1.861 +
1.862 + ///@{
1.863
1.864 - typedef PredMapPath<Digraph, PredMap> Path;
1.865 + /// \brief The shortest path to the given node.
1.866 + ///
1.867 + /// Gives back the shortest path to the given node from the root(s).
1.868 + ///
1.869 + /// \warning \c t should be reached from the root(s).
1.870 + ///
1.871 + /// \pre Either \ref run() or \ref init() must be called before
1.872 + /// using this function.
1.873 + Path path(Node t) const
1.874 + {
1.875 + return Path(*_gr, *_pred, t);
1.876 + }
1.877 +
1.878 + /// \brief The distance of the given node from the root(s).
1.879 + ///
1.880 + /// Returns the distance of the given node from the root(s).
1.881 + ///
1.882 + /// \warning If node \c v is not reached from the root(s), then
1.883 + /// the return value of this function is undefined.
1.884 + ///
1.885 + /// \pre Either \ref run() or \ref init() must be called before
1.886 + /// using this function.
1.887 + Value dist(Node v) const { return (*_dist)[v]; }
1.888
1.889 - /// \brief Gives back the shortest path.
1.890 - ///
1.891 - /// Gives back the shortest path.
1.892 - /// \pre The \c t should be reachable from the source.
1.893 - Path path(Node t)
1.894 - {
1.895 - return Path(*digraph, *_pred, t);
1.896 + /// \brief Returns the 'previous arc' of the shortest path tree for
1.897 + /// the given node.
1.898 + ///
1.899 + /// This function returns the 'previous arc' of the shortest path
1.900 + /// tree for node \c v, i.e. it returns the last arc of a
1.901 + /// shortest path from a root to \c v. It is \c INVALID if \c v
1.902 + /// is not reached from the root(s) or if \c v is a root.
1.903 + ///
1.904 + /// The shortest path tree used here is equal to the shortest path
1.905 + /// tree used in \ref predNode() and \predMap().
1.906 + ///
1.907 + /// \pre Either \ref run() or \ref init() must be called before
1.908 + /// using this function.
1.909 + Arc predArc(Node v) const { return (*_pred)[v]; }
1.910 +
1.911 + /// \brief Returns the 'previous node' of the shortest path tree for
1.912 + /// the given node.
1.913 + ///
1.914 + /// This function returns the 'previous node' of the shortest path
1.915 + /// tree for node \c v, i.e. it returns the last but one node of
1.916 + /// a shortest path from a root to \c v. It is \c INVALID if \c v
1.917 + /// is not reached from the root(s) or if \c v is a root.
1.918 + ///
1.919 + /// The shortest path tree used here is equal to the shortest path
1.920 + /// tree used in \ref predArc() and \predMap().
1.921 + ///
1.922 + /// \pre Either \ref run() or \ref init() must be called before
1.923 + /// using this function.
1.924 + Node predNode(Node v) const {
1.925 + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
1.926 + }
1.927 +
1.928 + /// \brief Returns a const reference to the node map that stores the
1.929 + /// distances of the nodes.
1.930 + ///
1.931 + /// Returns a const reference to the node map that stores the distances
1.932 + /// of the nodes calculated by the algorithm.
1.933 + ///
1.934 + /// \pre Either \ref run() or \ref init() must be called before
1.935 + /// using this function.
1.936 + const DistMap &distMap() const { return *_dist;}
1.937 +
1.938 + /// \brief Returns a const reference to the node map that stores the
1.939 + /// predecessor arcs.
1.940 + ///
1.941 + /// Returns a const reference to the node map that stores the predecessor
1.942 + /// arcs, which form the shortest path tree (forest).
1.943 + ///
1.944 + /// \pre Either \ref run() or \ref init() must be called before
1.945 + /// using this function.
1.946 + const PredMap &predMap() const { return *_pred; }
1.947 +
1.948 + /// \brief Checks if a node is reached from the root(s).
1.949 + ///
1.950 + /// Returns \c true if \c v is reached from the root(s).
1.951 + ///
1.952 + /// \pre Either \ref run() or \ref init() must be called before
1.953 + /// using this function.
1.954 + bool reached(Node v) const {
1.955 + return (*_dist)[v] != OperationTraits::infinity();
1.956 }
1.957
1.958 -
1.959 - // TODO : implement negative cycle
1.960 -// /// \brief Gives back a negative cycle.
1.961 -// ///
1.962 -// /// This function gives back a negative cycle.
1.963 -// /// If the algorithm have not found yet negative cycle it will give back
1.964 -// /// an empty path.
1.965 -// Path negativeCycle() {
1.966 -// typename Digraph::template NodeMap<int> state(*digraph, 0);
1.967 -// for (ActiveIt it(*this); it != INVALID; ++it) {
1.968 -// if (state[it] == 0) {
1.969 -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.970 -// if (state[t] == 0) {
1.971 -// state[t] = 1;
1.972 -// } else if (state[t] == 2) {
1.973 -// break;
1.974 -// } else {
1.975 -// p.clear();
1.976 -// typename Path::Builder b(p);
1.977 -// b.setStartNode(t);
1.978 -// b.pushFront(predArc(t));
1.979 -// for(Node s = predNode(t); s != t; s = predNode(s)) {
1.980 -// b.pushFront(predArc(s));
1.981 -// }
1.982 -// b.commit();
1.983 -// return true;
1.984 -// }
1.985 -// }
1.986 -// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.987 -// if (state[t] == 1) {
1.988 -// state[t] = 2;
1.989 -// } else {
1.990 -// break;
1.991 -// }
1.992 -// }
1.993 -// }
1.994 -// }
1.995 -// return false;
1.996 -// }
1.997 -
1.998 - /// \brief The distance of a node from the root.
1.999 - ///
1.1000 - /// Returns the distance of a node from the root.
1.1001 - /// \pre \ref run() must be called before using this function.
1.1002 - /// \warning If node \c v in unreachable from the root the return value
1.1003 - /// of this funcion is undefined.
1.1004 - Value dist(Node v) const { return (*_dist)[v]; }
1.1005 -
1.1006 - /// \brief Returns the 'previous arc' of the shortest path tree.
1.1007 - ///
1.1008 - /// For a node \c v it returns the 'previous arc' of the shortest path
1.1009 - /// tree, i.e. it returns the last arc of a shortest path from the root
1.1010 - /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
1.1011 - /// if \c v=s. The shortest path tree used here is equal to the shortest
1.1012 - /// path tree used in \ref predNode().
1.1013 - /// \pre \ref run() must be called before using
1.1014 - /// this function.
1.1015 - Arc predArc(Node v) const { return (*_pred)[v]; }
1.1016 -
1.1017 - /// \brief Returns the 'previous node' of the shortest path tree.
1.1018 - ///
1.1019 - /// For a node \c v it returns the 'previous node' of the shortest path
1.1020 - /// tree, i.e. it returns the last but one node from a shortest path from
1.1021 - /// the root to \c /v. It is INVALID if \c v is unreachable from the root
1.1022 - /// or if \c v=s. The shortest path tree used here is equal to the
1.1023 - /// shortest path tree used in \ref predArc(). \pre \ref run() must be
1.1024 - /// called before using this function.
1.1025 - Node predNode(Node v) const {
1.1026 - return (*_pred)[v] == INVALID ? INVALID : digraph->source((*_pred)[v]);
1.1027 - }
1.1028 -
1.1029 - /// \brief Returns a reference to the NodeMap of distances.
1.1030 - ///
1.1031 - /// Returns a reference to the NodeMap of distances. \pre \ref run() must
1.1032 - /// be called before using this function.
1.1033 - const DistMap &distMap() const { return *_dist;}
1.1034 -
1.1035 - /// \brief Returns a reference to the shortest path tree map.
1.1036 - ///
1.1037 - /// Returns a reference to the NodeMap of the arcs of the
1.1038 - /// shortest path tree.
1.1039 - /// \pre \ref run() must be called before using this function.
1.1040 - const PredMap &predMap() const { return *_pred; }
1.1041 -
1.1042 - /// \brief Checks if a node is reachable from the root.
1.1043 - ///
1.1044 - /// Returns \c true if \c v is reachable from the root.
1.1045 - /// \pre \ref run() must be called before using this function.
1.1046 - ///
1.1047 - bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
1.1048 + // TODO: implement negative cycle
1.1049 +// /// \brief Gives back a negative cycle.
1.1050 +// ///
1.1051 +// /// This function gives back a negative cycle.
1.1052 +// /// If the algorithm have not found yet negative cycle it will give back
1.1053 +// /// an empty path.
1.1054 +// Path negativeCycle() {
1.1055 +// typename Digraph::template NodeMap<int> state(*digraph, 0);
1.1056 +// for (ActiveIt it(*this); it != INVALID; ++it) {
1.1057 +// if (state[it] == 0) {
1.1058 +// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.1059 +// if (state[t] == 0) {
1.1060 +// state[t] = 1;
1.1061 +// } else if (state[t] == 2) {
1.1062 +// break;
1.1063 +// } else {
1.1064 +// p.clear();
1.1065 +// typename Path::Builder b(p);
1.1066 +// b.setStartNode(t);
1.1067 +// b.pushFront(predArc(t));
1.1068 +// for(Node s = predNode(t); s != t; s = predNode(s)) {
1.1069 +// b.pushFront(predArc(s));
1.1070 +// }
1.1071 +// b.commit();
1.1072 +// return true;
1.1073 +// }
1.1074 +// }
1.1075 +// for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
1.1076 +// if (state[t] == 1) {
1.1077 +// state[t] = 2;
1.1078 +// } else {
1.1079 +// break;
1.1080 +// }
1.1081 +// }
1.1082 +// }
1.1083 +// }
1.1084 +// return false;
1.1085 +// }
1.1086
1.1087 ///@}
1.1088 };
1.1089
1.1090 - /// \brief Default traits class of BellmanFord function.
1.1091 + /// \brief Default traits class of bellmanFord() function.
1.1092 ///
1.1093 - /// Default traits class of BellmanFord function.
1.1094 - /// \param _Digraph Digraph type.
1.1095 - /// \param _LengthMap Type of length map.
1.1096 - template <typename _Digraph, typename _LengthMap>
1.1097 + /// Default traits class of bellmanFord() function.
1.1098 + /// \tparam GR The type of the digraph.
1.1099 + /// \tparam LEN The type of the length map.
1.1100 + template <typename GR, typename LEN>
1.1101 struct BellmanFordWizardDefaultTraits {
1.1102 - /// \brief The digraph type the algorithm runs on.
1.1103 - typedef _Digraph Digraph;
1.1104 + /// The type of the digraph the algorithm runs on.
1.1105 + typedef GR Digraph;
1.1106
1.1107 /// \brief The type of the map that stores the arc lengths.
1.1108 ///
1.1109 /// The type of the map that stores the arc lengths.
1.1110 /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.1111 - typedef _LengthMap LengthMap;
1.1112 + typedef LEN LengthMap;
1.1113
1.1114 - /// \brief The value type of the length map.
1.1115 - typedef typename _LengthMap::Value Value;
1.1116 + /// The type of the arc lengths.
1.1117 + typedef typename LEN::Value Value;
1.1118
1.1119 /// \brief Operation traits for Bellman-Ford algorithm.
1.1120 ///
1.1121 - /// It defines the infinity type on the given Value type
1.1122 - /// and the used operation.
1.1123 + /// It defines the used operations and the infinity value for the
1.1124 + /// given \c Value type.
1.1125 /// \see BellmanFordDefaultOperationTraits
1.1126 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.1127
1.1128 /// \brief The type of the map that stores the last
1.1129 /// arcs of the shortest paths.
1.1130 ///
1.1131 - /// The type of the map that stores the last
1.1132 - /// arcs of the shortest paths.
1.1133 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1134 - typedef NullMap <typename _Digraph::Node,typename _Digraph::Arc> PredMap;
1.1135 + /// The type of the map that stores the last arcs of the shortest paths.
1.1136 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.1137 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
1.1138
1.1139 - /// \brief Instantiates a PredMap.
1.1140 + /// \brief Instantiates a \c PredMap.
1.1141 ///
1.1142 - /// This function instantiates a \ref PredMap.
1.1143 - static PredMap *createPredMap(const _Digraph &) {
1.1144 - return new PredMap();
1.1145 + /// This function instantiates a \ref PredMap.
1.1146 + /// \param g is the digraph to which we would like to define the
1.1147 + /// \ref PredMap.
1.1148 + static PredMap *createPredMap(const GR &g) {
1.1149 + return new PredMap(g);
1.1150 }
1.1151 - /// \brief The type of the map that stores the dists of the nodes.
1.1152 +
1.1153 + /// \brief The type of the map that stores the distances of the nodes.
1.1154 ///
1.1155 - /// The type of the map that stores the dists of the nodes.
1.1156 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1157 - typedef NullMap<typename Digraph::Node, Value> DistMap;
1.1158 - /// \brief Instantiates a DistMap.
1.1159 + /// The type of the map that stores the distances of the nodes.
1.1160 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.1161 + typedef typename GR::template NodeMap<Value> DistMap;
1.1162 +
1.1163 + /// \brief Instantiates a \c DistMap.
1.1164 ///
1.1165 /// This function instantiates a \ref DistMap.
1.1166 - static DistMap *createDistMap(const _Digraph &) {
1.1167 - return new DistMap();
1.1168 + /// \param g is the digraph to which we would like to define the
1.1169 + /// \ref DistMap.
1.1170 + static DistMap *createDistMap(const GR &g) {
1.1171 + return new DistMap(g);
1.1172 }
1.1173 +
1.1174 + ///The type of the shortest paths.
1.1175 +
1.1176 + ///The type of the shortest paths.
1.1177 + ///It must meet the \ref concepts::Path "Path" concept.
1.1178 + typedef lemon::Path<Digraph> Path;
1.1179 };
1.1180
1.1181 - /// \brief Default traits used by \ref BellmanFordWizard
1.1182 + /// \brief Default traits class used by BellmanFordWizard.
1.1183 ///
1.1184 - /// To make it easier to use BellmanFord algorithm
1.1185 - /// we have created a wizard class.
1.1186 - /// This \ref BellmanFordWizard class needs default traits,
1.1187 - /// as well as the \ref BellmanFord class.
1.1188 - /// The \ref BellmanFordWizardBase is a class to be the default traits of the
1.1189 - /// \ref BellmanFordWizard class.
1.1190 - /// \todo More named parameters are required...
1.1191 - template<class _Digraph,class _LengthMap>
1.1192 + /// Default traits class used by BellmanFordWizard.
1.1193 + /// \tparam GR The type of the digraph.
1.1194 + /// \tparam LEN The type of the length map.
1.1195 + template <typename GR, typename LEN>
1.1196 class BellmanFordWizardBase
1.1197 - : public BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> {
1.1198 + : public BellmanFordWizardDefaultTraits<GR, LEN> {
1.1199
1.1200 - typedef BellmanFordWizardDefaultTraits<_Digraph,_LengthMap> Base;
1.1201 + typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
1.1202 protected:
1.1203 - /// Type of the nodes in the digraph.
1.1204 + // Type of the nodes in the digraph.
1.1205 typedef typename Base::Digraph::Node Node;
1.1206
1.1207 - /// Pointer to the underlying digraph.
1.1208 + // Pointer to the underlying digraph.
1.1209 void *_graph;
1.1210 - /// Pointer to the length map
1.1211 + // Pointer to the length map
1.1212 void *_length;
1.1213 - ///Pointer to the map of predecessors arcs.
1.1214 + // Pointer to the map of predecessors arcs.
1.1215 void *_pred;
1.1216 - ///Pointer to the map of distances.
1.1217 + // Pointer to the map of distances.
1.1218 void *_dist;
1.1219 - ///Pointer to the source node.
1.1220 - Node _source;
1.1221 + //Pointer to the shortest path to the target node.
1.1222 + void *_path;
1.1223 + //Pointer to the distance of the target node.
1.1224 + void *_di;
1.1225
1.1226 public:
1.1227 /// Constructor.
1.1228
1.1229 - /// This constructor does not require parameters, therefore it initiates
1.1230 - /// all of the attributes to default values (0, INVALID).
1.1231 - BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
1.1232 - _dist(0), _source(INVALID) {}
1.1233 + /// This constructor does not require parameters, it initiates
1.1234 + /// all of the attributes to default values \c 0.
1.1235 + BellmanFordWizardBase() :
1.1236 + _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.1237
1.1238 /// Constructor.
1.1239
1.1240 - /// This constructor requires some parameters,
1.1241 - /// listed in the parameters list.
1.1242 - /// Others are initiated to 0.
1.1243 - /// \param digraph is the initial value of \ref _graph
1.1244 - /// \param length is the initial value of \ref _length
1.1245 - /// \param source is the initial value of \ref _source
1.1246 - BellmanFordWizardBase(const _Digraph& digraph,
1.1247 - const _LengthMap& length,
1.1248 - Node source = INVALID) :
1.1249 - _graph(reinterpret_cast<void*>(const_cast<_Digraph*>(&digraph))),
1.1250 - _length(reinterpret_cast<void*>(const_cast<_LengthMap*>(&length))),
1.1251 - _pred(0), _dist(0), _source(source) {}
1.1252 + /// This constructor requires two parameters,
1.1253 + /// others are initiated to \c 0.
1.1254 + /// \param gr The digraph the algorithm runs on.
1.1255 + /// \param len The length map.
1.1256 + BellmanFordWizardBase(const GR& gr,
1.1257 + const LEN& len) :
1.1258 + _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
1.1259 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
1.1260 + _pred(0), _dist(0), _path(0), _di(0) {}
1.1261
1.1262 };
1.1263
1.1264 - /// A class to make the usage of BellmanFord algorithm easier
1.1265 + /// \brief Auxiliary class for the function-type interface of the
1.1266 + /// \ref BellmanFord "Bellman-Ford" algorithm.
1.1267 + ///
1.1268 + /// This auxiliary class is created to implement the
1.1269 + /// \ref bellmanFord() "function-type interface" of the
1.1270 + /// \ref BellmanFord "Bellman-Ford" algorithm.
1.1271 + /// It does not have own \ref run() method, it uses the
1.1272 + /// functions and features of the plain \ref BellmanFord.
1.1273 + ///
1.1274 + /// This class should only be used through the \ref bellmanFord()
1.1275 + /// function, which makes it easier to use the algorithm.
1.1276 + template<class TR>
1.1277 + class BellmanFordWizard : public TR {
1.1278 + typedef TR Base;
1.1279
1.1280 - /// This class is created to make it easier to use BellmanFord algorithm.
1.1281 - /// It uses the functions and features of the plain \ref BellmanFord,
1.1282 - /// but it is much simpler to use it.
1.1283 - ///
1.1284 - /// Simplicity means that the way to change the types defined
1.1285 - /// in the traits class is based on functions that returns the new class
1.1286 - /// and not on templatable built-in classes.
1.1287 - /// When using the plain \ref BellmanFord
1.1288 - /// the new class with the modified type comes from
1.1289 - /// the original class by using the ::
1.1290 - /// operator. In the case of \ref BellmanFordWizard only
1.1291 - /// a function have to be called and it will
1.1292 - /// return the needed class.
1.1293 - ///
1.1294 - /// It does not have own \ref run method. When its \ref run method is called
1.1295 - /// it initiates a plain \ref BellmanFord class, and calls the \ref
1.1296 - /// BellmanFord::run method of it.
1.1297 - template<class _Traits>
1.1298 - class BellmanFordWizard : public _Traits {
1.1299 - typedef _Traits Base;
1.1300 -
1.1301 - ///The type of the underlying digraph.
1.1302 - typedef typename _Traits::Digraph Digraph;
1.1303 + typedef typename TR::Digraph Digraph;
1.1304
1.1305 typedef typename Digraph::Node Node;
1.1306 typedef typename Digraph::NodeIt NodeIt;
1.1307 typedef typename Digraph::Arc Arc;
1.1308 typedef typename Digraph::OutArcIt ArcIt;
1.1309
1.1310 - ///The type of the map that stores the arc lengths.
1.1311 - typedef typename _Traits::LengthMap LengthMap;
1.1312 -
1.1313 - ///The type of the length of the arcs.
1.1314 + typedef typename TR::LengthMap LengthMap;
1.1315 typedef typename LengthMap::Value Value;
1.1316 -
1.1317 - ///\brief The type of the map that stores the last
1.1318 - ///arcs of the shortest paths.
1.1319 - typedef typename _Traits::PredMap PredMap;
1.1320 -
1.1321 - ///The type of the map that stores the dists of the nodes.
1.1322 - typedef typename _Traits::DistMap DistMap;
1.1323 + typedef typename TR::PredMap PredMap;
1.1324 + typedef typename TR::DistMap DistMap;
1.1325 + typedef typename TR::Path Path;
1.1326
1.1327 public:
1.1328 /// Constructor.
1.1329 - BellmanFordWizard() : _Traits() {}
1.1330 + BellmanFordWizard() : TR() {}
1.1331
1.1332 /// \brief Constructor that requires parameters.
1.1333 ///
1.1334 /// Constructor that requires parameters.
1.1335 /// These parameters will be the default values for the traits class.
1.1336 - BellmanFordWizard(const Digraph& digraph, const LengthMap& length,
1.1337 - Node src = INVALID)
1.1338 - : _Traits(digraph, length, src) {}
1.1339 + /// \param gr The digraph the algorithm runs on.
1.1340 + /// \param len The length map.
1.1341 + BellmanFordWizard(const Digraph& gr, const LengthMap& len)
1.1342 + : TR(gr, len) {}
1.1343
1.1344 /// \brief Copy constructor
1.1345 - BellmanFordWizard(const _Traits &b) : _Traits(b) {}
1.1346 + BellmanFordWizard(const TR &b) : TR(b) {}
1.1347
1.1348 ~BellmanFordWizard() {}
1.1349
1.1350 - /// \brief Runs BellmanFord algorithm from a given node.
1.1351 + /// \brief Runs the Bellman-Ford algorithm from the given source node.
1.1352 ///
1.1353 - /// Runs BellmanFord algorithm from a given node.
1.1354 - /// The node can be given by the \ref source function.
1.1355 - void run() {
1.1356 - LEMON_ASSERT(Base::_source != INVALID, "Source node is not given");
1.1357 - BellmanFord<Digraph,LengthMap,_Traits>
1.1358 + /// This method runs the Bellman-Ford algorithm from the given source
1.1359 + /// node in order to compute the shortest path to each node.
1.1360 + void run(Node s) {
1.1361 + BellmanFord<Digraph,LengthMap,TR>
1.1362 bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.1363 *reinterpret_cast<const LengthMap*>(Base::_length));
1.1364 if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.1365 if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.1366 - bf.run(Base::_source);
1.1367 + bf.run(s);
1.1368 }
1.1369
1.1370 - /// \brief Runs BellmanFord algorithm from the given node.
1.1371 + /// \brief Runs the Bellman-Ford algorithm to find the shortest path
1.1372 + /// between \c s and \c t.
1.1373 ///
1.1374 - /// Runs BellmanFord algorithm from the given node.
1.1375 - /// \param src is the given source.
1.1376 - void run(Node src) {
1.1377 - Base::_source = src;
1.1378 - run();
1.1379 + /// This method runs the Bellman-Ford algorithm from node \c s
1.1380 + /// in order to compute the shortest path to node \c t.
1.1381 + /// Actually, it computes the shortest path to each node, but using
1.1382 + /// this function you can retrieve the distance and the shortest path
1.1383 + /// for a single target node easier.
1.1384 + ///
1.1385 + /// \return \c true if \c t is reachable form \c s.
1.1386 + bool run(Node s, Node t) {
1.1387 + BellmanFord<Digraph,LengthMap,TR>
1.1388 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
1.1389 + *reinterpret_cast<const LengthMap*>(Base::_length));
1.1390 + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.1391 + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.1392 + bf.run(s);
1.1393 + if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
1.1394 + if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
1.1395 + return bf.reached(t);
1.1396 }
1.1397
1.1398 template<class T>
1.1399 - struct DefPredMapBase : public Base {
1.1400 + struct SetPredMapBase : public Base {
1.1401 typedef T PredMap;
1.1402 static PredMap *createPredMap(const Digraph &) { return 0; };
1.1403 - DefPredMapBase(const _Traits &b) : _Traits(b) {}
1.1404 + SetPredMapBase(const TR &b) : TR(b) {}
1.1405 };
1.1406
1.1407 - ///\brief \ref named-templ-param "Named parameter"
1.1408 - ///function for setting PredMap type
1.1409 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1410 + /// the predecessor map.
1.1411 ///
1.1412 - /// \ref named-templ-param "Named parameter"
1.1413 - ///function for setting PredMap type
1.1414 - ///
1.1415 + /// \ref named-templ-param "Named parameter" for setting
1.1416 + /// the map that stores the predecessor arcs of the nodes.
1.1417 template<class T>
1.1418 - BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
1.1419 - {
1.1420 + BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
1.1421 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1422 - return BellmanFordWizard<DefPredMapBase<T> >(*this);
1.1423 + return BellmanFordWizard<SetPredMapBase<T> >(*this);
1.1424 }
1.1425
1.1426 template<class T>
1.1427 - struct DefDistMapBase : public Base {
1.1428 + struct SetDistMapBase : public Base {
1.1429 typedef T DistMap;
1.1430 static DistMap *createDistMap(const Digraph &) { return 0; };
1.1431 - DefDistMapBase(const _Traits &b) : _Traits(b) {}
1.1432 + SetDistMapBase(const TR &b) : TR(b) {}
1.1433 };
1.1434
1.1435 - ///\brief \ref named-templ-param "Named parameter"
1.1436 - ///function for setting DistMap type
1.1437 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1438 + /// the distance map.
1.1439 ///
1.1440 - /// \ref named-templ-param "Named parameter"
1.1441 - ///function for setting DistMap type
1.1442 - ///
1.1443 + /// \ref named-templ-param "Named parameter" for setting
1.1444 + /// the map that stores the distances of the nodes calculated
1.1445 + /// by the algorithm.
1.1446 template<class T>
1.1447 - BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
1.1448 + BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
1.1449 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1450 - return BellmanFordWizard<DefDistMapBase<T> >(*this);
1.1451 + return BellmanFordWizard<SetDistMapBase<T> >(*this);
1.1452 }
1.1453
1.1454 template<class T>
1.1455 - struct DefOperationTraitsBase : public Base {
1.1456 - typedef T OperationTraits;
1.1457 - DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1.1458 + struct SetPathBase : public Base {
1.1459 + typedef T Path;
1.1460 + SetPathBase(const TR &b) : TR(b) {}
1.1461 };
1.1462 -
1.1463 - ///\brief \ref named-templ-param "Named parameter"
1.1464 - ///function for setting OperationTraits type
1.1465 +
1.1466 + /// \brief \ref named-func-param "Named parameter" for getting
1.1467 + /// the shortest path to the target node.
1.1468 ///
1.1469 - /// \ref named-templ-param "Named parameter"
1.1470 - ///function for setting OperationTraits type
1.1471 + /// \ref named-func-param "Named parameter" for getting
1.1472 + /// the shortest path to the target node.
1.1473 + template<class T>
1.1474 + BellmanFordWizard<SetPathBase<T> > path(const T &t)
1.1475 + {
1.1476 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1477 + return BellmanFordWizard<SetPathBase<T> >(*this);
1.1478 + }
1.1479 +
1.1480 + /// \brief \ref named-func-param "Named parameter" for getting
1.1481 + /// the distance of the target node.
1.1482 ///
1.1483 - template<class T>
1.1484 - BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1.1485 - return BellmanFordWizard<DefDistMapBase<T> >(*this);
1.1486 - }
1.1487 -
1.1488 - /// \brief Sets the source node, from which the BellmanFord algorithm runs.
1.1489 - ///
1.1490 - /// Sets the source node, from which the BellmanFord algorithm runs.
1.1491 - /// \param src is the source node.
1.1492 - BellmanFordWizard<_Traits>& source(Node src) {
1.1493 - Base::_source = src;
1.1494 + /// \ref named-func-param "Named parameter" for getting
1.1495 + /// the distance of the target node.
1.1496 + BellmanFordWizard dist(const Value &d)
1.1497 + {
1.1498 + Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
1.1499 return *this;
1.1500 }
1.1501
1.1502 };
1.1503
1.1504 - /// \brief Function type interface for BellmanFord algorithm.
1.1505 + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
1.1506 + /// algorithm.
1.1507 ///
1.1508 /// \ingroup shortest_path
1.1509 - /// Function type interface for BellmanFord algorithm.
1.1510 + /// Function type interface for the \ref BellmanFord "Bellman-Ford"
1.1511 + /// algorithm.
1.1512 ///
1.1513 /// This function also has several \ref named-templ-func-param
1.1514 /// "named parameters", they are declared as the members of class
1.1515 /// \ref BellmanFordWizard.
1.1516 - /// The following
1.1517 - /// example shows how to use these parameters.
1.1518 - ///\code
1.1519 - /// bellmanford(g,length,source).predMap(preds).run();
1.1520 - ///\endcode
1.1521 + /// The following examples show how to use these parameters.
1.1522 + /// \code
1.1523 + /// // Compute shortest path from node s to each node
1.1524 + /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
1.1525 + ///
1.1526 + /// // Compute shortest path from s to t
1.1527 + /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
1.1528 + /// \endcode
1.1529 /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1.1530 /// to the end of the parameter list.
1.1531 /// \sa BellmanFordWizard
1.1532 /// \sa BellmanFord
1.1533 - template<class _Digraph, class _LengthMap>
1.1534 - BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
1.1535 - bellmanFord(const _Digraph& digraph,
1.1536 - const _LengthMap& length,
1.1537 - typename _Digraph::Node source = INVALID) {
1.1538 - return BellmanFordWizard<BellmanFordWizardBase<_Digraph,_LengthMap> >
1.1539 - (digraph, length, source);
1.1540 + template<typename GR, typename LEN>
1.1541 + BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
1.1542 + bellmanFord(const GR& digraph,
1.1543 + const LEN& length)
1.1544 + {
1.1545 + return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
1.1546 }
1.1547
1.1548 } //END OF NAMESPACE LEMON