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