1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bellman_ford.h Mon Dec 19 09:43:13 2005 +0000
1.3 @@ -0,0 +1,950 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/bellman_ford.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_BELMANN_FORD_H
1.21 +#define LEMON_BELMANN_FORD_H
1.22 +
1.23 +/// \ingroup flowalgs
1.24 +/// \file
1.25 +/// \brief BellmanFord algorithm.
1.26 +///
1.27 +
1.28 +#include <lemon/list_graph.h>
1.29 +#include <lemon/invalid.h>
1.30 +#include <lemon/error.h>
1.31 +#include <lemon/maps.h>
1.32 +
1.33 +#include <limits>
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 + /// \brief Default OperationTraits for the BellmanFord algorithm class.
1.38 + ///
1.39 + /// It defines all computational operations and constants which are
1.40 + /// used in the bellman ford algorithm. The default implementation
1.41 + /// is based on the numeric_limits class. If the numeric type does not
1.42 + /// have infinity value then the maximum value is used as extremal
1.43 + /// infinity value.
1.44 + template <
1.45 + typename Value,
1.46 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.47 + struct BellmanFordDefaultOperationTraits {
1.48 + /// \brief Gives back the zero value of the type.
1.49 + static Value zero() {
1.50 + return static_cast<Value>(0);
1.51 + }
1.52 + /// \brief Gives back the positive infinity value of the type.
1.53 + static Value infinity() {
1.54 + return std::numeric_limits<Value>::infinity();
1.55 + }
1.56 + /// \brief Gives back the sum of the given two elements.
1.57 + static Value plus(const Value& left, const Value& right) {
1.58 + return left + right;
1.59 + }
1.60 + /// \brief Gives back true only if the first value less than the second.
1.61 + static bool less(const Value& left, const Value& right) {
1.62 + return left < right;
1.63 + }
1.64 + };
1.65 +
1.66 + template <typename Value>
1.67 + struct BellmanFordDefaultOperationTraits<Value, false> {
1.68 + static Value zero() {
1.69 + return static_cast<Value>(0);
1.70 + }
1.71 + static Value infinity() {
1.72 + return std::numeric_limits<Value>::max();
1.73 + }
1.74 + static Value plus(const Value& left, const Value& right) {
1.75 + if (left == infinity() || right == infinity()) return infinity();
1.76 + return left + right;
1.77 + }
1.78 + static bool less(const Value& left, const Value& right) {
1.79 + return left < right;
1.80 + }
1.81 + };
1.82 +
1.83 + /// \brief Default traits class of BellmanFord class.
1.84 + ///
1.85 + /// Default traits class of BellmanFord class.
1.86 + /// \param _Graph Graph type.
1.87 + /// \param _LegthMap Type of length map.
1.88 + template<class _Graph, class _LengthMap>
1.89 + struct BellmanFordDefaultTraits {
1.90 + /// The graph type the algorithm runs on.
1.91 + typedef _Graph Graph;
1.92 +
1.93 + /// \brief The type of the map that stores the edge lengths.
1.94 + ///
1.95 + /// The type of the map that stores the edge lengths.
1.96 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.97 + typedef _LengthMap LengthMap;
1.98 +
1.99 + // The type of the length of the edges.
1.100 + typedef typename _LengthMap::Value Value;
1.101 +
1.102 + /// \brief Operation traits for bellman-ford algorithm.
1.103 + ///
1.104 + /// It defines the infinity type on the given Value type
1.105 + /// and the used operation.
1.106 + /// \see BellmanFordDefaultOperationTraits
1.107 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.108 +
1.109 + /// \brief The type of the map that stores the last edges of the
1.110 + /// shortest paths.
1.111 + ///
1.112 + /// The type of the map that stores the last
1.113 + /// edges of the shortest paths.
1.114 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.115 + ///
1.116 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
1.117 +
1.118 + /// \brief Instantiates a PredMap.
1.119 + ///
1.120 + /// This function instantiates a \ref PredMap.
1.121 + /// \param graph is the graph, to which we would like to define the PredMap.
1.122 + static PredMap *createPredMap(const _Graph& graph) {
1.123 + return new PredMap(graph);
1.124 + }
1.125 +
1.126 + /// \brief The type of the map that stores the dists of the nodes.
1.127 + ///
1.128 + /// The type of the map that stores the dists of the nodes.
1.129 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.130 + ///
1.131 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
1.132 + DistMap;
1.133 +
1.134 + /// \brief Instantiates a DistMap.
1.135 + ///
1.136 + /// This function instantiates a \ref DistMap.
1.137 + /// \param graph is the graph, to which we would like to define the
1.138 + /// \ref DistMap
1.139 + static DistMap *createDistMap(const _Graph& graph) {
1.140 + return new DistMap(graph);
1.141 + }
1.142 +
1.143 + };
1.144 +
1.145 + /// \brief %BellmanFord algorithm class.
1.146 + ///
1.147 + /// \ingroup flowalgs
1.148 + /// This class provides an efficient implementation of \c Bellman-Ford
1.149 + /// algorithm. The edge lengths are passed to the algorithm using a
1.150 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
1.151 + /// kind of length.
1.152 + ///
1.153 + /// The Bellman-Ford algorithm solves the shortest path from one node
1.154 + /// problem when the edges can have negative length but the graph should
1.155 + /// not contain cycles with negative sum of length. If we can assume
1.156 + /// that all edge is non-negative in the graph then the dijkstra algorithm
1.157 + /// should be used rather.
1.158 + ///
1.159 + /// The complexity of the algorithm is O(n * e).
1.160 + ///
1.161 + /// The type of the length is determined by the
1.162 + /// \ref concept::ReadMap::Value "Value" of the length map.
1.163 + ///
1.164 + /// \param _Graph The graph type the algorithm runs on. The default value
1.165 + /// is \ref ListGraph. The value of _Graph is not used directly by
1.166 + /// BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
1.167 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
1.168 + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
1.169 + /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
1.170 + /// by BellmanFord, it is only passed to \ref BellmanFordDefaultTraits.
1.171 + /// \param _Traits Traits class to set various data types used by the
1.172 + /// algorithm. The default traits class is \ref BellmanFordDefaultTraits
1.173 + /// "BellmanFordDefaultTraits<_Graph,_LengthMap>". See \ref
1.174 + /// BellmanFordDefaultTraits for the documentation of a BellmanFord traits
1.175 + /// class.
1.176 + ///
1.177 + /// \author Balazs Dezso
1.178 +
1.179 +#ifdef DOXYGEN
1.180 + template <typename _Graph, typename _LengthMap, typename _Traits>
1.181 +#else
1.182 + template <typename _Graph=ListGraph,
1.183 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
1.184 + typename _Traits=BellmanFordDefaultTraits<_Graph,_LengthMap> >
1.185 +#endif
1.186 + class BellmanFord {
1.187 + public:
1.188 +
1.189 + /// \brief \ref Exception for uninitialized parameters.
1.190 + ///
1.191 + /// This error represents problems in the initialization
1.192 + /// of the parameters of the algorithms.
1.193 +
1.194 + class UninitializedParameter : public lemon::UninitializedParameter {
1.195 + public:
1.196 + virtual const char* exceptionName() const {
1.197 + return "lemon::BellmanFord::UninitializedParameter";
1.198 + }
1.199 + };
1.200 +
1.201 + typedef _Traits Traits;
1.202 + ///The type of the underlying graph.
1.203 + typedef typename _Traits::Graph Graph;
1.204 +
1.205 + typedef typename Graph::Node Node;
1.206 + typedef typename Graph::NodeIt NodeIt;
1.207 + typedef typename Graph::Edge Edge;
1.208 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.209 +
1.210 + /// \brief The type of the length of the edges.
1.211 + typedef typename _Traits::LengthMap::Value Value;
1.212 + /// \brief The type of the map that stores the edge lengths.
1.213 + typedef typename _Traits::LengthMap LengthMap;
1.214 + /// \brief The type of the map that stores the last
1.215 + /// edges of the shortest paths.
1.216 + typedef typename _Traits::PredMap PredMap;
1.217 + /// \brief The type of the map that stores the dists of the nodes.
1.218 + typedef typename _Traits::DistMap DistMap;
1.219 + /// \brief The operation traits.
1.220 + typedef typename _Traits::OperationTraits OperationTraits;
1.221 + private:
1.222 + /// Pointer to the underlying graph.
1.223 + const Graph *graph;
1.224 + /// Pointer to the length map
1.225 + const LengthMap *length;
1.226 + ///Pointer to the map of predecessors edges.
1.227 + PredMap *_pred;
1.228 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.229 + bool local_pred;
1.230 + ///Pointer to the map of distances.
1.231 + DistMap *_dist;
1.232 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.233 + bool local_dist;
1.234 +
1.235 + typedef typename Graph::template NodeMap<bool> MaskMap;
1.236 + MaskMap *_mask;
1.237 +
1.238 + std::vector<Node> _process;
1.239 +
1.240 + /// Creates the maps if necessary.
1.241 + void create_maps() {
1.242 + if(!_pred) {
1.243 + local_pred = true;
1.244 + _pred = Traits::createPredMap(*graph);
1.245 + }
1.246 + if(!_dist) {
1.247 + local_dist = true;
1.248 + _dist = Traits::createDistMap(*graph);
1.249 + }
1.250 + _mask = new MaskMap(*graph, false);
1.251 + }
1.252 +
1.253 + public :
1.254 +
1.255 + typedef BellmanFord Create;
1.256 +
1.257 + /// \name Named template parameters
1.258 +
1.259 + ///@{
1.260 +
1.261 + template <class T>
1.262 + struct DefPredMapTraits : public Traits {
1.263 + typedef T PredMap;
1.264 + static PredMap *createPredMap(const Graph&) {
1.265 + throw UninitializedParameter();
1.266 + }
1.267 + };
1.268 +
1.269 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
1.270 + /// type
1.271 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.272 + ///
1.273 + template <class T>
1.274 + struct DefPredMap
1.275 + : public BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > {
1.276 + typedef BellmanFord< Graph, LengthMap, DefPredMapTraits<T> > Create;
1.277 + };
1.278 +
1.279 + template <class T>
1.280 + struct DefDistMapTraits : public Traits {
1.281 + typedef T DistMap;
1.282 + static DistMap *createDistMap(const Graph& graph) {
1.283 + throw UninitializedParameter();
1.284 + }
1.285 + };
1.286 +
1.287 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
1.288 + /// type
1.289 + ///
1.290 + /// \ref named-templ-param "Named parameter" for setting DistMap type
1.291 + ///
1.292 + template <class T>
1.293 + struct DefDistMap
1.294 + : public BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > {
1.295 + typedef BellmanFord< Graph, LengthMap, DefDistMapTraits<T> > Create;
1.296 + };
1.297 +
1.298 + template <class T>
1.299 + struct DefOperationTraitsTraits : public Traits {
1.300 + typedef T OperationTraits;
1.301 + };
1.302 +
1.303 + /// \brief \ref named-templ-param "Named parameter" for setting
1.304 + /// OperationTraits type
1.305 + ///
1.306 + /// \ref named-templ-param "Named parameter" for setting OperationTraits
1.307 + /// type
1.308 + template <class T>
1.309 + struct DefOperationTraits
1.310 + : public BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.311 + typedef BellmanFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
1.312 + Create;
1.313 + };
1.314 +
1.315 + ///@}
1.316 +
1.317 + protected:
1.318 +
1.319 + BellmanFord() {}
1.320 +
1.321 + public:
1.322 +
1.323 + /// \brief Constructor.
1.324 + ///
1.325 + /// \param _graph the graph the algorithm will run on.
1.326 + /// \param _length the length map used by the algorithm.
1.327 + BellmanFord(const Graph& _graph, const LengthMap& _length) :
1.328 + graph(&_graph), length(&_length),
1.329 + _pred(0), local_pred(false),
1.330 + _dist(0), local_dist(false) {}
1.331 +
1.332 + ///Destructor.
1.333 + ~BellmanFord() {
1.334 + if(local_pred) delete _pred;
1.335 + if(local_dist) delete _dist;
1.336 + delete _mask;
1.337 + }
1.338 +
1.339 + /// \brief Sets the length map.
1.340 + ///
1.341 + /// Sets the length map.
1.342 + /// \return \c (*this)
1.343 + BellmanFord &lengthMap(const LengthMap &m) {
1.344 + length = &m;
1.345 + return *this;
1.346 + }
1.347 +
1.348 + /// \brief Sets the map storing the predecessor edges.
1.349 + ///
1.350 + /// Sets the map storing the predecessor edges.
1.351 + /// If you don't use this function before calling \ref run(),
1.352 + /// it will allocate one. The destuctor deallocates this
1.353 + /// automatically allocated map, of course.
1.354 + /// \return \c (*this)
1.355 + BellmanFord &predMap(PredMap &m) {
1.356 + if(local_pred) {
1.357 + delete _pred;
1.358 + local_pred=false;
1.359 + }
1.360 + _pred = &m;
1.361 + return *this;
1.362 + }
1.363 +
1.364 + /// \brief Sets the map storing the distances calculated by the algorithm.
1.365 + ///
1.366 + /// Sets the map storing the distances calculated by the algorithm.
1.367 + /// If you don't use this function before calling \ref run(),
1.368 + /// it will allocate one. The destuctor deallocates this
1.369 + /// automatically allocated map, of course.
1.370 + /// \return \c (*this)
1.371 + BellmanFord &distMap(DistMap &m) {
1.372 + if(local_dist) {
1.373 + delete _dist;
1.374 + local_dist=false;
1.375 + }
1.376 + _dist = &m;
1.377 + return *this;
1.378 + }
1.379 +
1.380 + /// \name Execution control
1.381 + /// The simplest way to execute the algorithm is to use
1.382 + /// one of the member functions called \c run(...).
1.383 + /// \n
1.384 + /// If you need more control on the execution,
1.385 + /// first you must call \ref init(), then you can add several source nodes
1.386 + /// with \ref addSource().
1.387 + /// Finally \ref start() will perform the actual path
1.388 + /// computation.
1.389 +
1.390 + ///@{
1.391 +
1.392 + /// \brief Initializes the internal data structures.
1.393 + ///
1.394 + /// Initializes the internal data structures.
1.395 + void init(const Value value = OperationTraits::infinity()) {
1.396 + create_maps();
1.397 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.398 + _pred->set(it, INVALID);
1.399 + _dist->set(it, value);
1.400 + }
1.401 + _process.clear();
1.402 + if (OperationTraits::less(value, OperationTraits::infinity())) {
1.403 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.404 + _process.push_back(it);
1.405 + _mask->set(it, true);
1.406 + }
1.407 + }
1.408 + }
1.409 +
1.410 + /// \brief Adds a new source node.
1.411 + ///
1.412 + /// The optional second parameter is the initial distance of the node.
1.413 + /// It just sets the distance of the node to the given value.
1.414 + void addSource(Node source, Value dst = OperationTraits::zero()) {
1.415 + _dist->set(source, dst);
1.416 + if (!(*_mask)[source]) {
1.417 + _process.push_back(source);
1.418 + _mask->set(source, true);
1.419 + }
1.420 + }
1.421 +
1.422 + /// \brief Executes one round from the bellman ford algorithm.
1.423 + ///
1.424 + /// If the algoritm calculated the distances in the previous round
1.425 + /// strictly for all at most k length paths then it will calculate the
1.426 + /// distances strictly for all at most k + 1 length paths. With k
1.427 + /// iteration this function calculates the at most k length paths.
1.428 + /// \return %True when the algorithm have not found more shorter paths.
1.429 + bool processNextRound() {
1.430 + for (int i = 0; i < (int)_process.size(); ++i) {
1.431 + _mask->set(_process[i], false);
1.432 + }
1.433 + std::vector<Node> nextProcess;
1.434 + std::vector<Value> values(_process.size());
1.435 + for (int i = 0; i < (int)_process.size(); ++i) {
1.436 + values[i] = (*_dist)[_process[i]];
1.437 + }
1.438 + for (int i = 0; i < (int)_process.size(); ++i) {
1.439 + for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
1.440 + Node target = graph->target(it);
1.441 + Value relaxed = OperationTraits::plus(values[i], (*length)[it]);
1.442 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.443 + _pred->set(target, it);
1.444 + _dist->set(target, relaxed);
1.445 + if (!(*_mask)[target]) {
1.446 + _mask->set(target, true);
1.447 + nextProcess.push_back(target);
1.448 + }
1.449 + }
1.450 + }
1.451 + }
1.452 + _process.swap(nextProcess);
1.453 + return _process.empty();
1.454 + }
1.455 +
1.456 + /// \brief Executes one weak round from the bellman ford algorithm.
1.457 + ///
1.458 + /// If the algorithm calculated the distances in the
1.459 + /// previous round at least for all at most k length paths then it will
1.460 + /// calculate the distances at least for all at most k + 1 length paths.
1.461 + /// This function does not make it possible to calculate strictly the
1.462 + /// at most k length minimal paths, this is why it is
1.463 + /// called just weak round.
1.464 + /// \return %True when the algorithm have not found more shorter paths.
1.465 + bool processNextWeakRound() {
1.466 + for (int i = 0; i < (int)_process.size(); ++i) {
1.467 + _mask->set(_process[i], false);
1.468 + }
1.469 + std::vector<Node> nextProcess;
1.470 + for (int i = 0; i < (int)_process.size(); ++i) {
1.471 + for (OutEdgeIt it(*graph, _process[i]); it != INVALID; ++it) {
1.472 + Node target = graph->target(it);
1.473 + Value relaxed =
1.474 + OperationTraits::plus((*_dist)[_process[i]], (*length)[it]);
1.475 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.476 + _pred->set(target, it);
1.477 + _dist->set(target, relaxed);
1.478 + if (!(*_mask)[target]) {
1.479 + _mask->set(target, true);
1.480 + nextProcess.push_back(target);
1.481 + }
1.482 + }
1.483 + }
1.484 + }
1.485 + _process.swap(nextProcess);
1.486 + return _process.empty();
1.487 + }
1.488 +
1.489 + /// \brief Executes the algorithm.
1.490 + ///
1.491 + /// \pre init() must be called and at least one node should be added
1.492 + /// with addSource() before using this function.
1.493 + ///
1.494 + /// This method runs the %BellmanFord algorithm from the root node(s)
1.495 + /// in order to compute the shortest path to each node. The algorithm
1.496 + /// computes
1.497 + /// - The shortest path tree.
1.498 + /// - The distance of each node from the root(s).
1.499 + void start() {
1.500 + int num = countNodes(*graph) - 1;
1.501 + for (int i = 0; i < num; ++i) {
1.502 + if (processNextWeakRound()) break;
1.503 + }
1.504 + }
1.505 +
1.506 + /// \brief Executes the algorithm and checks the negative cycles.
1.507 + ///
1.508 + /// \pre init() must be called and at least one node should be added
1.509 + /// with addSource() before using this function. If there is
1.510 + /// a negative cycles in the graph it gives back false.
1.511 + ///
1.512 + /// This method runs the %BellmanFord algorithm from the root node(s)
1.513 + /// in order to compute the shortest path to each node. The algorithm
1.514 + /// computes
1.515 + /// - The shortest path tree.
1.516 + /// - The distance of each node from the root(s).
1.517 + bool checkedStart() {
1.518 + int num = countNodes(*graph);
1.519 + for (int i = 0; i < num; ++i) {
1.520 + if (processNextWeakRound()) return true;
1.521 + }
1.522 + return false;
1.523 + }
1.524 +
1.525 + /// \brief Executes the algorithm with path length limit.
1.526 + ///
1.527 + /// \pre init() must be called and at least one node should be added
1.528 + /// with addSource() before using this function.
1.529 + ///
1.530 + /// This method runs the %BellmanFord algorithm from the root node(s)
1.531 + /// in order to compute the shortest path with at most \c length edge
1.532 + /// long paths to each node. The algorithm computes
1.533 + /// - The shortest path tree.
1.534 + /// - The limited distance of each node from the root(s).
1.535 + void limitedStart(int length) {
1.536 + for (int i = 0; i < length; ++i) {
1.537 + if (processNextRound()) break;
1.538 + }
1.539 + }
1.540 +
1.541 + /// \brief Runs %BellmanFord algorithm from node \c s.
1.542 + ///
1.543 + /// This method runs the %BellmanFord algorithm from a root node \c s
1.544 + /// in order to compute the shortest path to each node. The algorithm
1.545 + /// computes
1.546 + /// - The shortest path tree.
1.547 + /// - The distance of each node from the root.
1.548 + ///
1.549 + /// \note d.run(s) is just a shortcut of the following code.
1.550 + /// \code
1.551 + /// d.init();
1.552 + /// d.addSource(s);
1.553 + /// d.start();
1.554 + /// \endcode
1.555 + void run(Node s) {
1.556 + init();
1.557 + addSource(s);
1.558 + start();
1.559 + }
1.560 +
1.561 + /// \brief Runs %BellmanFord algorithm with limited path length
1.562 + /// from node \c s.
1.563 + ///
1.564 + /// This method runs the %BellmanFord algorithm from a root node \c s
1.565 + /// in order to compute the shortest path with at most \c len edges
1.566 + /// to each node. The algorithm computes
1.567 + /// - The shortest path tree.
1.568 + /// - The distance of each node from the root.
1.569 + ///
1.570 + /// \note d.run(s, len) is just a shortcut of the following code.
1.571 + /// \code
1.572 + /// d.init();
1.573 + /// d.addSource(s);
1.574 + /// d.limitedStart(len);
1.575 + /// \endcode
1.576 + void run(Node s, int len) {
1.577 + init();
1.578 + addSource(s);
1.579 + limitedStart(len);
1.580 + }
1.581 +
1.582 + ///@}
1.583 +
1.584 + /// \name Query Functions
1.585 + /// The result of the %BellmanFord algorithm can be obtained using these
1.586 + /// functions.\n
1.587 + /// Before the use of these functions,
1.588 + /// either run() or start() must be called.
1.589 +
1.590 + ///@{
1.591 +
1.592 + /// \brief Copies the shortest path to \c t into \c p
1.593 + ///
1.594 + /// This function copies the shortest path to \c t into \c p.
1.595 + /// If it \c t is a source itself or unreachable, then it does not
1.596 + /// alter \c p.
1.597 + ///
1.598 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
1.599 + /// \c false otherwise.
1.600 + /// \sa DirPath
1.601 + template <typename Path>
1.602 + bool getPath(Path &p, Node t) {
1.603 + if(reached(t)) {
1.604 + p.clear();
1.605 + typename Path::Builder b(p);
1.606 + for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
1.607 + b.pushFront(predEdge(t));
1.608 + b.commit();
1.609 + return true;
1.610 + }
1.611 + return false;
1.612 + }
1.613 +
1.614 + /// \brief The distance of a node from the root.
1.615 + ///
1.616 + /// Returns the distance of a node from the root.
1.617 + /// \pre \ref run() must be called before using this function.
1.618 + /// \warning If node \c v in unreachable from the root the return value
1.619 + /// of this funcion is undefined.
1.620 + Value dist(Node v) const { return (*_dist)[v]; }
1.621 +
1.622 + /// \brief Returns the 'previous edge' of the shortest path tree.
1.623 + ///
1.624 + /// For a node \c v it returns the 'previous edge' of the shortest path
1.625 + /// tree, i.e. it returns the last edge of a shortest path from the root
1.626 + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
1.627 + /// if \c v=s. The shortest path tree used here is equal to the shortest
1.628 + /// path tree used in \ref predNode().
1.629 + /// \pre \ref run() must be called before using
1.630 + /// this function.
1.631 + Edge predEdge(Node v) const { return (*_pred)[v]; }
1.632 +
1.633 + /// \brief Returns the 'previous node' of the shortest path tree.
1.634 + ///
1.635 + /// For a node \c v it returns the 'previous node' of the shortest path
1.636 + /// tree, i.e. it returns the last but one node from a shortest path from
1.637 + /// the root to \c /v. It is INVALID if \c v is unreachable from the root
1.638 + /// or if \c v=s. The shortest path tree used here is equal to the
1.639 + /// shortest path tree used in \ref predEdge(). \pre \ref run() must be
1.640 + /// called before using this function.
1.641 + Node predNode(Node v) const {
1.642 + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
1.643 + }
1.644 +
1.645 + /// \brief Returns a reference to the NodeMap of distances.
1.646 + ///
1.647 + /// Returns a reference to the NodeMap of distances. \pre \ref run() must
1.648 + /// be called before using this function.
1.649 + const DistMap &distMap() const { return *_dist;}
1.650 +
1.651 + /// \brief Returns a reference to the shortest path tree map.
1.652 + ///
1.653 + /// Returns a reference to the NodeMap of the edges of the
1.654 + /// shortest path tree.
1.655 + /// \pre \ref run() must be called before using this function.
1.656 + const PredMap &predMap() const { return *_pred; }
1.657 +
1.658 + /// \brief Checks if a node is reachable from the root.
1.659 + ///
1.660 + /// Returns \c true if \c v is reachable from the root.
1.661 + /// \pre \ref run() must be called before using this function.
1.662 + ///
1.663 + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
1.664 +
1.665 + ///@}
1.666 + };
1.667 +
1.668 + /// \brief Default traits class of BellmanFord function.
1.669 + ///
1.670 + /// Default traits class of BellmanFord function.
1.671 + /// \param _Graph Graph type.
1.672 + /// \param _LengthMap Type of length map.
1.673 + template <typename _Graph, typename _LengthMap>
1.674 + struct BellmanFordWizardDefaultTraits {
1.675 + /// \brief The graph type the algorithm runs on.
1.676 + typedef _Graph Graph;
1.677 +
1.678 + /// \brief The type of the map that stores the edge lengths.
1.679 + ///
1.680 + /// The type of the map that stores the edge lengths.
1.681 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.682 + typedef _LengthMap LengthMap;
1.683 +
1.684 + /// \brief The value type of the length map.
1.685 + typedef typename _LengthMap::Value Value;
1.686 +
1.687 + /// \brief Operation traits for bellman-ford algorithm.
1.688 + ///
1.689 + /// It defines the infinity type on the given Value type
1.690 + /// and the used operation.
1.691 + /// \see BellmanFordDefaultOperationTraits
1.692 + typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;
1.693 +
1.694 + /// \brief The type of the map that stores the last
1.695 + /// edges of the shortest paths.
1.696 + ///
1.697 + /// The type of the map that stores the last
1.698 + /// edges of the shortest paths.
1.699 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.700 + typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
1.701 +
1.702 + /// \brief Instantiates a PredMap.
1.703 + ///
1.704 + /// This function instantiates a \ref PredMap.
1.705 + static PredMap *createPredMap(const _Graph &) {
1.706 + return new PredMap();
1.707 + }
1.708 + /// \brief The type of the map that stores the dists of the nodes.
1.709 + ///
1.710 + /// The type of the map that stores the dists of the nodes.
1.711 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.712 + typedef NullMap<typename Graph::Node, Value> DistMap;
1.713 + /// \brief Instantiates a DistMap.
1.714 + ///
1.715 + /// This function instantiates a \ref DistMap.
1.716 + static DistMap *createDistMap(const _Graph &) {
1.717 + return new DistMap();
1.718 + }
1.719 + };
1.720 +
1.721 + /// \brief Default traits used by \ref BellmanFordWizard
1.722 + ///
1.723 + /// To make it easier to use BellmanFord algorithm
1.724 + /// we have created a wizard class.
1.725 + /// This \ref BellmanFordWizard class needs default traits,
1.726 + /// as well as the \ref BellmanFord class.
1.727 + /// The \ref BellmanFordWizardBase is a class to be the default traits of the
1.728 + /// \ref BellmanFordWizard class.
1.729 + /// \todo More named parameters are required...
1.730 + template<class _Graph,class _LengthMap>
1.731 + class BellmanFordWizardBase
1.732 + : public BellmanFordWizardDefaultTraits<_Graph,_LengthMap> {
1.733 +
1.734 + typedef BellmanFordWizardDefaultTraits<_Graph,_LengthMap> Base;
1.735 + protected:
1.736 + /// Type of the nodes in the graph.
1.737 + typedef typename Base::Graph::Node Node;
1.738 +
1.739 + /// Pointer to the underlying graph.
1.740 + void *_graph;
1.741 + /// Pointer to the length map
1.742 + void *_length;
1.743 + ///Pointer to the map of predecessors edges.
1.744 + void *_pred;
1.745 + ///Pointer to the map of distances.
1.746 + void *_dist;
1.747 + ///Pointer to the source node.
1.748 + Node _source;
1.749 +
1.750 + public:
1.751 + /// Constructor.
1.752 +
1.753 + /// This constructor does not require parameters, therefore it initiates
1.754 + /// all of the attributes to default values (0, INVALID).
1.755 + BellmanFordWizardBase() : _graph(0), _length(0), _pred(0),
1.756 + _dist(0), _source(INVALID) {}
1.757 +
1.758 + /// Constructor.
1.759 +
1.760 + /// This constructor requires some parameters,
1.761 + /// listed in the parameters list.
1.762 + /// Others are initiated to 0.
1.763 + /// \param graph is the initial value of \ref _graph
1.764 + /// \param length is the initial value of \ref _length
1.765 + /// \param source is the initial value of \ref _source
1.766 + BellmanFordWizardBase(const _Graph& graph,
1.767 + const _LengthMap& length,
1.768 + Node source = INVALID) :
1.769 + _graph((void *)&graph), _length((void *)&length), _pred(0),
1.770 + _dist(0), _source(source) {}
1.771 +
1.772 + };
1.773 +
1.774 + /// A class to make the usage of BellmanFord algorithm easier
1.775 +
1.776 + /// This class is created to make it easier to use BellmanFord algorithm.
1.777 + /// It uses the functions and features of the plain \ref BellmanFord,
1.778 + /// but it is much simpler to use it.
1.779 + ///
1.780 + /// Simplicity means that the way to change the types defined
1.781 + /// in the traits class is based on functions that returns the new class
1.782 + /// and not on templatable built-in classes.
1.783 + /// When using the plain \ref BellmanFord
1.784 + /// the new class with the modified type comes from
1.785 + /// the original class by using the ::
1.786 + /// operator. In the case of \ref BellmanFordWizard only
1.787 + /// a function have to be called and it will
1.788 + /// return the needed class.
1.789 + ///
1.790 + /// It does not have own \ref run method. When its \ref run method is called
1.791 + /// it initiates a plain \ref BellmanFord class, and calls the \ref
1.792 + /// BellmanFord::run method of it.
1.793 + template<class _Traits>
1.794 + class BellmanFordWizard : public _Traits {
1.795 + typedef _Traits Base;
1.796 +
1.797 + ///The type of the underlying graph.
1.798 + typedef typename _Traits::Graph Graph;
1.799 +
1.800 + typedef typename Graph::Node Node;
1.801 + typedef typename Graph::NodeIt NodeIt;
1.802 + typedef typename Graph::Edge Edge;
1.803 + typedef typename Graph::OutEdgeIt EdgeIt;
1.804 +
1.805 + ///The type of the map that stores the edge lengths.
1.806 + typedef typename _Traits::LengthMap LengthMap;
1.807 +
1.808 + ///The type of the length of the edges.
1.809 + typedef typename LengthMap::Value Value;
1.810 +
1.811 + ///\brief The type of the map that stores the last
1.812 + ///edges of the shortest paths.
1.813 + typedef typename _Traits::PredMap PredMap;
1.814 +
1.815 + ///The type of the map that stores the dists of the nodes.
1.816 + typedef typename _Traits::DistMap DistMap;
1.817 +
1.818 + public:
1.819 + /// Constructor.
1.820 + BellmanFordWizard() : _Traits() {}
1.821 +
1.822 + /// \brief Constructor that requires parameters.
1.823 + ///
1.824 + /// Constructor that requires parameters.
1.825 + /// These parameters will be the default values for the traits class.
1.826 + BellmanFordWizard(const Graph& graph, const LengthMap& length,
1.827 + Node source = INVALID)
1.828 + : _Traits(graph, length, source) {}
1.829 +
1.830 + /// \brief Copy constructor
1.831 + BellmanFordWizard(const _Traits &b) : _Traits(b) {}
1.832 +
1.833 + ~BellmanFordWizard() {}
1.834 +
1.835 + /// \brief Runs BellmanFord algorithm from a given node.
1.836 + ///
1.837 + /// Runs BellmanFord algorithm from a given node.
1.838 + /// The node can be given by the \ref source function.
1.839 + void run() {
1.840 + if(Base::_source == INVALID) throw UninitializedParameter();
1.841 + BellmanFord<Graph,LengthMap,_Traits>
1.842 + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
1.843 + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
1.844 + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
1.845 + bf.run(Base::_source);
1.846 + }
1.847 +
1.848 + /// \brief Runs BellmanFord algorithm from the given node.
1.849 + ///
1.850 + /// Runs BellmanFord algorithm from the given node.
1.851 + /// \param source is the given source.
1.852 + void run(Node source) {
1.853 + Base::_source = source;
1.854 + run();
1.855 + }
1.856 +
1.857 + template<class T>
1.858 + struct DefPredMapBase : public Base {
1.859 + typedef T PredMap;
1.860 + static PredMap *createPredMap(const Graph &) { return 0; };
1.861 + DefPredMapBase(const _Traits &b) : _Traits(b) {}
1.862 + };
1.863 +
1.864 + ///\brief \ref named-templ-param "Named parameter"
1.865 + ///function for setting PredMap type
1.866 + ///
1.867 + /// \ref named-templ-param "Named parameter"
1.868 + ///function for setting PredMap type
1.869 + ///
1.870 + template<class T>
1.871 + BellmanFordWizard<DefPredMapBase<T> > predMap(const T &t)
1.872 + {
1.873 + Base::_pred=(void *)&t;
1.874 + return BellmanFordWizard<DefPredMapBase<T> >(*this);
1.875 + }
1.876 +
1.877 + template<class T>
1.878 + struct DefDistMapBase : public Base {
1.879 + typedef T DistMap;
1.880 + static DistMap *createDistMap(const Graph &) { return 0; };
1.881 + DefDistMapBase(const _Traits &b) : _Traits(b) {}
1.882 + };
1.883 +
1.884 + ///\brief \ref named-templ-param "Named parameter"
1.885 + ///function for setting DistMap type
1.886 + ///
1.887 + /// \ref named-templ-param "Named parameter"
1.888 + ///function for setting DistMap type
1.889 + ///
1.890 + template<class T>
1.891 + BellmanFordWizard<DefDistMapBase<T> > distMap(const T &t) {
1.892 + Base::_dist=(void *)&t;
1.893 + return BellmanFordWizard<DefDistMapBase<T> >(*this);
1.894 + }
1.895 +
1.896 + template<class T>
1.897 + struct DefOperationTraitsBase : public Base {
1.898 + typedef T OperationTraits;
1.899 + DefOperationTraitsBase(const _Traits &b) : _Traits(b) {}
1.900 + };
1.901 +
1.902 + ///\brief \ref named-templ-param "Named parameter"
1.903 + ///function for setting OperationTraits type
1.904 + ///
1.905 + /// \ref named-templ-param "Named parameter"
1.906 + ///function for setting OperationTraits type
1.907 + ///
1.908 + template<class T>
1.909 + BellmanFordWizard<DefOperationTraitsBase<T> > distMap() {
1.910 + return BellmanFordWizard<DefDistMapBase<T> >(*this);
1.911 + }
1.912 +
1.913 + /// \brief Sets the source node, from which the BellmanFord algorithm runs.
1.914 + ///
1.915 + /// Sets the source node, from which the BellmanFord algorithm runs.
1.916 + /// \param source is the source node.
1.917 + BellmanFordWizard<_Traits>& source(Node source) {
1.918 + Base::_source = source;
1.919 + return *this;
1.920 + }
1.921 +
1.922 + };
1.923 +
1.924 + /// \brief Function type interface for BellmanFord algorithm.
1.925 + ///
1.926 + /// \ingroup flowalgs
1.927 + /// Function type interface for BellmanFord algorithm.
1.928 + ///
1.929 + /// This function also has several \ref named-templ-func-param
1.930 + /// "named parameters", they are declared as the members of class
1.931 + /// \ref BellmanFordWizard.
1.932 + /// The following
1.933 + /// example shows how to use these parameters.
1.934 + /// \code
1.935 + /// bellmanford(g,length,source).predMap(preds).run();
1.936 + /// \endcode
1.937 + /// \warning Don't forget to put the \ref BellmanFordWizard::run() "run()"
1.938 + /// to the end of the parameter list.
1.939 + /// \sa BellmanFordWizard
1.940 + /// \sa BellmanFord
1.941 + template<class _Graph, class _LengthMap>
1.942 + BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1.943 + bellmanFord(const _Graph& graph,
1.944 + const _LengthMap& length,
1.945 + typename _Graph::Node source = INVALID) {
1.946 + return BellmanFordWizard<BellmanFordWizardBase<_Graph,_LengthMap> >
1.947 + (graph, length, source);
1.948 + }
1.949 +
1.950 +} //END OF NAMESPACE LEMON
1.951 +
1.952 +#endif
1.953 +