1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/floyd_warshall.h Mon Oct 03 10:20:56 2005 +0000
1.3 @@ -0,0 +1,525 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/floyd_warshall.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_FLOYD_WARSHALL_H
1.21 +#define LEMON_FLOYD_WARSHALL_H
1.22 +
1.23 +///\ingroup flowalgs
1.24 +/// \file
1.25 +/// \brief FloydWarshall 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/graph_utils.h>
1.31 +#include <lemon/invalid.h>
1.32 +#include <lemon/error.h>
1.33 +#include <lemon/maps.h>
1.34 +
1.35 +#include <limits>
1.36 +
1.37 +namespace lemon {
1.38 +
1.39 + /// \brief Default OperationTraits for the FloydWarshall algorithm class.
1.40 + ///
1.41 + /// It defines all computational operations and constants which are
1.42 + /// used in the Floyd-Warshall algorithm. The default implementation
1.43 + /// is based on the numeric_limits class. If the numeric type does not
1.44 + /// have infinity value then the maximum value is used as extremal
1.45 + /// infinity value.
1.46 + template <
1.47 + typename Value,
1.48 + bool has_infinity = std::numeric_limits<Value>::has_infinity>
1.49 + struct FloydWarshallDefaultOperationTraits {
1.50 + /// \brief Gives back the zero value of the type.
1.51 + static Value zero() {
1.52 + return static_cast<Value>(0);
1.53 + }
1.54 + /// \brief Gives back the positive infinity value of the type.
1.55 + static Value infinity() {
1.56 + return std::numeric_limits<Value>::infinity();
1.57 + }
1.58 + /// \brief Gives back the sum of the given two elements.
1.59 + static Value plus(const Value& left, const Value& right) {
1.60 + return left + right;
1.61 + }
1.62 + /// \brief Gives back true only if the first value less than the second.
1.63 + static bool less(const Value& left, const Value& right) {
1.64 + return left < right;
1.65 + }
1.66 + };
1.67 +
1.68 + template <typename Value>
1.69 + struct FloydWarshallDefaultOperationTraits<Value, false> {
1.70 + static Value zero() {
1.71 + return static_cast<Value>(0);
1.72 + }
1.73 + static Value infinity() {
1.74 + return std::numeric_limits<Value>::max();
1.75 + }
1.76 + static Value plus(const Value& left, const Value& right) {
1.77 + if (left == infinity() || right == infinity()) return infinity();
1.78 + return left + right;
1.79 + }
1.80 + static bool less(const Value& left, const Value& right) {
1.81 + return left < right;
1.82 + }
1.83 + };
1.84 +
1.85 + /// \brief Default traits class of FloydWarshall class.
1.86 + ///
1.87 + /// Default traits class of FloydWarshall class.
1.88 + /// \param _Graph Graph type.
1.89 + /// \param _LegthMap Type of length map.
1.90 + template<class _Graph, class _LengthMap>
1.91 + struct FloydWarshallDefaultTraits {
1.92 + /// The graph type the algorithm runs on.
1.93 + typedef _Graph Graph;
1.94 +
1.95 + /// \brief The type of the map that stores the edge lengths.
1.96 + ///
1.97 + /// The type of the map that stores the edge lengths.
1.98 + /// It must meet the \ref concept::ReadMap "ReadMap" concept.
1.99 + typedef _LengthMap LengthMap;
1.100 +
1.101 + // The type of the length of the edges.
1.102 + typedef typename _LengthMap::Value Value;
1.103 +
1.104 + /// \brief Operation traits for belmann-ford algorithm.
1.105 + ///
1.106 + /// It defines the infinity type on the given Value type
1.107 + /// and the used operation.
1.108 + /// \see FloydWarshallDefaultOperationTraits
1.109 + typedef FloydWarshallDefaultOperationTraits<Value> OperationTraits;
1.110 +
1.111 + /// \brief The type of the map that stores the last edges of the
1.112 + /// shortest paths.
1.113 + ///
1.114 + /// The type of the map that stores the last
1.115 + /// edges of the shortest paths.
1.116 + /// It must be a matrix map with \c Graph::Edge value type.
1.117 + ///
1.118 + typedef NodeMatrixMap<Graph, typename Graph::Edge> PredMap;
1.119 +
1.120 + /// \brief Instantiates a PredMap.
1.121 + ///
1.122 + /// This function instantiates a \ref PredMap.
1.123 + /// \param G is the graph, to which we would like to define the PredMap.
1.124 + /// \todo The graph alone may be insufficient for the initialization
1.125 + static PredMap *createPredMap(const _Graph& graph) {
1.126 + return new PredMap(graph);
1.127 + }
1.128 +
1.129 + /// \brief The type of the map that stores the dists of the nodes.
1.130 + ///
1.131 + /// The type of the map that stores the dists of the nodes.
1.132 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.133 + ///
1.134 + typedef NodeMatrixMap<Graph, Value> 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 FloydWarshall algorithm class.
1.148 + ///
1.149 + /// \ingroup flowalgs
1.150 + /// This class provides an efficient implementation of \c FloydWarshall
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 + /// FloydWarshall, it is only passed to \ref FloydWarshallDefaultTraits.
1.161 + /// \param _LengthMap This read-only EdgeMap determines the lengths of the
1.162 + /// edges. It is read once for each edge, so the map may involve in
1.163 + /// relatively time consuming process to compute the edge length if
1.164 + /// it is necessary. The default map type is \ref
1.165 + /// concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
1.166 + /// of _LengthMap is not used directly by FloydWarshall, it is only passed
1.167 + /// to \ref FloydWarshallDefaultTraits. \param _Traits Traits class to set
1.168 + /// various data types used by the algorithm. The default traits
1.169 + /// class is \ref FloydWarshallDefaultTraits
1.170 + /// "FloydWarshallDefaultTraits<_Graph,_LengthMap>". See \ref
1.171 + /// FloydWarshallDefaultTraits for the documentation of a FloydWarshall
1.172 + /// traits class.
1.173 + ///
1.174 + /// \author Balazs Dezso
1.175 +
1.176 +
1.177 + template <typename _Graph=ListGraph,
1.178 + typename _LengthMap=typename _Graph::template EdgeMap<int>,
1.179 + typename _Traits=FloydWarshallDefaultTraits<_Graph,_LengthMap> >
1.180 + class FloydWarshall {
1.181 + public:
1.182 +
1.183 + /// \brief \ref Exception for uninitialized parameters.
1.184 + ///
1.185 + /// This error represents problems in the initialization
1.186 + /// of the parameters of the algorithms.
1.187 +
1.188 + class UninitializedParameter : public lemon::UninitializedParameter {
1.189 + public:
1.190 + virtual const char* exceptionName() const {
1.191 + return "lemon::FloydWarshall::UninitializedParameter";
1.192 + }
1.193 + };
1.194 +
1.195 + typedef _Traits Traits;
1.196 + ///The type of the underlying graph.
1.197 + typedef typename _Traits::Graph Graph;
1.198 +
1.199 + typedef typename Graph::Node Node;
1.200 + typedef typename Graph::NodeIt NodeIt;
1.201 + typedef typename Graph::Edge Edge;
1.202 + typedef typename Graph::EdgeIt EdgeIt;
1.203 +
1.204 + /// \brief The type of the length of the edges.
1.205 + typedef typename _Traits::LengthMap::Value Value;
1.206 + /// \brief The type of the map that stores the edge lengths.
1.207 + typedef typename _Traits::LengthMap LengthMap;
1.208 + /// \brief The type of the map that stores the last
1.209 + /// edges of the shortest paths. The type of the PredMap
1.210 + /// is a matrix map for Edges
1.211 + typedef typename _Traits::PredMap PredMap;
1.212 + /// \brief The type of the map that stores the dists of the nodes.
1.213 + /// The type of the DistMap is a matrix map for Values
1.214 + typedef typename _Traits::DistMap DistMap;
1.215 + /// \brief The operation traits.
1.216 + typedef typename _Traits::OperationTraits OperationTraits;
1.217 + private:
1.218 + /// Pointer to the underlying graph.
1.219 + const Graph *graph;
1.220 + /// Pointer to the length map
1.221 + const LengthMap *length;
1.222 + ///Pointer to the map of predecessors edges.
1.223 + PredMap *_pred;
1.224 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.225 + bool local_pred;
1.226 + ///Pointer to the map of distances.
1.227 + DistMap *_dist;
1.228 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.229 + bool local_dist;
1.230 +
1.231 + /// Creates the maps if necessary.
1.232 + void create_maps() {
1.233 + if(!_pred) {
1.234 + local_pred = true;
1.235 + _pred = Traits::createPredMap(*graph);
1.236 + }
1.237 + if(!_dist) {
1.238 + local_dist = true;
1.239 + _dist = Traits::createDistMap(*graph);
1.240 + }
1.241 + }
1.242 +
1.243 + public :
1.244 +
1.245 + /// \name Named template parameters
1.246 +
1.247 + ///@{
1.248 +
1.249 + template <class T>
1.250 + struct DefPredMapTraits : public Traits {
1.251 + typedef T PredMap;
1.252 + static PredMap *createPredMap(const Graph& graph) {
1.253 + throw UninitializedParameter();
1.254 + }
1.255 + };
1.256 +
1.257 + /// \brief \ref named-templ-param "Named parameter" for setting PredMap
1.258 + /// type
1.259 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.260 + ///
1.261 + template <class T>
1.262 + class DefPredMap
1.263 + : public FloydWarshall< Graph, LengthMap, DefPredMapTraits<T> > {};
1.264 +
1.265 + template <class T>
1.266 + struct DefDistMapTraits : public Traits {
1.267 + typedef T DistMap;
1.268 + static DistMap *createDistMap(const Graph& graph) {
1.269 + throw UninitializedParameter();
1.270 + }
1.271 + };
1.272 + /// \brief \ref named-templ-param "Named parameter" for setting DistMap
1.273 + /// type
1.274 + ///
1.275 + /// \ref named-templ-param "Named parameter" for setting DistMap type
1.276 + ///
1.277 + template <class T>
1.278 + class DefDistMap
1.279 + : public FloydWarshall< Graph, LengthMap, DefDistMapTraits<T> > {};
1.280 +
1.281 + template <class T>
1.282 + struct DefOperationTraitsTraits : public Traits {
1.283 + typedef T OperationTraits;
1.284 + };
1.285 +
1.286 + /// \brief \ref named-templ-param "Named parameter" for setting
1.287 + /// OperationTraits type
1.288 + ///
1.289 + /// \ref named-templ-param "Named parameter" for setting PredMap type
1.290 + template <class T>
1.291 + class DefOperationTraits
1.292 + : public FloydWarshall< Graph, LengthMap, DefOperationTraitsTraits<T> > {
1.293 + };
1.294 +
1.295 + ///@}
1.296 +
1.297 + public:
1.298 +
1.299 + /// \brief Constructor.
1.300 + ///
1.301 + /// \param _graph the graph the algorithm will run on.
1.302 + /// \param _length the length map used by the algorithm.
1.303 + FloydWarshall(const Graph& _graph, const LengthMap& _length) :
1.304 + graph(&_graph), length(&_length),
1.305 + _pred(0), local_pred(false),
1.306 + _dist(0), local_dist(false) {}
1.307 +
1.308 + ///Destructor.
1.309 + ~FloydWarshall() {
1.310 + if(local_pred) delete _pred;
1.311 + if(local_dist) delete _dist;
1.312 + }
1.313 +
1.314 + /// \brief Sets the length map.
1.315 + ///
1.316 + /// Sets the length map.
1.317 + /// \return \c (*this)
1.318 + FloydWarshall &lengthMap(const LengthMap &m) {
1.319 + length = &m;
1.320 + return *this;
1.321 + }
1.322 +
1.323 + /// \brief Sets the map storing the predecessor edges.
1.324 + ///
1.325 + /// Sets the map storing the predecessor edges.
1.326 + /// If you don't use this function before calling \ref run(),
1.327 + /// it will allocate one. The destuctor deallocates this
1.328 + /// automatically allocated map, of course.
1.329 + /// \return \c (*this)
1.330 + FloydWarshall &predMap(PredMap &m) {
1.331 + if(local_pred) {
1.332 + delete _pred;
1.333 + local_pred=false;
1.334 + }
1.335 + _pred = &m;
1.336 + return *this;
1.337 + }
1.338 +
1.339 + /// \brief Sets the map storing the distances calculated by the algorithm.
1.340 + ///
1.341 + /// Sets the map storing the distances calculated by the algorithm.
1.342 + /// If you don't use this function before calling \ref run(),
1.343 + /// it will allocate one. The destuctor deallocates this
1.344 + /// automatically allocated map, of course.
1.345 + /// \return \c (*this)
1.346 + FloydWarshall &distMap(DistMap &m) {
1.347 + if(local_dist) {
1.348 + delete _dist;
1.349 + local_dist=false;
1.350 + }
1.351 + _dist = &m;
1.352 + return *this;
1.353 + }
1.354 +
1.355 + ///\name Execution control
1.356 + /// The simplest way to execute the algorithm is to use
1.357 + /// one of the member functions called \c run(...).
1.358 + /// \n
1.359 + /// If you need more control on the execution,
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 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
1.372 + _pred->set(it, jt, INVALID);
1.373 + _dist->set(it, jt, it == jt ?
1.374 + OperationTraits::zero() : OperationTraits::infinity());
1.375 + }
1.376 + }
1.377 + for (EdgeIt it(*graph); it != INVALID; ++it) {
1.378 + Node source = graph->source(it);
1.379 + Node target = graph->target(it);
1.380 + if (OperationTraits::less((*length)[it], (*_dist)(source, target))) {
1.381 + _dist->set(source, target, (*length)[it]);
1.382 + _pred->set(source, target, it);
1.383 + }
1.384 + }
1.385 + }
1.386 +
1.387 + /// \brief Executes the algorithm.
1.388 + ///
1.389 + /// This method runs the %FloydWarshall algorithm in order to compute
1.390 + /// the shortest path to each node pairs. The algorithm
1.391 + /// computes
1.392 + /// - The shortest path tree for each node.
1.393 + /// - The distance between each node pairs.
1.394 + void start() {
1.395 + for (NodeIt kt(*graph); kt != INVALID; ++kt) {
1.396 + for (NodeIt it(*graph); it != INVALID; ++it) {
1.397 + for (NodeIt jt(*graph); jt != INVALID; ++jt) {
1.398 + Value relaxed = OperationTraits::plus((*_dist)(it, kt),
1.399 + (*_dist)(kt, jt));
1.400 + if (OperationTraits::less(relaxed, (*_dist)(it, jt))) {
1.401 + _dist->set(it, jt, relaxed);
1.402 + _pred->set(it, jt, (*_pred)(kt, jt));
1.403 + }
1.404 + }
1.405 + }
1.406 + }
1.407 + }
1.408 +
1.409 + /// \brief Runs %FloydWarshall algorithm.
1.410 + ///
1.411 + /// This method runs the %FloydWarshall algorithm from a each node
1.412 + /// in order to compute the shortest path to each node pairs.
1.413 + /// The algorithm computes
1.414 + /// - The shortest path tree for each node.
1.415 + /// - The distance between each node pairs.
1.416 + ///
1.417 + /// \note d.run(s) is just a shortcut of the following code.
1.418 + /// \code
1.419 + /// d.init();
1.420 + /// d.start();
1.421 + /// \endcode
1.422 + void run() {
1.423 + init();
1.424 + start();
1.425 + }
1.426 +
1.427 + ///@}
1.428 +
1.429 + /// \name Query Functions
1.430 + /// The result of the %FloydWarshall algorithm can be obtained using these
1.431 + /// functions.\n
1.432 + /// Before the use of these functions,
1.433 + /// either run() or start() must be called.
1.434 +
1.435 + ///@{
1.436 +
1.437 + /// \brief Copies the shortest path to \c t into \c p
1.438 + ///
1.439 + /// This function copies the shortest path to \c t into \c p.
1.440 + /// If it \c t is a source itself or unreachable, then it does not
1.441 + /// alter \c p.
1.442 + /// \todo Is it the right way to handle unreachable nodes?
1.443 + /// \return Returns \c true if a path to \c t was actually copied to \c p,
1.444 + /// \c false otherwise.
1.445 + /// \sa DirPath
1.446 + template <typename Path>
1.447 + bool getPath(Path &p, Node source, Node target) {
1.448 + if (connected(source, target)) {
1.449 + p.clear();
1.450 + typename Path::Builder b(target);
1.451 + for(b.setStartNode(target); pred(source, target) != INVALID;
1.452 + target = predNode(target)) {
1.453 + b.pushFront(pred(source, target));
1.454 + }
1.455 + b.commit();
1.456 + return true;
1.457 + }
1.458 + return false;
1.459 + }
1.460 +
1.461 + /// \brief The distance between two nodes.
1.462 + ///
1.463 + /// Returns the distance between two nodes.
1.464 + /// \pre \ref run() must be called before using this function.
1.465 + /// \warning If node \c v in unreachable from the root the return value
1.466 + /// of this funcion is undefined.
1.467 + Value dist(Node source, Node target) const {
1.468 + return (*_dist)(source, target);
1.469 + }
1.470 +
1.471 + /// \brief Returns the 'previous edge' of the shortest path tree.
1.472 + ///
1.473 + /// For the node \c node it returns the 'previous edge' of the shortest
1.474 + /// path tree to direction of the node \c root
1.475 + /// i.e. it returns the last edge of a shortest path from the node \c root
1.476 + /// to \c node. It is \ref INVALID if \c node is unreachable from the root
1.477 + /// or if \c node=root. The shortest path tree used here is equal to the
1.478 + /// shortest path tree used in \ref predNode().
1.479 + /// \pre \ref run() must be called before using this function.
1.480 + /// \todo predEdge could be a better name.
1.481 + Edge pred(Node root, Node node) const {
1.482 + return (*_pred)(root, node);
1.483 + }
1.484 +
1.485 + /// \brief Returns the 'previous node' of the shortest path tree.
1.486 + ///
1.487 + /// For a node \c node it returns the 'previous node' of the shortest path
1.488 + /// tree to direction of the node \c root, i.e. it returns the last but
1.489 + /// one node from a shortest path from the \c root to \c node. It is
1.490 + /// INVALID if \c node is unreachable from the root or if \c node=root.
1.491 + /// The shortest path tree used here is equal to the
1.492 + /// shortest path tree used in \ref pred().
1.493 + /// \pre \ref run() must be called before using this function.
1.494 + Node predNode(Node root, Node node) const {
1.495 + return (*_pred)(root, node) == INVALID ?
1.496 + INVALID : graph->source((*_pred)(root, node));
1.497 + }
1.498 +
1.499 + /// \brief Returns a reference to the matrix node map of distances.
1.500 + ///
1.501 + /// Returns a reference to the matrix node map of distances.
1.502 + ///
1.503 + /// \pre \ref run() must be called before using this function.
1.504 + const DistMap &distMap() const { return *_dist;}
1.505 +
1.506 + /// \brief Returns a reference to the shortest path tree map.
1.507 + ///
1.508 + /// Returns a reference to the matrix node map of the edges of the
1.509 + /// shortest path tree.
1.510 + /// \pre \ref run() must be called before using this function.
1.511 + const PredMap &predMap() const { return *_pred;}
1.512 +
1.513 + /// \brief Checks if a node is reachable from the root.
1.514 + ///
1.515 + /// Returns \c true if \c v is reachable from the root.
1.516 + /// \pre \ref run() must be called before using this function.
1.517 + ///
1.518 + bool connected(Node source, Node target) {
1.519 + return (*_dist)(source, target) != OperationTraits::infinity();
1.520 + }
1.521 +
1.522 + ///@}
1.523 + };
1.524 +
1.525 +} //END OF NAMESPACE LEMON
1.526 +
1.527 +#endif
1.528 +