lemon/grosso_locatelli_pullan_mc.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 08 Jan 2011 22:49:09 +0100
changeset 1032 62ba43576f85
child 918 8583fb74238c
permissions -rw-r--r--
Doc group for TSP algorithms (#386)
kpeter@904
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@904
     2
 *
kpeter@904
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@904
     4
 *
kpeter@904
     5
 * Copyright (C) 2003-2010
kpeter@904
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@904
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@904
     8
 *
kpeter@904
     9
 * Permission to use, modify and distribute this software is granted
kpeter@904
    10
 * provided that this copyright notice appears in all copies. For
kpeter@904
    11
 * precise terms see the accompanying LICENSE file.
kpeter@904
    12
 *
kpeter@904
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@904
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@904
    15
 * purpose.
kpeter@904
    16
 *
kpeter@904
    17
 */
kpeter@904
    18
kpeter@904
    19
#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
kpeter@904
    20
#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
kpeter@904
    21
kpeter@904
    22
/// \ingroup approx_algs
kpeter@904
    23
///
kpeter@904
    24
/// \file
kpeter@904
    25
/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
kpeter@904
    26
/// for the maximum clique problem
kpeter@904
    27
kpeter@904
    28
#include <vector>
kpeter@904
    29
#include <limits>
kpeter@904
    30
#include <lemon/core.h>
kpeter@904
    31
#include <lemon/random.h>
kpeter@904
    32
kpeter@904
    33
namespace lemon {
kpeter@904
    34
kpeter@904
    35
  /// \addtogroup approx_algs
kpeter@904
    36
  /// @{
kpeter@904
    37
kpeter@904
    38
  /// \brief Implementation of the iterated local search algorithm of Grosso,
kpeter@904
    39
  /// Locatelli, and Pullan for the maximum clique problem
kpeter@904
    40
  ///
kpeter@904
    41
  /// \ref GrossoLocatelliPullanMc implements the iterated local search
kpeter@904
    42
  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
kpeter@904
    43
  /// \e clique \e problem \ref grosso08maxclique.
kpeter@904
    44
  /// It is to find the largest complete subgraph (\e clique) in an
kpeter@904
    45
  /// undirected graph, i.e., the largest set of nodes where each
kpeter@904
    46
  /// pair of nodes is connected.
kpeter@904
    47
  ///
kpeter@904
    48
  /// This class provides a simple but highly efficient and robust heuristic
kpeter@904
    49
  /// method that quickly finds a large clique, but not necessarily the
kpeter@904
    50
  /// largest one.
kpeter@904
    51
  ///
kpeter@904
    52
  /// \tparam GR The undirected graph type the algorithm runs on.
kpeter@904
    53
  ///
kpeter@904
    54
  /// \note %GrossoLocatelliPullanMc provides three different node selection
kpeter@904
    55
  /// rules, from which the most powerful one is used by default.
kpeter@904
    56
  /// For more information, see \ref SelectionRule.
kpeter@904
    57
  template <typename GR>
kpeter@904
    58
  class GrossoLocatelliPullanMc
kpeter@904
    59
  {
kpeter@904
    60
  public:
kpeter@904
    61
kpeter@904
    62
    /// \brief Constants for specifying the node selection rule.
kpeter@904
    63
    ///
kpeter@904
    64
    /// Enum type containing constants for specifying the node selection rule
kpeter@904
    65
    /// for the \ref run() function.
kpeter@904
    66
    ///
kpeter@904
    67
    /// During the algorithm, nodes are selected for addition to the current
kpeter@904
    68
    /// clique according to the applied rule.
kpeter@904
    69
    /// In general, the PENALTY_BASED rule turned out to be the most powerful
kpeter@904
    70
    /// and the most robust, thus it is the default option.
kpeter@904
    71
    /// However, another selection rule can be specified using the \ref run()
kpeter@904
    72
    /// function with the proper parameter.
kpeter@904
    73
    enum SelectionRule {
kpeter@904
    74
kpeter@904
    75
      /// A node is selected randomly without any evaluation at each step.
kpeter@904
    76
      RANDOM,
kpeter@904
    77
kpeter@904
    78
      /// A node of maximum degree is selected randomly at each step.
kpeter@904
    79
      DEGREE_BASED,
kpeter@904
    80
kpeter@904
    81
      /// A node of minimum penalty is selected randomly at each step.
kpeter@904
    82
      /// The node penalties are updated adaptively after each stage of the
kpeter@904
    83
      /// search process.
kpeter@904
    84
      PENALTY_BASED
kpeter@904
    85
    };
kpeter@904
    86
kpeter@904
    87
  private:
kpeter@904
    88
kpeter@904
    89
    TEMPLATE_GRAPH_TYPEDEFS(GR);
kpeter@904
    90
kpeter@904
    91
    typedef std::vector<int> IntVector;
kpeter@904
    92
    typedef std::vector<char> BoolVector;
kpeter@904
    93
    typedef std::vector<BoolVector> BoolMatrix;
kpeter@904
    94
    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
kpeter@904
    95
kpeter@904
    96
    const GR &_graph;
kpeter@904
    97
    IntNodeMap _id;
kpeter@904
    98
kpeter@904
    99
    // Internal matrix representation of the graph
kpeter@904
   100
    BoolMatrix _gr;
kpeter@904
   101
    int _n;
kpeter@904
   102
kpeter@904
   103
    // The current clique
kpeter@904
   104
    BoolVector _clique;
kpeter@904
   105
    int _size;
kpeter@904
   106
kpeter@904
   107
    // The best clique found so far
kpeter@904
   108
    BoolVector _best_clique;
kpeter@904
   109
    int _best_size;
kpeter@904
   110
kpeter@904
   111
    // The "distances" of the nodes from the current clique.
kpeter@904
   112
    // _delta[u] is the number of nodes in the clique that are
kpeter@904
   113
    // not connected with u.
kpeter@904
   114
    IntVector _delta;
kpeter@904
   115
kpeter@904
   116
    // The current tabu set
kpeter@904
   117
    BoolVector _tabu;
kpeter@904
   118
kpeter@904
   119
    // Random number generator
kpeter@904
   120
    Random _rnd;
kpeter@904
   121
kpeter@904
   122
  private:
kpeter@904
   123
kpeter@904
   124
    // Implementation of the RANDOM node selection rule.
kpeter@904
   125
    class RandomSelectionRule
kpeter@904
   126
    {
kpeter@904
   127
    private:
kpeter@904
   128
kpeter@904
   129
      // References to the algorithm instance
kpeter@904
   130
      const BoolVector &_clique;
kpeter@904
   131
      const IntVector  &_delta;
kpeter@904
   132
      const BoolVector &_tabu;
kpeter@904
   133
      Random &_rnd;
kpeter@904
   134
kpeter@904
   135
      // Pivot rule data
kpeter@904
   136
      int _n;
kpeter@904
   137
kpeter@904
   138
    public:
kpeter@904
   139
kpeter@904
   140
      // Constructor
kpeter@904
   141
      RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904
   142
        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904
   143
        _rnd(mc._rnd), _n(mc._n)
kpeter@904
   144
      {}
kpeter@904
   145
kpeter@904
   146
      // Return a node index for a feasible add move or -1 if no one exists
kpeter@904
   147
      int nextFeasibleAddNode() const {
kpeter@904
   148
        int start_node = _rnd[_n];
kpeter@904
   149
        for (int i = start_node; i != _n; i++) {
kpeter@904
   150
          if (_delta[i] == 0 && !_tabu[i]) return i;
kpeter@904
   151
        }
kpeter@904
   152
        for (int i = 0; i != start_node; i++) {
kpeter@904
   153
          if (_delta[i] == 0 && !_tabu[i]) return i;
kpeter@904
   154
        }
kpeter@904
   155
        return -1;
kpeter@904
   156
      }
kpeter@904
   157
kpeter@904
   158
      // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904
   159
      int nextFeasibleSwapNode() const {
kpeter@904
   160
        int start_node = _rnd[_n];
kpeter@904
   161
        for (int i = start_node; i != _n; i++) {
kpeter@904
   162
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
kpeter@904
   163
        }
kpeter@904
   164
        for (int i = 0; i != start_node; i++) {
kpeter@904
   165
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
kpeter@904
   166
        }
kpeter@904
   167
        return -1;
kpeter@904
   168
      }
kpeter@904
   169
kpeter@904
   170
      // Return a node index for an add move or -1 if no one exists
kpeter@904
   171
      int nextAddNode() const {
kpeter@904
   172
        int start_node = _rnd[_n];
kpeter@904
   173
        for (int i = start_node; i != _n; i++) {
kpeter@904
   174
          if (_delta[i] == 0) return i;
kpeter@904
   175
        }
kpeter@904
   176
        for (int i = 0; i != start_node; i++) {
kpeter@904
   177
          if (_delta[i] == 0) return i;
kpeter@904
   178
        }
kpeter@904
   179
        return -1;
kpeter@904
   180
      }
kpeter@904
   181
kpeter@904
   182
      // Update internal data structures between stages (if necessary)
kpeter@904
   183
      void update() {}
kpeter@904
   184
kpeter@904
   185
    }; //class RandomSelectionRule
kpeter@904
   186
kpeter@904
   187
kpeter@904
   188
    // Implementation of the DEGREE_BASED node selection rule.
kpeter@904
   189
    class DegreeBasedSelectionRule
kpeter@904
   190
    {
kpeter@904
   191
    private:
kpeter@904
   192
kpeter@904
   193
      // References to the algorithm instance
kpeter@904
   194
      const BoolVector &_clique;
kpeter@904
   195
      const IntVector  &_delta;
kpeter@904
   196
      const BoolVector &_tabu;
kpeter@904
   197
      Random &_rnd;
kpeter@904
   198
kpeter@904
   199
      // Pivot rule data
kpeter@904
   200
      int _n;
kpeter@904
   201
      IntVector _deg;
kpeter@904
   202
kpeter@904
   203
    public:
kpeter@904
   204
kpeter@904
   205
      // Constructor
kpeter@904
   206
      DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904
   207
        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904
   208
        _rnd(mc._rnd), _n(mc._n), _deg(_n)
kpeter@904
   209
      {
kpeter@904
   210
        for (int i = 0; i != _n; i++) {
kpeter@904
   211
          int d = 0;
kpeter@904
   212
          BoolVector &row = mc._gr[i];
kpeter@904
   213
          for (int j = 0; j != _n; j++) {
kpeter@904
   214
            if (row[j]) d++;
kpeter@904
   215
          }
kpeter@904
   216
          _deg[i] = d;
kpeter@904
   217
        }
kpeter@904
   218
      }
kpeter@904
   219
kpeter@904
   220
      // Return a node index for a feasible add move or -1 if no one exists
kpeter@904
   221
      int nextFeasibleAddNode() const {
kpeter@904
   222
        int start_node = _rnd[_n];
kpeter@904
   223
        int node = -1, max_deg = -1;
kpeter@904
   224
        for (int i = start_node; i != _n; i++) {
kpeter@904
   225
          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
kpeter@904
   226
            node = i;
kpeter@904
   227
            max_deg = _deg[i];
kpeter@904
   228
          }
kpeter@904
   229
        }
kpeter@904
   230
        for (int i = 0; i != start_node; i++) {
kpeter@904
   231
          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
kpeter@904
   232
            node = i;
kpeter@904
   233
            max_deg = _deg[i];
kpeter@904
   234
          }
kpeter@904
   235
        }
kpeter@904
   236
        return node;
kpeter@904
   237
      }
kpeter@904
   238
kpeter@904
   239
      // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904
   240
      int nextFeasibleSwapNode() const {
kpeter@904
   241
        int start_node = _rnd[_n];
kpeter@904
   242
        int node = -1, max_deg = -1;
kpeter@904
   243
        for (int i = start_node; i != _n; i++) {
kpeter@904
   244
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904
   245
              _deg[i] > max_deg) {
kpeter@904
   246
            node = i;
kpeter@904
   247
            max_deg = _deg[i];
kpeter@904
   248
          }
kpeter@904
   249
        }
kpeter@904
   250
        for (int i = 0; i != start_node; i++) {
kpeter@904
   251
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904
   252
              _deg[i] > max_deg) {
kpeter@904
   253
            node = i;
kpeter@904
   254
            max_deg = _deg[i];
kpeter@904
   255
          }
kpeter@904
   256
        }
kpeter@904
   257
        return node;
kpeter@904
   258
      }
