1.1 --- a/lemon/min_mean_cycle.h Fri Aug 07 14:52:40 2009 +0200
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,568 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - *
1.6 - * This file is a part of LEMON, a generic C++ optimization library
1.7 - *
1.8 - * Copyright (C) 2003-2008
1.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 - *
1.12 - * Permission to use, modify and distribute this software is granted
1.13 - * provided that this copyright notice appears in all copies. For
1.14 - * precise terms see the accompanying LICENSE file.
1.15 - *
1.16 - * This software is provided "AS IS" with no warranty of any kind,
1.17 - * express or implied, and with no claim as to its suitability for any
1.18 - * purpose.
1.19 - *
1.20 - */
1.21 -
1.22 -#ifndef LEMON_MIN_MEAN_CYCLE_H
1.23 -#define LEMON_MIN_MEAN_CYCLE_H
1.24 -
1.25 -/// \ingroup shortest_path
1.26 -///
1.27 -/// \file
1.28 -/// \brief Howard's algorithm for finding a minimum mean cycle.
1.29 -
1.30 -#include <vector>
1.31 -#include <limits>
1.32 -#include <lemon/core.h>
1.33 -#include <lemon/path.h>
1.34 -#include <lemon/tolerance.h>
1.35 -#include <lemon/connectivity.h>
1.36 -
1.37 -namespace lemon {
1.38 -
1.39 - /// \brief Default traits class of MinMeanCycle class.
1.40 - ///
1.41 - /// Default traits class of MinMeanCycle class.
1.42 - /// \tparam GR The type of the digraph.
1.43 - /// \tparam LEN The type of the length map.
1.44 - /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.45 -#ifdef DOXYGEN
1.46 - template <typename GR, typename LEN>
1.47 -#else
1.48 - template <typename GR, typename LEN,
1.49 - bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
1.50 -#endif
1.51 - struct MinMeanCycleDefaultTraits
1.52 - {
1.53 - /// The type of the digraph
1.54 - typedef GR Digraph;
1.55 - /// The type of the length map
1.56 - typedef LEN LengthMap;
1.57 - /// The type of the arc lengths
1.58 - typedef typename LengthMap::Value Value;
1.59 -
1.60 - /// \brief The large value type used for internal computations
1.61 - ///
1.62 - /// The large value type used for internal computations.
1.63 - /// It is \c long \c long if the \c Value type is integer,
1.64 - /// otherwise it is \c double.
1.65 - /// \c Value must be convertible to \c LargeValue.
1.66 - typedef double LargeValue;
1.67 -
1.68 - /// The tolerance type used for internal computations
1.69 - typedef lemon::Tolerance<LargeValue> Tolerance;
1.70 -
1.71 - /// \brief The path type of the found cycles
1.72 - ///
1.73 - /// The path type of the found cycles.
1.74 - /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.75 - /// and it must have an \c addBack() function.
1.76 - typedef lemon::Path<Digraph> Path;
1.77 - };
1.78 -
1.79 - // Default traits class for integer value types
1.80 - template <typename GR, typename LEN>
1.81 - struct MinMeanCycleDefaultTraits<GR, LEN, true>
1.82 - {
1.83 - typedef GR Digraph;
1.84 - typedef LEN LengthMap;
1.85 - typedef typename LengthMap::Value Value;
1.86 -#ifdef LEMON_HAVE_LONG_LONG
1.87 - typedef long long LargeValue;
1.88 -#else
1.89 - typedef long LargeValue;
1.90 -#endif
1.91 - typedef lemon::Tolerance<LargeValue> Tolerance;
1.92 - typedef lemon::Path<Digraph> Path;
1.93 - };
1.94 -
1.95 -
1.96 - /// \addtogroup shortest_path
1.97 - /// @{
1.98 -
1.99 - /// \brief Implementation of Howard's algorithm for finding a minimum
1.100 - /// mean cycle.
1.101 - ///
1.102 - /// \ref MinMeanCycle implements Howard's algorithm for finding a
1.103 - /// directed cycle of minimum mean length (cost) in a digraph.
1.104 - ///
1.105 - /// \tparam GR The type of the digraph the algorithm runs on.
1.106 - /// \tparam LEN The type of the length map. The default
1.107 - /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.108 -#ifdef DOXYGEN
1.109 - template <typename GR, typename LEN, typename TR>
1.110 -#else
1.111 - template < typename GR,
1.112 - typename LEN = typename GR::template ArcMap<int>,
1.113 - typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
1.114 -#endif
1.115 - class MinMeanCycle
1.116 - {
1.117 - public:
1.118 -
1.119 - /// The type of the digraph
1.120 - typedef typename TR::Digraph Digraph;
1.121 - /// The type of the length map
1.122 - typedef typename TR::LengthMap LengthMap;
1.123 - /// The type of the arc lengths
1.124 - typedef typename TR::Value Value;
1.125 -
1.126 - /// \brief The large value type
1.127 - ///
1.128 - /// The large value type used for internal computations.
1.129 - /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
1.130 - /// it is \c long \c long if the \c Value type is integer,
1.131 - /// otherwise it is \c double.
1.132 - typedef typename TR::LargeValue LargeValue;
1.133 -
1.134 - /// The tolerance type
1.135 - typedef typename TR::Tolerance Tolerance;
1.136 -
1.137 - /// \brief The path type of the found cycles
1.138 - ///
1.139 - /// The path type of the found cycles.
1.140 - /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
1.141 - /// it is \ref lemon::Path "Path<Digraph>".
1.142 - typedef typename TR::Path Path;
1.143 -
1.144 - /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
1.145 - typedef TR Traits;
1.146 -
1.147 - private:
1.148 -
1.149 - TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.150 -
1.151 - // The digraph the algorithm runs on
1.152 - const Digraph &_gr;
1.153 - // The length of the arcs
1.154 - const LengthMap &_length;
1.155 -
1.156 - // Data for the found cycles
1.157 - bool _curr_found, _best_found;
1.158 - LargeValue _curr_length, _best_length;
1.159 - int _curr_size, _best_size;
1.160 - Node _curr_node, _best_node;
1.161 -
1.162 - Path *_cycle_path;
1.163 - bool _local_path;
1.164 -
1.165 - // Internal data used by the algorithm
1.166 - typename Digraph::template NodeMap<Arc> _policy;
1.167 - typename Digraph::template NodeMap<bool> _reached;
1.168 - typename Digraph::template NodeMap<int> _level;
1.169 - typename Digraph::template NodeMap<LargeValue> _dist;
1.170 -
1.171 - // Data for storing the strongly connected components
1.172 - int _comp_num;
1.173 - typename Digraph::template NodeMap<int> _comp;
1.174 - std::vector<std::vector<Node> > _comp_nodes;
1.175 - std::vector<Node>* _nodes;
1.176 - typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
1.177 -
1.178 - // Queue used for BFS search
1.179 - std::vector<Node> _queue;
1.180 - int _qfront, _qback;
1.181 -
1.182 - Tolerance _tolerance;
1.183 -
1.184 - public:
1.185 -
1.186 - /// \name Named Template Parameters
1.187 - /// @{
1.188 -
1.189 - template <typename T>
1.190 - struct SetLargeValueTraits : public Traits {
1.191 - typedef T LargeValue;
1.192 - typedef lemon::Tolerance<T> Tolerance;
1.193 - };
1.194 -
1.195 - /// \brief \ref named-templ-param "Named parameter" for setting
1.196 - /// \c LargeValue type.
1.197 - ///
1.198 - /// \ref named-templ-param "Named parameter" for setting \c LargeValue
1.199 - /// type. It is used for internal computations in the algorithm.
1.200 - template <typename T>
1.201 - struct SetLargeValue
1.202 - : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
1.203 - typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
1.204 - };
1.205 -
1.206 - template <typename T>
1.207 - struct SetPathTraits : public Traits {
1.208 - typedef T Path;
1.209 - };
1.210 -
1.211 - /// \brief \ref named-templ-param "Named parameter" for setting
1.212 - /// \c %Path type.
1.213 - ///
1.214 - /// \ref named-templ-param "Named parameter" for setting the \c %Path
1.215 - /// type of the found cycles.
1.216 - /// It must conform to the \ref lemon::concepts::Path "Path" concept
1.217 - /// and it must have an \c addBack() function.
1.218 - template <typename T>
1.219 - struct SetPath
1.220 - : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
1.221 - typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
1.222 - };
1.223 -
1.224 - /// @}
1.225 -
1.226 - public:
1.227 -
1.228 - /// \brief Constructor.
1.229 - ///
1.230 - /// The constructor of the class.
1.231 - ///
1.232 - /// \param digraph The digraph the algorithm runs on.
1.233 - /// \param length The lengths (costs) of the arcs.
1.234 - MinMeanCycle( const Digraph &digraph,
1.235 - const LengthMap &length ) :
1.236 - _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
1.237 - _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
1.238 - _comp(digraph), _in_arcs(digraph)
1.239 - {}
1.240 -
1.241 - /// Destructor.
1.242 - ~MinMeanCycle() {
1.243 - if (_local_path) delete _cycle_path;
1.244 - }
1.245 -
1.246 - /// \brief Set the path structure for storing the found cycle.
1.247 - ///
1.248 - /// This function sets an external path structure for storing the
1.249 - /// found cycle.
1.250 - ///
1.251 - /// If you don't call this function before calling \ref run() or
1.252 - /// \ref findMinMean(), it will allocate a local \ref Path "path"
1.253 - /// structure. The destuctor deallocates this automatically
1.254 - /// allocated object, of course.
1.255 - ///
1.256 - /// \note The algorithm calls only the \ref lemon::Path::addBack()
1.257 - /// "addBack()" function of the given path structure.
1.258 - ///
1.259 - /// \return <tt>(*this)</tt>
1.260 - MinMeanCycle& cycle(Path &path) {
1.261 - if (_local_path) {
1.262 - delete _cycle_path;
1.263 - _local_path = false;
1.264 - }
1.265 - _cycle_path = &path;
1.266 - return *this;
1.267 - }
1.268 -
1.269 - /// \name Execution control
1.270 - /// The simplest way to execute the algorithm is to call the \ref run()
1.271 - /// function.\n
1.272 - /// If you only need the minimum mean length, you may call
1.273 - /// \ref findMinMean().
1.274 -
1.275 - /// @{
1.276 -
1.277 - /// \brief Run the algorithm.
1.278 - ///
1.279 - /// This function runs the algorithm.
1.280 - /// It can be called more than once (e.g. if the underlying digraph
1.281 - /// and/or the arc lengths have been modified).
1.282 - ///
1.283 - /// \return \c true if a directed cycle exists in the digraph.
1.284 - ///
1.285 - /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
1.286 - /// \code
1.287 - /// return mmc.findMinMean() && mmc.findCycle();
1.288 - /// \endcode
1.289 - bool run() {
1.290 - return findMinMean() && findCycle();
1.291 - }
1.292 -
1.293 - /// \brief Find the minimum cycle mean.
1.294 - ///
1.295 - /// This function finds the minimum mean length of the directed
1.296 - /// cycles in the digraph.
1.297 - ///
1.298 - /// \return \c true if a directed cycle exists in the digraph.
1.299 - bool findMinMean() {
1.300 - // Initialize and find strongly connected components
1.301 - init();
1.302 - findComponents();
1.303 -
1.304 - // Find the minimum cycle mean in the components
1.305 - for (int comp = 0; comp < _comp_num; ++comp) {
1.306 - // Find the minimum mean cycle in the current component
1.307 - if (!buildPolicyGraph(comp)) continue;
1.308 - while (true) {
1.309 - findPolicyCycle();
1.310 - if (!computeNodeDistances()) break;
1.311 - }
1.312 - // Update the best cycle (global minimum mean cycle)
1.313 - if ( !_best_found || (_curr_found &&
1.314 - _curr_length * _best_size < _best_length * _curr_size) ) {
1.315 - _best_found = true;
1.316 - _best_length = _curr_length;
1.317 - _best_size = _curr_size;
1.318 - _best_node = _curr_node;
1.319 - }
1.320 - }
1.321 - return _best_found;
1.322 - }
1.323 -
1.324 - /// \brief Find a minimum mean directed cycle.
1.325 - ///
1.326 - /// This function finds a directed cycle of minimum mean length
1.327 - /// in the digraph using the data computed by findMinMean().
1.328 - ///
1.329 - /// \return \c true if a directed cycle exists in the digraph.
1.330 - ///
1.331 - /// \pre \ref findMinMean() must be called before using this function.
1.332 - bool findCycle() {
1.333 - if (!_best_found) return false;
1.334 - _cycle_path->addBack(_policy[_best_node]);
1.335 - for ( Node v = _best_node;
1.336 - (v = _gr.target(_policy[v])) != _best_node; ) {
1.337 - _cycle_path->addBack(_policy[v]);
1.338 - }
1.339 - return true;
1.340 - }
1.341 -
1.342 - /// @}
1.343 -
1.344 - /// \name Query Functions
1.345 - /// The results of the algorithm can be obtained using these
1.346 - /// functions.\n
1.347 - /// The algorithm should be executed before using them.
1.348 -
1.349 - /// @{
1.350 -
1.351 - /// \brief Return the total length of the found cycle.
1.352 - ///
1.353 - /// This function returns the total length of the found cycle.
1.354 - ///
1.355 - /// \pre \ref run() or \ref findMinMean() must be called before
1.356 - /// using this function.
1.357 - LargeValue cycleLength() const {
1.358 - return _best_length;
1.359 - }
1.360 -
1.361 - /// \brief Return the number of arcs on the found cycle.
1.362 - ///
1.363 - /// This function returns the number of arcs on the found cycle.
1.364 - ///
1.365 - /// \pre \ref run() or \ref findMinMean() must be called before
1.366 - /// using this function.
1.367 - int cycleArcNum() const {
1.368 - return _best_size;
1.369 - }
1.370 -
1.371 - /// \brief Return the mean length of the found cycle.
1.372 - ///
1.373 - /// This function returns the mean length of the found cycle.
1.374 - ///
1.375 - /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
1.376 - /// following code.
1.377 - /// \code
1.378 - /// return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
1.379 - /// \endcode
1.380 - ///
1.381 - /// \pre \ref run() or \ref findMinMean() must be called before
1.382 - /// using this function.
1.383 - double cycleMean() const {
1.384 - return static_cast<double>(_best_length) / _best_size;
1.385 - }
1.386 -
1.387 - /// \brief Return the found cycle.
1.388 - ///
1.389 - /// This function returns a const reference to the path structure
1.390 - /// storing the found cycle.
1.391 - ///
1.392 - /// \pre \ref run() or \ref findCycle() must be called before using
1.393 - /// this function.
1.394 - const Path& cycle() const {
1.395 - return *_cycle_path;
1.396 - }
1.397 -
1.398 - ///@}
1.399 -
1.400 - private:
1.401 -
1.402 - // Initialize
1.403 - void init() {
1.404 - if (!_cycle_path) {
1.405 - _local_path = true;
1.406 - _cycle_path = new Path;
1.407 - }
1.408 - _queue.resize(countNodes(_gr));
1.409 - _best_found = false;
1.410 - _best_length = 0;
1.411 - _best_size = 1;
1.412 - _cycle_path->clear();
1.413 - }
1.414 -
1.415 - // Find strongly connected components and initialize _comp_nodes
1.416 - // and _in_arcs
1.417 - void findComponents() {
1.418 - _comp_num = stronglyConnectedComponents(_gr, _comp);
1.419 - _comp_nodes.resize(_comp_num);
1.420 - if (_comp_num == 1) {
1.421 - _comp_nodes[0].clear();
1.422 - for (NodeIt n(_gr); n != INVALID; ++n) {
1.423 - _comp_nodes[0].push_back(n);
1.424 - _in_arcs[n].clear();
1.425 - for (InArcIt a(_gr, n); a != INVALID; ++a) {
1.426 - _in_arcs[n].push_back(a);
1.427 - }
1.428 - }
1.429 - } else {
1.430 - for (int i = 0; i < _comp_num; ++i)
1.431 - _comp_nodes[i].clear();
1.432 - for (NodeIt n(_gr); n != INVALID; ++n) {
1.433 - int k = _comp[n];
1.434 - _comp_nodes[k].push_back(n);
1.435 - _in_arcs[n].clear();
1.436 - for (InArcIt a(_gr, n); a != INVALID; ++a) {
1.437 - if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
1.438 - }
1.439 - }
1.440 - }
1.441 - }
1.442 -
1.443 - // Build the policy graph in the given strongly connected component
1.444 - // (the out-degree of every node is 1)
1.445 - bool buildPolicyGraph(int comp) {
1.446 - _nodes = &(_comp_nodes[comp]);
1.447 - if (_nodes->size() < 1 ||
1.448 - (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
1.449 - return false;
1.450 - }
1.451 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.452 - _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
1.453 - }
1.454 - Node u, v;
1.455 - Arc e;
1.456 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.457 - v = (*_nodes)[i];
1.458 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
1.459 - e = _in_arcs[v][j];
1.460 - u = _gr.source(e);
1.461 - if (_length[e] < _dist[u]) {
1.462 - _dist[u] = _length[e];
1.463 - _policy[u] = e;
1.464 - }
1.465 - }
1.466 - }
1.467 - return true;
1.468 - }
1.469 -
1.470 - // Find the minimum mean cycle in the policy graph
1.471 - void findPolicyCycle() {
1.472 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.473 - _level[(*_nodes)[i]] = -1;
1.474 - }
1.475 - LargeValue clength;
1.476 - int csize;
1.477 - Node u, v;
1.478 - _curr_found = false;
1.479 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.480 - u = (*_nodes)[i];
1.481 - if (_level[u] >= 0) continue;
1.482 - for (; _level[u] < 0; u = _gr.target(_policy[u])) {
1.483 - _level[u] = i;
1.484 - }
1.485 - if (_level[u] == i) {
1.486 - // A cycle is found
1.487 - clength = _length[_policy[u]];
1.488 - csize = 1;
1.489 - for (v = u; (v = _gr.target(_policy[v])) != u; ) {
1.490 - clength += _length[_policy[v]];
1.491 - ++csize;
1.492 - }
1.493 - if ( !_curr_found ||
1.494 - (clength * _curr_size < _curr_length * csize) ) {
1.495 - _curr_found = true;
1.496 - _curr_length = clength;
1.497 - _curr_size = csize;
1.498 - _curr_node = u;
1.499 - }
1.500 - }
1.501 - }
1.502 - }
1.503 -
1.504 - // Contract the policy graph and compute node distances
1.505 - bool computeNodeDistances() {
1.506 - // Find the component of the main cycle and compute node distances
1.507 - // using reverse BFS
1.508 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.509 - _reached[(*_nodes)[i]] = false;
1.510 - }
1.511 - _qfront = _qback = 0;
1.512 - _queue[0] = _curr_node;
1.513 - _reached[_curr_node] = true;
1.514 - _dist[_curr_node] = 0;
1.515 - Node u, v;
1.516 - Arc e;
1.517 - while (_qfront <= _qback) {
1.518 - v = _queue[_qfront++];
1.519 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
1.520 - e = _in_arcs[v][j];
1.521 - u = _gr.source(e);
1.522 - if (_policy[u] == e && !_reached[u]) {
1.523 - _reached[u] = true;
1.524 - _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
1.525 - _queue[++_qback] = u;
1.526 - }
1.527 - }
1.528 - }
1.529 -
1.530 - // Connect all other nodes to this component and compute node
1.531 - // distances using reverse BFS
1.532 - _qfront = 0;
1.533 - while (_qback < int(_nodes->size())-1) {
1.534 - v = _queue[_qfront++];
1.535 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
1.536 - e = _in_arcs[v][j];
1.537 - u = _gr.source(e);
1.538 - if (!_reached[u]) {
1.539 - _reached[u] = true;
1.540 - _policy[u] = e;
1.541 - _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
1.542 - _queue[++_qback] = u;
1.543 - }
1.544 - }
1.545 - }
1.546 -
1.547 - // Improve node distances
1.548 - bool improved = false;
1.549 - for (int i = 0; i < int(_nodes->size()); ++i) {
1.550 - v = (*_nodes)[i];
1.551 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
1.552 - e = _in_arcs[v][j];
1.553 - u = _gr.source(e);
1.554 - LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
1.555 - if (_tolerance.less(delta, _dist[u])) {
1.556 - _dist[u] = delta;
1.557 - _policy[u] = e;
1.558 - improved = true;
1.559 - }
1.560 - }
1.561 - }
1.562 - return improved;
1.563 - }
1.564 -
1.565 - }; //class MinMeanCycle
1.566 -
1.567 - ///@}
1.568 -
1.569 -} //namespace lemon
1.570 -
1.571 -#endif //LEMON_MIN_MEAN_CYCLE_H