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