kpeter@904
   259
kpeter@904
   260
      // Return a node index for an add move or -1 if no one exists
kpeter@904
   261
      int nextAddNode() const {
kpeter@904
   262
        int start_node = _rnd[_n];
kpeter@904
   263
        int node = -1, max_deg = -1;
kpeter@904
   264
        for (int i = start_node; i != _n; i++) {
kpeter@904
   265
          if (_delta[i] == 0 && _deg[i] > max_deg) {
kpeter@904
   266
            node = i;
kpeter@904
   267
            max_deg = _deg[i];
kpeter@904
   268
          }
kpeter@904
   269
        }
kpeter@904
   270
        for (int i = 0; i != start_node; i++) {
kpeter@904
   271
          if (_delta[i] == 0 && _deg[i] > max_deg) {
kpeter@904
   272
            node = i;
kpeter@904
   273
            max_deg = _deg[i];
kpeter@904
   274
          }
kpeter@904
   275
        }
kpeter@904
   276
        return node;
kpeter@904
   277
      }
kpeter@904
   278
kpeter@904
   279
      // Update internal data structures between stages (if necessary)
kpeter@904
   280
      void update() {}
kpeter@904
   281
kpeter@904
   282
    }; //class DegreeBasedSelectionRule
kpeter@904
   283
