1.1 --- a/lemon/Makefile.am Mon Aug 31 08:25:33 2009 +0200
1.2 +++ b/lemon/Makefile.am Mon Aug 31 08:32:25 2009 +0200
1.3 @@ -57,6 +57,7 @@
1.4 lemon/adaptors.h \
1.5 lemon/arg_parser.h \
1.6 lemon/assert.h \
1.7 + lemon/bellman_ford.h \
1.8 lemon/bfs.h \
1.9 lemon/bin_heap.h \
1.10 lemon/bucket_heap.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/bellman_ford.h Mon Aug 31 08:32:25 2009 +0200
2.3 @@ -0,0 +1,1100 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_BELLMAN_FORD_H
2.23 +#define LEMON_BELLMAN_FORD_H
2.24 +
2.25 +/// \ingroup shortest_path
2.26 +/// \file
2.27 +/// \brief Bellman-Ford algorithm.
2.28 +
2.29 +#include <lemon/bits/path_dump.h>
2.30 +#include <lemon/core.h>
2.31 +#include <lemon/error.h>
2.32 +#include <lemon/maps.h>
2.33 +#include <lemon/path.h>
2.34 +
2.35 +#include <limits>
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + /// \brief Default OperationTraits for the BellmanFord algorithm class.
2.40 + ///
2.41 + /// This operation traits class defines all computational operations
2.42 + /// and constants that are used in the Bellman-Ford algorithm.
2.43 + /// The default implementation is based on the \c numeric_limits class.
2.44 + /// If the numeric type does not have infinity value, then the maximum
2.45 + /// value is used as extremal infinity value.
2.46 + template <
2.47 + typename V,
2.48 + bool has_inf = std::numeric_limits<V>::has_infinity>
2.49 + struct BellmanFordDefaultOperationTraits {
2.50 + /// \e
2.51 + typedef V Value;
2.52 + /// \brief Gives back the zero value of the type.
2.53 + static Value zero() {
2.54 + return static_cast<Value>(0);
2.55 + }
2.56 + /// \brief Gives back the positive infinity value of the type.
2.57 + static Value infinity() {
2.58 + return std::numeric_limits<Value>::infinity();
2.59 + }
2.60 + /// \brief Gives back the sum of the given two elements.
2.61 + static Value plus(const Value& left, const Value& right) {
2.62 + return left + right;
2.63 + }
2.64 + /// \brief Gives back \c true only if the first value is less than
2.65 + /// the second.
2.66 + static bool less(const Value& left, const Value& right) {
2.67 + return left < right;
2.68 + }
2.69 + };
2.70 +
2.71 + template <typename V>
2.72 + struct BellmanFordDefaultOperationTraits<V, false> {
2.73 + typedef V Value;
2.74 + static Value zero() {
2.75 + return static_cast<Value>(0);
2.76 + }
2.77 + static Value infinity() {
2.78 + return std::numeric_limits<Value>::max();
2.79 + }
2.80 + static Value plus(const Value& left, const Value& right) {
2.81 + if (left == infinity() || right == infinity()) return infinity();
2.82 + return left + right;
2.83 + }
2.84 + static bool less(const Value& left, const Value& right) {
2.85 + return left < right;
2.86 + }
2.87 + };
2.88 +
2.89 + /// \brief Default traits class of BellmanFord class.
2.90 + ///
2.91 + /// Default traits class of BellmanFord class.
2.92 + /// \param GR The type of the digraph.
2.93 + /// \param LEN The type of the length map.
2.94 + template<typename GR, typename LEN>
2.95 + struct BellmanFordDefaultTraits {
2.96 + /// The type of the digraph the algorithm runs on.
2.97 + typedef GR Digraph;
2.98 +
2.99 + /// \brief The type of the map that stores the arc lengths.
2.100 + ///
2.101 + /// The type of the map that stores the arc lengths.
2.102 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
2.103 + typedef LEN LengthMap;
2.104 +
2.105 + /// The type of the arc lengths.
2.106 + typedef typename LEN::Value Value;
2.107 +
2.108 + /// \brief Operation traits for Bellman-Ford algorithm.
2.109 + ///
2.110 + /// It defines the used operations and the infinity value for the
2.111 + /// given \c Value type.
2.112 + /// \see BellmanFordDefaultOperationTraits
2.113 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
2.114 +
2.115 + /// \brief The type of the map that stores the last arcs of the
2.116 + /// shortest paths.
2.117 + ///
2.118 + /// The type of the map that stores the last
2.119 + /// arcs of the shortest paths.
2.120 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.121 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
2.122 +
2.123 + /// \brief Instantiates a \c PredMap.
2.124 + ///
2.125 + /// This function instantiates a \ref PredMap.
2.126 + /// \param g is the digraph to which we would like to define the
2.127 + /// \ref PredMap.
2.128 + static PredMap *createPredMap(const GR& g) {
2.129 + return new PredMap(g);
2.130 + }
2.131 +
2.132 + /// \brief The type of the map that stores the distances of the nodes.
2.133 + ///
2.134 + /// The type of the map that stores the distances of the nodes.
2.135 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.136 + typedef typename GR::template NodeMap<typename LEN::Value> DistMap;
2.137 +
2.138 + /// \brief Instantiates a \c DistMap.
2.139 + ///
2.140 + /// This function instantiates a \ref DistMap.
2.141 + /// \param g is the digraph to which we would like to define the
2.142 + /// \ref DistMap.
2.143 + static DistMap *createDistMap(const GR& g) {
2.144 + return new DistMap(g);
2.145 + }
2.146 +
2.147 + };
2.148 +
2.149 + /// \brief %BellmanFord algorithm class.
2.150 + ///
2.151 + /// \ingroup shortest_path
2.152 + /// This class provides an efficient implementation of the Bellman-Ford
2.153 + /// algorithm. The maximum time complexity of the algorithm is
2.154 + /// <tt>O(ne)</tt>.
2.155 + ///
2.156 + /// The Bellman-Ford algorithm solves the single-source shortest path
2.157 + /// problem when the arcs can have negative lengths, but the digraph
2.158 + /// should not contain directed cycles with negative total length.
2.159 + /// If all arc costs are non-negative, consider to use the Dijkstra
2.160 + /// algorithm instead, since it is more efficient.
2.161 + ///
2.162 + /// The arc lengths are passed to the algorithm using a
2.163 + /// \ref concepts::ReadMap "ReadMap", so it is easy to change it to any
2.164 + /// kind of length. The type of the length values is determined by the
2.165 + /// \ref concepts::ReadMap::Value "Value" type of the length map.
2.166 + ///
2.167 + /// There is also a \ref bellmanFord() "function-type interface" for the
2.168 + /// Bellman-Ford algorithm, which is convenient in the simplier cases and
2.169 + /// it can be used easier.
2.170 + ///
2.171 + /// \tparam GR The type of the digraph the algorithm runs on.
2.172 + /// The default type is \ref ListDigraph.
2.173 + /// \tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
2.174 + /// the lengths of the arcs. The default map type is
2.175 + /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
2.176 +#ifdef DOXYGEN
2.177 + template <typename GR, typename LEN, typename TR>
2.178 +#else
2.179 + template <typename GR=ListDigraph,
2.180 + typename LEN=typename GR::template ArcMap<int>,
2.181 + typename TR=BellmanFordDefaultTraits<GR,LEN> >
2.182 +#endif
2.183 + class BellmanFord {
2.184 + public:
2.185 +
2.186 + ///The type of the underlying digraph.
2.187 + typedef typename TR::Digraph Digraph;
2.188 +
2.189 + /// \brief The type of the arc lengths.
2.190 + typedef typename TR::LengthMap::Value Value;
2.191 + /// \brief The type of the map that stores the arc lengths.
2.192 + typedef typename TR::LengthMap LengthMap;
2.193 + /// \brief The type of the map that stores the last
2.194 + /// arcs of the shortest paths.
2.195 + typedef typename TR::PredMap PredMap;
2.196 + /// \brief The type of the map that stores the distances of the nodes.
2.197 + typedef typename TR::DistMap DistMap;
2.198 + /// The type of the paths.
2.199 + typedef PredMapPath<Digraph, PredMap> Path;
2.200 + ///\brief The \ref BellmanFordDefaultOperationTraits
2.201 + /// "operation traits class" of the algorithm.
2.202 + typedef typename TR::OperationTraits OperationTraits;
2.203 +
2.204 + ///The \ref BellmanFordDefaultTraits "traits class" of the algorithm.
2.205 + typedef TR Traits;
2.206 +
2.207 + private:
2.208 +
2.209 + typedef typename Digraph::Node Node;
2.210 + typedef typename Digraph::NodeIt NodeIt;
2.211 + typedef typename Digraph::Arc Arc;
2.212 + typedef typename Digraph::OutArcIt OutArcIt;
2.213 +
2.214 + // Pointer to the underlying digraph.
2.215 + const Digraph *_gr;
2.216 + // Pointer to the length map
2.217 + const LengthMap *_length;
2.218 + // Pointer to the map of predecessors arcs.
2.219 + PredMap *_pred;
2.220 + // Indicates if _pred is locally allocated (true) or not.
2.221 + bool _local_pred;
2.222 + // Pointer to the map of distances.
2.223 + DistMap *_dist;
2.224 + // Indicates if _dist is locally allocated (true) or not.
2.225 + bool _local_dist;
2.226 +
2.227 + typedef typename Digraph::template NodeMap<bool> MaskMap;
2.228 + MaskMap *_mask;
2.229 +
2.230 + std::vector<Node> _process;
2.231 +
2.232 + // Creates the maps if necessary.
2.233 + void create_maps() {
2.234 + if(!_pred) {
2.235 + _local_pred = true;
2.236 + _pred = Traits::createPredMap(*_gr);
2.237 + }
2.238 + if(!_dist) {
2.239 + _local_dist = true;
2.240 + _dist = Traits::createDistMap(*_gr);
2.241 + }
2.242 + _mask = new MaskMap(*_gr, false);
2.243 + }
2.244 +
2.245 + public :
2.246 +
2.247 + typedef BellmanFord Create;
2.248 +
2.249 + /// \name Named Template Parameters
2.250 +
2.251 + ///@{
2.252 +
2.253 + template <class T>
2.254 + struct SetPredMapTraits : public Traits {
2.255 + typedef T PredMap;
2.256 + static PredMap *createPredMap(const Digraph&) {
2.257 + LEMON_ASSERT(false, "PredMap is not initialized");
2.258 + return 0; // ignore warnings
2.259 + }
2.260 + };
2.261 +
2.262 + /// \brief \ref named-templ-param "Named parameter" for setting
2.263 + /// \c PredMap type.
2.264 + ///
2.265 + /// \ref named-templ-param "Named parameter" for setting
2.266 + /// \c PredMap type.
2.267 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.268 + template <class T>
2.269 + struct SetPredMap
2.270 + : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {
2.271 + typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;
2.272 + };
2.273 +
2.274 + template <class T>
2.275 + struct SetDistMapTraits : public Traits {
2.276 + typedef T DistMap;
2.277 + static DistMap *createDistMap(const Digraph&) {
2.278 + LEMON_ASSERT(false, "DistMap is not initialized");
2.279 + return 0; // ignore warnings
2.280 + }
2.281 + };
2.282 +
2.283 + /// \brief \ref named-templ-param "Named parameter" for setting
2.284 + /// \c DistMap type.
2.285 + ///
2.286 + /// \ref named-templ-param "Named parameter" for setting
2.287 + /// \c DistMap type.
2.288 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.289 + template <class T>
2.290 + struct SetDistMap
2.291 + : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {
2.292 + typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;
2.293 + };
2.294 +
2.295 + template <class T>
2.296 + struct SetOperationTraitsTraits : public Traits {
2.297 + typedef T OperationTraits;
2.298 + };
2.299 +
2.300 + /// \brief \ref named-templ-param "Named parameter" for setting
2.301 + /// \c OperationTraits type.
2.302 + ///
2.303 + /// \ref named-templ-param "Named parameter" for setting
2.304 + /// \c OperationTraits type.
2.305 + /// For more information see \ref BellmanFordDefaultOperationTraits.
2.306 + template <class T>
2.307 + struct SetOperationTraits
2.308 + : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {
2.309 + typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >
2.310 + Create;
2.311 + };
2.312 +
2.313 + ///@}
2.314 +
2.315 + protected:
2.316 +
2.317 + BellmanFord() {}
2.318 +
2.319 + public:
2.320 +
2.321 + /// \brief Constructor.
2.322 + ///
2.323 + /// Constructor.
2.324 + /// \param g The digraph the algorithm runs on.
2.325 + /// \param length The length map used by the algorithm.
2.326 + BellmanFord(const Digraph& g, const LengthMap& length) :
2.327 + _gr(&g), _length(&length),
2.328 + _pred(0), _local_pred(false),
2.329 + _dist(0), _local_dist(false), _mask(0) {}
2.330 +
2.331 + ///Destructor.
2.332 + ~BellmanFord() {
2.333 + if(_local_pred) delete _pred;
2.334 + if(_local_dist) delete _dist;
2.335 + if(_mask) delete _mask;
2.336 + }
2.337 +
2.338 + /// \brief Sets the length map.
2.339 + ///
2.340 + /// Sets the length map.
2.341 + /// \return <tt>(*this)</tt>
2.342 + BellmanFord &lengthMap(const LengthMap &map) {
2.343 + _length = ↦
2.344 + return *this;
2.345 + }
2.346 +
2.347 + /// \brief Sets the map that stores the predecessor arcs.
2.348 + ///
2.349 + /// Sets the map that stores the predecessor arcs.
2.350 + /// If you don't use this function before calling \ref run()
2.351 + /// or \ref init(), an instance will be allocated automatically.
2.352 + /// The destructor deallocates this automatically allocated map,
2.353 + /// of course.
2.354 + /// \return <tt>(*this)</tt>
2.355 + BellmanFord &predMap(PredMap &map) {
2.356 + if(_local_pred) {
2.357 + delete _pred;
2.358 + _local_pred=false;
2.359 + }
2.360 + _pred = ↦
2.361 + return *this;
2.362 + }
2.363 +
2.364 + /// \brief Sets the map that stores the distances of the nodes.
2.365 + ///
2.366 + /// Sets the map that stores the distances of the nodes calculated
2.367 + /// by the algorithm.
2.368 + /// If you don't use this function before calling \ref run()
2.369 + /// or \ref init(), an instance will be allocated automatically.
2.370 + /// The destructor deallocates this automatically allocated map,
2.371 + /// of course.
2.372 + /// \return <tt>(*this)</tt>
2.373 + BellmanFord &distMap(DistMap &map) {
2.374 + if(_local_dist) {
2.375 + delete _dist;
2.376 + _local_dist=false;
2.377 + }
2.378 + _dist = ↦
2.379 + return *this;
2.380 + }
2.381 +
2.382 + /// \name Execution Control
2.383 + /// The simplest way to execute the Bellman-Ford algorithm is to use
2.384 + /// one of the member functions called \ref run().\n
2.385 + /// If you need better control on the execution, you have to call
2.386 + /// \ref init() first, then you can add several source nodes
2.387 + /// with \ref addSource(). Finally the actual path computation can be
2.388 + /// performed with \ref start(), \ref checkedStart() or
2.389 + /// \ref limitedStart().
2.390 +
2.391 + ///@{
2.392 +
2.393 + /// \brief Initializes the internal data structures.
2.394 + ///
2.395 + /// Initializes the internal data structures. The optional parameter
2.396 + /// is the initial distance of each node.
2.397 + void init(const Value value = OperationTraits::infinity()) {
2.398 + create_maps();
2.399 + for (NodeIt it(*_gr); it != INVALID; ++it) {
2.400 + _pred->set(it, INVALID);
2.401 + _dist->set(it, value);
2.402 + }
2.403 + _process.clear();
2.404 + if (OperationTraits::less(value, OperationTraits::infinity())) {
2.405 + for (NodeIt it(*_gr); it != INVALID; ++it) {
2.406 + _process.push_back(it);
2.407 + _mask->set(it, true);
2.408 + }
2.409 + }
2.410 + }
2.411 +
2.412 + /// \brief Adds a new source node.
2.413 + ///
2.414 + /// This function adds a new source node. The optional second parameter
2.415 + /// is the initial distance of the node.
2.416 + void addSource(Node source, Value dst = OperationTraits::zero()) {
2.417 + _dist->set(source, dst);
2.418 + if (!(*_mask)[source]) {
2.419 + _process.push_back(source);
2.420 + _mask->set(source, true);
2.421 + }
2.422 + }
2.423 +
2.424 + /// \brief Executes one round from the Bellman-Ford algorithm.
2.425 + ///
2.426 + /// If the algoritm calculated the distances in the previous round
2.427 + /// exactly for the paths of at most \c k arcs, then this function
2.428 + /// will calculate the distances exactly for the paths of at most
2.429 + /// <tt>k+1</tt> arcs. Performing \c k iterations using this function
2.430 + /// calculates the shortest path distances exactly for the paths
2.431 + /// consisting of at most \c k arcs.
2.432 + ///
2.433 + /// \warning The paths with limited arc number cannot be retrieved
2.434 + /// easily with \ref path() or \ref predArc() functions. If you also
2.435 + /// need the shortest paths and not only the distances, you should
2.436 + /// store the \ref predMap() "predecessor map" after each iteration
2.437 + /// and build the path manually.
2.438 + ///
2.439 + /// \return \c true when the algorithm have not found more shorter
2.440 + /// paths.
2.441 + ///
2.442 + /// \see ActiveIt
2.443 + bool processNextRound() {
2.444 + for (int i = 0; i < int(_process.size()); ++i) {
2.445 + _mask->set(_process[i], false);
2.446 + }
2.447 + std::vector<Node> nextProcess;
2.448 + std::vector<Value> values(_process.size());
2.449 + for (int i = 0; i < int(_process.size()); ++i) {
2.450 + values[i] = (*_dist)[_process[i]];
2.451 + }
2.452 + for (int i = 0; i < int(_process.size()); ++i) {
2.453 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
2.454 + Node target = _gr->target(it);
2.455 + Value relaxed = OperationTraits::plus(values[i], (*_length)[it]);
2.456 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
2.457 + _pred->set(target, it);
2.458 + _dist->set(target, relaxed);
2.459 + if (!(*_mask)[target]) {
2.460 + _mask->set(target, true);
2.461 + nextProcess.push_back(target);
2.462 + }
2.463 + }
2.464 + }
2.465 + }
2.466 + _process.swap(nextProcess);
2.467 + return _process.empty();
2.468 + }
2.469 +
2.470 + /// \brief Executes one weak round from the Bellman-Ford algorithm.
2.471 + ///
2.472 + /// If the algorithm calculated the distances in the previous round
2.473 + /// at least for the paths of at most \c k arcs, then this function
2.474 + /// will calculate the distances at least for the paths of at most
2.475 + /// <tt>k+1</tt> arcs.
2.476 + /// This function does not make it possible to calculate the shortest
2.477 + /// path distances exactly for paths consisting of at most \c k arcs,
2.478 + /// this is why it is called weak round.
2.479 + ///
2.480 + /// \return \c true when the algorithm have not found more shorter
2.481 + /// paths.
2.482 + ///
2.483 + /// \see ActiveIt
2.484 + bool processNextWeakRound() {
2.485 + for (int i = 0; i < int(_process.size()); ++i) {
2.486 + _mask->set(_process[i], false);
2.487 + }
2.488 + std::vector<Node> nextProcess;
2.489 + for (int i = 0; i < int(_process.size()); ++i) {
2.490 + for (OutArcIt it(*_gr, _process[i]); it != INVALID; ++it) {
2.491 + Node target = _gr->target(it);
2.492 + Value relaxed =
2.493 + OperationTraits::plus((*_dist)[_process[i]], (*_length)[it]);
2.494 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
2.495 + _pred->set(target, it);
2.496 + _dist->set(target, relaxed);
2.497 + if (!(*_mask)[target]) {
2.498 + _mask->set(target, true);
2.499 + nextProcess.push_back(target);
2.500 + }
2.501 + }
2.502 + }
2.503 + }
2.504 + _process.swap(nextProcess);
2.505 + return _process.empty();
2.506 + }
2.507 +
2.508 + /// \brief Executes the algorithm.
2.509 + ///
2.510 + /// Executes the algorithm.
2.511 + ///
2.512 + /// This method runs the Bellman-Ford algorithm from the root node(s)
2.513 + /// in order to compute the shortest path to each node.
2.514 + ///
2.515 + /// The algorithm computes
2.516 + /// - the shortest path tree (forest),
2.517 + /// - the distance of each node from the root(s).
2.518 + ///
2.519 + /// \pre init() must be called and at least one root node should be
2.520 + /// added with addSource() before using this function.
2.521 + void start() {
2.522 + int num = countNodes(*_gr) - 1;
2.523 + for (int i = 0; i < num; ++i) {
2.524 + if (processNextWeakRound()) break;
2.525 + }
2.526 + }
2.527 +
2.528 + /// \brief Executes the algorithm and checks the negative cycles.
2.529 + ///
2.530 + /// Executes the algorithm and checks the negative cycles.
2.531 + ///
2.532 + /// This method runs the Bellman-Ford algorithm from the root node(s)
2.533 + /// in order to compute the shortest path to each node and also checks
2.534 + /// if the digraph contains cycles with negative total length.
2.535 + ///
2.536 + /// The algorithm computes
2.537 + /// - the shortest path tree (forest),
2.538 + /// - the distance of each node from the root(s).
2.539 + ///
2.540 + /// \return \c false if there is a negative cycle in the digraph.
2.541 + ///
2.542 + /// \pre init() must be called and at least one root node should be
2.543 + /// added with addSource() before using this function.
2.544 + bool checkedStart() {
2.545 + int num = countNodes(*_gr);
2.546 + for (int i = 0; i < num; ++i) {
2.547 + if (processNextWeakRound()) return true;
2.548 + }
2.549 + return _process.empty();
2.550 + }
2.551 +
2.552 + /// \brief Executes the algorithm with arc number limit.
2.553 + ///
2.554 + /// Executes the algorithm with arc number limit.
2.555 + ///
2.556 + /// This method runs the Bellman-Ford algorithm from the root node(s)
2.557 + /// in order to compute the shortest path distance for each node
2.558 + /// using only the paths consisting of at most \c num arcs.
2.559 + ///
2.560 + /// The algorithm computes
2.561 + /// - the limited distance of each node from the root(s),
2.562 + /// - the predecessor arc for each node.
2.563 + ///
2.564 + /// \warning The paths with limited arc number cannot be retrieved
2.565 + /// easily with \ref path() or \ref predArc() functions. If you also
2.566 + /// need the shortest paths and not only the distances, you should
2.567 + /// store the \ref predMap() "predecessor map" after each iteration
2.568 + /// and build the path manually.
2.569 + ///
2.570 + /// \pre init() must be called and at least one root node should be
2.571 + /// added with addSource() before using this function.
2.572 + void limitedStart(int num) {
2.573 + for (int i = 0; i < num; ++i) {
2.574 + if (processNextRound()) break;
2.575 + }
2.576 + }
2.577 +
2.578 + /// \brief Runs the algorithm from the given root node.
2.579 + ///
2.580 + /// This method runs the Bellman-Ford algorithm from the given root
2.581 + /// node \c s in order to compute the shortest path to each node.
2.582 + ///
2.583 + /// The algorithm computes
2.584 + /// - the shortest path tree (forest),
2.585 + /// - the distance of each node from the root(s).
2.586 + ///
2.587 + /// \note bf.run(s) is just a shortcut of the following code.
2.588 + /// \code
2.589 + /// bf.init();
2.590 + /// bf.addSource(s);
2.591 + /// bf.start();
2.592 + /// \endcode
2.593 + void run(Node s) {
2.594 + init();
2.595 + addSource(s);
2.596 + start();
2.597 + }
2.598 +
2.599 + /// \brief Runs the algorithm from the given root node with arc
2.600 + /// number limit.
2.601 + ///
2.602 + /// This method runs the Bellman-Ford algorithm from the given root
2.603 + /// node \c s in order to compute the shortest path distance for each
2.604 + /// node using only the paths consisting of at most \c num arcs.
2.605 + ///
2.606 + /// The algorithm computes
2.607 + /// - the limited distance of each node from the root(s),
2.608 + /// - the predecessor arc for each node.
2.609 + ///
2.610 + /// \warning The paths with limited arc number cannot be retrieved
2.611 + /// easily with \ref path() or \ref predArc() functions. If you also
2.612 + /// need the shortest paths and not only the distances, you should
2.613 + /// store the \ref predMap() "predecessor map" after each iteration
2.614 + /// and build the path manually.
2.615 + ///
2.616 + /// \note bf.run(s, num) is just a shortcut of the following code.
2.617 + /// \code
2.618 + /// bf.init();
2.619 + /// bf.addSource(s);
2.620 + /// bf.limitedStart(num);
2.621 + /// \endcode
2.622 + void run(Node s, int num) {
2.623 + init();
2.624 + addSource(s);
2.625 + limitedStart(num);
2.626 + }
2.627 +
2.628 + ///@}
2.629 +
2.630 + /// \brief LEMON iterator for getting the active nodes.
2.631 + ///
2.632 + /// This class provides a common style LEMON iterator that traverses
2.633 + /// the active nodes of the Bellman-Ford algorithm after the last
2.634 + /// phase. These nodes should be checked in the next phase to
2.635 + /// find augmenting arcs outgoing from them.
2.636 + class ActiveIt {
2.637 + public:
2.638 +
2.639 + /// \brief Constructor.
2.640 + ///
2.641 + /// Constructor for getting the active nodes of the given BellmanFord
2.642 + /// instance.
2.643 + ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
2.644 + {
2.645 + _index = _algorithm->_process.size() - 1;
2.646 + }
2.647 +
2.648 + /// \brief Invalid constructor.
2.649 + ///
2.650 + /// Invalid constructor.
2.651 + ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
2.652 +
2.653 + /// \brief Conversion to \c Node.
2.654 + ///
2.655 + /// Conversion to \c Node.
2.656 + operator Node() const {
2.657 + return _index >= 0 ? _algorithm->_process[_index] : INVALID;
2.658 + }
2.659 +
2.660 + /// \brief Increment operator.
2.661 + ///
2.662 + /// Increment operator.
2.663 + ActiveIt& operator++() {
2.664 + --_index;
2.665 + return *this;
2.666 + }
2.667 +
2.668 + bool operator==(const ActiveIt& it) const {
2.669 + return static_cast<Node>(*this) == static_cast<Node>(it);
2.670 + }
2.671 + bool operator!=(const ActiveIt& it) const {
2.672 + return static_cast<Node>(*this) != static_cast<Node>(it);
2.673 + }
2.674 + bool operator<(const ActiveIt& it) const {
2.675 + return static_cast<Node>(*this) < static_cast<Node>(it);
2.676 + }
2.677 +
2.678 + private:
2.679 + const BellmanFord* _algorithm;
2.680 + int _index;
2.681 + };
2.682 +
2.683 + /// \name Query Functions
2.684 + /// The result of the Bellman-Ford algorithm can be obtained using these
2.685 + /// functions.\n
2.686 + /// Either \ref run() or \ref init() should be called before using them.
2.687 +
2.688 + ///@{
2.689 +
2.690 + /// \brief The shortest path to the given node.
2.691 + ///
2.692 + /// Gives back the shortest path to the given node from the root(s).
2.693 + ///
2.694 + /// \warning \c t should be reached from the root(s).
2.695 + ///
2.696 + /// \pre Either \ref run() or \ref init() must be called before
2.697 + /// using this function.
2.698 + Path path(Node t) const
2.699 + {
2.700 + return Path(*_gr, *_pred, t);
2.701 + }
2.702 +
2.703 + /// \brief The distance of the given node from the root(s).
2.704 + ///
2.705 + /// Returns the distance of the given node from the root(s).
2.706 + ///
2.707 + /// \warning If node \c v is not reached from the root(s), then
2.708 + /// the return value of this function is undefined.
2.709 + ///
2.710 + /// \pre Either \ref run() or \ref init() must be called before
2.711 + /// using this function.
2.712 + Value dist(Node v) const { return (*_dist)[v]; }
2.713 +
2.714 + /// \brief Returns the 'previous arc' of the shortest path tree for
2.715 + /// the given node.
2.716 + ///
2.717 + /// This function returns the 'previous arc' of the shortest path
2.718 + /// tree for node \c v, i.e. it returns the last arc of a
2.719 + /// shortest path from a root to \c v. It is \c INVALID if \c v
2.720 + /// is not reached from the root(s) or if \c v is a root.
2.721 + ///
2.722 + /// The shortest path tree used here is equal to the shortest path
2.723 + /// tree used in \ref predNode() and \predMap().
2.724 + ///
2.725 + /// \pre Either \ref run() or \ref init() must be called before
2.726 + /// using this function.
2.727 + Arc predArc(Node v) const { return (*_pred)[v]; }
2.728 +
2.729 + /// \brief Returns the 'previous node' of the shortest path tree for
2.730 + /// the given node.
2.731 + ///
2.732 + /// This function returns the 'previous node' of the shortest path
2.733 + /// tree for node \c v, i.e. it returns the last but one node of
2.734 + /// a shortest path from a root to \c v. It is \c INVALID if \c v
2.735 + /// is not reached from the root(s) or if \c v is a root.
2.736 + ///
2.737 + /// The shortest path tree used here is equal to the shortest path
2.738 + /// tree used in \ref predArc() and \predMap().
2.739 + ///
2.740 + /// \pre Either \ref run() or \ref init() must be called before
2.741 + /// using this function.
2.742 + Node predNode(Node v) const {
2.743 + return (*_pred)[v] == INVALID ? INVALID : _gr->source((*_pred)[v]);
2.744 + }
2.745 +
2.746 + /// \brief Returns a const reference to the node map that stores the
2.747 + /// distances of the nodes.
2.748 + ///
2.749 + /// Returns a const reference to the node map that stores the distances
2.750 + /// of the nodes calculated by the algorithm.
2.751 + ///
2.752 + /// \pre Either \ref run() or \ref init() must be called before
2.753 + /// using this function.
2.754 + const DistMap &distMap() const { return *_dist;}
2.755 +
2.756 + /// \brief Returns a const reference to the node map that stores the
2.757 + /// predecessor arcs.
2.758 + ///
2.759 + /// Returns a const reference to the node map that stores the predecessor
2.760 + /// arcs, which form the shortest path tree (forest).
2.761 + ///
2.762 + /// \pre Either \ref run() or \ref init() must be called before
2.763 + /// using this function.
2.764 + const PredMap &predMap() const { return *_pred; }
2.765 +
2.766 + /// \brief Checks if a node is reached from the root(s).
2.767 + ///
2.768 + /// Returns \c true if \c v is reached from the root(s).
2.769 + ///
2.770 + /// \pre Either \ref run() or \ref init() must be called before
2.771 + /// using this function.
2.772 + bool reached(Node v) const {
2.773 + return (*_dist)[v] != OperationTraits::infinity();
2.774 + }
2.775 +
2.776 + /// \brief Gives back a negative cycle.
2.777 + ///
2.778 + /// This function gives back a directed cycle with negative total
2.779 + /// length if the algorithm has already found one.
2.780 + /// Otherwise it gives back an empty path.
2.781 + lemon::Path<Digraph> negativeCycle() {
2.782 + typename Digraph::template NodeMap<int> state(*_gr, -1);
2.783 + lemon::Path<Digraph> cycle;
2.784 + for (int i = 0; i < int(_process.size()); ++i) {
2.785 + if (state[_process[i]] != -1) continue;
2.786 + for (Node v = _process[i]; (*_pred)[v] != INVALID;
2.787 + v = _gr->source((*_pred)[v])) {
2.788 + if (state[v] == i) {
2.789 + cycle.addFront((*_pred)[v]);
2.790 + for (Node u = _gr->source((*_pred)[v]); u != v;
2.791 + u = _gr->source((*_pred)[u])) {
2.792 + cycle.addFront((*_pred)[u]);
2.793 + }
2.794 + return cycle;
2.795 + }
2.796 + else if (state[v] >= 0) {
2.797 + break;
2.798 + }
2.799 + state[v] = i;
2.800 + }
2.801 + }
2.802 + return cycle;
2.803 + }
2.804 +
2.805 + ///@}
2.806 + };
2.807 +
2.808 + /// \brief Default traits class of bellmanFord() function.
2.809 + ///
2.810 + /// Default traits class of bellmanFord() function.
2.811 + /// \tparam GR The type of the digraph.
2.812 + /// \tparam LEN The type of the length map.
2.813 + template <typename GR, typename LEN>
2.814 + struct BellmanFordWizardDefaultTraits {
2.815 + /// The type of the digraph the algorithm runs on.
2.816 + typedef GR Digraph;
2.817 +
2.818 + /// \brief The type of the map that stores the arc lengths.
2.819 + ///
2.820 + /// The type of the map that stores the arc lengths.
2.821 + /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
2.822 + typedef LEN LengthMap;
2.823 +
2.824 + /// The type of the arc lengths.
2.825 + typedef typename LEN::Value Value;
2.826 +
2.827 + /// \brief Operation traits for Bellman-Ford algorithm.
2.828 + ///
2.829 + /// It defines the used operations and the infinity value for the
2.830 + /// given \c Value type.
2.831 + /// \see BellmanFordDefaultOperationTraits
2.832 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
2.833 +
2.834 + /// \brief The type of the map that stores the last
2.835 + /// arcs of the shortest paths.
2.836 + ///
2.837 + /// The type of the map that stores the last arcs of the shortest paths.
2.838 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.839 + typedef typename GR::template NodeMap<typename GR::Arc> PredMap;
2.840 +
2.841 + /// \brief Instantiates a \c PredMap.
2.842 + ///
2.843 + /// This function instantiates a \ref PredMap.
2.844 + /// \param g is the digraph to which we would like to define the
2.845 + /// \ref PredMap.
2.846 + static PredMap *createPredMap(const GR &g) {
2.847 + return new PredMap(g);
2.848 + }
2.849 +
2.850 + /// \brief The type of the map that stores the distances of the nodes.
2.851 + ///
2.852 + /// The type of the map that stores the distances of the nodes.
2.853 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
2.854 + typedef typename GR::template NodeMap<Value> DistMap;
2.855 +
2.856 + /// \brief Instantiates a \c DistMap.
2.857 + ///
2.858 + /// This function instantiates a \ref DistMap.
2.859 + /// \param g is the digraph to which we would like to define the
2.860 + /// \ref DistMap.
2.861 + static DistMap *createDistMap(const GR &g) {
2.862 + return new DistMap(g);
2.863 + }
2.864 +
2.865 + ///The type of the shortest paths.
2.866 +
2.867 + ///The type of the shortest paths.
2.868 + ///It must meet the \ref concepts::Path "Path" concept.
2.869 + typedef lemon::Path<Digraph> Path;
2.870 + };
2.871 +
2.872 + /// \brief Default traits class used by BellmanFordWizard.
2.873 + ///
2.874 + /// Default traits class used by BellmanFordWizard.
2.875 + /// \tparam GR The type of the digraph.
2.876 + /// \tparam LEN The type of the length map.
2.877 + template <typename GR, typename LEN>
2.878 + class BellmanFordWizardBase
2.879 + : public BellmanFordWizardDefaultTraits<GR, LEN> {
2.880 +
2.881 + typedef BellmanFordWizardDefaultTraits<GR, LEN> Base;
2.882 + protected:
2.883 + // Type of the nodes in the digraph.
2.884 + typedef typename Base::Digraph::Node Node;
2.885 +
2.886 + // Pointer to the underlying digraph.
2.887 + void *_graph;
2.888 + // Pointer to the length map
2.889 + void *_length;
2.890 + // Pointer to the map of predecessors arcs.
2.891 + void *_pred;
2.892 + // Pointer to the map of distances.
2.893 + void *_dist;
2.894 + //Pointer to the shortest path to the target node.
2.895 + void *_path;
2.896 + //Pointer to the distance of the target node.
2.897 + void *_di;
2.898 +
2.899 + public:
2.900 + /// Constructor.
2.901 +
2.902 + /// This constructor does not require parameters, it initiates
2.903 + /// all of the attributes to default values \c 0.
2.904 + BellmanFordWizardBase() :
2.905 + _graph(0), _length(0), _pred(0), _dist(0), _path(0), _di(0) {}
2.906 +
2.907 + /// Constructor.
2.908 +
2.909 + /// This constructor requires two parameters,
2.910 + /// others are initiated to \c 0.
2.911 + /// \param gr The digraph the algorithm runs on.
2.912 + /// \param len The length map.
2.913 + BellmanFordWizardBase(const GR& gr,
2.914 + const LEN& len) :
2.915 + _graph(reinterpret_cast<void*>(const_cast<GR*>(&gr))),
2.916 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&len))),
2.917 + _pred(0), _dist(0), _path(0), _di(0) {}
2.918 +
2.919 + };
2.920 +
2.921 + /// \brief Auxiliary class for the function-type interface of the
2.922 + /// \ref BellmanFord "Bellman-Ford" algorithm.
2.923 + ///
2.924 + /// This auxiliary class is created to implement the
2.925 + /// \ref bellmanFord() "function-type interface" of the
2.926 + /// \ref BellmanFord "Bellman-Ford" algorithm.
2.927 + /// It does not have own \ref run() method, it uses the
2.928 + /// functions and features of the plain \ref BellmanFord.
2.929 + ///
2.930 + /// This class should only be used through the \ref bellmanFord()
2.931 + /// function, which makes it easier to use the algorithm.
2.932 + template<class TR>
2.933 + class BellmanFordWizard : public TR {
2.934 + typedef TR Base;
2.935 +
2.936 + typedef typename TR::Digraph Digraph;
2.937 +
2.938 + typedef typename Digraph::Node Node;
2.939 + typedef typename Digraph::NodeIt NodeIt;
2.940 + typedef typename Digraph::Arc Arc;
2.941 + typedef typename Digraph::OutArcIt ArcIt;
2.942 +
2.943 + typedef typename TR::LengthMap LengthMap;
2.944 + typedef typename LengthMap::Value Value;
2.945 + typedef typename TR::PredMap PredMap;
2.946 + typedef typename TR::DistMap DistMap;
2.947 + typedef typename TR::Path Path;
2.948 +
2.949 + public:
2.950 + /// Constructor.
2.951 + BellmanFordWizard() : TR() {}
2.952 +
2.953 + /// \brief Constructor that requires parameters.
2.954 + ///
2.955 + /// Constructor that requires parameters.
2.956 + /// These parameters will be the default values for the traits class.
2.957 + /// \param gr The digraph the algorithm runs on.
2.958 + /// \param len The length map.
2.959 + BellmanFordWizard(const Digraph& gr, const LengthMap& len)
2.960 + : TR(gr, len) {}
2.961 +
2.962 + /// \brief Copy constructor
2.963 + BellmanFordWizard(const TR &b) : TR(b) {}
2.964 +
2.965 + ~BellmanFordWizard() {}
2.966 +
2.967 + /// \brief Runs the Bellman-Ford algorithm from the given source node.
2.968 + ///
2.969 + /// This method runs the Bellman-Ford algorithm from the given source
2.970 + /// node in order to compute the shortest path to each node.
2.971 + void run(Node s) {
2.972 + BellmanFord<Digraph,LengthMap,TR>
2.973 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
2.974 + *reinterpret_cast<const LengthMap*>(Base::_length));
2.975 + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
2.976 + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
2.977 + bf.run(s);
2.978 + }
2.979 +
2.980 + /// \brief Runs the Bellman-Ford algorithm to find the shortest path
2.981 + /// between \c s and \c t.
2.982 + ///
2.983 + /// This method runs the Bellman-Ford algorithm from node \c s
2.984 + /// in order to compute the shortest path to node \c t.
2.985 + /// Actually, it computes the shortest path to each node, but using
2.986 + /// this function you can retrieve the distance and the shortest path
2.987 + /// for a single target node easier.
2.988 + ///
2.989 + /// \return \c true if \c t is reachable form \c s.
2.990 + bool run(Node s, Node t) {
2.991 + BellmanFord<Digraph,LengthMap,TR>
2.992 + bf(*reinterpret_cast<const Digraph*>(Base::_graph),
2.993 + *reinterpret_cast<const LengthMap*>(Base::_length));
2.994 + if (Base::_pred) bf.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
2.995 + if (Base::_dist) bf.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
2.996 + bf.run(s);
2.997 + if (Base::_path) *reinterpret_cast<Path*>(Base::_path) = bf.path(t);
2.998 + if (Base::_di) *reinterpret_cast<Value*>(Base::_di) = bf.dist(t);
2.999 + return bf.reached(t);
2.1000 + }
2.1001 +
2.1002 + template<class T>
2.1003 + struct SetPredMapBase : public Base {
2.1004 + typedef T PredMap;
2.1005 + static PredMap *createPredMap(const Digraph &) { return 0; };
2.1006 + SetPredMapBase(const TR &b) : TR(b) {}
2.1007 + };
2.1008 +
2.1009 + /// \brief \ref named-templ-param "Named parameter" for setting
2.1010 + /// the predecessor map.
2.1011 + ///
2.1012 + /// \ref named-templ-param "Named parameter" for setting
2.1013 + /// the map that stores the predecessor arcs of the nodes.
2.1014 + template<class T>
2.1015 + BellmanFordWizard<SetPredMapBase<T> > predMap(const T &t) {
2.1016 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
2.1017 + return BellmanFordWizard<SetPredMapBase<T> >(*this);
2.1018 + }
2.1019 +
2.1020 + template<class T>
2.1021 + struct SetDistMapBase : public Base {
2.1022 + typedef T DistMap;
2.1023 + static DistMap *createDistMap(const Digraph &) { return 0; };
2.1024 + SetDistMapBase(const TR &b) : TR(b) {}
2.1025 + };
2.1026 +
2.1027 + /// \brief \ref named-templ-param "Named parameter" for setting
2.1028 + /// the distance map.
2.1029 + ///
2.1030 + /// \ref named-templ-param "Named parameter" for setting
2.1031 + /// the map that stores the distances of the nodes calculated
2.1032 + /// by the algorithm.
2.1033 + template<class T>
2.1034 + BellmanFordWizard<SetDistMapBase<T> > distMap(const T &t) {
2.1035 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
2.1036 + return BellmanFordWizard<SetDistMapBase<T> >(*this);
2.1037 + }
2.1038 +
2.1039 + template<class T>
2.1040 + struct SetPathBase : public Base {
2.1041 + typedef T Path;
2.1042 + SetPathBase(const TR &b) : TR(b) {}
2.1043 + };
2.1044 +
2.1045 + /// \brief \ref named-func-param "Named parameter" for getting
2.1046 + /// the shortest path to the target node.
2.1047 + ///
2.1048 + /// \ref named-func-param "Named parameter" for getting
2.1049 + /// the shortest path to the target node.
2.1050 + template<class T>
2.1051 + BellmanFordWizard<SetPathBase<T> > path(const T &t)
2.1052 + {
2.1053 + Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
2.1054 + return BellmanFordWizard<SetPathBase<T> >(*this);
2.1055 + }
2.1056 +
2.1057 + /// \brief \ref named-func-param "Named parameter" for getting
2.1058 + /// the distance of the target node.
2.1059 + ///
2.1060 + /// \ref named-func-param "Named parameter" for getting
2.1061 + /// the distance of the target node.
2.1062 + BellmanFordWizard dist(const Value &d)
2.1063 + {
2.1064 + Base::_di=reinterpret_cast<void*>(const_cast<Value*>(&d));
2.1065 + return *this;
2.1066 + }
2.1067 +
2.1068 + };
2.1069 +
2.1070 + /// \brief Function type interface for the \ref BellmanFord "Bellman-Ford"
2.1071 + /// algorithm.
2.1072 + ///
2.1073 + /// \ingroup shortest_path
2.1074 + /// Function type interface for the \ref BellmanFord "Bellman-Ford"
2.1075 + /// algorithm.
2.1076 + ///
2.1077 + /// This function also has several \ref named-templ-func-param
2.1078 + /// "named parameters", they are declared as the members of class
2.1079 + /// \ref BellmanFordWizard.
2.1080 + /// The following examples show how to use these parameters.
2.1081 + /// \code
2.1082 + /// // Compute shortest path from node s to each node
2.1083 + /// bellmanFord(g,length).predMap(preds).distMap(dists).run(s);
2.1084 + ///
2.1085 + /// // Compute shortest path from s to t
2.1086 + /// bool reached = bellmanFord(g,length).path(p).dist(d).run(s,t);
2.1087 + /// \endcode
2.1088 + /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
2.1089 + /// to the end of the parameter list.
2.1090 + /// \sa BellmanFordWizard
2.1091 + /// \sa BellmanFord
2.1092 + template<typename GR, typename LEN>
2.1093 + BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >
2.1094 + bellmanFord(const GR& digraph,
2.1095 + const LEN& length)
2.1096 + {
2.1097 + return BellmanFordWizard<BellmanFordWizardBase<GR,LEN> >(digraph, length);
2.1098 + }
2.1099 +
2.1100 +} //END OF NAMESPACE LEMON
2.1101 +
2.1102 +#endif
2.1103 +
3.1 --- a/test/CMakeLists.txt Mon Aug 31 08:25:33 2009 +0200
3.2 +++ b/test/CMakeLists.txt Mon Aug 31 08:32:25 2009 +0200
3.3 @@ -9,6 +9,7 @@
3.4
3.5 SET(TESTS
3.6 adaptors_test
3.7 + bellman_ford_test
3.8 bfs_test
3.9 circulation_test
3.10 connectivity_test
4.1 --- a/test/Makefile.am Mon Aug 31 08:25:33 2009 +0200
4.2 +++ b/test/Makefile.am Mon Aug 31 08:32:25 2009 +0200
4.3 @@ -7,6 +7,7 @@
4.4
4.5 check_PROGRAMS += \
4.6 test/adaptors_test \
4.7 + test/bellman_ford_test \
4.8 test/bfs_test \
4.9 test/circulation_test \
4.10 test/connectivity_test \
4.11 @@ -52,6 +53,7 @@
4.12 XFAIL_TESTS += test/test_tools_fail$(EXEEXT)
4.13
4.14 test_adaptors_test_SOURCES = test/adaptors_test.cc
4.15 +test_bellman_ford_test_SOURCES = test/bellman_ford_test.cc
4.16 test_bfs_test_SOURCES = test/bfs_test.cc
4.17 test_circulation_test_SOURCES = test/circulation_test.cc
4.18 test_counter_test_SOURCES = test/counter_test.cc
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/test/bellman_ford_test.cc Mon Aug 31 08:32:25 2009 +0200
5.3 @@ -0,0 +1,283 @@
5.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library.
5.7 + *
5.8 + * Copyright (C) 2003-2009
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +#include <lemon/concepts/digraph.h>
5.23 +#include <lemon/smart_graph.h>
5.24 +#include <lemon/list_graph.h>
5.25 +#include <lemon/lgf_reader.h>
5.26 +#include <lemon/bellman_ford.h>
5.27 +#include <lemon/path.h>
5.28 +
5.29 +#include "graph_test.h"
5.30 +#include "test_tools.h"
5.31 +
5.32 +using namespace lemon;
5.33 +
5.34 +char test_lgf[] =
5.35 + "@nodes\n"
5.36 + "label\n"
5.37 + "0\n"
5.38 + "1\n"
5.39 + "2\n"
5.40 + "3\n"
5.41 + "4\n"
5.42 + "@arcs\n"
5.43 + " length\n"
5.44 + "0 1 3\n"
5.45 + "1 2 -3\n"
5.46 + "1 2 -5\n"
5.47 + "1 3 -2\n"
5.48 + "0 2 -1\n"
5.49 + "1 2 -4\n"
5.50 + "0 3 2\n"
5.51 + "4 2 -5\n"
5.52 + "2 3 1\n"
5.53 + "@attributes\n"
5.54 + "source 0\n"
5.55 + "target 3\n";
5.56 +
5.57 +
5.58 +void checkBellmanFordCompile()
5.59 +{
5.60 + typedef int Value;
5.61 + typedef concepts::Digraph Digraph;
5.62 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
5.63 + typedef BellmanFord<Digraph, LengthMap> BF;
5.64 + typedef Digraph::Node Node;
5.65 + typedef Digraph::Arc Arc;
5.66 +
5.67 + Digraph gr;
5.68 + Node s, t, n;
5.69 + Arc e;
5.70 + Value l;
5.71 + int k;
5.72 + bool b;
5.73 + BF::DistMap d(gr);
5.74 + BF::PredMap p(gr);
5.75 + LengthMap length;
5.76 + concepts::Path<Digraph> pp;
5.77 +
5.78 + {
5.79 + BF bf_test(gr,length);
5.80 + const BF& const_bf_test = bf_test;
5.81 +
5.82 + bf_test.run(s);
5.83 + bf_test.run(s,k);
5.84 +
5.85 + bf_test.init();
5.86 + bf_test.addSource(s);
5.87 + bf_test.addSource(s, 1);
5.88 + b = bf_test.processNextRound();
5.89 + b = bf_test.processNextWeakRound();
5.90 +
5.91 + bf_test.start();
5.92 + bf_test.checkedStart();
5.93 + bf_test.limitedStart(k);
5.94 +
5.95 + l = const_bf_test.dist(t);
5.96 + e = const_bf_test.predArc(t);
5.97 + s = const_bf_test.predNode(t);
5.98 + b = const_bf_test.reached(t);
5.99 + d = const_bf_test.distMap();
5.100 + p = const_bf_test.predMap();
5.101 + pp = const_bf_test.path(t);
5.102 +
5.103 + for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}
5.104 + }
5.105 + {
5.106 + BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >
5.107 + ::SetDistMap<concepts::ReadWriteMap<Node,Value> >
5.108 + ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >
5.109 + ::Create bf_test(gr,length);
5.110 +
5.111 + LengthMap length_map;
5.112 + concepts::ReadWriteMap<Node,Arc> pred_map;
5.113 + concepts::ReadWriteMap<Node,Value> dist_map;
5.114 +
5.115 + bf_test
5.116 + .lengthMap(length_map)
5.117 + .predMap(pred_map)
5.118 + .distMap(dist_map);
5.119 +
5.120 + bf_test.run(s);
5.121 + bf_test.run(s,k);
5.122 +
5.123 + bf_test.init();
5.124 + bf_test.addSource(s);
5.125 + bf_test.addSource(s, 1);
5.126 + b = bf_test.processNextRound();
5.127 + b = bf_test.processNextWeakRound();
5.128 +
5.129 + bf_test.start();
5.130 + bf_test.checkedStart();
5.131 + bf_test.limitedStart(k);
5.132 +
5.133 + l = bf_test.dist(t);
5.134 + e = bf_test.predArc(t);
5.135 + s = bf_test.predNode(t);
5.136 + b = bf_test.reached(t);
5.137 + pp = bf_test.path(t);
5.138 + }
5.139 +}
5.140 +
5.141 +void checkBellmanFordFunctionCompile()
5.142 +{
5.143 + typedef int Value;
5.144 + typedef concepts::Digraph Digraph;
5.145 + typedef Digraph::Arc Arc;
5.146 + typedef Digraph::Node Node;
5.147 + typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;
5.148 +
5.149 + Digraph g;
5.150 + bool b;
5.151 + bellmanFord(g,LengthMap()).run(Node());
5.152 + b = bellmanFord(g,LengthMap()).run(Node(),Node());
5.153 + bellmanFord(g,LengthMap())
5.154 + .predMap(concepts::ReadWriteMap<Node,Arc>())
5.155 + .distMap(concepts::ReadWriteMap<Node,Value>())
5.156 + .run(Node());
5.157 + b=bellmanFord(g,LengthMap())
5.158 + .predMap(concepts::ReadWriteMap<Node,Arc>())
5.159 + .distMap(concepts::ReadWriteMap<Node,Value>())
5.160 + .path(concepts::Path<Digraph>())
5.161 + .dist(Value())
5.162 + .run(Node(),Node());
5.163 +}
5.164 +
5.165 +
5.166 +template <typename Digraph, typename Value>
5.167 +void checkBellmanFord() {
5.168 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
5.169 + typedef typename Digraph::template ArcMap<Value> LengthMap;
5.170 +
5.171 + Digraph gr;
5.172 + Node s, t;
5.173 + LengthMap length(gr);
5.174 +
5.175 + std::istringstream input(test_lgf);
5.176 + digraphReader(gr, input).
5.177 + arcMap("length", length).
5.178 + node("source", s).
5.179 + node("target", t).
5.180 + run();
5.181 +
5.182 + BellmanFord<Digraph, LengthMap>
5.183 + bf(gr, length);
5.184 + bf.run(s);
5.185 + Path<Digraph> p = bf.path(t);
5.186 +
5.187 + check(bf.reached(t) && bf.dist(t) == -1, "Bellman-Ford found a wrong path.");
5.188 + check(p.length() == 3, "path() found a wrong path.");
5.189 + check(checkPath(gr, p), "path() found a wrong path.");
5.190 + check(pathSource(gr, p) == s, "path() found a wrong path.");
5.191 + check(pathTarget(gr, p) == t, "path() found a wrong path.");
5.192 +
5.193 + ListPath<Digraph> path;
5.194 + Value dist;
5.195 + bool reached = bellmanFord(gr,length).path(path).dist(dist).run(s,t);
5.196 +
5.197 + check(reached && dist == -1, "Bellman-Ford found a wrong path.");
5.198 + check(path.length() == 3, "path() found a wrong path.");
5.199 + check(checkPath(gr, path), "path() found a wrong path.");
5.200 + check(pathSource(gr, path) == s, "path() found a wrong path.");
5.201 + check(pathTarget(gr, path) == t, "path() found a wrong path.");
5.202 +
5.203 + for(ArcIt e(gr); e!=INVALID; ++e) {
5.204 + Node u=gr.source(e);
5.205 + Node v=gr.target(e);
5.206 + check(!bf.reached(u) || (bf.dist(v) - bf.dist(u) <= length[e]),
5.207 + "Wrong output. dist(target)-dist(source)-arc_length=" <<
5.208 + bf.dist(v) - bf.dist(u) - length[e]);
5.209 + }
5.210 +
5.211 + for(NodeIt v(gr); v!=INVALID; ++v) {
5.212 + if (bf.reached(v)) {
5.213 + check(v==s || bf.predArc(v)!=INVALID, "Wrong tree.");
5.214 + if (bf.predArc(v)!=INVALID ) {
5.215 + Arc e=bf.predArc(v);
5.216 + Node u=gr.source(e);
5.217 + check(u==bf.predNode(v),"Wrong tree.");
5.218 + check(bf.dist(v) - bf.dist(u) == length[e],
5.219 + "Wrong distance! Difference: " <<
5.220 + bf.dist(v) - bf.dist(u) - length[e]);
5.221 + }
5.222 + }
5.223 + }
5.224 +}
5.225 +
5.226 +void checkBellmanFordNegativeCycle() {
5.227 + DIGRAPH_TYPEDEFS(SmartDigraph);
5.228 +
5.229 + SmartDigraph gr;
5.230 + IntArcMap length(gr);
5.231 +
5.232 + Node n1 = gr.addNode();
5.233 + Node n2 = gr.addNode();
5.234 + Node n3 = gr.addNode();
5.235 + Node n4 = gr.addNode();
5.236 +
5.237 + Arc a1 = gr.addArc(n1, n2);
5.238 + Arc a2 = gr.addArc(n2, n2);
5.239 +
5.240 + length[a1] = 2;
5.241 + length[a2] = -1;
5.242 +
5.243 + {
5.244 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
5.245 + bf.run(n1);
5.246 + StaticPath<SmartDigraph> p = bf.negativeCycle();
5.247 + check(p.length() == 1 && p.front() == p.back() && p.front() == a2,
5.248 + "Wrong negative cycle.");
5.249 + }
5.250 +
5.251 + length[a2] = 0;
5.252 +
5.253 + {
5.254 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
5.255 + bf.run(n1);
5.256 + check(bf.negativeCycle().empty(),
5.257 + "Negative cycle should not be found.");
5.258 + }
5.259 +
5.260 + length[gr.addArc(n1, n3)] = 5;
5.261 + length[gr.addArc(n4, n3)] = 1;
5.262 + length[gr.addArc(n2, n4)] = 2;
5.263 + length[gr.addArc(n3, n2)] = -4;
5.264 +
5.265 + {
5.266 + BellmanFord<SmartDigraph, IntArcMap> bf(gr, length);
5.267 + bf.init();
5.268 + bf.addSource(n1);
5.269 + for (int i = 0; i < 4; ++i) {
5.270 + check(bf.negativeCycle().empty(),
5.271 + "Negative cycle should not be found.");
5.272 + bf.processNextRound();
5.273 + }
5.274 + StaticPath<SmartDigraph> p = bf.negativeCycle();
5.275 + check(p.length() == 3, "Wrong negative cycle.");
5.276 + check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1,
5.277 + "Wrong negative cycle.");
5.278 + }
5.279 +}
5.280 +
5.281 +int main() {
5.282 + checkBellmanFord<ListDigraph, int>();
5.283 + checkBellmanFord<SmartDigraph, double>();
5.284 + checkBellmanFordNegativeCycle();
5.285 + return 0;
5.286 +}