author Peter Kovacs Fri, 23 Jul 2010 06:29:37 +0200 changeset 999 c279b19abc62 parent 989 24b3f18ed9e2 child 1000 de428ebb47ab
Add a heuristic algorithm for the max clique problem (#380)
 doc/groups.dox file | annotate | diff | comparison | revisions doc/references.bib file | annotate | diff | comparison | revisions lemon/Makefile.am file | annotate | diff | comparison | revisions lemon/grosso_locatelli_pullan_mc.h file | annotate | diff | comparison | revisions test/CMakeLists.txt file | annotate | diff | comparison | revisions test/Makefile.am file | annotate | diff | comparison | revisions test/max_clique_test.cc file | annotate | diff | comparison | revisions
     1.1 --- a/doc/groups.dox	Tue Jun 22 16:13:00 2010 +0200
1.2 +++ b/doc/groups.dox	Fri Jul 23 06:29:37 2010 +0200
1.3 @@ -551,12 +551,16 @@
1.4  */
1.5
1.6  /**
1.7 -@defgroup approx Approximation Algorithms
1.8 +@defgroup approx_algs Approximation Algorithms
1.9  @ingroup algs
1.10  \brief Approximation algorithms.
1.11
1.12  This group contains the approximation and heuristic algorithms
1.13  implemented in LEMON.
1.14 +
1.15 +<b>Maximum Clique Problem</b>
1.16 +  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
1.17 +    Grosso, Locatelli, and Pullan.
1.18  */
1.19
1.20  /**

     2.1 --- a/doc/references.bib	Tue Jun 22 16:13:00 2010 +0200
2.2 +++ b/doc/references.bib	Fri Jul 23 06:29:37 2010 +0200
2.3 @@ -297,5 +297,18 @@
2.4    school =       {University College},
2.5    address =      {Dublin, Ireland},
2.6    year =         1991,
2.7 -  month =        sep,
2.8 +  month =        sep
2.9  }
2.10 +
2.11 +%%%%% Other algorithms %%%%%
2.12 +
2.13 +@article{grosso08maxclique,
2.14 +  author =       {Andrea Grosso and Marco Locatelli and Wayne Pullan},
2.15 +  title =        {Simple ingredients leading to very efficient
2.16 +                  heuristics for the maximum clique problem},
2.17 +  journal =      {Journal of Heuristics},
2.18 +  year =         2008,
2.19 +  volume =       14,
2.20 +  number =       6,
2.21 +  pages =        {587--612}
2.22 +}

     3.1 --- a/lemon/Makefile.am	Tue Jun 22 16:13:00 2010 +0200
3.2 +++ b/lemon/Makefile.am	Fri Jul 23 06:29:37 2010 +0200
3.3 @@ -90,6 +90,7 @@
3.4  	lemon/gomory_hu.h \
3.5  	lemon/graph_to_eps.h \
3.6  	lemon/grid_graph.h \
3.7 +	lemon/grosso_locatelli_pullan_mc.h \
3.8  	lemon/hartmann_orlin_mmc.h \
3.9  	lemon/howard_mmc.h \
3.10  	lemon/hypercube_graph.h \

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/grosso_locatelli_pullan_mc.h	Fri Jul 23 06:29:37 2010 +0200
4.3 @@ -0,0 +1,680 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2010
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
4.23 +#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
4.24 +
4.25 +/// \ingroup approx_algs
4.26 +///
4.27 +/// \file
4.28 +/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
4.29 +/// for the maximum clique problem
4.30 +
4.31 +#include <vector>
4.32 +#include <limits>
4.33 +#include <lemon/core.h>
4.34 +#include <lemon/random.h>
4.35 +
4.36 +namespace lemon {
4.37 +
4.38 +  /// \addtogroup approx_algs
4.39 +  /// @{
4.40 +
4.41 +  /// \brief Implementation of the iterated local search algorithm of Grosso,
4.42 +  /// Locatelli, and Pullan for the maximum clique problem
4.43 +  ///
4.44 +  /// \ref GrossoLocatelliPullanMc implements the iterated local search
4.45 +  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
4.46 +  /// \e clique \e problem \ref grosso08maxclique.
4.47 +  /// It is to find the largest complete subgraph (\e clique) in an
4.48 +  /// undirected graph, i.e., the largest set of nodes where each
4.49 +  /// pair of nodes is connected.
4.50 +  ///
4.51 +  /// This class provides a simple but highly efficient and robust heuristic
4.52 +  /// method that quickly finds a large clique, but not necessarily the
4.53 +  /// largest one.
4.54 +  ///
4.55 +  /// \tparam GR The undirected graph type the algorithm runs on.
4.56 +  ///
4.57 +  /// \note %GrossoLocatelliPullanMc provides three different node selection
4.58 +  /// rules, from which the most powerful one is used by default.
4.59 +  /// For more information, see \ref SelectionRule.
4.60 +  template <typename GR>
4.61 +  class GrossoLocatelliPullanMc
4.62 +  {
4.63 +  public:
4.64 +
4.65 +    /// \brief Constants for specifying the node selection rule.
4.66 +    ///
4.67 +    /// Enum type containing constants for specifying the node selection rule
4.68 +    /// for the \ref run() function.
4.69 +    ///
4.70 +    /// During the algorithm, nodes are selected for addition to the current
4.71 +    /// clique according to the applied rule.
4.72 +    /// In general, the PENALTY_BASED rule turned out to be the most powerful
4.73 +    /// and the most robust, thus it is the default option.
4.74 +    /// However, another selection rule can be specified using the \ref run()
4.75 +    /// function with the proper parameter.
4.76 +    enum SelectionRule {
4.77 +
4.78 +      /// A node is selected randomly without any evaluation at each step.
4.79 +      RANDOM,
4.80 +
4.81 +      /// A node of maximum degree is selected randomly at each step.
4.82 +      DEGREE_BASED,
4.83 +
4.84 +      /// A node of minimum penalty is selected randomly at each step.
4.85 +      /// The node penalties are updated adaptively after each stage of the
4.86 +      /// search process.
4.87 +      PENALTY_BASED
4.88 +    };
4.89 +
4.90 +  private:
4.91 +
4.92 +    TEMPLATE_GRAPH_TYPEDEFS(GR);
4.93 +
4.94 +    typedef std::vector<int> IntVector;
4.95 +    typedef std::vector<char> BoolVector;
4.96 +    typedef std::vector<BoolVector> BoolMatrix;
4.97 +    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
4.98 +
4.99 +    const GR &_graph;
4.100 +    IntNodeMap _id;
4.101 +
4.102 +    // Internal matrix representation of the graph
4.103 +    BoolMatrix _gr;
4.104 +    int _n;
4.105 +
4.106 +    // The current clique
4.107 +    BoolVector _clique;
4.108 +    int _size;
4.109 +
4.110 +    // The best clique found so far
4.111 +    BoolVector _best_clique;
4.112 +    int _best_size;
4.113 +
4.114 +    // The "distances" of the nodes from the current clique.
4.115 +    // _delta[u] is the number of nodes in the clique that are
4.116 +    // not connected with u.
4.117 +    IntVector _delta;
4.118 +
4.119 +    // The current tabu set
4.120 +    BoolVector _tabu;
4.121 +
4.122 +    // Random number generator
4.123 +    Random _rnd;
4.124 +
4.125 +  private:
4.126 +
4.127 +    // Implementation of the RANDOM node selection rule.
4.128 +    class RandomSelectionRule
4.129 +    {
4.130 +    private:
4.131 +
4.132 +      // References to the algorithm instance
4.133 +      const BoolVector &_clique;
4.134 +      const IntVector  &_delta;
4.135 +      const BoolVector &_tabu;
4.136 +      Random &_rnd;
4.137 +
4.138 +      // Pivot rule data
4.139 +      int _n;
4.140 +
4.141 +    public:
4.142 +
4.143 +      // Constructor
4.144 +      RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
4.145 +        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.146 +        _rnd(mc._rnd), _n(mc._n)
4.147 +      {}
4.148 +
4.149 +      // Return a node index for a feasible add move or -1 if no one exists
4.150 +      int nextFeasibleAddNode() const {
4.151 +        int start_node = _rnd[_n];
4.152 +        for (int i = start_node; i != _n; i++) {
4.153 +          if (_delta[i] == 0 && !_tabu[i]) return i;
4.154 +        }
4.155 +        for (int i = 0; i != start_node; i++) {
4.156 +          if (_delta[i] == 0 && !_tabu[i]) return i;
4.157 +        }
4.158 +        return -1;
4.159 +      }
4.160 +
4.161 +      // Return a node index for a feasible swap move or -1 if no one exists
4.162 +      int nextFeasibleSwapNode() const {
4.163 +        int start_node = _rnd[_n];
4.164 +        for (int i = start_node; i != _n; i++) {
4.165 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
4.166 +        }
4.167 +        for (int i = 0; i != start_node; i++) {
4.168 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
4.169 +        }
4.170 +        return -1;
4.171 +      }
4.172 +
4.173 +      // Return a node index for an add move or -1 if no one exists
4.174 +      int nextAddNode() const {
4.175 +        int start_node = _rnd[_n];
4.176 +        for (int i = start_node; i != _n; i++) {
4.177 +          if (_delta[i] == 0) return i;
4.178 +        }
4.179 +        for (int i = 0; i != start_node; i++) {
4.180 +          if (_delta[i] == 0) return i;
4.181 +        }
4.182 +        return -1;
4.183 +      }
4.184 +
4.185 +      // Update internal data structures between stages (if necessary)
4.186 +      void update() {}
4.187 +
4.188 +    }; //class RandomSelectionRule
4.189 +
4.190 +
4.191 +    // Implementation of the DEGREE_BASED node selection rule.
4.192 +    class DegreeBasedSelectionRule
4.193 +    {
4.194 +    private:
4.195 +
4.196 +      // References to the algorithm instance
4.197 +      const BoolVector &_clique;
4.198 +      const IntVector  &_delta;
4.199 +      const BoolVector &_tabu;
4.200 +      Random &_rnd;
4.201 +
4.202 +      // Pivot rule data
4.203 +      int _n;
4.204 +      IntVector _deg;
4.205 +
4.206 +    public:
4.207 +
4.208 +      // Constructor
4.209 +      DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
4.210 +        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.211 +        _rnd(mc._rnd), _n(mc._n), _deg(_n)
4.212 +      {
4.213 +        for (int i = 0; i != _n; i++) {
4.214 +          int d = 0;
4.215 +          BoolVector &row = mc._gr[i];
4.216 +          for (int j = 0; j != _n; j++) {
4.217 +            if (row[j]) d++;
4.218 +          }
4.219 +          _deg[i] = d;
4.220 +        }
4.221 +      }
4.222 +
4.223 +      // Return a node index for a feasible add move or -1 if no one exists
4.224 +      int nextFeasibleAddNode() const {
4.225 +        int start_node = _rnd[_n];
4.226 +        int node = -1, max_deg = -1;
4.227 +        for (int i = start_node; i != _n; i++) {
4.228 +          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
4.229 +            node = i;
4.230 +            max_deg = _deg[i];
4.231 +          }
4.232 +        }
4.233 +        for (int i = 0; i != start_node; i++) {
4.234 +          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
4.235 +            node = i;
4.236 +            max_deg = _deg[i];
4.237 +          }
4.238 +        }
4.239 +        return node;
4.240 +      }
4.241 +
4.242 +      // Return a node index for a feasible swap move or -1 if no one exists
4.243 +      int nextFeasibleSwapNode() const {
4.244 +        int start_node = _rnd[_n];
4.245 +        int node = -1, max_deg = -1;
4.246 +        for (int i = start_node; i != _n; i++) {
4.247 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.248 +              _deg[i] > max_deg) {
4.249 +            node = i;
4.250 +            max_deg = _deg[i];
4.251 +          }
4.252 +        }
4.253 +        for (int i = 0; i != start_node; i++) {
4.254 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.255 +              _deg[i] > max_deg) {
4.256 +            node = i;
4.257 +            max_deg = _deg[i];
4.258 +          }
4.259 +        }
4.260 +        return node;
4.261 +      }
4.262 +
4.263 +      // Return a node index for an add move or -1 if no one exists
4.264 +      int nextAddNode() const {
4.265 +        int start_node = _rnd[_n];
4.266 +        int node = -1, max_deg = -1;
4.267 +        for (int i = start_node; i != _n; i++) {
4.268 +          if (_delta[i] == 0 && _deg[i] > max_deg) {
4.269 +            node = i;
4.270 +            max_deg = _deg[i];
4.271 +          }
4.272 +        }
4.273 +        for (int i = 0; i != start_node; i++) {
4.274 +          if (_delta[i] == 0 && _deg[i] > max_deg) {
4.275 +            node = i;
4.276 +            max_deg = _deg[i];
4.277 +          }
4.278 +        }
4.279 +        return node;
4.280 +      }
4.281 +
4.282 +      // Update internal data structures between stages (if necessary)
4.283 +      void update() {}
4.284 +
4.285 +    }; //class DegreeBasedSelectionRule
4.286 +
4.287 +
4.288 +    // Implementation of the PENALTY_BASED node selection rule.
4.289 +    class PenaltyBasedSelectionRule
4.290 +    {
4.291 +    private:
4.292 +
4.293 +      // References to the algorithm instance
4.294 +      const BoolVector &_clique;
4.295 +      const IntVector  &_delta;
4.296 +      const BoolVector &_tabu;
4.297 +      Random &_rnd;
4.298 +
4.299 +      // Pivot rule data
4.300 +      int _n;
4.301 +      IntVector _penalty;
4.302 +
4.303 +    public:
4.304 +
4.305 +      // Constructor
4.306 +      PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
4.307 +        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.308 +        _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
4.309 +      {}
4.310 +
4.311 +      // Return a node index for a feasible add move or -1 if no one exists
4.312 +      int nextFeasibleAddNode() const {
4.313 +        int start_node = _rnd[_n];
4.314 +        int node = -1, min_p = std::numeric_limits<int>::max();
4.315 +        for (int i = start_node; i != _n; i++) {
4.316 +          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
4.317 +            node = i;
4.318 +            min_p = _penalty[i];
4.319 +          }
4.320 +        }
4.321 +        for (int i = 0; i != start_node; i++) {
4.322 +          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
4.323 +            node = i;
4.324 +            min_p = _penalty[i];
4.325 +          }
4.326 +        }
4.327 +        return node;
4.328 +      }
4.329 +
4.330 +      // Return a node index for a feasible swap move or -1 if no one exists
4.331 +      int nextFeasibleSwapNode() const {
4.332 +        int start_node = _rnd[_n];
4.333 +        int node = -1, min_p = std::numeric_limits<int>::max();
4.334 +        for (int i = start_node; i != _n; i++) {
4.335 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.336 +              _penalty[i] < min_p) {
4.337 +            node = i;
4.338 +            min_p = _penalty[i];
4.339 +          }
4.340 +        }
4.341 +        for (int i = 0; i != start_node; i++) {
4.342 +          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.343 +              _penalty[i] < min_p) {
4.344 +            node = i;
4.345 +            min_p = _penalty[i];
4.346 +          }
4.347 +        }
4.348 +        return node;
4.349 +      }
4.350 +
4.351 +      // Return a node index for an add move or -1 if no one exists
4.352 +      int nextAddNode() const {
4.353 +        int start_node = _rnd[_n];
4.354 +        int node = -1, min_p = std::numeric_limits<int>::max();
4.355 +        for (int i = start_node; i != _n; i++) {
4.356 +          if (_delta[i] == 0 && _penalty[i] < min_p) {
4.357 +            node = i;
4.358 +            min_p = _penalty[i];
4.359 +          }
4.360 +        }
4.361 +        for (int i = 0; i != start_node; i++) {
4.362 +          if (_delta[i] == 0 && _penalty[i] < min_p) {
4.363 +            node = i;
4.364 +            min_p = _penalty[i];
4.365 +          }
4.366 +        }
4.367 +        return node;
4.368 +      }
4.369 +
4.370 +      // Update internal data structures between stages (if necessary)
4.371 +      void update() {}
4.372 +
4.373 +    }; //class PenaltyBasedSelectionRule
4.374 +
4.375 +  public:
4.376 +
4.377 +    /// \brief Constructor.
4.378 +    ///
4.379 +    /// Constructor.
4.380 +    /// The global \ref rnd "random number generator instance" is used
4.381 +    /// during the algorithm.
4.382 +    ///
4.383 +    /// \param graph The undirected graph the algorithm runs on.
4.384 +    GrossoLocatelliPullanMc(const GR& graph) :
4.385 +      _graph(graph), _id(_graph), _rnd(rnd)
4.386 +    {}
4.387 +
4.388 +    /// \brief Constructor with random seed.
4.389 +    ///
4.390 +    /// Constructor with random seed.
4.391 +    ///
4.392 +    /// \param graph The undirected graph the algorithm runs on.
4.393 +    /// \param seed Seed value for the internal random number generator
4.394 +    /// that is used during the algorithm.
4.395 +    GrossoLocatelliPullanMc(const GR& graph, int seed) :
4.396 +      _graph(graph), _id(_graph), _rnd(seed)
4.397 +    {}
4.398 +
4.399 +    /// \brief Constructor with random number generator.
4.400 +    ///
4.401 +    /// Constructor with random number generator.
4.402 +    ///
4.403 +    /// \param graph The undirected graph the algorithm runs on.
4.404 +    /// \param random A random number generator that is used during the
4.405 +    /// algorithm.
4.406 +    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
4.407 +      _graph(graph), _id(_graph), _rnd(random)
4.408 +    {}
4.409 +
4.410 +    /// \name Execution Control
4.411 +    /// @{
4.412 +
4.413 +    /// \brief Runs the algorithm.
4.414 +    ///
4.415 +    /// This function runs the algorithm.
4.416 +    ///
4.417 +    /// \param step_num The maximum number of node selections (steps)
4.418 +    /// during the search process.
4.419 +    /// This parameter controls the running time and the success of the
4.420 +    /// algorithm. For larger values, the algorithm runs slower but it more
4.421 +    /// likely finds larger cliques. For smaller values, the algorithm is
4.422 +    /// faster but probably gives worse results.
4.423 +    /// \param rule The node selection rule. For more information, see
4.424 +    /// \ref SelectionRule.
4.425 +    ///
4.426 +    /// \return The size of the found clique.
4.427 +    int run(int step_num = 100000,
4.428 +            SelectionRule rule = PENALTY_BASED)
4.429 +    {
4.430 +      init();
4.431 +      switch (rule) {
4.432 +        case RANDOM:
4.433 +          return start<RandomSelectionRule>(step_num);
4.434 +        case DEGREE_BASED:
4.435 +          return start<DegreeBasedSelectionRule>(step_num);
4.436 +        case PENALTY_BASED:
4.437 +          return start<PenaltyBasedSelectionRule>(step_num);
4.438 +      }
4.439 +      return 0; // avoid warning
4.440 +    }
4.441 +
4.442 +    /// @}
4.443 +
4.444 +    /// \name Query Functions
4.445 +    /// @{
4.446 +
4.447 +    /// \brief The size of the found clique
4.448 +    ///
4.449 +    /// This function returns the size of the found clique.
4.450 +    ///
4.451 +    /// \pre run() must be called before using this function.
4.452 +    int cliqueSize() const {
4.453 +      return _best_size;
4.454 +    }
4.455 +
4.456 +    /// \brief Gives back the found clique in a \c bool node map
4.457 +    ///
4.458 +    /// This function gives back the characteristic vector of the found
4.459 +    /// clique in the given node map.
4.460 +    /// It must be a \ref concepts::WriteMap "writable" node map with
4.461 +    /// \c bool (or convertible) value type.
4.462 +    ///
4.463 +    /// \pre run() must be called before using this function.
4.464 +    template <typename CliqueMap>
4.465 +    void cliqueMap(CliqueMap &map) const {
4.466 +      for (NodeIt n(_graph); n != INVALID; ++n) {
4.467 +        map[n] = static_cast<bool>(_best_clique[_id[n]]);
4.468 +      }
4.469 +    }
4.470 +
4.471 +    /// \brief Iterator to list the nodes of the found clique
4.472 +    ///
4.473 +    /// This iterator class lists the nodes of the found clique.
4.474 +    /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
4.475 +    /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
4.476 +    ///
4.477 +    /// The following example prints out the IDs of the nodes in the found
4.478 +    /// clique.
4.479 +    /// \code
4.480 +    ///   GrossoLocatelliPullanMc<Graph> mc(g);
4.481 +    ///   mc.run();
4.482 +    ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
4.483 +    ///        n != INVALID; ++n)
4.484 +    ///   {
4.485 +    ///     std::cout << g.id(n) << std::endl;
4.486 +    ///   }
4.487 +    /// \endcode
4.488 +    class CliqueNodeIt
4.489 +    {
4.490 +    private:
4.491 +      NodeIt _it;
4.492 +      BoolNodeMap _map;
4.493 +
4.494 +    public:
4.495 +
4.496 +      /// Constructor
4.497 +
4.498 +      /// Constructor.
4.499 +      /// \param mc The algorithm instance.
4.500 +      CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
4.501 +       : _map(mc._graph)
4.502 +      {
4.503 +        mc.cliqueMap(_map);
4.504 +        for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
4.505 +      }
4.506 +
4.507 +      /// Conversion to \c Node
4.508 +      operator Node() const { return _it; }
4.509 +
4.510 +      bool operator==(Invalid) const { return _it == INVALID; }
4.511 +      bool operator!=(Invalid) const { return _it != INVALID; }
4.512 +
4.513 +      /// Next node
4.514 +      CliqueNodeIt &operator++() {
4.515 +        for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
4.516 +        return *this;
4.517 +      }
4.518 +
4.519 +      /// Postfix incrementation
4.520 +
4.521 +      /// Postfix incrementation.
4.522 +      ///
4.523 +      /// \warning This incrementation returns a \c Node, not a
4.524 +      /// \c CliqueNodeIt as one may expect.
4.525 +      typename GR::Node operator++(int) {
4.526 +        Node n=*this;
4.527 +        ++(*this);
4.528 +        return n;
4.529 +      }
4.530 +
4.531 +    };
4.532 +
4.533 +    /// @}
4.534 +
4.535 +  private:
4.536 +
4.537 +    // Adds a node to the current clique
4.538 +    void addCliqueNode(int u) {
4.539 +      if (_clique[u]) return;
4.540 +      _clique[u] = true;
4.541 +      _size++;
4.542 +      BoolVector &row = _gr[u];
4.543 +      for (int i = 0; i != _n; i++) {
4.544 +        if (!row[i]) _delta[i]++;
4.545 +      }
4.546 +    }
4.547 +
4.548 +    // Removes a node from the current clique
4.549 +    void delCliqueNode(int u) {
4.550 +      if (!_clique[u]) return;
4.551 +      _clique[u] = false;
4.552 +      _size--;
4.553 +      BoolVector &row = _gr[u];
4.554 +      for (int i = 0; i != _n; i++) {
4.555 +        if (!row[i]) _delta[i]--;
4.556 +      }
4.557 +    }
4.558 +
4.559 +    // Initialize data structures
4.560 +    void init() {
4.561 +      _n = countNodes(_graph);
4.562 +      int ui = 0;
4.563 +      for (NodeIt u(_graph); u != INVALID; ++u) {
4.564 +        _id[u] = ui++;
4.565 +      }
4.566 +      _gr.clear();
4.567 +      _gr.resize(_n, BoolVector(_n, false));
4.568 +      ui = 0;
4.569 +      for (NodeIt u(_graph); u != INVALID; ++u) {
4.570 +        for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
4.571 +          int vi = _id[_graph.runningNode(e)];
4.572 +          _gr[ui][vi] = true;
4.573 +          _gr[vi][ui] = true;
4.574 +        }
4.575 +        ++ui;
4.576 +      }
4.577 +
4.578 +      _clique.clear();
4.579 +      _clique.resize(_n, false);
4.580 +      _size = 0;
4.581 +      _best_clique.clear();
4.582 +      _best_clique.resize(_n, false);
4.583 +      _best_size = 0;
4.584 +      _delta.clear();
4.585 +      _delta.resize(_n, 0);
4.586 +      _tabu.clear();
4.587 +      _tabu.resize(_n, false);
4.588 +    }
4.589 +
4.590 +    // Executes the algorithm
4.591 +    template <typename SelectionRuleImpl>
4.592 +    int start(int max_select) {
4.593 +      // Options for the restart rule
4.594 +      const bool delta_based_restart = true;
4.595 +      const int restart_delta_limit = 4;
4.596 +
4.597 +      if (_n == 0) return 0;
4.598 +      if (_n == 1) {
4.599 +        _best_clique[0] = true;
4.600 +        _best_size = 1;
4.601 +        return _best_size;
4.602 +      }
4.603 +
4.604 +      // Iterated local search
4.605 +      SelectionRuleImpl sel_method(*this);
4.606 +      int select = 0;
4.607 +      IntVector restart_nodes;
4.608 +
4.609 +      while (select < max_select) {
4.610 +
4.611 +        // Perturbation/restart
4.612 +        if (delta_based_restart) {
4.613 +          restart_nodes.clear();
4.614 +          for (int i = 0; i != _n; i++) {
4.615 +            if (_delta[i] >= restart_delta_limit)
4.616 +              restart_nodes.push_back(i);
4.617 +          }
4.618 +        }
4.619 +        int rs_node = -1;
4.620 +        if (restart_nodes.size() > 0) {
4.621 +          rs_node = restart_nodes[_rnd[restart_nodes.size()]];
4.622 +        } else {
4.623 +          rs_node = _rnd[_n];
4.624 +        }
4.625 +        BoolVector &row = _gr[rs_node];
4.626 +        for (int i = 0; i != _n; i++) {
4.627 +          if (_clique[i] && !row[i]) delCliqueNode(i);
4.628 +        }
4.629 +        addCliqueNode(rs_node);
4.630 +
4.631 +        // Local search
4.632 +        _tabu.clear();
4.633 +        _tabu.resize(_n, false);
4.634 +        bool tabu_empty = true;
4.635 +        int max_swap = _size;
4.636 +        while (select < max_select) {
4.637 +          select++;
4.638 +          int u;
4.639 +          if ((u = sel_method.nextFeasibleAddNode()) != -1) {
4.640 +            // Feasible add move
4.641 +            addCliqueNode(u);
4.642 +            if (tabu_empty) max_swap = _size;
4.643 +          }
4.644 +          else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
4.645 +            // Feasible swap move
4.646 +            int v = -1;
4.647 +            BoolVector &row = _gr[u];
4.648 +            for (int i = 0; i != _n; i++) {
4.649 +              if (_clique[i] && !row[i]) {
4.650 +                v = i;
4.651 +                break;
4.652 +              }
4.653 +            }
4.654 +            addCliqueNode(u);
4.655 +            delCliqueNode(v);
4.656 +            _tabu[v] = true;
4.657 +            tabu_empty = false;
4.658 +            if (--max_swap <= 0) break;
4.659 +          }
4.660 +          else if ((u = sel_method.nextAddNode()) != -1) {
4.661 +            // Non-feasible add move
4.662 +            addCliqueNode(u);
4.663 +          }
4.664 +          else break;
4.665 +        }
4.666 +        if (_size > _best_size) {
4.667 +          _best_clique = _clique;
4.668 +          _best_size = _size;
4.669 +          if (_best_size == _n) return _best_size;
4.670 +        }
4.671 +        sel_method.update();
4.672 +      }
4.673 +
4.674 +      return _best_size;
4.675 +    }
4.676 +
4.677 +  }; //class GrossoLocatelliPullanMc
4.678 +
4.679 +  ///@}
4.680 +
4.681 +} //namespace lemon
4.682 +
4.683 +#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H

     5.1 --- a/test/CMakeLists.txt	Tue Jun 22 16:13:00 2010 +0200
5.2 +++ b/test/CMakeLists.txt	Fri Jul 23 06:29:37 2010 +0200
5.3 @@ -31,6 +31,7 @@
5.4    kruskal_test
5.5    maps_test
5.6    matching_test
5.7 +  max_clique_test
5.8    min_cost_arborescence_test
5.9    min_cost_flow_test
5.10    min_mean_cycle_test

     6.1 --- a/test/Makefile.am	Tue Jun 22 16:13:00 2010 +0200
6.2 +++ b/test/Makefile.am	Fri Jul 23 06:29:37 2010 +0200
6.3 @@ -33,6 +33,7 @@
6.4  	test/kruskal_test \
6.5  	test/maps_test \
6.6  	test/matching_test \
6.7 +	test/max_clique_test \
6.8  	test/min_cost_arborescence_test \
6.9  	test/min_cost_flow_test \
6.10  	test/min_mean_cycle_test \
6.11 @@ -84,6 +85,7 @@
6.12  test_maps_test_SOURCES = test/maps_test.cc
6.13  test_mip_test_SOURCES = test/mip_test.cc
6.14  test_matching_test_SOURCES = test/matching_test.cc
6.15 +test_max_clique_test_SOURCES = test/max_clique_test.cc
6.16  test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
6.17  test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
6.18  test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/test/max_clique_test.cc	Fri Jul 23 06:29:37 2010 +0200
7.3 @@ -0,0 +1,176 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2010
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#include <sstream>
7.23 +#include <lemon/list_graph.h>
7.24 +#include <lemon/full_graph.h>
7.25 +#include <lemon/grid_graph.h>
7.26 +#include <lemon/lgf_reader.h>
7.27 +#include <lemon/grosso_locatelli_pullan_mc.h>
7.28 +
7.29 +#include "test_tools.h"
7.30 +
7.31 +using namespace lemon;
7.32 +
7.33 +char test_lgf[] =
7.34 +  "@nodes\n"
7.35 +  "label max_clique\n"
7.36 +  "1     0\n"
7.37 +  "2     0\n"
7.38 +  "3     0\n"
7.39 +  "4     1\n"
7.40 +  "5     1\n"
7.41 +  "6     1\n"
7.42 +  "7     1\n"
7.43 +  "@edges\n"
7.44 +  "    label\n"
7.45 +  "1 2     1\n"
7.46 +  "1 3     2\n"
7.47 +  "1 4     3\n"
7.48 +  "1 6     4\n"
7.49 +  "2 3     5\n"
7.50 +  "2 5     6\n"
7.51 +  "2 7     7\n"
7.52 +  "3 4     8\n"
7.53 +  "3 5     9\n"
7.54 +  "4 5    10\n"
7.55 +  "4 6    11\n"
7.56 +  "4 7    12\n"
7.57 +  "5 6    13\n"
7.58 +  "5 7    14\n"
7.59 +  "6 7    15\n";
7.60 +
7.61 +
7.62 +// Check with general graphs
7.63 +template <typename Param>
7.64 +void checkMaxCliqueGeneral(int max_sel, Param rule) {
7.65 +  typedef ListGraph GR;
7.66 +  typedef GrossoLocatelliPullanMc<GR> McAlg;
7.67 +  typedef McAlg::CliqueNodeIt CliqueIt;
7.68 +
7.69 +  // Basic tests
7.70 +  {
7.71 +    GR g;
7.72 +    GR::NodeMap<bool> map(g);
7.73 +    McAlg mc(g);
7.74 +    check(mc.run(max_sel, rule) == 0, "Wrong clique size");
7.75 +    check(mc.cliqueSize() == 0, "Wrong clique size");
7.76 +    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
7.77 +
7.78 +    GR::Node u = g.addNode();
7.79 +    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
7.80 +    check(mc.cliqueSize() == 1, "Wrong clique size");
7.81 +    mc.cliqueMap(map);
7.82 +    check(map[u], "Wrong clique map");
7.83 +    CliqueIt it1(mc);
7.84 +    check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
7.85 +          "Wrong CliqueNodeIt");
7.86 +
7.87 +    GR::Node v = g.addNode();
7.88 +    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
7.89 +    check(mc.cliqueSize() == 1, "Wrong clique size");
7.90 +    mc.cliqueMap(map);
7.91 +    check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
7.92 +    CliqueIt it2(mc);
7.93 +    check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
7.94 +
7.95 +    g.addEdge(u, v);
7.96 +    check(mc.run(max_sel, rule) == 2, "Wrong clique size");
7.97 +    check(mc.cliqueSize() == 2, "Wrong clique size");
7.98 +    mc.cliqueMap(map);
7.99 +    check(map[u] && map[v], "Wrong clique map");
7.100 +    CliqueIt it3(mc);
7.101 +    check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
7.102 +          "Wrong CliqueNodeIt");
7.103 +  }
7.104 +
7.105 +  // Test graph
7.106 +  {
7.107 +    GR g;
7.108 +    GR::NodeMap<bool> max_clique(g);
7.109 +    GR::NodeMap<bool> map(g);
7.110 +    std::istringstream input(test_lgf);
7.111 +    graphReader(g, input)
7.112 +      .nodeMap("max_clique", max_clique)
7.113 +      .run();
7.114 +
7.115 +    McAlg mc(g);
7.116 +    check(mc.run(max_sel, rule) == 4, "Wrong clique size");
7.117 +    check(mc.cliqueSize() == 4, "Wrong clique size");
7.118 +    mc.cliqueMap(map);
7.119 +    for (GR::NodeIt n(g); n != INVALID; ++n) {
7.120 +      check(map[n] == max_clique[n], "Wrong clique map");
7.121 +    }
7.122 +    int cnt = 0;
7.123 +    for (CliqueIt n(mc); n != INVALID; ++n) {
7.124 +      cnt++;
7.125 +      check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
7.126 +    }
7.127 +    check(cnt == 4, "Wrong CliqueNodeIt");
7.128 +  }
7.129 +}
7.130 +
7.131 +// Check with full graphs
7.132 +template <typename Param>
7.133 +void checkMaxCliqueFullGraph(int max_sel, Param rule) {
7.134 +  typedef FullGraph GR;
7.135 +  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
7.136 +  typedef McAlg::CliqueNodeIt CliqueIt;
7.137 +
7.138 +  for (int size = 0; size <= 40; size = size * 3 + 1) {
7.139 +    GR g(size);
7.140 +    GR::NodeMap<bool> map(g);
7.141 +    McAlg mc(g);
7.142 +    check(mc.run(max_sel, rule) == size, "Wrong clique size");
7.143 +    check(mc.cliqueSize() == size, "Wrong clique size");
7.144 +    mc.cliqueMap(map);
7.145 +    for (GR::NodeIt n(g); n != INVALID; ++n) {
7.146 +      check(map[n], "Wrong clique map");
7.147 +    }
7.148 +    int cnt = 0;
7.149 +    for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
7.150 +    check(cnt == size, "Wrong CliqueNodeIt");
7.151 +  }
7.152 +}
7.153 +
7.154 +// Check with grid graphs
7.155 +template <typename Param>
7.156 +void checkMaxCliqueGridGraph(int max_sel, Param rule) {
7.157 +  GridGraph g(5, 7);
7.158 +  GridGraph::NodeMap<char> map(g);
7.159 +  GrossoLocatelliPullanMc<GridGraph> mc(g);
7.160 +  check(mc.run(max_sel, rule) == 2, "Wrong clique size");
7.161 +  check(mc.cliqueSize() == 2, "Wrong clique size");
7.162 +}
7.163 +
7.164 +
7.165 +int main() {
7.166 +  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
7.167 +  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
7.168 +  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
7.169 +
7.170 +  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
7.171 +  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
7.172 +  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
7.173 +
7.174 +  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
7.175 +  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
7.176 +  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
7.177 +
7.178 +  return 0;
7.179 +}