kpeter@904
   284
kpeter@904
   285
    // Implementation of the PENALTY_BASED node selection rule.
kpeter@904
   286
    class PenaltyBasedSelectionRule
kpeter@904
   287
    {
kpeter@904
   288
    private:
kpeter@904
   289
kpeter@904
   290
      // References to the algorithm instance
kpeter@904
   291
      const BoolVector &_clique;
kpeter@904
   292
      const IntVector  &_delta;
kpeter@904
   293
      const BoolVector &_tabu;
kpeter@904
   294
      Random &_rnd;
kpeter@904
   295
kpeter@904
   296
      // Pivot rule data
kpeter@904
   297
      int _n;
kpeter@904
   298
      IntVector _penalty;
kpeter@904
   299
kpeter@904
   300
    public:
kpeter@904
   301
kpeter@904
   302
      // Constructor
kpeter@904
   303
      PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904
   304
        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904
   305
        _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
kpeter@904
   306
      {}
kpeter@904
   307
kpeter@904
   308
      // Return a node index for a feasible add move or -1 if no one exists
kpeter@904
   309
      int nextFeasibleAddNode() const {
kpeter@904
   310
        int start_node = _rnd[_n];
kpeter@904
   311
        int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904
   312
        for (int i = start_node; i != _n; i++) {
kpeter@904
   313
          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
kpeter@904
   314
            node = i;
kpeter@904
   315
            min_p = _penalty[i];
kpeter@904
   316
          }
kpeter@904
   317
        }
kpeter@904
   318
        for (int i = 0; i != start_node; i++) {
kpeter@904
   319
          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
kpeter@904
   320
            node = i;
kpeter@904
   321
            min_p = _penalty[i];
kpeter@904
   322
          }
kpeter@904
   323
        }
