1.1 --- a/lemon/Makefile.am Fri Aug 07 14:52:40 2009 +0200
1.2 +++ b/lemon/Makefile.am Mon Aug 10 14:50:57 2009 +0200
1.3 @@ -83,6 +83,7 @@
1.4 lemon/gomory_hu.h \
1.5 lemon/graph_to_eps.h \
1.6 lemon/grid_graph.h \
1.7 + lemon/howard.h \
1.8 lemon/hypercube_graph.h \
1.9 lemon/kruskal.h \
1.10 lemon/hao_orlin.h \
1.11 @@ -97,7 +98,6 @@
1.12 lemon/matching.h \
1.13 lemon/math.h \
1.14 lemon/min_cost_arborescence.h \
1.15 - lemon/min_mean_cycle.h \
1.16 lemon/nauty_reader.h \
1.17 lemon/network_simplex.h \
1.18 lemon/path.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/lemon/howard.h Mon Aug 10 14:50:57 2009 +0200
2.3 @@ -0,0 +1,568 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +#ifndef LEMON_HOWARD_H
2.23 +#define LEMON_HOWARD_H
2.24 +
2.25 +/// \ingroup shortest_path
2.26 +///
2.27 +/// \file
2.28 +/// \brief Howard's algorithm for finding a minimum mean cycle.
2.29 +
2.30 +#include <vector>
2.31 +#include <limits>
2.32 +#include <lemon/core.h>
2.33 +#include <lemon/path.h>
2.34 +#include <lemon/tolerance.h>
2.35 +#include <lemon/connectivity.h>
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + /// \brief Default traits class of Howard class.
2.40 + ///
2.41 + /// Default traits class of Howard class.
2.42 + /// \tparam GR The type of the digraph.
2.43 + /// \tparam LEN The type of the length map.
2.44 + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
2.45 +#ifdef DOXYGEN
2.46 + template <typename GR, typename LEN>
2.47 +#else
2.48 + template <typename GR, typename LEN,
2.49 + bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
2.50 +#endif
2.51 + struct HowardDefaultTraits
2.52 + {
2.53 + /// The type of the digraph
2.54 + typedef GR Digraph;
2.55 + /// The type of the length map
2.56 + typedef LEN LengthMap;
2.57 + /// The type of the arc lengths
2.58 + typedef typename LengthMap::Value Value;
2.59 +
2.60 + /// \brief The large value type used for internal computations
2.61 + ///
2.62 + /// The large value type used for internal computations.
2.63 + /// It is \c long \c long if the \c Value type is integer,
2.64 + /// otherwise it is \c double.
2.65 + /// \c Value must be convertible to \c LargeValue.
2.66 + typedef double LargeValue;
2.67 +
2.68 + /// The tolerance type used for internal computations
2.69 + typedef lemon::Tolerance<LargeValue> Tolerance;
2.70 +
2.71 + /// \brief The path type of the found cycles
2.72 + ///
2.73 + /// The path type of the found cycles.
2.74 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
2.75 + /// and it must have an \c addBack() function.
2.76 + typedef lemon::Path<Digraph> Path;
2.77 + };
2.78 +
2.79 + // Default traits class for integer value types
2.80 + template <typename GR, typename LEN>
2.81 + struct HowardDefaultTraits<GR, LEN, true>
2.82 + {
2.83 + typedef GR Digraph;
2.84 + typedef LEN LengthMap;
2.85 + typedef typename LengthMap::Value Value;
2.86 +#ifdef LEMON_HAVE_LONG_LONG
2.87 + typedef long long LargeValue;
2.88 +#else
2.89 + typedef long LargeValue;
2.90 +#endif
2.91 + typedef lemon::Tolerance<LargeValue> Tolerance;
2.92 + typedef lemon::Path<Digraph> Path;
2.93 + };
2.94 +
2.95 +
2.96 + /// \addtogroup shortest_path
2.97 + /// @{
2.98 +
2.99 + /// \brief Implementation of Howard's algorithm for finding a minimum
2.100 + /// mean cycle.
2.101 + ///
2.102 + /// This class implements Howard's policy iteration algorithm for finding
2.103 + /// a directed cycle of minimum mean length (cost) in a digraph.
2.104 + ///
2.105 + /// \tparam GR The type of the digraph the algorithm runs on.
2.106 + /// \tparam LEN The type of the length map. The default
2.107 + /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
2.108 +#ifdef DOXYGEN
2.109 + template <typename GR, typename LEN, typename TR>
2.110 +#else
2.111 + template < typename GR,
2.112 + typename LEN = typename GR::template ArcMap<int>,
2.113 + typename TR = HowardDefaultTraits<GR, LEN> >
2.114 +#endif
2.115 + class Howard
2.116 + {
2.117 + public:
2.118 +
2.119 + /// The type of the digraph
2.120 + typedef typename TR::Digraph Digraph;
2.121 + /// The type of the length map
2.122 + typedef typename TR::LengthMap LengthMap;
2.123 + /// The type of the arc lengths
2.124 + typedef typename TR::Value Value;
2.125 +
2.126 + /// \brief The large value type
2.127 + ///
2.128 + /// The large value type used for internal computations.
2.129 + /// Using the \ref HowardDefaultTraits "default traits class",
2.130 + /// it is \c long \c long if the \c Value type is integer,
2.131 + /// otherwise it is \c double.
2.132 + typedef typename TR::LargeValue LargeValue;
2.133 +
2.134 + /// The tolerance type
2.135 + typedef typename TR::Tolerance Tolerance;
2.136 +
2.137 + /// \brief The path type of the found cycles
2.138 + ///
2.139 + /// The path type of the found cycles.
2.140 + /// Using the \ref HowardDefaultTraits "default traits class",
2.141 + /// it is \ref lemon::Path "Path<Digraph>".
2.142 + typedef typename TR::Path Path;
2.143 +
2.144 + /// The \ref HowardDefaultTraits "traits class" of the algorithm
2.145 + typedef TR Traits;
2.146 +
2.147 + private:
2.148 +
2.149 + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
2.150 +
2.151 + // The digraph the algorithm runs on
2.152 + const Digraph &_gr;
2.153 + // The length of the arcs
2.154 + const LengthMap &_length;
2.155 +
2.156 + // Data for the found cycles
2.157 + bool _curr_found, _best_found;
2.158 + LargeValue _curr_length, _best_length;
2.159 + int _curr_size, _best_size;
2.160 + Node _curr_node, _best_node;
2.161 +
2.162 + Path *_cycle_path;
2.163 + bool _local_path;
2.164 +
2.165 + // Internal data used by the algorithm
2.166 + typename Digraph::template NodeMap<Arc> _policy;
2.167 + typename Digraph::template NodeMap<bool> _reached;
2.168 + typename Digraph::template NodeMap<int> _level;
2.169 + typename Digraph::template NodeMap<LargeValue> _dist;
2.170 +
2.171 + // Data for storing the strongly connected components
2.172 + int _comp_num;
2.173 + typename Digraph::template NodeMap<int> _comp;
2.174 + std::vector<std::vector<Node> > _comp_nodes;
2.175 + std::vector<Node>* _nodes;
2.176 + typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
2.177 +
2.178 + // Queue used for BFS search
2.179 + std::vector<Node> _queue;
2.180 + int _qfront, _qback;
2.181 +
2.182 + Tolerance _tolerance;
2.183 +
2.184 + public:
2.185 +
2.186 + /// \name Named Template Parameters
2.187 + /// @{
2.188 +
2.189 + template <typename T>
2.190 + struct SetLargeValueTraits : public Traits {
2.191 + typedef T LargeValue;
2.192 + typedef lemon::Tolerance<T> Tolerance;
2.193 + };
2.194 +
2.195 + /// \brief \ref named-templ-param "Named parameter" for setting
2.196 + /// \c LargeValue type.
2.197 + ///
2.198 + /// \ref named-templ-param "Named parameter" for setting \c LargeValue
2.199 + /// type. It is used for internal computations in the algorithm.
2.200 + template <typename T>
2.201 + struct SetLargeValue
2.202 + : public Howard<GR, LEN, SetLargeValueTraits<T> > {
2.203 + typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
2.204 + };
2.205 +
2.206 + template <typename T>
2.207 + struct SetPathTraits : public Traits {
2.208 + typedef T Path;
2.209 + };
2.210 +
2.211 + /// \brief \ref named-templ-param "Named parameter" for setting
2.212 + /// \c %Path type.
2.213 + ///
2.214 + /// \ref named-templ-param "Named parameter" for setting the \c %Path
2.215 + /// type of the found cycles.
2.216 + /// It must conform to the \ref lemon::concepts::Path "Path" concept
2.217 + /// and it must have an \c addBack() function.
2.218 + template <typename T>
2.219 + struct SetPath
2.220 + : public Howard<GR, LEN, SetPathTraits<T> > {
2.221 + typedef Howard<GR, LEN, SetPathTraits<T> > Create;
2.222 + };
2.223 +
2.224 + /// @}
2.225 +
2.226 + public:
2.227 +
2.228 + /// \brief Constructor.
2.229 + ///
2.230 + /// The constructor of the class.
2.231 + ///
2.232 + /// \param digraph The digraph the algorithm runs on.
2.233 + /// \param length The lengths (costs) of the arcs.
2.234 + Howard( const Digraph &digraph,
2.235 + const LengthMap &length ) :
2.236 + _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
2.237 + _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
2.238 + _comp(digraph), _in_arcs(digraph)
2.239 + {}
2.240 +
2.241 + /// Destructor.
2.242 + ~Howard() {
2.243 + if (_local_path) delete _cycle_path;
2.244 + }
2.245 +
2.246 + /// \brief Set the path structure for storing the found cycle.
2.247 + ///
2.248 + /// This function sets an external path structure for storing the
2.249 + /// found cycle.
2.250 + ///
2.251 + /// If you don't call this function before calling \ref run() or
2.252 + /// \ref findMinMean(), it will allocate a local \ref Path "path"
2.253 + /// structure. The destuctor deallocates this automatically
2.254 + /// allocated object, of course.
2.255 + ///
2.256 + /// \note The algorithm calls only the \ref lemon::Path::addBack()
2.257 + /// "addBack()" function of the given path structure.
2.258 + ///
2.259 + /// \return <tt>(*this)</tt>
2.260 + Howard& cycle(Path &path) {
2.261 + if (_local_path) {
2.262 + delete _cycle_path;
2.263 + _local_path = false;
2.264 + }
2.265 + _cycle_path = &path;
2.266 + return *this;
2.267 + }
2.268 +
2.269 + /// \name Execution control
2.270 + /// The simplest way to execute the algorithm is to call the \ref run()
2.271 + /// function.\n
2.272 + /// If you only need the minimum mean length, you may call
2.273 + /// \ref findMinMean().
2.274 +
2.275 + /// @{
2.276 +
2.277 + /// \brief Run the algorithm.
2.278 + ///
2.279 + /// This function runs the algorithm.
2.280 + /// It can be called more than once (e.g. if the underlying digraph
2.281 + /// and/or the arc lengths have been modified).
2.282 + ///
2.283 + /// \return \c true if a directed cycle exists in the digraph.
2.284 + ///
2.285 + /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
2.286 + /// \code
2.287 + /// return mmc.findMinMean() && mmc.findCycle();
2.288 + /// \endcode
2.289 + bool run() {
2.290 + return findMinMean() && findCycle();
2.291 + }
2.292 +
2.293 + /// \brief Find the minimum cycle mean.
2.294 + ///
2.295 + /// This function finds the minimum mean length of the directed
2.296 + /// cycles in the digraph.
2.297 + ///
2.298 + /// \return \c true if a directed cycle exists in the digraph.
2.299 + bool findMinMean() {
2.300 + // Initialize and find strongly connected components
2.301 + init();
2.302 + findComponents();
2.303 +
2.304 + // Find the minimum cycle mean in the components
2.305 + for (int comp = 0; comp < _comp_num; ++comp) {
2.306 + // Find the minimum mean cycle in the current component
2.307 + if (!buildPolicyGraph(comp)) continue;
2.308 + while (true) {
2.309 + findPolicyCycle();
2.310 + if (!computeNodeDistances()) break;
2.311 + }
2.312 + // Update the best cycle (global minimum mean cycle)
2.313 + if ( !_best_found || (_curr_found &&
2.314 + _curr_length * _best_size < _best_length * _curr_size) ) {
2.315 + _best_found = true;
2.316 + _best_length = _curr_length;
2.317 + _best_size = _curr_size;
2.318 + _best_node = _curr_node;
2.319 + }
2.320 + }
2.321 + return _best_found;
2.322 + }
2.323 +
2.324 + /// \brief Find a minimum mean directed cycle.
2.325 + ///
2.326 + /// This function finds a directed cycle of minimum mean length
2.327 + /// in the digraph using the data computed by findMinMean().
2.328 + ///
2.329 + /// \return \c true if a directed cycle exists in the digraph.
2.330 + ///
2.331 + /// \pre \ref findMinMean() must be called before using this function.
2.332 + bool findCycle() {
2.333 + if (!_best_found) return false;
2.334 + _cycle_path->addBack(_policy[_best_node]);
2.335 + for ( Node v = _best_node;
2.336 + (v = _gr.target(_policy[v])) != _best_node; ) {
2.337 + _cycle_path->addBack(_policy[v]);
2.338 + }
2.339 + return true;
2.340 + }
2.341 +
2.342 + /// @}
2.343 +
2.344 + /// \name Query Functions
2.345 + /// The results of the algorithm can be obtained using these
2.346 + /// functions.\n
2.347 + /// The algorithm should be executed before using them.
2.348 +
2.349 + /// @{
2.350 +
2.351 + /// \brief Return the total length of the found cycle.
2.352 + ///
2.353 + /// This function returns the total length of the found cycle.
2.354 + ///
2.355 + /// \pre \ref run() or \ref findMinMean() must be called before
2.356 + /// using this function.
2.357 + LargeValue cycleLength() const {
2.358 + return _best_length;
2.359 + }
2.360 +
2.361 + /// \brief Return the number of arcs on the found cycle.
2.362 + ///
2.363 + /// This function returns the number of arcs on the found cycle.
2.364 + ///
2.365 + /// \pre \ref run() or \ref findMinMean() must be called before
2.366 + /// using this function.
2.367 + int cycleArcNum() const {
2.368 + return _best_size;
2.369 + }
2.370 +
2.371 + /// \brief Return the mean length of the found cycle.
2.372 + ///
2.373 + /// This function returns the mean length of the found cycle.
2.374 + ///
2.375 + /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
2.376 + /// following code.
2.377 + /// \code
2.378 + /// return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
2.379 + /// \endcode
2.380 + ///
2.381 + /// \pre \ref run() or \ref findMinMean() must be called before
2.382 + /// using this function.
2.383 + double cycleMean() const {
2.384 + return static_cast<double>(_best_length) / _best_size;
2.385 + }
2.386 +
2.387 + /// \brief Return the found cycle.
2.388 + ///
2.389 + /// This function returns a const reference to the path structure
2.390 + /// storing the found cycle.
2.391 + ///
2.392 + /// \pre \ref run() or \ref findCycle() must be called before using
2.393 + /// this function.
2.394 + const Path& cycle() const {
2.395 + return *_cycle_path;
2.396 + }
2.397 +
2.398 + ///@}
2.399 +
2.400 + private:
2.401 +
2.402 + // Initialize
2.403 + void init() {
2.404 + if (!_cycle_path) {
2.405 + _local_path = true;
2.406 + _cycle_path = new Path;
2.407 + }
2.408 + _queue.resize(countNodes(_gr));
2.409 + _best_found = false;
2.410 + _best_length = 0;
2.411 + _best_size = 1;
2.412 + _cycle_path->clear();
2.413 + }
2.414 +
2.415 + // Find strongly connected components and initialize _comp_nodes
2.416 + // and _in_arcs
2.417 + void findComponents() {
2.418 + _comp_num = stronglyConnectedComponents(_gr, _comp);
2.419 + _comp_nodes.resize(_comp_num);
2.420 + if (_comp_num == 1) {
2.421 + _comp_nodes[0].clear();
2.422 + for (NodeIt n(_gr); n != INVALID; ++n) {
2.423 + _comp_nodes[0].push_back(n);
2.424 + _in_arcs[n].clear();
2.425 + for (InArcIt a(_gr, n); a != INVALID; ++a) {
2.426 + _in_arcs[n].push_back(a);
2.427 + }
2.428 + }
2.429 + } else {
2.430 + for (int i = 0; i < _comp_num; ++i)
2.431 + _comp_nodes[i].clear();
2.432 + for (NodeIt n(_gr); n != INVALID; ++n) {
2.433 + int k = _comp[n];
2.434 + _comp_nodes[k].push_back(n);
2.435 + _in_arcs[n].clear();
2.436 + for (InArcIt a(_gr, n); a != INVALID; ++a) {
2.437 + if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
2.438 + }
2.439 + }
2.440 + }
2.441 + }
2.442 +
2.443 + // Build the policy graph in the given strongly connected component
2.444 + // (the out-degree of every node is 1)
2.445 + bool buildPolicyGraph(int comp) {
2.446 + _nodes = &(_comp_nodes[comp]);
2.447 + if (_nodes->size() < 1 ||
2.448 + (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
2.449 + return false;
2.450 + }
2.451 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.452 + _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
2.453 + }
2.454 + Node u, v;
2.455 + Arc e;
2.456 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.457 + v = (*_nodes)[i];
2.458 + for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
2.459 + e = _in_arcs[v][j];
2.460 + u = _gr.source(e);
2.461 + if (_length[e] < _dist[u]) {
2.462 + _dist[u] = _length[e];
2.463 + _policy[u] = e;
2.464 + }
2.465 + }
2.466 + }
2.467 + return true;
2.468 + }
2.469 +
2.470 + // Find the minimum mean cycle in the policy graph
2.471 + void findPolicyCycle() {
2.472 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.473 + _level[(*_nodes)[i]] = -1;
2.474 + }
2.475 + LargeValue clength;
2.476 + int csize;
2.477 + Node u, v;
2.478 + _curr_found = false;
2.479 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.480 + u = (*_nodes)[i];
2.481 + if (_level[u] >= 0) continue;
2.482 + for (; _level[u] < 0; u = _gr.target(_policy[u])) {
2.483 + _level[u] = i;
2.484 + }
2.485 + if (_level[u] == i) {
2.486 + // A cycle is found
2.487 + clength = _length[_policy[u]];
2.488 + csize = 1;
2.489 + for (v = u; (v = _gr.target(_policy[v])) != u; ) {
2.490 + clength += _length[_policy[v]];
2.491 + ++csize;
2.492 + }
2.493 + if ( !_curr_found ||
2.494 + (clength * _curr_size < _curr_length * csize) ) {
2.495 + _curr_found = true;
2.496 + _curr_length = clength;
2.497 + _curr_size = csize;
2.498 + _curr_node = u;
2.499 + }
2.500 + }
2.501 + }
2.502 + }
2.503 +
2.504 + // Contract the policy graph and compute node distances
2.505 + bool computeNodeDistances() {
2.506 + // Find the component of the main cycle and compute node distances
2.507 + // using reverse BFS
2.508 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.509 + _reached[(*_nodes)[i]] = false;
2.510 + }
2.511 + _qfront = _qback = 0;
2.512 + _queue[0] = _curr_node;
2.513 + _reached[_curr_node] = true;
2.514 + _dist[_curr_node] = 0;
2.515 + Node u, v;
2.516 + Arc e;
2.517 + while (_qfront <= _qback) {
2.518 + v = _queue[_qfront++];
2.519 + for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
2.520 + e = _in_arcs[v][j];
2.521 + u = _gr.source(e);
2.522 + if (_policy[u] == e && !_reached[u]) {
2.523 + _reached[u] = true;
2.524 + _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
2.525 + _queue[++_qback] = u;
2.526 + }
2.527 + }
2.528 + }
2.529 +
2.530 + // Connect all other nodes to this component and compute node
2.531 + // distances using reverse BFS
2.532 + _qfront = 0;
2.533 + while (_qback < int(_nodes->size())-1) {
2.534 + v = _queue[_qfront++];
2.535 + for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
2.536 + e = _in_arcs[v][j];
2.537 + u = _gr.source(e);
2.538 + if (!_reached[u]) {
2.539 + _reached[u] = true;
2.540 + _policy[u] = e;
2.541 + _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
2.542 + _queue[++_qback] = u;
2.543 + }
2.544 + }
2.545 + }
2.546 +
2.547 + // Improve node distances
2.548 + bool improved = false;
2.549 + for (int i = 0; i < int(_nodes->size()); ++i) {
2.550 + v = (*_nodes)[i];
2.551 + for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
2.552 + e = _in_arcs[v][j];
2.553 + u = _gr.source(e);
2.554 + LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
2.555 + if (_tolerance.less(delta, _dist[u])) {
2.556 + _dist[u] = delta;
2.557 + _policy[u] = e;
2.558 + improved = true;
2.559 + }
2.560 + }
2.561 + }
2.562 + return improved;
2.563 + }
2.564 +
2.565 + }; //class Howard
2.566 +
2.567 + ///@}
2.568 +
2.569 +} //namespace lemon
2.570 +
2.571 +#endif //LEMON_HOWARD_H
3.1 --- a/lemon/min_mean_cycle.h Fri Aug 07 14:52:40 2009 +0200
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,568 +0,0 @@
3.4 -/* -*- C++ -*-
3.5 - *
3.6 - * This file is a part of LEMON, a generic C++ optimization library
3.7 - *
3.8 - * Copyright (C) 2003-2008
3.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 - *
3.12 - * Permission to use, modify and distribute this software is granted
3.13 - * provided that this copyright notice appears in all copies. For
3.14 - * precise terms see the accompanying LICENSE file.
3.15 - *
3.16 - * This software is provided "AS IS" with no warranty of any kind,
3.17 - * express or implied, and with no claim as to its suitability for any
3.18 - * purpose.
3.19 - *
3.20 - */
3.21 -
3.22 -#ifndef LEMON_MIN_MEAN_CYCLE_H
3.23 -#define LEMON_MIN_MEAN_CYCLE_H
3.24 -
3.25 -/// \ingroup shortest_path
3.26 -///
3.27 -/// \file
3.28 -/// \brief Howard's algorithm for finding a minimum mean cycle.
3.29 -
3.30 -#include <vector>
3.31 -#include <limits>
3.32 -#include <lemon/core.h>
3.33 -#include <lemon/path.h>
3.34 -#include <lemon/tolerance.h>
3.35 -#include <lemon/connectivity.h>
3.36 -
3.37 -namespace lemon {
3.38 -
3.39 - /// \brief Default traits class of MinMeanCycle class.
3.40 - ///
3.41 - /// Default traits class of MinMeanCycle class.
3.42 - /// \tparam GR The type of the digraph.
3.43 - /// \tparam LEN The type of the length map.
3.44 - /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.
3.45 -#ifdef DOXYGEN
3.46 - template <typename GR, typename LEN>
3.47 -#else
3.48 - template <typename GR, typename LEN,
3.49 - bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
3.50 -#endif
3.51 - struct MinMeanCycleDefaultTraits
3.52 - {
3.53 - /// The type of the digraph
3.54 - typedef GR Digraph;
3.55 - /// The type of the length map
3.56 - typedef LEN LengthMap;
3.57 - /// The type of the arc lengths
3.58 - typedef typename LengthMap::Value Value;
3.59 -
3.60 - /// \brief The large value type used for internal computations
3.61 - ///
3.62 - /// The large value type used for internal computations.
3.63 - /// It is \c long \c long if the \c Value type is integer,
3.64 - /// otherwise it is \c double.
3.65 - /// \c Value must be convertible to \c LargeValue.
3.66 - typedef double LargeValue;
3.67 -
3.68 - /// The tolerance type used for internal computations
3.69 - typedef lemon::Tolerance<LargeValue> Tolerance;
3.70 -
3.71 - /// \brief The path type of the found cycles
3.72 - ///
3.73 - /// The path type of the found cycles.
3.74 - /// It must conform to the \ref lemon::concepts::Path "Path" concept
3.75 - /// and it must have an \c addBack() function.
3.76 - typedef lemon::Path<Digraph> Path;
3.77 - };
3.78 -
3.79 - // Default traits class for integer value types
3.80 - template <typename GR, typename LEN>
3.81 - struct MinMeanCycleDefaultTraits<GR, LEN, true>
3.82 - {
3.83 - typedef GR Digraph;
3.84 - typedef LEN LengthMap;
3.85 - typedef typename LengthMap::Value Value;
3.86 -#ifdef LEMON_HAVE_LONG_LONG
3.87 - typedef long long LargeValue;
3.88 -#else
3.89 - typedef long LargeValue;
3.90 -#endif
3.91 - typedef lemon::Tolerance<LargeValue> Tolerance;
3.92 - typedef lemon::Path<Digraph> Path;
3.93 - };
3.94 -
3.95 -
3.96 - /// \addtogroup shortest_path
3.97 - /// @{
3.98 -
3.99 - /// \brief Implementation of Howard's algorithm for finding a minimum
3.100 - /// mean cycle.
3.101 - ///
3.102 - /// \ref MinMeanCycle implements Howard's algorithm for finding a
3.103 - /// directed cycle of minimum mean length (cost) in a digraph.
3.104 - ///
3.105 - /// \tparam GR The type of the digraph the algorithm runs on.
3.106 - /// \tparam LEN The type of the length map. The default
3.107 - /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
3.108 -#ifdef DOXYGEN
3.109 - template <typename GR, typename LEN, typename TR>
3.110 -#else
3.111 - template < typename GR,
3.112 - typename LEN = typename GR::template ArcMap<int>,
3.113 - typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
3.114 -#endif
3.115 - class MinMeanCycle
3.116 - {
3.117 - public:
3.118 -
3.119 - /// The type of the digraph
3.120 - typedef typename TR::Digraph Digraph;
3.121 - /// The type of the length map
3.122 - typedef typename TR::LengthMap LengthMap;
3.123 - /// The type of the arc lengths
3.124 - typedef typename TR::Value Value;
3.125 -
3.126 - /// \brief The large value type
3.127 - ///
3.128 - /// The large value type used for internal computations.
3.129 - /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
3.130 - /// it is \c long \c long if the \c Value type is integer,
3.131 - /// otherwise it is \c double.
3.132 - typedef typename TR::LargeValue LargeValue;
3.133 -
3.134 - /// The tolerance type
3.135 - typedef typename TR::Tolerance Tolerance;
3.136 -
3.137 - /// \brief The path type of the found cycles
3.138 - ///
3.139 - /// The path type of the found cycles.
3.140 - /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
3.141 - /// it is \ref lemon::Path "Path<Digraph>".
3.142 - typedef typename TR::Path Path;
3.143 -
3.144 - /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
3.145 - typedef TR Traits;
3.146 -
3.147 - private:
3.148 -
3.149 - TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
3.150 -
3.151 - // The digraph the algorithm runs on
3.152 - const Digraph &_gr;
3.153 - // The length of the arcs
3.154 - const LengthMap &_length;
3.155 -
3.156 - // Data for the found cycles
3.157 - bool _curr_found, _best_found;
3.158 - LargeValue _curr_length, _best_length;
3.159 - int _curr_size, _best_size;
3.160 - Node _curr_node, _best_node;
3.161 -
3.162 - Path *_cycle_path;
3.163 - bool _local_path;
3.164 -
3.165 - // Internal data used by the algorithm
3.166 - typename Digraph::template NodeMap<Arc> _policy;
3.167 - typename Digraph::template NodeMap<bool> _reached;
3.168 - typename Digraph::template NodeMap<int> _level;
3.169 - typename Digraph::template NodeMap<LargeValue> _dist;
3.170 -
3.171 - // Data for storing the strongly connected components
3.172 - int _comp_num;
3.173 - typename Digraph::template NodeMap<int> _comp;
3.174 - std::vector<std::vector<Node> > _comp_nodes;
3.175 - std::vector<Node>* _nodes;
3.176 - typename Digraph::template NodeMap<std::vector<Arc> > _in_arcs;
3.177 -
3.178 - // Queue used for BFS search
3.179 - std::vector<Node> _queue;
3.180 - int _qfront, _qback;
3.181 -
3.182 - Tolerance _tolerance;
3.183 -
3.184 - public:
3.185 -
3.186 - /// \name Named Template Parameters
3.187 - /// @{
3.188 -
3.189 - template <typename T>
3.190 - struct SetLargeValueTraits : public Traits {
3.191 - typedef T LargeValue;
3.192 - typedef lemon::Tolerance<T> Tolerance;
3.193 - };
3.194 -
3.195 - /// \brief \ref named-templ-param "Named parameter" for setting
3.196 - /// \c LargeValue type.
3.197 - ///
3.198 - /// \ref named-templ-param "Named parameter" for setting \c LargeValue
3.199 - /// type. It is used for internal computations in the algorithm.
3.200 - template <typename T>
3.201 - struct SetLargeValue
3.202 - : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
3.203 - typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
3.204 - };
3.205 -
3.206 - template <typename T>
3.207 - struct SetPathTraits : public Traits {
3.208 - typedef T Path;
3.209 - };
3.210 -
3.211 - /// \brief \ref named-templ-param "Named parameter" for setting
3.212 - /// \c %Path type.
3.213 - ///
3.214 - /// \ref named-templ-param "Named parameter" for setting the \c %Path
3.215 - /// type of the found cycles.
3.216 - /// It must conform to the \ref lemon::concepts::Path "Path" concept
3.217 - /// and it must have an \c addBack() function.
3.218 - template <typename T>
3.219 - struct SetPath
3.220 - : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
3.221 - typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
3.222 - };
3.223 -
3.224 - /// @}
3.225 -
3.226 - public:
3.227 -
3.228 - /// \brief Constructor.
3.229 - ///
3.230 - /// The constructor of the class.
3.231 - ///
3.232 - /// \param digraph The digraph the algorithm runs on.
3.233 - /// \param length The lengths (costs) of the arcs.
3.234 - MinMeanCycle( const Digraph &digraph,
3.235 - const LengthMap &length ) :
3.236 - _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
3.237 - _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
3.238 - _comp(digraph), _in_arcs(digraph)
3.239 - {}
3.240 -
3.241 - /// Destructor.
3.242 - ~MinMeanCycle() {
3.243 - if (_local_path) delete _cycle_path;
3.244 - }
3.245 -
3.246 - /// \brief Set the path structure for storing the found cycle.
3.247 - ///
3.248 - /// This function sets an external path structure for storing the
3.249 - /// found cycle.
3.250 - ///
3.251 - /// If you don't call this function before calling \ref run() or
3.252 - /// \ref findMinMean(), it will allocate a local \ref Path "path"
3.253 - /// structure. The destuctor deallocates this automatically
3.254 - /// allocated object, of course.
3.255 - ///
3.256 - /// \note The algorithm calls only the \ref lemon::Path::addBack()
3.257 - /// "addBack()" function of the given path structure.
3.258 - ///
3.259 - /// \return <tt>(*this)</tt>
3.260 - MinMeanCycle& cycle(Path &path) {
3.261 - if (_local_path) {
3.262 - delete _cycle_path;
3.263 - _local_path = false;
3.264 - }
3.265 - _cycle_path = &path;
3.266 - return *this;
3.267 - }
3.268 -
3.269 - /// \name Execution control
3.270 - /// The simplest way to execute the algorithm is to call the \ref run()
3.271 - /// function.\n
3.272 - /// If you only need the minimum mean length, you may call
3.273 - /// \ref findMinMean().
3.274 -
3.275 - /// @{
3.276 -
3.277 - /// \brief Run the algorithm.
3.278 - ///
3.279 - /// This function runs the algorithm.
3.280 - /// It can be called more than once (e.g. if the underlying digraph
3.281 - /// and/or the arc lengths have been modified).
3.282 - ///
3.283 - /// \return \c true if a directed cycle exists in the digraph.
3.284 - ///
3.285 - /// \note <tt>mmc.run()</tt> is just a shortcut of the following code.
3.286 - /// \code
3.287 - /// return mmc.findMinMean() && mmc.findCycle();
3.288 - /// \endcode
3.289 - bool run() {
3.290 - return findMinMean() && findCycle();
3.291 - }
3.292 -
3.293 - /// \brief Find the minimum cycle mean.
3.294 - ///
3.295 - /// This function finds the minimum mean length of the directed
3.296 - /// cycles in the digraph.
3.297 - ///
3.298 - /// \return \c true if a directed cycle exists in the digraph.
3.299 - bool findMinMean() {
3.300 - // Initialize and find strongly connected components
3.301 - init();
3.302 - findComponents();
3.303 -
3.304 - // Find the minimum cycle mean in the components
3.305 - for (int comp = 0; comp < _comp_num; ++comp) {
3.306 - // Find the minimum mean cycle in the current component
3.307 - if (!buildPolicyGraph(comp)) continue;
3.308 - while (true) {
3.309 - findPolicyCycle();
3.310 - if (!computeNodeDistances()) break;
3.311 - }
3.312 - // Update the best cycle (global minimum mean cycle)
3.313 - if ( !_best_found || (_curr_found &&
3.314 - _curr_length * _best_size < _best_length * _curr_size) ) {
3.315 - _best_found = true;
3.316 - _best_length = _curr_length;
3.317 - _best_size = _curr_size;
3.318 - _best_node = _curr_node;
3.319 - }
3.320 - }
3.321 - return _best_found;
3.322 - }
3.323 -
3.324 - /// \brief Find a minimum mean directed cycle.
3.325 - ///
3.326 - /// This function finds a directed cycle of minimum mean length
3.327 - /// in the digraph using the data computed by findMinMean().
3.328 - ///
3.329 - /// \return \c true if a directed cycle exists in the digraph.
3.330 - ///
3.331 - /// \pre \ref findMinMean() must be called before using this function.
3.332 - bool findCycle() {
3.333 - if (!_best_found) return false;
3.334 - _cycle_path->addBack(_policy[_best_node]);
3.335 - for ( Node v = _best_node;
3.336 - (v = _gr.target(_policy[v])) != _best_node; ) {
3.337 - _cycle_path->addBack(_policy[v]);
3.338 - }
3.339 - return true;
3.340 - }
3.341 -
3.342 - /// @}
3.343 -
3.344 - /// \name Query Functions
3.345 - /// The results of the algorithm can be obtained using these
3.346 - /// functions.\n
3.347 - /// The algorithm should be executed before using them.
3.348 -
3.349 - /// @{
3.350 -
3.351 - /// \brief Return the total length of the found cycle.
3.352 - ///
3.353 - /// This function returns the total length of the found cycle.
3.354 - ///
3.355 - /// \pre \ref run() or \ref findMinMean() must be called before
3.356 - /// using this function.
3.357 - LargeValue cycleLength() const {
3.358 - return _best_length;
3.359 - }
3.360 -
3.361 - /// \brief Return the number of arcs on the found cycle.
3.362 - ///
3.363 - /// This function returns the number of arcs on the found cycle.
3.364 - ///
3.365 - /// \pre \ref run() or \ref findMinMean() must be called before
3.366 - /// using this function.
3.367 - int cycleArcNum() const {
3.368 - return _best_size;
3.369 - }
3.370 -
3.371 - /// \brief Return the mean length of the found cycle.
3.372 - ///
3.373 - /// This function returns the mean length of the found cycle.
3.374 - ///
3.375 - /// \note <tt>alg.cycleMean()</tt> is just a shortcut of the
3.376 - /// following code.
3.377 - /// \code
3.378 - /// return static_cast<double>(alg.cycleLength()) / alg.cycleArcNum();
3.379 - /// \endcode
3.380 - ///
3.381 - /// \pre \ref run() or \ref findMinMean() must be called before
3.382 - /// using this function.
3.383 - double cycleMean() const {
3.384 - return static_cast<double>(_best_length) / _best_size;
3.385 - }
3.386 -
3.387 - /// \brief Return the found cycle.
3.388 - ///
3.389 - /// This function returns a const reference to the path structure
3.390 - /// storing the found cycle.
3.391 - ///
3.392 - /// \pre \ref run() or \ref findCycle() must be called before using
3.393 - /// this function.
3.394 - const Path& cycle() const {
3.395 - return *_cycle_path;
3.396 - }
3.397 -
3.398 - ///@}
3.399 -
3.400 - private:
3.401 -
3.402 - // Initialize
3.403 - void init() {
3.404 - if (!_cycle_path) {
3.405 - _local_path = true;
3.406 - _cycle_path = new Path;
3.407 - }
3.408 - _queue.resize(countNodes(_gr));
3.409 - _best_found = false;
3.410 - _best_length = 0;
3.411 - _best_size = 1;
3.412 - _cycle_path->clear();
3.413 - }
3.414 -
3.415 - // Find strongly connected components and initialize _comp_nodes
3.416 - // and _in_arcs
3.417 - void findComponents() {
3.418 - _comp_num = stronglyConnectedComponents(_gr, _comp);
3.419 - _comp_nodes.resize(_comp_num);
3.420 - if (_comp_num == 1) {
3.421 - _comp_nodes[0].clear();
3.422 - for (NodeIt n(_gr); n != INVALID; ++n) {
3.423 - _comp_nodes[0].push_back(n);
3.424 - _in_arcs[n].clear();
3.425 - for (InArcIt a(_gr, n); a != INVALID; ++a) {
3.426 - _in_arcs[n].push_back(a);
3.427 - }
3.428 - }
3.429 - } else {
3.430 - for (int i = 0; i < _comp_num; ++i)
3.431 - _comp_nodes[i].clear();
3.432 - for (NodeIt n(_gr); n != INVALID; ++n) {
3.433 - int k = _comp[n];
3.434 - _comp_nodes[k].push_back(n);
3.435 - _in_arcs[n].clear();
3.436 - for (InArcIt a(_gr, n); a != INVALID; ++a) {
3.437 - if (_comp[_gr.source(a)] == k) _in_arcs[n].push_back(a);
3.438 - }
3.439 - }
3.440 - }
3.441 - }
3.442 -
3.443 - // Build the policy graph in the given strongly connected component
3.444 - // (the out-degree of every node is 1)
3.445 - bool buildPolicyGraph(int comp) {
3.446 - _nodes = &(_comp_nodes[comp]);
3.447 - if (_nodes->size() < 1 ||
3.448 - (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) {
3.449 - return false;
3.450 - }
3.451 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.452 - _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max();
3.453 - }
3.454 - Node u, v;
3.455 - Arc e;
3.456 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.457 - v = (*_nodes)[i];
3.458 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
3.459 - e = _in_arcs[v][j];
3.460 - u = _gr.source(e);
3.461 - if (_length[e] < _dist[u]) {
3.462 - _dist[u] = _length[e];
3.463 - _policy[u] = e;
3.464 - }
3.465 - }
3.466 - }
3.467 - return true;
3.468 - }
3.469 -
3.470 - // Find the minimum mean cycle in the policy graph
3.471 - void findPolicyCycle() {
3.472 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.473 - _level[(*_nodes)[i]] = -1;
3.474 - }
3.475 - LargeValue clength;
3.476 - int csize;
3.477 - Node u, v;
3.478 - _curr_found = false;
3.479 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.480 - u = (*_nodes)[i];
3.481 - if (_level[u] >= 0) continue;
3.482 - for (; _level[u] < 0; u = _gr.target(_policy[u])) {
3.483 - _level[u] = i;
3.484 - }
3.485 - if (_level[u] == i) {
3.486 - // A cycle is found
3.487 - clength = _length[_policy[u]];
3.488 - csize = 1;
3.489 - for (v = u; (v = _gr.target(_policy[v])) != u; ) {
3.490 - clength += _length[_policy[v]];
3.491 - ++csize;
3.492 - }
3.493 - if ( !_curr_found ||
3.494 - (clength * _curr_size < _curr_length * csize) ) {
3.495 - _curr_found = true;
3.496 - _curr_length = clength;
3.497 - _curr_size = csize;
3.498 - _curr_node = u;
3.499 - }
3.500 - }
3.501 - }
3.502 - }
3.503 -
3.504 - // Contract the policy graph and compute node distances
3.505 - bool computeNodeDistances() {
3.506 - // Find the component of the main cycle and compute node distances
3.507 - // using reverse BFS
3.508 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.509 - _reached[(*_nodes)[i]] = false;
3.510 - }
3.511 - _qfront = _qback = 0;
3.512 - _queue[0] = _curr_node;
3.513 - _reached[_curr_node] = true;
3.514 - _dist[_curr_node] = 0;
3.515 - Node u, v;
3.516 - Arc e;
3.517 - while (_qfront <= _qback) {
3.518 - v = _queue[_qfront++];
3.519 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
3.520 - e = _in_arcs[v][j];
3.521 - u = _gr.source(e);
3.522 - if (_policy[u] == e && !_reached[u]) {
3.523 - _reached[u] = true;
3.524 - _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
3.525 - _queue[++_qback] = u;
3.526 - }
3.527 - }
3.528 - }
3.529 -
3.530 - // Connect all other nodes to this component and compute node
3.531 - // distances using reverse BFS
3.532 - _qfront = 0;
3.533 - while (_qback < int(_nodes->size())-1) {
3.534 - v = _queue[_qfront++];
3.535 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
3.536 - e = _in_arcs[v][j];
3.537 - u = _gr.source(e);
3.538 - if (!_reached[u]) {
3.539 - _reached[u] = true;
3.540 - _policy[u] = e;
3.541 - _dist[u] = _dist[v] + _length[e] * _curr_size - _curr_length;
3.542 - _queue[++_qback] = u;
3.543 - }
3.544 - }
3.545 - }
3.546 -
3.547 - // Improve node distances
3.548 - bool improved = false;
3.549 - for (int i = 0; i < int(_nodes->size()); ++i) {
3.550 - v = (*_nodes)[i];
3.551 - for (int j = 0; j < int(_in_arcs[v].size()); ++j) {
3.552 - e = _in_arcs[v][j];
3.553 - u = _gr.source(e);
3.554 - LargeValue delta = _dist[v] + _length[e] * _curr_size - _curr_length;
3.555 - if (_tolerance.less(delta, _dist[u])) {
3.556 - _dist[u] = delta;
3.557 - _policy[u] = e;
3.558 - improved = true;
3.559 - }
3.560 - }
3.561 - }
3.562 - return improved;
3.563 - }
3.564 -
3.565 - }; //class MinMeanCycle
3.566 -
3.567 - ///@}
3.568 -
3.569 -} //namespace lemon
3.570 -
3.571 -#endif //LEMON_MIN_MEAN_CYCLE_H
4.1 --- a/test/min_mean_cycle_test.cc Fri Aug 07 14:52:40 2009 +0200
4.2 +++ b/test/min_mean_cycle_test.cc Mon Aug 10 14:50:57 2009 +0200
4.3 @@ -21,7 +21,7 @@
4.4
4.5 #include <lemon/smart_graph.h>
4.6 #include <lemon/lgf_reader.h>
4.7 -#include <lemon/min_mean_cycle.h>
4.8 +#include <lemon/howard.h>
4.9 #include <lemon/path.h>
4.10 #include <lemon/concepts/digraph.h>
4.11 #include <lemon/concept_check.h>
4.12 @@ -141,8 +141,8 @@
4.13 // Check the interface
4.14 {
4.15 typedef concepts::Digraph GR;
4.16 - typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
4.17 - typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
4.18 + typedef Howard<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
4.19 + typedef Howard<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
4.20
4.21 checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
4.22 checkConcept<MmcClassConcept<GR, float>, FloatMmcAlg>();
4.23 @@ -174,10 +174,10 @@
4.24 arcMap("c4", c4).
4.25 run();
4.26
4.27 - checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1, 6, 3);
4.28 - checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2, 5, 2);
4.29 - checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3, 0, 1);
4.30 - checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);
4.31 + checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1, 6, 3);
4.32 + checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2, 5, 2);
4.33 + checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3, 0, 1);
4.34 + checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
4.35 }
4.36
4.37 return 0;