Add a heuristic algorithm for the max clique problem (#380)
authorPeter Kovacs <kpeter@inf.elte.hu>
Fri, 23 Jul 2010 06:29:37 +0200
changeset 999c279b19abc62
parent 989 24b3f18ed9e2
child 1000 de428ebb47ab
Add a heuristic algorithm for the max clique problem (#380)
doc/groups.dox
doc/references.bib
lemon/Makefile.am
lemon/grosso_locatelli_pullan_mc.h
test/CMakeLists.txt
test/Makefile.am
test/max_clique_test.cc
     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 +}