kpeter@904
   324
        return node;
kpeter@904
   325
      }
kpeter@904
   326
kpeter@904
   327
      // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904
   328
      int nextFeasibleSwapNode() const {
kpeter@904
   329
        int start_node = _rnd[_n];
kpeter@904
   330
        int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904
   331
        for (int i = start_node; i != _n; i++) {
kpeter@904
   332
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904
   333
              _penalty[i] < min_p) {
kpeter@904
   334
            node = i;
kpeter@904
   335
            min_p = _penalty[i];
kpeter@904
   336
          }
kpeter@904
   337
        }
kpeter@904
   338
        for (int i = 0; i != start_node; i++) {
kpeter@904
   339
          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904
   340
              _penalty[i] < min_p) {
kpeter@904
   341
            node = i;
kpeter@904
   342
            min_p = _penalty[i];
kpeter@904
   343
          }
kpeter@904
   344
        }
kpeter@904
   345
        return node;
kpeter@904
   346
      }
kpeter@904
   347
kpeter@904
   348
      // Return a node index for an add move or -1 if no one exists
kpeter@904
   349
      int nextAddNode() const {
kpeter@904
   350
        int start_node = _rnd[_n];
kpeter@904
   351
        int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904
   352
        for (int i = start_node; i != _n; i++) {
kpeter@904
   353
          if (_delta[i] == 0 && _penalty[i] < min_p) {
kpeter@904
   354
            node = i;
kpeter@904
   355
            min_p = _penalty[i];
kpeter@904
   356
          }
kpeter@904
   357
        }
kpeter@904
   358
        for (int i = 0; i != start_node; i++) {
kpeter@904
   359
          if (_delta[i] == 0 && _penalty[i] < min_p) {
kpeter@904
   360
            node = i;
kpeter@904
   361
            min_p = _penalty[i];
kpeter@904
   362
          }
kpeter@904
   363
        }
kpeter@904
   364
        return node;
kpeter@904
   365
      }
