1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/belmann_ford.h Mon Oct 03 10:20:56 2005 +0000
1.3 @@ -0,0 +1,784 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/belmann_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 BelmannFord algorithm.
1.26 +///
1.27 +/// \todo getPath() should be implemented! (also for BFS and DFS)
1.28 +
1.29 +#include <lemon/list_graph.h>
1.30 +#include <lemon/invalid.h>
1.31 +#include <lemon/error.h>
1.32 +#include <lemon/maps.h>
1.33 +
1.34 +#include <limits>
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 + /// \brief Default OperationTraits for the BelmannFord algorithm class.
1.39 + ///
1.40 + /// It defines all computational operations and constants which are
1.41 + /// used in the belmann ford algorithm. The default implementation
1.42 + /// is based on the numeric_limits class. If the numeric type does not
1.43 + /// have infinity value then the maximum value is used as extremal
1.44 + /// infinity value.
1.45 + template <
1.46 + typename Value,
1.47 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.48 + struct BelmannFordDefaultOperationTraits {
1.49 + /// \brief Gives back the zero value of the type.
1.50 + static Value zero() {
1.51 + return static_cast<Value>(0);
1.52 + }
1.53 + /// \brief Gives back the positive infinity value of the type.
1.54 + static Value infinity() {
1.55 + return std::numeric_limits<Value>::infinity();
1.56 + }
1.57 + /// \brief Gives back the sum of the given two elements.
1.58 + static Value plus(const Value& left, const Value& right) {
1.59 + return left + right;
1.60 + }
1.61 + /// \brief Gives back true only if the first value less than the second.
1.62 + static bool less(const Value& left, const Value& right) {
1.63 + return left < right;
1.64 + }
1.65 + };
1.66 +
1.67 + template <typename Value>
1.68 + struct BelmannFordDefaultOperationTraits<Value, false> {
1.69 + static Value zero() {
1.70 + return static_cast<Value>(0);
1.71 + }
1.72 + static Value infinity() {
1.73 + return std::numeric_limits<Value>::max();
1.74 + }
1.75 + static Value plus(const Value& left, const Value& right) {
1.76 + if (left == infinity() || right == infinity()) return infinity();
1.77 + return left + right;
1.78 + }
1.79 + static bool less(const Value& left, const Value& right) {
1.80 + return left < right;
1.81 + }
1.82 + };
1.83 +
1.84 + /// \brief Default traits class of BelmannFord class.
1.85 + ///
1.86 + /// Default traits class of BelmannFord class.
1.87 + /// \param _Graph Graph type.
1.88 + /// \param _LegthMap Type of length map.
1.89 + template<class _Graph, class _LengthMap>
1.90 + struct BelmannFordDefaultTraits {
1.91 + /// The graph type the algorithm runs on.
1.92 + typedef _Graph Graph;
1.93 +
1.94 + /// \brief The type of the map that stores the edge lengths.
1.95 + ///
1.96 + /// The type of the map that stores the edge lengths.
1.97 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.98 + typedef _LengthMap LengthMap;
1.99 +
1.100 + // The type of the length of the edges.
1.101 + typedef typename _LengthMap::Value Value;
1.102 +
1.103 + /// \brief Operation traits for belmann-ford algorithm.
1.104 + ///
1.105 + /// It defines the infinity type on the given Value type
1.106 + /// and the used operation.
1.107 + /// \see BelmannFordDefaultOperationTraits
1.108 + typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
1.109 +
1.110 + /// \brief The type of the map that stores the last edges of the
1.111 + /// shortest paths.
1.112 + ///
1.113 + /// The type of the map that stores the last
1.114 + /// edges of the shortest paths.
1.115 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.116 + ///
1.117 + typedef typename Graph::template NodeMap<typename _Graph::Edge> PredMap;
1.118 +
1.119 + /// \brief Instantiates a PredMap.
1.120 + ///
1.121 + /// This function instantiates a \ref PredMap.
1.122 + /// \param G is the graph, to which we would like to define the PredMap.
1.123 + /// \todo The graph alone may be insufficient for the initialization
1.124 + static PredMap *createPredMap(const _Graph& graph) {
1.125 + return new PredMap(graph);
1.126 + }
1.127 +
1.128 + /// \brief The type of the map that stores the dists of the nodes.
1.129 + ///
1.130 + /// The type of the map that stores the dists of the nodes.
1.131 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.132 + ///
1.133 + typedef typename Graph::template NodeMap<typename _LengthMap::Value>
1.134 + DistMap;
1.135 +
1.136 + /// \brief Instantiates a DistMap.
1.137 + ///
1.138 + /// This function instantiates a \ref DistMap.
1.139 + /// \param G is the graph, to which we would like to define the
1.140 + /// \ref DistMap
1.141 + static DistMap *createDistMap(const _Graph& graph) {
1.142 + return new DistMap(graph);
1.143 + }
1.144 +
1.145 + };
1.146 +
1.147 + /// \brief BelmannFord algorithm class.
1.148 + ///
1.149 + /// \ingroup flowalgs
1.150 + /// This class provides an efficient implementation of \c BelmannFord
1.151 + /// algorithm. The edge lengths are passed to the algorithm using a
1.152 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
1.153 + /// kind of length.
1.154 + ///
1.155 + /// The type of the length is determined by the
1.156 + /// \ref concept::ReadMap::Value "Value" of the length map.
1.157 + ///
1.158 + /// \param _Graph The graph type the algorithm runs on. The default value
1.159 + /// is \ref ListGraph. The value of _Graph is not used directly by
1.160 + /// BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
1.161 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
1.162 + /// edges. The default map type is \ref concept::StaticGraph::EdgeMap
1.163 + /// "Graph::EdgeMap<int>". The value of _LengthMap is not used directly
1.164 + /// by BelmannFord, it is only passed to \ref BelmannFordDefaultTraits.
1.165 + /// \param _Traits Traits class to set various data types used by the
1.166 + /// algorithm. The default traits class is \ref BelmannFordDefaultTraits
1.167 + /// "BelmannFordDefaultTraits<_Graph,_LengthMap>". See \ref
1.168 + /// BelmannFordDefaultTraits for the documentation of a BelmannFord traits
1.169 + /// class.
1.170 + ///
1.171 + /// \author Balazs Dezso
1.172 +
1.173 + template <typename _Graph=ListGraph,
1.174 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
1.175 + typename _Traits=BelmannFordDefaultTraits<_Graph,_LengthMap> >
1.176 + class BelmannFord {
1.177 + public:
1.178 +
1.179 + /// \brief \ref Exception for uninitialized parameters.
1.180 + ///
1.181 + /// This error represents problems in the initialization
1.182 + /// of the parameters of the algorithms.
1.183 +
1.184 + class UninitializedParameter : public lemon::UninitializedParameter {
1.185 + public:
1.186 + virtual const char* exceptionName() const {
1.187 + return "lemon::BelmannFord::UninitializedParameter";
1.188 + }
1.189 + };
1.190 +
1.191 + typedef _Traits Traits;
1.192 + ///The type of the underlying graph.
1.193 + typedef typename _Traits::Graph Graph;
1.194 +
1.195 + typedef typename Graph::Node Node;
1.196 + typedef typename Graph::NodeIt NodeIt;
1.197 + typedef typename Graph::Edge Edge;
1.198 + typedef typename Graph::EdgeIt EdgeIt;
1.199 +
1.200 + /// \brief The type of the length of the edges.
1.201 + typedef typename _Traits::LengthMap::Value Value;
1.202 + /// \brief The type of the map that stores the edge lengths.
1.203 + typedef typename _Traits::LengthMap LengthMap;
1.204 + /// \brief The type of the map that stores the last
1.205 + /// edges of the shortest paths.
1.206 + typedef typename _Traits::PredMap PredMap;
1.207 + /// \brief The type of the map that stores the dists of the nodes.
1.208 + typedef typename _Traits::DistMap DistMap;
1.209 + /// \brief The operation traits.
1.210 + typedef typename _Traits::OperationTraits OperationTraits;
1.211 + private:
1.212 + /// Pointer to the underlying graph.
1.213 + const Graph *graph;
1.214 + /// Pointer to the length map
1.215 + const LengthMap *length;
1.216 + ///Pointer to the map of predecessors edges.
1.217 + PredMap *_pred;
1.218 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.219 + bool local_pred;
1.220 + ///Pointer to the map of distances.
1.221 + DistMap *_dist;
1.222 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.223 + bool local_dist;
1.224 +
1.225 + /// Creates the maps if necessary.
1.226 + void create_maps() {
1.227 + if(!_pred) {
1.228 + local_pred = true;
1.229 + _pred = Traits::createPredMap(*graph);
1.230 + }
1.231 + if(!_dist) {
1.232 + local_dist = true;
1.233 + _dist = Traits::createDistMap(*graph);
1.234 + }
1.235 + }
1.236 +
1.237 + public :
1.238 +
1.239 + /// \name Named template parameters
1.240 +
1.241 + ///@{
1.242 +
1.243 + template <class T>
1.244 + struct DefPredMapTraits : public Traits {
1.245 + typedef T PredMap;
1.246 + static PredMap *createPredMap(const Graph& graph) {
1.247 + throw UninitializedParameter();
1.248 + }
1.249 + };
1.250 +
1.251 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
1.252 + /// type
1.253 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.254 + ///
1.255 + template <class T>
1.256 + class DefPredMap
1.257 + : public BelmannFord< Graph, LengthMap, DefPredMapTraits<T> > {};
1.258 +
1.259 + template <class T>
1.260 + struct DefDistMapTraits : public Traits {
1.261 + typedef T DistMap;
1.262 + static DistMap *createDistMap(const Graph& graph) {
1.263 + throw UninitializedParameter();
1.264 + }
1.265 + };
1.266 +
1.267 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
1.268 + /// type
1.269 + ///
1.270 + /// \ref named-templ-param "Named parameter" for setting DistMap type
1.271 + ///
1.272 + template <class T>
1.273 + class DefDistMap
1.274 + : public BelmannFord< Graph, LengthMap, DefDistMapTraits<T> > {};
1.275 +
1.276 + template <class T>
1.277 + struct DefOperationTraitsTraits : public Traits {
1.278 + typedef T OperationTraits;
1.279 + };
1.280 +
1.281 + /// \brief \ref named-templ-param "Named parameter" for setting
1.282 + /// OperationTraits type
1.283 + ///
1.284 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.285 + template <class T>
1.286 + class DefOperationTraits
1.287 + : public BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.288 + public:
1.289 + typedef BelmannFord< Graph, LengthMap, DefOperationTraitsTraits<T> >
1.290 + BelmannFord;
1.291 + };
1.292 +
1.293 + ///@}
1.294 +
1.295 + public:
1.296 +
1.297 + /// \brief Constructor.
1.298 + ///
1.299 + /// \param _graph the graph the algorithm will run on.
1.300 + /// \param _length the length map used by the algorithm.
1.301 + BelmannFord(const Graph& _graph, const LengthMap& _length) :
1.302 + graph(&_graph), length(&_length),
1.303 + _pred(0), local_pred(false),
1.304 + _dist(0), local_dist(false) {}
1.305 +
1.306 + ///Destructor.
1.307 + ~BelmannFord() {
1.308 + if(local_pred) delete _pred;
1.309 + if(local_dist) delete _dist;
1.310 + }
1.311 +
1.312 + /// \brief Sets the length map.
1.313 + ///
1.314 + /// Sets the length map.
1.315 + /// \return \c (*this)
1.316 + BelmannFord &lengthMap(const LengthMap &m) {
1.317 + length = &m;
1.318 + return *this;
1.319 + }
1.320 +
1.321 + /// \brief Sets the map storing the predecessor edges.
1.322 + ///
1.323 + /// Sets the map storing the predecessor edges.
1.324 + /// If you don't use this function before calling \ref run(),
1.325 + /// it will allocate one. The destuctor deallocates this
1.326 + /// automatically allocated map, of course.
1.327 + /// \return \c (*this)
1.328 + BelmannFord &predMap(PredMap &m) {
1.329 + if(local_pred) {
1.330 + delete _pred;
1.331 + local_pred=false;
1.332 + }
1.333 + _pred = &m;
1.334 + return *this;
1.335 + }
1.336 +
1.337 + /// \brief Sets the map storing the distances calculated by the algorithm.
1.338 + ///
1.339 + /// Sets the map storing the distances calculated by the algorithm.
1.340 + /// If you don't use this function before calling \ref run(),
1.341 + /// it will allocate one. The destuctor deallocates this
1.342 + /// automatically allocated map, of course.
1.343 + /// \return \c (*this)
1.344 + BelmannFord &distMap(DistMap &m) {
1.345 + if(local_dist) {
1.346 + delete _dist;
1.347 + local_dist=false;
1.348 + }
1.349 + _dist = &m;
1.350 + return *this;
1.351 + }
1.352 +
1.353 + /// \name Execution control
1.354 + /// The simplest way to execute the algorithm is to use
1.355 + /// one of the member functions called \c run(...).
1.356 + /// \n
1.357 + /// If you need more control on the execution,
1.358 + /// first you must call \ref init(), then you can add several source nodes
1.359 + /// with \ref addSource().
1.360 + /// Finally \ref start() will perform the actual path
1.361 + /// computation.
1.362 +
1.363 + ///@{
1.364 +
1.365 + /// \brief Initializes the internal data structures.
1.366 + ///
1.367 + /// Initializes the internal data structures.
1.368 + void init() {
1.369 + create_maps();
1.370 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.371 + _pred->set(it, INVALID);
1.372 + _dist->set(it, OperationTraits::infinity());
1.373 + }
1.374 + }
1.375 +
1.376 + /// \brief Adds a new source node.
1.377 + ///
1.378 + /// The optional second parameter is the initial distance of the node.
1.379 + /// It just sets the distance of the node to the given value.
1.380 + void addSource(Node source, Value dst = OperationTraits::zero()) {
1.381 + _dist->set(source, dst);
1.382 + }
1.383 +
1.384 + /// \brief Executes the algorithm.
1.385 + ///
1.386 + /// \pre init() must be called and at least one node should be added
1.387 + /// with addSource() before using this function.
1.388 + ///
1.389 + /// This method runs the %BelmannFord algorithm from the root node(s)
1.390 + /// in order to compute the shortest path to each node. The algorithm
1.391 + /// computes
1.392 + /// - The shortest path tree.
1.393 + /// - The distance of each node from the root(s).
1.394 + void start() {
1.395 + bool ready = false;
1.396 + while (!ready) {
1.397 + ready = true;
1.398 + for (EdgeIt it(*graph); it != INVALID; ++it) {
1.399 + Node source = graph->source(it);
1.400 + Node target = graph->target(it);
1.401 + Value relaxed =
1.402 + OperationTraits::plus((*_dist)[source], (*length)[it]);
1.403 + if (OperationTraits::less(relaxed, (*_dist)[target])) {
1.404 + _pred->set(target, it);
1.405 + _dist->set(target, relaxed);
1.406 + ready = false;
1.407 + }
1.408 + }
1.409 + }
1.410 + }
1.411 +
1.412 + /// \brief Runs %BelmannFord algorithm from node \c s.
1.413 + ///
1.414 + /// This method runs the %BelmannFord algorithm from a root node \c s
1.415 + /// in order to compute the shortest path to each node. The algorithm
1.416 + /// computes
1.417 + /// - The shortest path tree.
1.418 + /// - The distance of each node from the root.
1.419 + ///
1.420 + /// \note d.run(s) is just a shortcut of the following code.
1.421 + /// \code
1.422 + /// d.init();
1.423 + /// d.addSource(s);
1.424 + /// d.start();
1.425 + /// \endcode
1.426 + void run(Node s) {
1.427 + init();
1.428 + addSource(s);
1.429 + start();
1.430 + }
1.431 +
1.432 + ///@}
1.433 +
1.434 + /// \name Query Functions
1.435 + /// The result of the %BelmannFord algorithm can be obtained using these
1.436 + /// functions.\n
1.437 + /// Before the use of these functions,
1.438 + /// either run() or start() must be called.
1.439 +
1.440 + ///@{
1.441 +
1.442 + /// \brief Copies the shortest path to \c t into \c p
1.443 + ///
1.444 + /// This function copies the shortest path to \c t into \c p.
1.445 + /// If it \c t is a source itself or unreachable, then it does not
1.446 + /// alter \c p.
1.447 + /// \todo Is it the right way to handle unreachable nodes?
1.448 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
1.449 + /// \c false otherwise.
1.450 + /// \sa DirPath
1.451 + template <typename Path>
1.452 + bool getPath(Path &p, Node t) {
1.453 + if(reached(t)) {
1.454 + p.clear();
1.455 + typename Path::Builder b(p);
1.456 + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
1.457 + b.pushFront(pred(t));
1.458 + b.commit();
1.459 + return true;
1.460 + }
1.461 + return false;
1.462 + }
1.463 +
1.464 + /// \brief The distance of a node from the root.
1.465 + ///
1.466 + /// Returns the distance of a node from the root.
1.467 + /// \pre \ref run() must be called before using this function.
1.468 + /// \warning If node \c v in unreachable from the root the return value
1.469 + /// of this funcion is undefined.
1.470 + Value dist(Node v) const { return (*_dist)[v]; }
1.471 +
1.472 + /// \brief Returns the 'previous edge' of the shortest path tree.
1.473 + ///
1.474 + /// For a node \c v it returns the 'previous edge' of the shortest path
1.475 + /// tree, i.e. it returns the last edge of a shortest path from the root
1.476 + /// to \c v. It is \ref INVALID if \c v is unreachable from the root or
1.477 + /// if \c v=s. The shortest path tree used here is equal to the shortest
1.478 + /// path tree used in \ref predNode().
1.479 + /// \pre \ref run() must be called before using
1.480 + /// this function.
1.481 + /// \todo predEdge could be a better name.
1.482 + Edge pred(Node v) const { return (*_pred)[v]; }
1.483 +
1.484 + /// \brief Returns the 'previous node' of the shortest path tree.
1.485 + ///
1.486 + /// For a node \c v it returns the 'previous node' of the shortest path
1.487 + /// tree, i.e. it returns the last but one node from a shortest path from
1.488 + /// the root to \c /v. It is INVALID if \c v is unreachable from the root
1.489 + /// or if \c v=s. The shortest path tree used here is equal to the
1.490 + /// shortest path tree used in \ref pred(). \pre \ref run() must be
1.491 + /// called before using this function.
1.492 + Node predNode(Node v) const {
1.493 + return (*_pred)[v] == INVALID ? INVALID : graph->source((*_pred)[v]);
1.494 + }
1.495 +
1.496 + /// \brief Returns a reference to the NodeMap of distances.
1.497 + ///
1.498 + /// Returns a reference to the NodeMap of distances. \pre \ref run() must
1.499 + /// be called before using this function.
1.500 + const DistMap &distMap() const { return *_dist;}
1.501 +
1.502 + /// \brief Returns a reference to the shortest path tree map.
1.503 + ///
1.504 + /// Returns a reference to the NodeMap of the edges of the
1.505 + /// shortest path tree.
1.506 + /// \pre \ref run() must be called before using this function.
1.507 + const PredMap &predMap() const { return *_pred; }
1.508 +
1.509 + /// \brief Checks if a node is reachable from the root.
1.510 + ///
1.511 + /// Returns \c true if \c v is reachable from the root.
1.512 + /// \pre \ref run() must be called before using this function.
1.513 + ///
1.514 + bool reached(Node v) { return (*_dist)[v] != OperationTraits::infinity(); }
1.515 +
1.516 + ///@}
1.517 + };
1.518 +
1.519 + /// \brief Default traits class of BelmannFord function.
1.520 + ///
1.521 + /// Default traits class of BelmannFord function.
1.522 + /// \param _Graph Graph type.
1.523 + /// \param _LengthMap Type of length map.
1.524 + template <typename _Graph, typename _LengthMap>
1.525 + struct BelmannFordWizardDefaultTraits {
1.526 + /// \brief The graph type the algorithm runs on.
1.527 + typedef _Graph Graph;
1.528 +
1.529 + /// \brief The type of the map that stores the edge lengths.
1.530 + ///
1.531 + /// The type of the map that stores the edge lengths.
1.532 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.533 + typedef _LengthMap LengthMap;
1.534 +
1.535 + /// \brief The value type of the length map.
1.536 + typedef typename _LengthMap::Value Value;
1.537 +
1.538 + /// \brief Operation traits for belmann-ford algorithm.
1.539 + ///
1.540 + /// It defines the infinity type on the given Value type
1.541 + /// and the used operation.
1.542 + /// \see BelmannFordDefaultOperationTraits
1.543 + typedef BelmannFordDefaultOperationTraits<Value> OperationTraits;
1.544 +
1.545 + /// \brief The type of the map that stores the last
1.546 + /// edges of the shortest paths.
1.547 + ///
1.548 + /// The type of the map that stores the last
1.549 + /// edges of the shortest paths.
1.550 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.551 + typedef NullMap <typename _Graph::Node,typename _Graph::Edge> PredMap;
1.552 +
1.553 + /// \brief Instantiates a PredMap.
1.554 + ///
1.555 + /// This function instantiates a \ref PredMap.
1.556 + static PredMap *createPredMap(const _Graph &) {
1.557 + return new PredMap();
1.558 + }
1.559 + /// \brief The type of the map that stores the dists of the nodes.
1.560 + ///
1.561 + /// The type of the map that stores the dists of the nodes.
1.562 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.563 + typedef NullMap<typename Graph::Node, Value> DistMap;
1.564 + /// \brief Instantiates a DistMap.
1.565 + ///
1.566 + /// This function instantiates a \ref DistMap.
1.567 + static DistMap *createDistMap(const _Graph &) {
1.568 + return new DistMap();
1.569 + }
1.570 + };
1.571 +
1.572 + /// \brief Default traits used by \ref BelmannFordWizard
1.573 + ///
1.574 + /// To make it easier to use BelmannFord algorithm
1.575 + /// we have created a wizard class.
1.576 + /// This \ref BelmannFordWizard class needs default traits,
1.577 + /// as well as the \ref BelmannFord class.
1.578 + /// The \ref BelmannFordWizardBase is a class to be the default traits of the
1.579 + /// \ref BelmannFordWizard class.
1.580 + /// \todo More named parameters are required...
1.581 + template<class _Graph,class _LengthMap>
1.582 + class BelmannFordWizardBase
1.583 + : public BelmannFordWizardDefaultTraits<_Graph,_LengthMap> {
1.584 +
1.585 + typedef BelmannFordWizardDefaultTraits<_Graph,_LengthMap> Base;
1.586 + protected:
1.587 + /// Type of the nodes in the graph.
1.588 + typedef typename Base::Graph::Node Node;
1.589 +
1.590 + /// Pointer to the underlying graph.
1.591 + void *_graph;
1.592 + /// Pointer to the length map
1.593 + void *_length;
1.594 + ///Pointer to the map of predecessors edges.
1.595 + void *_pred;
1.596 + ///Pointer to the map of distances.
1.597 + void *_dist;
1.598 + ///Pointer to the source node.
1.599 + Node _source;
1.600 +
1.601 + public:
1.602 + /// Constructor.
1.603 +
1.604 + /// This constructor does not require parameters, therefore it initiates
1.605 + /// all of the attributes to default values (0, INVALID).
1.606 + BelmannFordWizardBase() : _graph(0), _length(0), _pred(0),
1.607 + _dist(0), _source(INVALID) {}
1.608 +
1.609 + /// Constructor.
1.610 +
1.611 + /// This constructor requires some parameters,
1.612 + /// listed in the parameters list.
1.613 + /// Others are initiated to 0.
1.614 + /// \param graph is the initial value of \ref _graph
1.615 + /// \param length is the initial value of \ref _length
1.616 + /// \param source is the initial value of \ref _source
1.617 + BelmannFordWizardBase(const _Graph& graph,
1.618 + const _LengthMap& length,
1.619 + Node source = INVALID) :
1.620 + _graph((void *)&graph), _length((void *)&length), _pred(0),
1.621 + _dist(0), _source(source) {}
1.622 +
1.623 + };
1.624 +
1.625 + /// A class to make the usage of BelmannFord algorithm easier
1.626 +
1.627 + /// This class is created to make it easier to use BelmannFord algorithm.
1.628 + /// It uses the functions and features of the plain \ref BelmannFord,
1.629 + /// but it is much simpler to use it.
1.630 + ///
1.631 + /// Simplicity means that the way to change the types defined
1.632 + /// in the traits class is based on functions that returns the new class
1.633 + /// and not on templatable built-in classes.
1.634 + /// When using the plain \ref BelmannFord
1.635 + /// the new class with the modified type comes from
1.636 + /// the original class by using the ::
1.637 + /// operator. In the case of \ref BelmannFordWizard only
1.638 + /// a function have to be called and it will
1.639 + /// return the needed class.
1.640 + ///
1.641 + /// It does not have own \ref run method. When its \ref run method is called
1.642 + /// it initiates a plain \ref BelmannFord class, and calls the \ref
1.643 + /// BelmannFord::run method of it.
1.644 + template<class _Traits>
1.645 + class BelmannFordWizard : public _Traits {
1.646 + typedef _Traits Base;
1.647 +
1.648 + ///The type of the underlying graph.
1.649 + typedef typename _Traits::Graph Graph;
1.650 +
1.651 + typedef typename Graph::Node Node;
1.652 + typedef typename Graph::NodeIt NodeIt;
1.653 + typedef typename Graph::Edge Edge;
1.654 + typedef typename Graph::OutEdgeIt EdgeIt;
1.655 +
1.656 + ///The type of the map that stores the edge lengths.
1.657 + typedef typename _Traits::LengthMap LengthMap;
1.658 +
1.659 + ///The type of the length of the edges.
1.660 + typedef typename LengthMap::Value Value;
1.661 +
1.662 + ///\brief The type of the map that stores the last
1.663 + ///edges of the shortest paths.
1.664 + typedef typename _Traits::PredMap PredMap;
1.665 +
1.666 + ///The type of the map that stores the dists of the nodes.
1.667 + typedef typename _Traits::DistMap DistMap;
1.668 +
1.669 + public:
1.670 + /// Constructor.
1.671 + BelmannFordWizard() : _Traits() {}
1.672 +
1.673 + /// \brief Constructor that requires parameters.
1.674 + ///
1.675 + /// Constructor that requires parameters.
1.676 + /// These parameters will be the default values for the traits class.
1.677 + BelmannFordWizard(const Graph& graph, const LengthMap& length,
1.678 + Node source = INVALID)
1.679 + : _Traits(graph, length, source) {}
1.680 +
1.681 + /// \brief Copy constructor
1.682 + BelmannFordWizard(const _Traits &b) : _Traits(b) {}
1.683 +
1.684 + ~BelmannFordWizard() {}
1.685 +
1.686 + /// \brief Runs BelmannFord algorithm from a given node.
1.687 + ///
1.688 + /// Runs BelmannFord algorithm from a given node.
1.689 + /// The node can be given by the \ref source function.
1.690 + void run() {
1.691 + if(Base::_source == INVALID) throw UninitializedParameter();
1.692 + BelmannFord<Graph,LengthMap,_Traits>
1.693 + bf(*(Graph*)Base::_graph, *(LengthMap*)Base::_length);
1.694 + if (Base::_pred) bf.predMap(*(PredMap*)Base::_pred);
1.695 + if (Base::_dist) bf.distMap(*(DistMap*)Base::_dist);
1.696 + bf.run(Base::_source);
1.697 + }
1.698 +
1.699 + /// \brief Runs BelmannFord algorithm from the given node.
1.700 + ///
1.701 + /// Runs BelmannFord algorithm from the given node.
1.702 + /// \param s is the given source.
1.703 + void run(Node source) {
1.704 + Base::_source = source;
1.705 + run();
1.706 + }
1.707 +
1.708 + template<class T>
1.709 + struct DefPredMapBase : public Base {
1.710 + typedef T PredMap;
1.711 + static PredMap *createPredMap(const Graph &) { return 0; };
1.712 + DefPredMapBase(const _Traits &b) : _Traits(b) {}
1.713 + };
1.714 +
1.715 + ///\brief \ref named-templ-param "Named parameter"
1.716 + ///function for setting PredMap type
1.717 + ///
1.718 + /// \ref named-templ-param "Named parameter"
1.719 + ///function for setting PredMap type
1.720 + ///
1.721 + template<class T>
1.722 + BelmannFordWizard<DefPredMapBase<T> > predMap(const T &t)
1.723 + {
1.724 + Base::_pred=(void *)&t;
1.725 + return BelmannFordWizard<DefPredMapBase<T> >(*this);
1.726 + }
1.727 +
1.728 + template<class T>
1.729 + struct DefDistMapBase : public Base {
1.730 + typedef T DistMap;
1.731 + static DistMap *createDistMap(const Graph &) { return 0; };
1.732 + DefDistMapBase(const _Traits &b) : _Traits(b) {}
1.733 + };
1.734 +
1.735 + ///\brief \ref named-templ-param "Named parameter"
1.736 + ///function for setting DistMap type
1.737 + ///
1.738 + /// \ref named-templ-param "Named parameter"
1.739 + ///function for setting DistMap type
1.740 + ///
1.741 + template<class T>
1.742 + BelmannFordWizard<DefDistMapBase<T> > distMap(const T &t) {
1.743 + Base::_dist=(void *)&t;
1.744 + return BelmannFordWizard<DefDistMapBase<T> >(*this);
1.745 + }
1.746 +
1.747 + /// \brief Sets the source node, from which the BelmannFord algorithm runs.
1.748 + ///
1.749 + /// Sets the source node, from which the BelmannFord algorithm runs.
1.750 + /// \param s is the source node.
1.751 + BelmannFordWizard<_Traits>& source(Node source) {
1.752 + Base::_source = source;
1.753 + return *this;
1.754 + }
1.755 +
1.756 + };
1.757 +
1.758 + /// \brief Function type interface for BelmannFord algorithm.
1.759 + ///
1.760 + /// \ingroup flowalgs
1.761 + /// Function type interface for BelmannFord algorithm.
1.762 + ///
1.763 + /// This function also has several \ref named-templ-func-param
1.764 + /// "named parameters", they are declared as the members of class
1.765 + /// \ref BelmannFordWizard.
1.766 + /// The following
1.767 + /// example shows how to use these parameters.
1.768 + /// \code
1.769 + /// belmannford(g,length,source).predMap(preds).run();
1.770 + /// \endcode
1.771 + /// \warning Don't forget to put the \ref BelmannFordWizard::run() "run()"
1.772 + /// to the end of the parameter list.
1.773 + /// \sa BelmannFordWizard
1.774 + /// \sa BelmannFord
1.775 + template<class _Graph, class _LengthMap>
1.776 + BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
1.777 + belmannFord(const _Graph& graph,
1.778 + const _LengthMap& length,
1.779 + typename _Graph::Node source = INVALID) {
1.780 + return BelmannFordWizard<BelmannFordWizardBase<_Graph,_LengthMap> >
1.781 + (graph, length, source);
1.782 + }
1.783 +
1.784 +} //END OF NAMESPACE LEMON
1.785 +
1.786 +#endif
1.787 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/floyd_warshall.h Mon Oct 03 10:20:56 2005 +0000
2.3 @@ -0,0 +1,525 @@
2.4 +/* -*- C++ -*-
2.5 + * lemon/floyd_warshall.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +#ifndef LEMON_FLOYD_WARSHALL_H
2.21 +#define LEMON_FLOYD_WARSHALL_H
2.22 +
2.23 +///\ingroup flowalgs
2.24 +/// \file
2.25 +/// \brief FloydWarshall algorithm.
2.26 +///
2.27 +/// \todo getPath() should be implemented! (also for BFS and DFS)
2.28 +
2.29 +#include <lemon/list_graph.h>
2.30 +#include <lemon/graph_utils.h>
2.31 +#include <lemon/invalid.h>
2.32 +#include <lemon/error.h>
2.33 +#include <lemon/maps.h>
2.34 +
2.35 +#include <limits>
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + /// \brief Default OperationTraits for the FloydWarshall algorithm class.
2.40 + ///
2.41 + /// It defines all computational operations and constants which are
2.42 + /// used in the Floyd-Warshall algorithm. The default implementation
2.43 + /// is based on the numeric_limits class. If the numeric type does not
2.44 + /// have infinity value then the maximum value is used as extremal
2.45 + /// infinity value.
2.46 + template <
2.47 + typename Value,
2.48 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
2.49 + struct FloydWarshallDefaultOperationTraits {
2.50 + /// \brief Gives back the zero value of the type.
2.51 + static Value zero() {
2.52 + return static_cast<Value>(0);
2.53 + }
2.54 + /// \brief Gives back the positive infinity value of the type.
2.55 + static Value infinity() {
2.56 + return std::numeric_limits<Value>::infinity();
2.57 + }
2.58 + /// \brief Gives back the sum of the given two elements.
2.59 + static Value plus(const Value& left, const Value& right) {
2.60 + return left + right;
2.61 + }
2.62 + /// \brief Gives back true only if the first value less than the second.
2.63 + static bool less(const Value& left, const Value& right) {
2.64 + return left < right;
2.65 + }
2.66 + };
2.67 +
2.68 + template <typename Value>
2.69 + struct FloydWarshallDefaultOperationTraits<Value, false> {
2.70 + static Value zero() {
2.71 + return static_cast<Value>(0);
2.72 + }
2.73 + static Value infinity() {
2.74 + return std::numeric_limits<Value>::max();
2.75 + }
2.76 + static Value plus(const Value& left, const Value& right) {
2.77 + if (left == infinity() || right == infinity()) return infinity();
2.78 + return left + right;
2.79 + }
2.80 + static bool less(const Value& left, const Value& right) {
2.81 + return left < right;
2.82 + }
2.83 + };
2.84 +
2.85 + /// \brief Default traits class of FloydWarshall class.
2.86 + ///
2.87 + /// Default traits class of FloydWarshall class.
2.88 + /// \param _Graph Graph type.
2.89 + /// \param _LegthMap Type of length map.
2.90 + template<class _Graph, class _LengthMap>
2.91 + struct FloydWarshallDefaultTraits {
2.92 + /// The graph type the algorithm runs on.
2.93 + typedef _Graph Graph;
2.94 +
2.95 + /// \brief The type of the map that stores the edge lengths.
2.96 + ///
2.97 + /// The type of the map that stores the edge lengths.
2.98 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
2.99 + typedef _LengthMap LengthMap;
2.100 +
2.101 + // The type of the length of the edges.
2.102 + typedef typename _LengthMap::Value Value;
2.103 +
2.104 + /// \brief Operation traits for belmann-ford algorithm.
2.105 + ///
2.106 + /// It defines the infinity type on the given Value type
2.107 + /// and the used operation.
2.108 + /// \see FloydWarshallDefaultOperationTraits
2.109 + typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
2.110 +
2.111 + /// \brief The type of the map that stores the last edges of the
2.112 + /// shortest paths.
2.113 + ///
2.114 + /// The type of the map that stores the last
2.115 + /// edges of the shortest paths.
2.116 + /// It must be a matrix map with \c Graph::Edge value type.
2.117 + ///
2.118 + typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
2.119 +
2.120 + /// \brief Instantiates a PredMap.
2.121 + ///
2.122 + /// This function instantiates a \ref PredMap.
2.123 + /// \param G is the graph, to which we would like to define the PredMap.
2.124 + /// \todo The graph alone may be insufficient for the initialization
2.125 + static PredMap *createPredMap(const _Graph& graph) {
2.126 + return new PredMap(graph);
2.127 + }
2.128 +
2.129 + /// \brief The type of the map that stores the dists of the nodes.
2.130 + ///
2.131 + /// The type of the map that stores the dists of the nodes.
2.132 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
2.133 + ///
2.134 + typedef NodeMatrixMap<Graph, Value> DistMap;
2.135 +
2.136 + /// \brief Instantiates a DistMap.
2.137 + ///
2.138 + /// This function instantiates a \ref DistMap.
2.139 + /// \param G is the graph, to which we would like to define the
2.140 + /// \ref DistMap
2.141 + static DistMap *createDistMap(const _Graph& graph) {
2.142 + return new DistMap(graph);
2.143 + }
2.144 +
2.145 + };
2.146 +
2.147 + /// \brief FloydWarshall algorithm class.
2.148 + ///
2.149 + /// \ingroup flowalgs
2.150 + /// This class provides an efficient implementation of \c FloydWarshall
2.151 + /// algorithm. The edge lengths are passed to the algorithm using a
2.152 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
2.153 + /// kind of length.
2.154 + ///
2.155 + /// The type of the length is determined by the
2.156 + /// \ref concept::ReadMap::Value "Value" of the length map.
2.157 + ///
2.158 + /// \param _Graph The graph type the algorithm runs on. The default value
2.159 + /// is \ref ListGraph. The value of _Graph is not used directly by
2.160 + /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits.
2.161 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
2.162 + /// edges. It is read once for each edge, so the map may involve in
2.163 + /// relatively time consuming process to compute the edge length if
2.164 + /// it is necessary. The default map type is \ref
2.165 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
2.166 + /// of _LengthMap is not used directly by FloydWarshall, it is only passed
2.167 + /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set
2.168 + /// various data types used by the algorithm. The default traits
2.169 + /// class is \ref FloydWarshallDefaultTraits
2.170 + /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref
2.171 + /// FloydWarshallDefaultTraits for the documentation of a FloydWarshall
2.172 + /// traits class.
2.173 + ///
2.174 + /// \author Balazs Dezso
2.175 +
2.176 +
2.177 + template <typename _Graph=ListGraph,
2.178 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
2.179 + typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
2.180 + class FloydWarshall {
2.181 + public:
2.182 +
2.183 + /// \brief \ref Exception for uninitialized parameters.
2.184 + ///
2.185 + /// This error represents problems in the initialization
2.186 + /// of the parameters of the algorithms.
2.187 +
2.188 + class UninitializedParameter : public lemon::UninitializedParameter {
2.189 + public:
2.190 + virtual const char* exceptionName() const {
2.191 + return "lemon::FloydWarshall::UninitializedParameter";
2.192 + }
2.193 + };
2.194 +
2.195 + typedef _Traits Traits;
2.196 + ///The type of the underlying graph.
2.197 + typedef typename _Traits::Graph Graph;
2.198 +
2.199 + typedef typename Graph::Node Node;
2.200 + typedef typename Graph::NodeIt NodeIt;
2.201 + typedef typename Graph::Edge Edge;
2.202 + typedef typename Graph::EdgeIt EdgeIt;
2.203 +
2.204 + /// \brief The type of the length of the edges.
2.205 + typedef typename _Traits::LengthMap::Value Value;
2.206 + /// \brief The type of the map that stores the edge lengths.
2.207 + typedef typename _Traits::LengthMap LengthMap;
2.208 + /// \brief The type of the map that stores the last
2.209 + /// edges of the shortest paths. The type of the PredMap
2.210 + /// is a matrix map for Edges
2.211 + typedef typename _Traits::PredMap PredMap;
2.212 + /// \brief The type of the map that stores the dists of the nodes.
2.213 + /// The type of the DistMap is a matrix map for Values
2.214 + typedef typename _Traits::DistMap DistMap;
2.215 + /// \brief The operation traits.
2.216 + typedef typename _Traits::OperationTraits OperationTraits;
2.217 + private:
2.218 + /// Pointer to the underlying graph.
2.219 + const Graph *graph;
2.220 + /// Pointer to the length map
2.221 + const LengthMap *length;
2.222 + ///Pointer to the map of predecessors edges.
2.223 + PredMap *_pred;
2.224 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
2.225 + bool local_pred;
2.226 + ///Pointer to the map of distances.
2.227 + DistMap *_dist;
2.228 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
2.229 + bool local_dist;
2.230 +
2.231 + /// Creates the maps if necessary.
2.232 + void create_maps() {
2.233 + if(!_pred) {
2.234 + local_pred = true;
2.235 + _pred = Traits::createPredMap(*graph);
2.236 + }
2.237 + if(!_dist) {
2.238 + local_dist = true;
2.239 + _dist = Traits::createDistMap(*graph);
2.240 + }
2.241 + }
2.242 +
2.243 + public :
2.244 +
2.245 + /// \name Named template parameters
2.246 +
2.247 + ///@{
2.248 +
2.249 + template <class T>
2.250 + struct DefPredMapTraits : public Traits {
2.251 + typedef T PredMap;
2.252 + static PredMap *createPredMap(const Graph& graph) {
2.253 + throw UninitializedParameter();
2.254 + }
2.255 + };
2.256 +
2.257 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
2.258 + /// type
2.259 + /// \ref named-templ-param "Named parameter" for setting PredMap type
2.260 + ///
2.261 + template <class T>
2.262 + class DefPredMap
2.263 + : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {};
2.264 +
2.265 + template <class T>
2.266 + struct DefDistMapTraits : public Traits {
2.267 + typedef T DistMap;
2.268 + static DistMap *createDistMap(const Graph& graph) {
2.269 + throw UninitializedParameter();
2.270 + }
2.271 + };
2.272 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
2.273 + /// type
2.274 + ///
2.275 + /// \ref named-templ-param "Named parameter" for setting DistMap type
2.276 + ///
2.277 + template <class T>
2.278 + class DefDistMap
2.279 + : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {};
2.280 +
2.281 + template <class T>
2.282 + struct DefOperationTraitsTraits : public Traits {
2.283 + typedef T OperationTraits;
2.284 + };
2.285 +
2.286 + /// \brief \ref named-templ-param "Named parameter" for setting
2.287 + /// OperationTraits type
2.288 + ///
2.289 + /// \ref named-templ-param "Named parameter" for setting PredMap type
2.290 + template <class T>
2.291 + class DefOperationTraits
2.292 + : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
2.293 + };
2.294 +
2.295 + ///@}
2.296 +
2.297 + public:
2.298 +
2.299 + /// \brief Constructor.
2.300 + ///
2.301 + /// \param _graph the graph the algorithm will run on.
2.302 + /// \param _length the length map used by the algorithm.
2.303 + FloydWarshall(const Graph& _graph, const LengthMap& _length) :
2.304 + graph(&_graph), length(&_length),
2.305 + _pred(0), local_pred(false),
2.306 + _dist(0), local_dist(false) {}
2.307 +
2.308 + ///Destructor.
2.309 + ~FloydWarshall() {
2.310 + if(local_pred) delete _pred;
2.311 + if(local_dist) delete _dist;
2.312 + }
2.313 +
2.314 + /// \brief Sets the length map.
2.315 + ///
2.316 + /// Sets the length map.
2.317 + /// \return \c (*this)
2.318 + FloydWarshall &lengthMap(const LengthMap &m) {
2.319 + length = &m;
2.320 + return *this;
2.321 + }
2.322 +
2.323 + /// \brief Sets the map storing the predecessor edges.
2.324 + ///
2.325 + /// Sets the map storing the predecessor edges.
2.326 + /// If you don't use this function before calling \ref run(),
2.327 + /// it will allocate one. The destuctor deallocates this
2.328 + /// automatically allocated map, of course.
2.329 + /// \return \c (*this)
2.330 + FloydWarshall &predMap(PredMap &m) {
2.331 + if(local_pred) {
2.332 + delete _pred;
2.333 + local_pred=false;
2.334 + }
2.335 + _pred = &m;
2.336 + return *this;
2.337 + }
2.338 +
2.339 + /// \brief Sets the map storing the distances calculated by the algorithm.
2.340 + ///
2.341 + /// Sets the map storing the distances calculated by the algorithm.
2.342 + /// If you don't use this function before calling \ref run(),
2.343 + /// it will allocate one. The destuctor deallocates this
2.344 + /// automatically allocated map, of course.
2.345 + /// \return \c (*this)
2.346 + FloydWarshall &distMap(DistMap &m) {
2.347 + if(local_dist) {
2.348 + delete _dist;
2.349 + local_dist=false;
2.350 + }
2.351 + _dist = &m;
2.352 + return *this;
2.353 + }
2.354 +
2.355 + ///\name Execution control
2.356 + /// The simplest way to execute the algorithm is to use
2.357 + /// one of the member functions called \c run(...).
2.358 + /// \n
2.359 + /// If you need more control on the execution,
2.360 + /// Finally \ref start() will perform the actual path
2.361 + /// computation.
2.362 +
2.363 + ///@{
2.364 +
2.365 + /// \brief Initializes the internal data structures.
2.366 + ///
2.367 + /// Initializes the internal data structures.
2.368 + void init() {
2.369 + create_maps();
2.370 + for (NodeIt it(*graph); it != INVALID; ++it) {
2.371 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
2.372 + _pred->set(it, jt, INVALID);
2.373 + _dist->set(it, jt, it == jt ?
2.374 + OperationTraits::zero() : OperationTraits::infinity());
2.375 + }
2.376 + }
2.377 + for (EdgeIt it(*graph); it != INVALID; ++it) {
2.378 + Node source = graph->source(it);
2.379 + Node target = graph->target(it);
2.380 + if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
2.381 + _dist->set(source, target, (*length)[it]);
2.382 + _pred->set(source, target, it);
2.383 + }
2.384 + }
2.385 + }
2.386 +
2.387 + /// \brief Executes the algorithm.
2.388 + ///
2.389 + /// This method runs the %FloydWarshall algorithm in order to compute
2.390 + /// the shortest path to each node pairs. The algorithm
2.391 + /// computes
2.392 + /// - The shortest path tree for each node.
2.393 + /// - The distance between each node pairs.
2.394 + void start() {
2.395 + for (NodeIt kt(*graph); kt != INVALID; ++kt) {
2.396 + for (NodeIt it(*graph); it != INVALID; ++it) {
2.397 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
2.398 + Value relaxed = OperationTraits::plus((*_dist)(it, kt),
2.399 + (*_dist)(kt, jt));
2.400 + if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
2.401 + _dist->set(it, jt, relaxed);
2.402 + _pred->set(it, jt, (*_pred)(kt, jt));
2.403 + }
2.404 + }
2.405 + }
2.406 + }
2.407 + }
2.408 +
2.409 + /// \brief Runs %FloydWarshall algorithm.
2.410 + ///
2.411 + /// This method runs the %FloydWarshall algorithm from a each node
2.412 + /// in order to compute the shortest path to each node pairs.
2.413 + /// The algorithm computes
2.414 + /// - The shortest path tree for each node.
2.415 + /// - The distance between each node pairs.
2.416 + ///
2.417 + /// \note d.run(s) is just a shortcut of the following code.
2.418 + /// \code
2.419 + /// d.init();
2.420 + /// d.start();
2.421 + /// \endcode
2.422 + void run() {
2.423 + init();
2.424 + start();
2.425 + }
2.426 +
2.427 + ///@}
2.428 +
2.429 + /// \name Query Functions
2.430 + /// The result of the %FloydWarshall algorithm can be obtained using these
2.431 + /// functions.\n
2.432 + /// Before the use of these functions,
2.433 + /// either run() or start() must be called.
2.434 +
2.435 + ///@{
2.436 +
2.437 + /// \brief Copies the shortest path to \c t into \c p
2.438 + ///
2.439 + /// This function copies the shortest path to \c t into \c p.
2.440 + /// If it \c t is a source itself or unreachable, then it does not
2.441 + /// alter \c p.
2.442 + /// \todo Is it the right way to handle unreachable nodes?
2.443 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
2.444 + /// \c false otherwise.
2.445 + /// \sa DirPath
2.446 + template <typename Path>
2.447 + bool getPath(Path &p, Node source, Node target) {
2.448 + if (connected(source, target)) {
2.449 + p.clear();
2.450 + typename Path::Builder b(target);
2.451 + for(b.setStartNode(target); pred(source, target) != INVALID;
2.452 + target = predNode(target)) {
2.453 + b.pushFront(pred(source, target));
2.454 + }
2.455 + b.commit();
2.456 + return true;
2.457 + }
2.458 + return false;
2.459 + }
2.460 +
2.461 + /// \brief The distance between two nodes.
2.462 + ///
2.463 + /// Returns the distance between two nodes.
2.464 + /// \pre \ref run() must be called before using this function.
2.465 + /// \warning If node \c v in unreachable from the root the return value
2.466 + /// of this funcion is undefined.
2.467 + Value dist(Node source, Node target) const {
2.468 + return (*_dist)(source, target);
2.469 + }
2.470 +
2.471 + /// \brief Returns the 'previous edge' of the shortest path tree.
2.472 + ///
2.473 + /// For the node \c node it returns the 'previous edge' of the shortest
2.474 + /// path tree to direction of the node \c root
2.475 + /// i.e. it returns the last edge of a shortest path from the node \c root
2.476 + /// to \c node. It is \ref INVALID if \c node is unreachable from the root
2.477 + /// or if \c node=root. The shortest path tree used here is equal to the
2.478 + /// shortest path tree used in \ref predNode().
2.479 + /// \pre \ref run() must be called before using this function.
2.480 + /// \todo predEdge could be a better name.
2.481 + Edge pred(Node root, Node node) const {
2.482 + return (*_pred)(root, node);
2.483 + }
2.484 +
2.485 + /// \brief Returns the 'previous node' of the shortest path tree.
2.486 + ///
2.487 + /// For a node \c node it returns the 'previous node' of the shortest path
2.488 + /// tree to direction of the node \c root, i.e. it returns the last but
2.489 + /// one node from a shortest path from the \c root to \c node. It is
2.490 + /// INVALID if \c node is unreachable from the root or if \c node=root.
2.491 + /// The shortest path tree used here is equal to the
2.492 + /// shortest path tree used in \ref pred().
2.493 + /// \pre \ref run() must be called before using this function.
2.494 + Node predNode(Node root, Node node) const {
2.495 + return (*_pred)(root, node) == INVALID ?
2.496 + INVALID : graph->source((*_pred)(root, node));
2.497 + }
2.498 +
2.499 + /// \brief Returns a reference to the matrix node map of distances.
2.500 + ///
2.501 + /// Returns a reference to the matrix node map of distances.
2.502 + ///
2.503 + /// \pre \ref run() must be called before using this function.
2.504 + const DistMap &distMap() const { return *_dist;}
2.505 +
2.506 + /// \brief Returns a reference to the shortest path tree map.
2.507 + ///
2.508 + /// Returns a reference to the matrix node map of the edges of the
2.509 + /// shortest path tree.
2.510 + /// \pre \ref run() must be called before using this function.
2.511 + const PredMap &predMap() const { return *_pred;}
2.512 +
2.513 + /// \brief Checks if a node is reachable from the root.
2.514 + ///
2.515 + /// Returns \c true if \c v is reachable from the root.
2.516 + /// \pre \ref run() must be called before using this function.
2.517 + ///
2.518 + bool connected(Node source, Node target) {
2.519 + return (*_dist)(source, target) != OperationTraits::infinity();
2.520 + }
2.521 +
2.522 + ///@}
2.523 + };
2.524 +
2.525 +} //END OF NAMESPACE LEMON
2.526 +
2.527 +#endif
2.528 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/lemon/johnson.h Mon Oct 03 10:20:56 2005 +0000
3.3 @@ -0,0 +1,547 @@
3.4 +/* -*- C++ -*-
3.5 + * lemon/johnson.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +#ifndef LEMON_JOHNSON_H
3.21 +#define LEMON_JOHNSON_H
3.22 +
3.23 +///\ingroup flowalgs
3.24 +/// \file
3.25 +/// \brief Johnson algorithm.
3.26 +///
3.27 +
3.28 +#include <lemon/list_graph.h>
3.29 +#include <lemon/graph_utils.h>
3.30 +#include <lemon/dfs.h>
3.31 +#include <lemon/dijkstra.h>
3.32 +#include <lemon/belmann_ford.h>
3.33 +#include <lemon/invalid.h>
3.34 +#include <lemon/error.h>
3.35 +#include <lemon/maps.h>
3.36 +
3.37 +#include <limits>
3.38 +
3.39 +namespace lemon {
3.40 +
3.41 + /// \brief Default OperationTraits for the Johnson algorithm class.
3.42 + ///
3.43 + /// It defines all computational operations and constants which are
3.44 + /// used in the Floyd-Warshall algorithm. The default implementation
3.45 + /// is based on the numeric_limits class. If the numeric type does not
3.46 + /// have infinity value then the maximum value is used as extremal
3.47 + /// infinity value.
3.48 + template <
3.49 + typename Value,
3.50 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
3.51 + struct JohnsonDefaultOperationTraits {
3.52 + /// \brief Gives back the zero value of the type.
3.53 + static Value zero() {
3.54 + return static_cast<Value>(0);
3.55 + }
3.56 + /// \brief Gives back the positive infinity value of the type.
3.57 + static Value infinity() {
3.58 + return std::numeric_limits<Value>::infinity();
3.59 + }
3.60 + /// \brief Gives back the sum of the given two elements.
3.61 + static Value plus(const Value& left, const Value& right) {
3.62 + return left + right;
3.63 + }
3.64 + /// \brief Gives back true only if the first value less than the second.
3.65 + static bool less(const Value& left, const Value& right) {
3.66 + return left < right;
3.67 + }
3.68 + };
3.69 +
3.70 + template <typename Value>
3.71 + struct JohnsonDefaultOperationTraits<Value, false> {
3.72 + static Value zero() {
3.73 + return static_cast<Value>(0);
3.74 + }
3.75 + static Value infinity() {
3.76 + return std::numeric_limits<Value>::max();
3.77 + }
3.78 + static Value plus(const Value& left, const Value& right) {
3.79 + if (left == infinity() || right == infinity()) return infinity();
3.80 + return left + right;
3.81 + }
3.82 + static bool less(const Value& left, const Value& right) {
3.83 + return left < right;
3.84 + }
3.85 + };
3.86 +
3.87 + /// \brief Default traits class of Johnson class.
3.88 + ///
3.89 + /// Default traits class of Johnson class.
3.90 + /// \param _Graph Graph type.
3.91 + /// \param _LegthMap Type of length map.
3.92 + template<class _Graph, class _LengthMap>
3.93 + struct JohnsonDefaultTraits {
3.94 + /// The graph type the algorithm runs on.
3.95 + typedef _Graph Graph;
3.96 +
3.97 + /// \brief The type of the map that stores the edge lengths.
3.98 + ///
3.99 + /// The type of the map that stores the edge lengths.
3.100 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
3.101 + typedef _LengthMap LengthMap;
3.102 +
3.103 + // The type of the length of the edges.
3.104 + typedef typename _LengthMap::Value Value;
3.105 +
3.106 + /// \brief Operation traits for belmann-ford algorithm.
3.107 + ///
3.108 + /// It defines the infinity type on the given Value type
3.109 + /// and the used operation.
3.110 + /// \see JohnsonDefaultOperationTraits
3.111 + typedef JohnsonDefaultOperationTraits<Value> OperationTraits;
3.112 +
3.113 + /// \brief The type of the map that stores the last edges of the
3.114 + /// shortest paths.
3.115 + ///
3.116 + /// The type of the map that stores the last
3.117 + /// edges of the shortest paths.
3.118 + /// It must be a matrix map with \c Graph::Edge value type.
3.119 + ///
3.120 + typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
3.121 +
3.122 + /// \brief Instantiates a PredMap.
3.123 + ///
3.124 + /// This function instantiates a \ref PredMap.
3.125 + /// \param G is the graph, to which we would like to define the PredMap.
3.126 + /// \todo The graph alone may be insufficient for the initialization
3.127 + static PredMap *createPredMap(const _Graph& graph) {
3.128 + return new PredMap(graph);
3.129 + }
3.130 +
3.131 + /// \brief The type of the map that stores the dists of the nodes.
3.132 + ///
3.133 + /// The type of the map that stores the dists of the nodes.
3.134 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
3.135 + ///
3.136 + typedef NodeMatrixMap<Graph, Value> DistMap;
3.137 +
3.138 + /// \brief Instantiates a DistMap.
3.139 + ///
3.140 + /// This function instantiates a \ref DistMap.
3.141 + /// \param G is the graph, to which we would like to define the
3.142 + /// \ref DistMap
3.143 + static DistMap *createDistMap(const _Graph& graph) {
3.144 + return new DistMap(graph);
3.145 + }
3.146 +
3.147 + };
3.148 +
3.149 + /// \brief Johnson algorithm class.
3.150 + ///
3.151 + /// \ingroup flowalgs
3.152 + /// This class provides an efficient implementation of \c Johnson
3.153 + /// algorithm. The edge lengths are passed to the algorithm using a
3.154 + /// \ref concept::ReadMap "ReadMap", so it is easy to change it to any
3.155 + /// kind of length.
3.156 + ///
3.157 + /// The type of the length is determined by the
3.158 + /// \ref concept::ReadMap::Value "Value" of the length map.
3.159 + ///
3.160 + /// \param _Graph The graph type the algorithm runs on. The default value
3.161 + /// is \ref ListGraph. The value of _Graph is not used directly by
3.162 + /// Johnson, it is only passed to \ref JohnsonDefaultTraits.
3.163 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
3.164 + /// edges. It is read once for each edge, so the map may involve in
3.165 + /// relatively time consuming process to compute the edge length if
3.166 + /// it is necessary. The default map type is \ref
3.167 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
3.168 + /// of _LengthMap is not used directly by Johnson, it is only passed
3.169 + /// to \ref JohnsonDefaultTraits. \param _Traits Traits class to set
3.170 + /// various data types used by the algorithm. The default traits
3.171 + /// class is \ref JohnsonDefaultTraits
3.172 + /// "JohnsonDefaultTraits<_Graph,_LengthMap>". See \ref
3.173 + /// JohnsonDefaultTraits for the documentation of a Johnson traits
3.174 + /// class.
3.175 + ///
3.176 + /// \author Balazs Dezso
3.177 +
3.178 + template <typename _Graph=ListGraph,
3.179 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
3.180 + typename _Traits=JohnsonDefaultTraits<_Graph,_LengthMap> >
3.181 + class Johnson {
3.182 + public:
3.183 +
3.184 + /// \brief \ref Exception for uninitialized parameters.
3.185 + ///
3.186 + /// This error represents problems in the initialization
3.187 + /// of the parameters of the algorithms.
3.188 +
3.189 + class UninitializedParameter : public lemon::UninitializedParameter {
3.190 + public:
3.191 + virtual const char* exceptionName() const {
3.192 + return "lemon::Johnson::UninitializedParameter";
3.193 + }
3.194 + };
3.195 +
3.196 + typedef _Traits Traits;
3.197 + ///The type of the underlying graph.
3.198 + typedef typename _Traits::Graph Graph;
3.199 +
3.200 + typedef typename Graph::Node Node;
3.201 + typedef typename Graph::NodeIt NodeIt;
3.202 + typedef typename Graph::Edge Edge;
3.203 + typedef typename Graph::EdgeIt EdgeIt;
3.204 +
3.205 + /// \brief The type of the length of the edges.
3.206 + typedef typename _Traits::LengthMap::Value Value;
3.207 + /// \brief The type of the map that stores the edge lengths.
3.208 + typedef typename _Traits::LengthMap LengthMap;
3.209 + /// \brief The type of the map that stores the last
3.210 + /// edges of the shortest paths. The type of the PredMap
3.211 + /// is a matrix map for Edges
3.212 + typedef typename _Traits::PredMap PredMap;
3.213 + /// \brief The type of the map that stores the dists of the nodes.
3.214 + /// The type of the DistMap is a matrix map for Values
3.215 + typedef typename _Traits::DistMap DistMap;
3.216 + /// \brief The operation traits.
3.217 + typedef typename _Traits::OperationTraits OperationTraits;
3.218 + private:
3.219 + /// Pointer to the underlying graph.
3.220 + const Graph *graph;
3.221 + /// Pointer to the length map
3.222 + const LengthMap *length;
3.223 + ///Pointer to the map of predecessors edges.
3.224 + PredMap *_pred;
3.225 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
3.226 + bool local_pred;
3.227 + ///Pointer to the map of distances.
3.228 + DistMap *_dist;
3.229 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
3.230 + bool local_dist;
3.231 +
3.232 + /// Creates the maps if necessary.
3.233 + void create_maps() {
3.234 + if(!_pred) {
3.235 + local_pred = true;
3.236 + _pred = Traits::createPredMap(*graph);
3.237 + }
3.238 + if(!_dist) {
3.239 + local_dist = true;
3.240 + _dist = Traits::createDistMap(*graph);
3.241 + }
3.242 + }
3.243 +
3.244 + public :
3.245 +
3.246 + /// \name Named template parameters
3.247 +
3.248 + ///@{
3.249 +
3.250 + template <class T>
3.251 + struct DefPredMapTraits : public Traits {
3.252 + typedef T PredMap;
3.253 + static PredMap *createPredMap(const Graph& graph) {
3.254 + throw UninitializedParameter();
3.255 + }
3.256 + };
3.257 +
3.258 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
3.259 + /// type
3.260 + /// \ref named-templ-param "Named parameter" for setting PredMap type
3.261 + ///
3.262 + template <class T>
3.263 + class DefPredMap
3.264 + : public Johnson< Graph, LengthMap, DefPredMapTraits<T> > {};
3.265 +
3.266 + template <class T>
3.267 + struct DefDistMapTraits : public Traits {
3.268 + typedef T DistMap;
3.269 + static DistMap *createDistMap(const Graph& graph) {
3.270 + throw UninitializedParameter();
3.271 + }
3.272 + };
3.273 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
3.274 + /// type
3.275 + ///
3.276 + /// \ref named-templ-param "Named parameter" for setting DistMap type
3.277 + ///
3.278 + template <class T>
3.279 + class DefDistMap
3.280 + : public Johnson< Graph, LengthMap, DefDistMapTraits<T> > {};
3.281 +
3.282 + template <class T>
3.283 + struct DefOperationTraitsTraits : public Traits {
3.284 + typedef T OperationTraits;
3.285 + };
3.286 +
3.287 + /// \brief \ref named-templ-param "Named parameter" for setting
3.288 + /// OperationTraits type
3.289 + ///
3.290 + /// \ref named-templ-param "Named parameter" for setting PredMap type
3.291 + template <class T>
3.292 + class DefOperationTraits
3.293 + : public Johnson< Graph, LengthMap, DefOperationTraitsTraits<T> > {};
3.294 +
3.295 + ///@}
3.296 +
3.297 + public:
3.298 +
3.299 + /// \brief Constructor.
3.300 + ///
3.301 + /// \param _graph the graph the algorithm will run on.
3.302 + /// \param _length the length map used by the algorithm.
3.303 + Johnson(const Graph& _graph, const LengthMap& _length) :
3.304 + graph(&_graph), length(&_length),
3.305 + _pred(0), local_pred(false),
3.306 + _dist(0), local_dist(false) {}
3.307 +
3.308 + ///Destructor.
3.309 + ~Johnson() {
3.310 + if(local_pred) delete _pred;
3.311 + if(local_dist) delete _dist;
3.312 + }
3.313 +
3.314 + /// \brief Sets the length map.
3.315 + ///
3.316 + /// Sets the length map.
3.317 + /// \return \c (*this)
3.318 + Johnson &lengthMap(const LengthMap &m) {
3.319 + length = &m;
3.320 + return *this;
3.321 + }
3.322 +
3.323 + /// \brief Sets the map storing the predecessor edges.
3.324 + ///
3.325 + /// Sets the map storing the predecessor edges.
3.326 + /// If you don't use this function before calling \ref run(),
3.327 + /// it will allocate one. The destuctor deallocates this
3.328 + /// automatically allocated map, of course.
3.329 + /// \return \c (*this)
3.330 + Johnson &predMap(PredMap &m) {
3.331 + if(local_pred) {
3.332 + delete _pred;
3.333 + local_pred=false;
3.334 + }
3.335 + _pred = &m;
3.336 + return *this;
3.337 + }
3.338 +
3.339 + /// \brief Sets the map storing the distances calculated by the algorithm.
3.340 + ///
3.341 + /// Sets the map storing the distances calculated by the algorithm.
3.342 + /// If you don't use this function before calling \ref run(),
3.343 + /// it will allocate one. The destuctor deallocates this
3.344 + /// automatically allocated map, of course.
3.345 + /// \return \c (*this)
3.346 + Johnson &distMap(DistMap &m) {
3.347 + if(local_dist) {
3.348 + delete _dist;
3.349 + local_dist=false;
3.350 + }
3.351 + _dist = &m;
3.352 + return *this;
3.353 + }
3.354 +
3.355 + ///\name Execution control
3.356 + /// The simplest way to execute the algorithm is to use
3.357 + /// one of the member functions called \c run(...).
3.358 + /// \n
3.359 + /// If you need more control on the execution,
3.360 + /// Finally \ref start() will perform the actual path
3.361 + /// computation.
3.362 +
3.363 + ///@{
3.364 +
3.365 + /// \brief Initializes the internal data structures.
3.366 + ///
3.367 + /// Initializes the internal data structures.
3.368 + void init() {
3.369 + create_maps();
3.370 + }
3.371 +
3.372 + /// \brief Executes the algorithm.
3.373 + ///
3.374 + /// This method runs the %Johnson algorithm in order to compute
3.375 + /// the shortest path to each node pairs. The algorithm
3.376 + /// computes
3.377 + /// - The shortest path tree for each node.
3.378 + /// - The distance between each node pairs.
3.379 + void start() {
3.380 + typename BelmannFord<Graph, LengthMap>::
3.381 + template DefOperationTraits<OperationTraits>::
3.382 + BelmannFord belmannford(*graph, *length);
3.383 +
3.384 + belmannford.init();
3.385 +
3.386 + typename Graph::template NodeMap<bool> initial(*graph, false);
3.387 +
3.388 + {
3.389 + Dfs<Graph> dfs(*graph);
3.390 +
3.391 + dfs.init();
3.392 + for (NodeIt it(*graph); it != INVALID; ++it) {
3.393 + if (!dfs.reached(it)) {
3.394 + dfs.addSource(it);
3.395 + while (!dfs.emptyQueue()) {
3.396 + Edge edge = dfs.processNextEdge();
3.397 + initial.set(graph->target(edge), false);
3.398 + }
3.399 + initial.set(it, true);
3.400 + }
3.401 + }
3.402 + for (NodeIt it(*graph); it != INVALID; ++it) {
3.403 + if (initial[it]) {
3.404 + belmannford.addSource(it);
3.405 + }
3.406 + }
3.407 + }
3.408 +
3.409 + belmannford.start();
3.410 +
3.411 + for (NodeIt it(*graph); it != INVALID; ++it) {
3.412 + typedef PotentialDifferenceMap<Graph,
3.413 + typename BelmannFord<Graph, LengthMap>::DistMap> PotDiffMap;
3.414 + PotDiffMap potdiff(*graph, belmannford.distMap());
3.415 + typedef SubMap<LengthMap, PotDiffMap> ShiftLengthMap;
3.416 + ShiftLengthMap shiftlen(*length, potdiff);
3.417 + Dijkstra<Graph, ShiftLengthMap> dijkstra(*graph, shiftlen);
3.418 + dijkstra.run(it);
3.419 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
3.420 + if (dijkstra.reached(jt)) {
3.421 + _dist->set(it, jt, dijkstra.dist(jt) +
3.422 + belmannford.dist(jt) - belmannford.dist(it));
3.423 + _pred->set(it, jt, dijkstra.pred(jt));
3.424 + } else {
3.425 + _dist->set(it, jt, OperationTraits::infinity());
3.426 + _pred->set(it, jt, INVALID);
3.427 + }
3.428 + }
3.429 + }
3.430 + }
3.431 +
3.432 + /// \brief Runs %Johnson algorithm.
3.433 + ///
3.434 + /// This method runs the %Johnson algorithm from a each node
3.435 + /// in order to compute the shortest path to each node pairs.
3.436 + /// The algorithm computes
3.437 + /// - The shortest path tree for each node.
3.438 + /// - The distance between each node pairs.
3.439 + ///
3.440 + /// \note d.run(s) is just a shortcut of the following code.
3.441 + /// \code
3.442 + /// d.init();
3.443 + /// d.start();
3.444 + /// \endcode
3.445 + void run() {
3.446 + init();
3.447 + start();
3.448 + }
3.449 +
3.450 + ///@}
3.451 +
3.452 + /// \name Query Functions
3.453 + /// The result of the %Johnson algorithm can be obtained using these
3.454 + /// functions.\n
3.455 + /// Before the use of these functions,
3.456 + /// either run() or start() must be called.
3.457 +
3.458 + ///@{
3.459 +
3.460 + /// \brief Copies the shortest path to \c t into \c p
3.461 + ///
3.462 + /// This function copies the shortest path to \c t into \c p.
3.463 + /// If it \c t is a source itself or unreachable, then it does not
3.464 + /// alter \c p.
3.465 + /// \todo Is it the right way to handle unreachable nodes?
3.466 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
3.467 + /// \c false otherwise.
3.468 + /// \sa DirPath
3.469 + template <typename Path>
3.470 + bool getPath(Path &p, Node source, Node target) {
3.471 + if (connected(source, target)) {
3.472 + p.clear();
3.473 + typename Path::Builder b(target);
3.474 + for(b.setStartNode(target); pred(source, target) != INVALID;
3.475 + target = predNode(target)) {
3.476 + b.pushFront(pred(source, target));
3.477 + }
3.478 + b.commit();
3.479 + return true;
3.480 + }
3.481 + return false;
3.482 + }
3.483 +
3.484 + /// \brief The distance between two nodes.
3.485 + ///
3.486 + /// Returns the distance between two nodes.
3.487 + /// \pre \ref run() must be called before using this function.
3.488 + /// \warning If node \c v in unreachable from the root the return value
3.489 + /// of this funcion is undefined.
3.490 + Value dist(Node source, Node target) const {
3.491 + return (*_dist)(source, target);
3.492 + }
3.493 +
3.494 + /// \brief Returns the 'previous edge' of the shortest path tree.
3.495 + ///
3.496 + /// For the node \c node it returns the 'previous edge' of the shortest
3.497 + /// path tree to direction of the node \c root
3.498 + /// i.e. it returns the last edge of a shortest path from the node \c root
3.499 + /// to \c node. It is \ref INVALID if \c node is unreachable from the root
3.500 + /// or if \c node=root. The shortest path tree used here is equal to the
3.501 + /// shortest path tree used in \ref predNode().
3.502 + /// \pre \ref run() must be called before using this function.
3.503 + /// \todo predEdge could be a better name.
3.504 + Edge pred(Node root, Node node) const {
3.505 + return (*_pred)(root, node);
3.506 + }
3.507 +
3.508 + /// \brief Returns the 'previous node' of the shortest path tree.
3.509 + ///
3.510 + /// For a node \c node it returns the 'previous node' of the shortest path
3.511 + /// tree to direction of the node \c root, i.e. it returns the last but
3.512 + /// one node from a shortest path from the \c root to \c node. It is
3.513 + /// INVALID if \c node is unreachable from the root or if \c node=root.
3.514 + /// The shortest path tree used here is equal to the
3.515 + /// shortest path tree used in \ref pred().
3.516 + /// \pre \ref run() must be called before using this function.
3.517 + Node predNode(Node root, Node node) const {
3.518 + return (*_pred)(root, node) == INVALID ?
3.519 + INVALID : graph->source((*_pred)(root, node));
3.520 + }
3.521 +
3.522 + /// \brief Returns a reference to the matrix node map of distances.
3.523 + ///
3.524 + /// Returns a reference to the matrix node map of distances.
3.525 + ///
3.526 + /// \pre \ref run() must be called before using this function.
3.527 + const DistMap &distMap() const { return *_dist;}
3.528 +
3.529 + /// \brief Returns a reference to the shortest path tree map.
3.530 + ///
3.531 + /// Returns a reference to the matrix node map of the edges of the
3.532 + /// shortest path tree.
3.533 + /// \pre \ref run() must be called before using this function.
3.534 + const PredMap &predMap() const { return *_pred;}
3.535 +
3.536 + /// \brief Checks if a node is reachable from the root.
3.537 + ///
3.538 + /// Returns \c true if \c v is reachable from the root.
3.539 + /// \pre \ref run() must be called before using this function.
3.540 + ///
3.541 + bool connected(Node source, Node target) {
3.542 + return (*_dist)(source, target) != OperationTraits::infinity();
3.543 + }
3.544 +
3.545 + ///@}
3.546 + };
3.547 +
3.548 +} //END OF NAMESPACE LEMON
3.549 +
3.550 +#endif