kpeter@904
   366
kpeter@904
   367
      // Update internal data structures between stages (if necessary)
kpeter@904
   368
      void update() {}
kpeter@904
   369
kpeter@904
   370
    }; //class PenaltyBasedSelectionRule
kpeter@904
   371
kpeter@904
   372
  public:
kpeter@904
   373
kpeter@904
   374
    /// \brief Constructor.
kpeter@904
   375
    ///
kpeter@904
   376
    /// Constructor.
kpeter@904
   377
    /// The global \ref rnd "random number generator instance" is used
kpeter@904
   378
    /// during the algorithm.
kpeter@904
   379
    ///
kpeter@904
   380
    /// \param graph The undirected graph the algorithm runs on.
kpeter@904
   381
    GrossoLocatelliPullanMc(const GR& graph) :
kpeter@904
   382
      _graph(graph), _id(_graph), _rnd(rnd)
kpeter@904
   383
    {}
kpeter@904
   384
kpeter@904
   385
    /// \brief Constructor with random seed.
kpeter@904
   386
    ///
kpeter@904
   387
    /// Constructor with random seed.
kpeter@904
   388
    ///
kpeter@904
   389
    /// \param graph The undirected graph the algorithm runs on.
kpeter@904
   390
    /// \param seed Seed value for the internal random number generator
kpeter@904
   391
    /// that is used during the algorithm.
kpeter@904
   392
    GrossoLocatelliPullanMc(const GR& graph, int seed) :
kpeter@904
   393
      _graph(graph), _id(_graph), _rnd(seed)
kpeter@904
   394
    {}
kpeter@904
   395
kpeter@904
   396
    /// \brief Constructor with random number generator.
kpeter@904
   397
    ///
kpeter@904
   398
    /// Constructor with random number generator.
kpeter@904
   399
    ///
kpeter@904
   400
    /// \param graph The undirected graph the algorithm runs on.
kpeter@904
   401
    /// \param random A random number generator that is used during the
kpeter@904
   402
    /// algorithm.
kpeter@904
   403
    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
kpeter@904
   404
      _graph(graph), _id(_graph), _rnd(random)
kpeter@904
   405
    {}
kpeter@904
   406
kpeter@904
   407
    /// \name Execution Control
kpeter@904
   408
    /// @{
kpeter@904
   409
kpeter@904
   410
    /// \brief Runs the algorithm.
kpeter@904
   411
    ///
kpeter@904
   412
    /// This function runs the algorithm.
kpeter@904
   413
    ///
kpeter@904
   414
    /// \param step_num The maximum number of node selections (steps)
kpeter@904
   415
    /// during the search process.
kpeter@904
   416
    /// This parameter controls the running time and the success of the
kpeter@904
   417
    /// algorithm. For larger values, the algorithm runs slower but it more
kpeter@904
   418
    /// likely finds larger cliques. For smaller values, the algorithm is
kpeter@904
   419
    /// faster but probably gives worse results.
kpeter@904
   420
    /// \param rule The node selection rule. For more information, see
kpeter@904
   421
    /// \ref SelectionRule.
kpeter@904
   422
    ///
kpeter@904
   423
    /// \return The size of the found clique.
kpeter@904
   424
    int run(int step_num = 100000,
kpeter@904
   425
            SelectionRule rule = PENALTY_BASED)
kpeter@904
   426
    {
kpeter@904
   427
      init();
kpeter@904
   428
      switch (rule) {
kpeter@904
   429
        case RANDOM:
kpeter@904
   430
          return start<RandomSelectionRule>(step_num);
kpeter@904
   431
        case DEGREE_BASED:
kpeter@904
   432
          return start<DegreeBasedSelectionRule>(step_num);
kpeter@904
   433
        case PENALTY_BASED:
kpeter@904
   434
          return start<PenaltyBasedSelectionRule>(step_num);
kpeter@904
   435
      }
kpeter@904
   436
      return 0; // avoid warning
kpeter@904
   437
    }
kpeter@904
   438
kpeter@904
   439
    /// @}
kpeter@904
   440
kpeter@904
   441
    /// \name Query Functions
kpeter@904
   442
    /// @{
kpeter@904
   443
kpeter@904
   444
    /// \brief The size of the found clique
kpeter@904
   445
    ///
kpeter@904
   446
    /// This function returns the size of the found clique.
kpeter@904
   447
    ///
kpeter@904
   448
    /// \pre run() must be called before using this function.
kpeter@904
   449
    int cliqueSize() const {
kpeter@904
   450
      return _best_size;
kpeter@904
   451
    }
kpeter@904
   452
kpeter@904
   453
    /// \brief Gives back the found clique in a \c bool node map
kpeter@904
   454
    ///
kpeter@904
   455
    /// This function gives back the characteristic vector of the found
kpeter@904
   456
    /// clique in the given node map.
kpeter@904
   457
    /// It must be a \ref concepts::WriteMap "writable" node map with
kpeter@904
   458
    /// \c bool (or convertible) value type.
kpeter@904
   459
    ///
kpeter@904
   460
    /// \pre run() must be called before using this function.
kpeter@904
   461
    template <typename CliqueMap>
kpeter@904
   462
    void cliqueMap(CliqueMap &map) const {
kpeter@904
   463
      for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@904
   464
        map[n] = static_cast<bool>(_best_clique[_id[n]]);
kpeter@904
   465
      }
kpeter@904
   466
    }
kpeter@904
   467
kpeter@904
   468
    /// \brief Iterator to list the nodes of the found clique
kpeter@904
   469
    ///
kpeter@904
   470
    /// This iterator class lists the nodes of the found clique.
kpeter@904
   471
    /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
kpeter@904
   472
    /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
kpeter@904
   473
    ///
kpeter@904
   474
    /// The following example prints out the IDs of the nodes in the found
kpeter@904
   475
    /// clique.
kpeter@904
   476
    /// \code
kpeter@904
   477
    ///   GrossoLocatelliPullanMc<Graph> mc(g);
kpeter@904
   478
    ///   mc.run();
kpeter@904
   479
    ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
kpeter@904
   480
    ///        n != INVALID; ++n)
kpeter@904
   481
    ///   {
kpeter@904
   482
    ///     std::cout << g.id(n) << std::endl;
kpeter@904
   483
    ///   }
kpeter@904
   484
    /// \endcode
kpeter@904
   485
    class CliqueNodeIt
kpeter@904
   486
    {
kpeter@904
   487
    private:
kpeter@904
   488
      NodeIt _it;
kpeter@904
   489
      BoolNodeMap _map;
kpeter@904
   490
kpeter@904
   491
    public:
kpeter@904
   492
kpeter@904
   493
      /// Constructor
kpeter@904
   494
kpeter@904
   495
      /// Constructor.
kpeter@904
   496
      /// \param mc The algorithm instance.
kpeter@904
   497
      CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
kpeter@904
   498
       : _map(mc._graph)
kpeter@904
   499
      {
kpeter@904
   500
        mc.cliqueMap(_map);
kpeter@904
   501
        for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
kpeter@904
   502
      }
kpeter@904
   503
kpeter@904
   504
      /// Conversion to \c Node
kpeter@904
   505
      operator Node() const { return _it; }
kpeter@904
   506
kpeter@904
   507
      bool operator==(Invalid) const { return _it == INVALID; }
kpeter@904
   508
      bool operator!=(Invalid) const { return _it != INVALID; }
kpeter@904
   509
kpeter@904
   510
      /// Next node
kpeter@904
   511
      CliqueNodeIt &operator++() {
kpeter@904
   512
        for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
kpeter@904
   513
        return *this;
kpeter@904
   514
      }
kpeter@904
   515
kpeter@904
   516
      /// Postfix incrementation
kpeter@904
   517
kpeter@904
   518
      /// Postfix incrementation.
kpeter@904
   519
      ///
kpeter@904
   520
      /// \warning This incrementation returns a \c Node, not a
kpeter@904
   521
      /// \c CliqueNodeIt as one may expect.
kpeter@904
   522
      typename GR::Node operator++(int) {
kpeter@904
   523
        Node n=*this;
kpeter@904
   524
        ++(*this);
kpeter@904
   525
        return n;
kpeter@904
   526
      }
kpeter@904
   527
kpeter@904
   528
    };
kpeter@904
   529
kpeter@904
   530
    /// @}
kpeter@904
   531
kpeter@904
   532
  private:
kpeter@904
   533
kpeter@904
   534
    // Adds a node to the current clique
kpeter@904
   535
    void addCliqueNode(int u) {
kpeter@904
   536
      if (_clique[u]) return;
kpeter@904
   537
      _clique[u] = true;
kpeter@904
   538
      _size++;
kpeter@904
   539
      BoolVector &row = _gr[u];
kpeter@904
   540
      for (int i = 0; i != _n; i++) {
kpeter@904
   541
        if (!row[i]) _delta[i]++;
kpeter@904
   542
      }
kpeter@904
   543
    }
kpeter@904
   544
kpeter@904
   545
    // Removes a node from the current clique
kpeter@904
   546
    void delCliqueNode(int u) {
kpeter@904
   547
      if (!_clique[u]) return;
kpeter@904
   548
      _clique[u] = false;
kpeter@904
   549
      _size--;
kpeter@904
   550
      BoolVector &row = _gr[u];
kpeter@904
   551
      for (int i = 0; i != _n; i++) {
kpeter@904
   552
        if (!row[i]) _delta[i]--;
kpeter@904
   553
      }
kpeter@904
   554
    }
kpeter@904
   555
kpeter@904
   556
    // Initialize data structures
kpeter@904
   557
    void init() {
kpeter@904
   558
      _n = countNodes(_graph);
kpeter@904
   559
      int ui = 0;
kpeter@904
   560
      for (NodeIt u(_graph); u != INVALID; ++u) {
kpeter@904
   561
        _id[u] = ui++;
kpeter@904
   562
      }
kpeter@904
   563
      _gr.clear();
kpeter@904
   564
      _gr.resize(_n, BoolVector(_n, false));
kpeter@904
   565
      ui = 0;
kpeter@904
   566
      for (NodeIt u(_graph); u != INVALID; ++u) {
kpeter@904
   567
        for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
kpeter@904
   568
          int vi = _id[_graph.runningNode(e)];
kpeter@904
   569
          _gr[ui][vi] = true;
kpeter@904
   570
          _gr[vi][ui] = true;
kpeter@904
   571
        }
kpeter@904
   572
        ++ui;
kpeter@904
   573
      }
kpeter@904
   574
kpeter@904
   575
      _clique.clear();
kpeter@904
   576
      _clique.resize(_n, false);
kpeter@904
   577
      _size = 0;
kpeter@904
   578
      _best_clique.clear();
kpeter@904
   579
      _best_clique.resize(_n, false);
kpeter@904
   580
      _best_size = 0;
kpeter@904
   581
      _delta.clear();
kpeter@904
   582
      _delta.resize(_n, 0);
kpeter@904
   583
      _tabu.clear();
kpeter@904
   584
      _tabu.resize(_n, false);
kpeter@904
   585
    }
kpeter@904
   586
kpeter@904
   587
    // Executes the algorithm
kpeter@904
   588
    template <typename SelectionRuleImpl>
kpeter@904
   589
    int start(int max_select) {
kpeter@904
   590
      // Options for the restart rule
kpeter@904
   591
      const bool delta_based_restart = true;
kpeter@904
   592
      const int restart_delta_limit = 4;
kpeter@904
   593
kpeter@904
   594
      if (_n == 0) return 0;
kpeter@904
   595
      if (_n == 1) {
kpeter@904
   596
        _best_clique[0] = true;
kpeter@904
   597
        _best_size = 1;
kpeter@904
   598
        return _best_size;
kpeter@904
   599
      }
kpeter@904
   600
kpeter@904
   601
      // Iterated local search
kpeter@904
   602
      SelectionRuleImpl sel_method(*this);
kpeter@904
   603
      int select = 0;
kpeter@904
   604
      IntVector restart_nodes;
kpeter@904
   605
kpeter@904
   606
      while (select < max_select) {
kpeter@904
   607
kpeter@904
   608
        // Perturbation/restart
kpeter@904
   609
        if (delta_based_restart) {
kpeter@904
   610
          restart_nodes.clear();
kpeter@904
   611
          for (int i = 0; i != _n; i++) {
kpeter@904
   612
            if (_delta[i] >= restart_delta_limit)
kpeter@904
   613
              restart_nodes.push_back(i);
kpeter@904
   614
          }
kpeter@904
   615
        }
kpeter@904
   616
        int rs_node = -1;
kpeter@904
   617
        if (restart_nodes.size() > 0) {
kpeter@904
   618
          rs_node = restart_nodes[_rnd[restart_nodes.size()]];
kpeter@904
   619
        } else {
kpeter@904
   620
          rs_node = _rnd[_n];
kpeter@904
   621
        }
kpeter@904
   622
        BoolVector &row = _gr[rs_node];
kpeter@904
   623
        for (int i = 0; i != _n; i++) {
kpeter@904
   624
          if (_clique[i] && !row[i]) delCliqueNode(i);
kpeter@904
   625
        }
kpeter@904
   626
        addCliqueNode(rs_node);
kpeter@904
   627
kpeter@904
   628
        // Local search
kpeter@904
   629
        _tabu.clear();
kpeter@904
   630
        _tabu.resize(_n, false);
kpeter@904
   631
        bool tabu_empty = true;
kpeter@904
   632
        int max_swap = _size;
kpeter@904
   633
        while (select < max_select) {
kpeter@904
   634
          select++;
kpeter@904
   635
          int u;
kpeter@904
   636
          if ((u = sel_method.nextFeasibleAddNode()) != -1) {
kpeter@904
   637
            // Feasible add move
kpeter@904
   638
            addCliqueNode(u);
kpeter@904
   639
            if (tabu_empty) max_swap = _size;
kpeter@904
   640
          }
kpeter@904
   641
          else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
kpeter@904
   642
            // Feasible swap move
kpeter@904
   643
            int v = -1;
kpeter@904
   644
            BoolVector &row = _gr[u];
kpeter@904
   645
            for (int i = 0; i != _n; i++) {
kpeter@904
   646
              if (_clique[i] && !row[i]) {
kpeter@904
   647
                v = i;
kpeter@904
   648
                break;
kpeter@904
   649
              }
kpeter@904
   650
            }
kpeter@904
   651
            addCliqueNode(u);
kpeter@904
   652
            delCliqueNode(v);
kpeter@904
   653
            _tabu[v] = true;
kpeter@904
   654
            tabu_empty = false;
kpeter@904
   655
            if (--max_swap <= 0) break;
kpeter@904
   656
          }
kpeter@904
   657
          else if ((u = sel_method.nextAddNode()) != -1) {
kpeter@904
   658
            // Non-feasible add move
kpeter@904
   659
            addCliqueNode(u);
kpeter@904
   660
          }
kpeter@904
   661
          else break;
kpeter@904
   662
        }
kpeter@904
   663
        if (_size > _best_size) {
kpeter@904
   664
          _best_clique = _clique;
kpeter@904
   665
          _best_size = _size;
kpeter@904
   666
          if (_best_size == _n) return _best_size;
kpeter@904
   667
        }
kpeter@904
   668
        sel_method.update();
kpeter@904
   669
      }
kpeter@904
   670
kpeter@904
   671
      return _best_size;
kpeter@904
   672
    }
kpeter@904
   673
kpeter@904
   674
  }; //class GrossoLocatelliPullanMc
kpeter@904
   675
kpeter@904
   676
  ///@}
kpeter@904
   677
kpeter@904
   678
} //namespace lemon
kpeter@904
   679
kpeter@904
   680
#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H