kpeter@904: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@904:  *
kpeter@904:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@904:  *
alpar@1092:  * Copyright (C) 2003-2013
kpeter@904:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@904:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@904:  *
kpeter@904:  * Permission to use, modify and distribute this software is granted
kpeter@904:  * provided that this copyright notice appears in all copies. For
kpeter@904:  * precise terms see the accompanying LICENSE file.
kpeter@904:  *
kpeter@904:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@904:  * express or implied, and with no claim as to its suitability for any
kpeter@904:  * purpose.
kpeter@904:  *
kpeter@904:  */
kpeter@904: 
kpeter@904: #ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
kpeter@904: #define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
kpeter@904: 
kpeter@904: /// \ingroup approx_algs
kpeter@904: ///
kpeter@904: /// \file
kpeter@904: /// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
kpeter@904: /// for the maximum clique problem
kpeter@904: 
kpeter@904: #include <vector>
kpeter@904: #include <limits>
kpeter@904: #include <lemon/core.h>
kpeter@904: #include <lemon/random.h>
kpeter@904: 
kpeter@904: namespace lemon {
kpeter@904: 
kpeter@904:   /// \addtogroup approx_algs
kpeter@904:   /// @{
kpeter@904: 
kpeter@904:   /// \brief Implementation of the iterated local search algorithm of Grosso,
kpeter@904:   /// Locatelli, and Pullan for the maximum clique problem
kpeter@904:   ///
kpeter@904:   /// \ref GrossoLocatelliPullanMc implements the iterated local search
kpeter@904:   /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
alpar@1053:   /// \e clique \e problem \cite grosso08maxclique.
kpeter@904:   /// It is to find the largest complete subgraph (\e clique) in an
kpeter@904:   /// undirected graph, i.e., the largest set of nodes where each
kpeter@904:   /// pair of nodes is connected.
kpeter@904:   ///
kpeter@904:   /// This class provides a simple but highly efficient and robust heuristic
kpeter@918:   /// method that quickly finds a quite large clique, but not necessarily the
kpeter@904:   /// largest one.
kpeter@918:   /// The algorithm performs a certain number of iterations to find several
kpeter@918:   /// cliques and selects the largest one among them. Various limits can be
kpeter@918:   /// specified to control the running time and the effectiveness of the
kpeter@918:   /// search process.
kpeter@904:   ///
kpeter@904:   /// \tparam GR The undirected graph type the algorithm runs on.
kpeter@904:   ///
kpeter@904:   /// \note %GrossoLocatelliPullanMc provides three different node selection
kpeter@904:   /// rules, from which the most powerful one is used by default.
kpeter@904:   /// For more information, see \ref SelectionRule.
kpeter@904:   template <typename GR>
kpeter@904:   class GrossoLocatelliPullanMc
kpeter@904:   {
kpeter@904:   public:
kpeter@904: 
kpeter@904:     /// \brief Constants for specifying the node selection rule.
kpeter@904:     ///
kpeter@904:     /// Enum type containing constants for specifying the node selection rule
kpeter@904:     /// for the \ref run() function.
kpeter@904:     ///
kpeter@904:     /// During the algorithm, nodes are selected for addition to the current
kpeter@904:     /// clique according to the applied rule.
kpeter@904:     /// In general, the PENALTY_BASED rule turned out to be the most powerful
kpeter@904:     /// and the most robust, thus it is the default option.
kpeter@904:     /// However, another selection rule can be specified using the \ref run()
kpeter@904:     /// function with the proper parameter.
kpeter@904:     enum SelectionRule {
kpeter@904: 
kpeter@904:       /// A node is selected randomly without any evaluation at each step.
kpeter@904:       RANDOM,
kpeter@904: 
kpeter@904:       /// A node of maximum degree is selected randomly at each step.
kpeter@904:       DEGREE_BASED,
kpeter@904: 
kpeter@904:       /// A node of minimum penalty is selected randomly at each step.
kpeter@904:       /// The node penalties are updated adaptively after each stage of the
kpeter@904:       /// search process.
kpeter@904:       PENALTY_BASED
kpeter@904:     };
kpeter@904: 
kpeter@918:     /// \brief Constants for the causes of search termination.
kpeter@918:     ///
kpeter@918:     /// Enum type containing constants for the different causes of search
kpeter@918:     /// termination. The \ref run() function returns one of these values.
kpeter@918:     enum TerminationCause {
kpeter@918: 
kpeter@918:       /// The iteration count limit is reached.
kpeter@918:       ITERATION_LIMIT,
kpeter@918: 
kpeter@918:       /// The step count limit is reached.
kpeter@918:       STEP_LIMIT,
kpeter@918: 
kpeter@918:       /// The clique size limit is reached.
kpeter@918:       SIZE_LIMIT
kpeter@918:     };
kpeter@918: 
kpeter@904:   private:
kpeter@904: 
kpeter@904:     TEMPLATE_GRAPH_TYPEDEFS(GR);
kpeter@904: 
kpeter@904:     typedef std::vector<int> IntVector;
kpeter@904:     typedef std::vector<char> BoolVector;
kpeter@904:     typedef std::vector<BoolVector> BoolMatrix;
kpeter@904:     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
kpeter@904: 
kpeter@918:     // The underlying graph
kpeter@904:     const GR &_graph;
kpeter@904:     IntNodeMap _id;
kpeter@904: 
kpeter@904:     // Internal matrix representation of the graph
kpeter@904:     BoolMatrix _gr;
kpeter@904:     int _n;
alpar@1092: 
kpeter@918:     // Search options
kpeter@918:     bool _delta_based_restart;
kpeter@918:     int _restart_delta_limit;
alpar@1092: 
kpeter@918:     // Search limits
kpeter@918:     int _iteration_limit;
kpeter@918:     int _step_limit;
kpeter@918:     int _size_limit;
kpeter@904: 
kpeter@904:     // The current clique
kpeter@904:     BoolVector _clique;
kpeter@904:     int _size;
kpeter@904: 
kpeter@904:     // The best clique found so far
kpeter@904:     BoolVector _best_clique;
kpeter@904:     int _best_size;
kpeter@904: 
kpeter@904:     // The "distances" of the nodes from the current clique.
kpeter@904:     // _delta[u] is the number of nodes in the clique that are
kpeter@904:     // not connected with u.
kpeter@904:     IntVector _delta;
kpeter@904: 
kpeter@904:     // The current tabu set
kpeter@904:     BoolVector _tabu;
kpeter@904: 
kpeter@904:     // Random number generator
kpeter@904:     Random _rnd;
kpeter@904: 
kpeter@904:   private:
kpeter@904: 
kpeter@904:     // Implementation of the RANDOM node selection rule.
kpeter@904:     class RandomSelectionRule
kpeter@904:     {
kpeter@904:     private:
kpeter@904: 
kpeter@904:       // References to the algorithm instance
kpeter@904:       const BoolVector &_clique;
kpeter@904:       const IntVector  &_delta;
kpeter@904:       const BoolVector &_tabu;
kpeter@904:       Random &_rnd;
kpeter@904: 
kpeter@904:       // Pivot rule data
kpeter@904:       int _n;
kpeter@904: 
kpeter@904:     public:
kpeter@904: 
kpeter@904:       // Constructor
kpeter@904:       RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904:         _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904:         _rnd(mc._rnd), _n(mc._n)
kpeter@904:       {}
kpeter@904: 
kpeter@904:       // Return a node index for a feasible add move or -1 if no one exists
kpeter@904:       int nextFeasibleAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i]) return i;
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i]) return i;
kpeter@904:         }
kpeter@904:         return -1;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904:       int nextFeasibleSwapNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
kpeter@904:         }
kpeter@904:         return -1;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for an add move or -1 if no one exists
kpeter@904:       int nextAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0) return i;
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0) return i;
kpeter@904:         }
kpeter@904:         return -1;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Update internal data structures between stages (if necessary)
kpeter@904:       void update() {}
kpeter@904: 
kpeter@904:     }; //class RandomSelectionRule
kpeter@904: 
kpeter@904: 
kpeter@904:     // Implementation of the DEGREE_BASED node selection rule.
kpeter@904:     class DegreeBasedSelectionRule
kpeter@904:     {
kpeter@904:     private:
kpeter@904: 
kpeter@904:       // References to the algorithm instance
kpeter@904:       const BoolVector &_clique;
kpeter@904:       const IntVector  &_delta;
kpeter@904:       const BoolVector &_tabu;
kpeter@904:       Random &_rnd;
kpeter@904: 
kpeter@904:       // Pivot rule data
kpeter@904:       int _n;
kpeter@904:       IntVector _deg;
kpeter@904: 
kpeter@904:     public:
kpeter@904: 
kpeter@904:       // Constructor
kpeter@904:       DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904:         _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904:         _rnd(mc._rnd), _n(mc._n), _deg(_n)
kpeter@904:       {
kpeter@904:         for (int i = 0; i != _n; i++) {
kpeter@904:           int d = 0;
kpeter@904:           BoolVector &row = mc._gr[i];
kpeter@904:           for (int j = 0; j != _n; j++) {
kpeter@904:             if (row[j]) d++;
kpeter@904:           }
kpeter@904:           _deg[i] = d;
kpeter@904:         }
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for a feasible add move or -1 if no one exists
kpeter@904:       int nextFeasibleAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, max_deg = -1;
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904:       int nextFeasibleSwapNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, max_deg = -1;
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904:               _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904:               _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for an add move or -1 if no one exists
kpeter@904:       int nextAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, max_deg = -1;
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0 && _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0 && _deg[i] > max_deg) {
kpeter@904:             node = i;
kpeter@904:             max_deg = _deg[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Update internal data structures between stages (if necessary)
kpeter@904:       void update() {}
kpeter@904: 
kpeter@904:     }; //class DegreeBasedSelectionRule
kpeter@904: 
kpeter@904: 
kpeter@904:     // Implementation of the PENALTY_BASED node selection rule.
kpeter@904:     class PenaltyBasedSelectionRule
kpeter@904:     {
kpeter@904:     private:
kpeter@904: 
kpeter@904:       // References to the algorithm instance
kpeter@904:       const BoolVector &_clique;
kpeter@904:       const IntVector  &_delta;
kpeter@904:       const BoolVector &_tabu;
kpeter@904:       Random &_rnd;
kpeter@904: 
kpeter@904:       // Pivot rule data
kpeter@904:       int _n;
kpeter@904:       IntVector _penalty;
kpeter@904: 
kpeter@904:     public:
kpeter@904: 
kpeter@904:       // Constructor
kpeter@904:       PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
kpeter@904:         _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
kpeter@904:         _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
kpeter@904:       {}
kpeter@904: 
kpeter@904:       // Return a node index for a feasible add move or -1 if no one exists
kpeter@904:       int nextFeasibleAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for a feasible swap move or -1 if no one exists
kpeter@904:       int nextFeasibleSwapNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904:               _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
kpeter@904:               _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Return a node index for an add move or -1 if no one exists
kpeter@904:       int nextAddNode() const {
kpeter@904:         int start_node = _rnd[_n];
kpeter@904:         int node = -1, min_p = std::numeric_limits<int>::max();
kpeter@904:         for (int i = start_node; i != _n; i++) {
kpeter@904:           if (_delta[i] == 0 && _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         for (int i = 0; i != start_node; i++) {
kpeter@904:           if (_delta[i] == 0 && _penalty[i] < min_p) {
kpeter@904:             node = i;
kpeter@904:             min_p = _penalty[i];
kpeter@904:           }
kpeter@904:         }
kpeter@904:         return node;
kpeter@904:       }
kpeter@904: 
kpeter@904:       // Update internal data structures between stages (if necessary)
kpeter@904:       void update() {}
kpeter@904: 
kpeter@904:     }; //class PenaltyBasedSelectionRule
kpeter@904: 
kpeter@904:   public:
kpeter@904: 
kpeter@904:     /// \brief Constructor.
kpeter@904:     ///
kpeter@904:     /// Constructor.
kpeter@904:     /// The global \ref rnd "random number generator instance" is used
kpeter@904:     /// during the algorithm.
kpeter@904:     ///
kpeter@904:     /// \param graph The undirected graph the algorithm runs on.
kpeter@904:     GrossoLocatelliPullanMc(const GR& graph) :
kpeter@904:       _graph(graph), _id(_graph), _rnd(rnd)
kpeter@918:     {
kpeter@918:       initOptions();
kpeter@918:     }
kpeter@904: 
kpeter@904:     /// \brief Constructor with random seed.
kpeter@904:     ///
kpeter@904:     /// Constructor with random seed.
kpeter@904:     ///
kpeter@904:     /// \param graph The undirected graph the algorithm runs on.
kpeter@904:     /// \param seed Seed value for the internal random number generator
kpeter@904:     /// that is used during the algorithm.
kpeter@904:     GrossoLocatelliPullanMc(const GR& graph, int seed) :
kpeter@904:       _graph(graph), _id(_graph), _rnd(seed)
kpeter@918:     {
kpeter@918:       initOptions();
kpeter@918:     }
kpeter@904: 
kpeter@904:     /// \brief Constructor with random number generator.
kpeter@904:     ///
kpeter@904:     /// Constructor with random number generator.
kpeter@904:     ///
kpeter@904:     /// \param graph The undirected graph the algorithm runs on.
kpeter@904:     /// \param random A random number generator that is used during the
kpeter@904:     /// algorithm.
kpeter@904:     GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
kpeter@904:       _graph(graph), _id(_graph), _rnd(random)
kpeter@918:     {
kpeter@918:       initOptions();
kpeter@918:     }
kpeter@904: 
kpeter@904:     /// \name Execution Control
kpeter@918:     /// The \ref run() function can be used to execute the algorithm.\n
alpar@1092:     /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
kpeter@918:     /// \ref sizeLimit(int) can be used to specify various limits for the
kpeter@918:     /// search process.
alpar@1092: 
kpeter@904:     /// @{
alpar@1092: 
kpeter@918:     /// \brief Sets the maximum number of iterations.
kpeter@918:     ///
kpeter@918:     /// This function sets the maximum number of iterations.
kpeter@918:     /// Each iteration of the algorithm finds a maximal clique (but not
kpeter@918:     /// necessarily the largest one) by performing several search steps
kpeter@918:     /// (node selections).
kpeter@918:     ///
kpeter@918:     /// This limit controls the running time and the success of the
kpeter@918:     /// algorithm. For larger values, the algorithm runs slower, but it more
kpeter@918:     /// likely finds larger cliques. For smaller values, the algorithm is
kpeter@918:     /// faster but probably gives worse results.
alpar@1092:     ///
kpeter@918:     /// The default value is \c 1000.
kpeter@918:     /// \c -1 means that number of iterations is not limited.
kpeter@918:     ///
kpeter@918:     /// \warning You should specify a reasonable limit for the number of
kpeter@918:     /// iterations and/or the number of search steps.
kpeter@918:     ///
kpeter@918:     /// \return <tt>(*this)</tt>
kpeter@918:     ///
kpeter@918:     /// \sa stepLimit(int)
kpeter@918:     /// \sa sizeLimit(int)
kpeter@918:     GrossoLocatelliPullanMc& iterationLimit(int limit) {
kpeter@918:       _iteration_limit = limit;
kpeter@918:       return *this;
kpeter@918:     }
alpar@1092: 
kpeter@918:     /// \brief Sets the maximum number of search steps.
kpeter@918:     ///
kpeter@918:     /// This function sets the maximum number of elementary search steps.
kpeter@918:     /// Each iteration of the algorithm finds a maximal clique (but not
kpeter@918:     /// necessarily the largest one) by performing several search steps
kpeter@918:     /// (node selections).
kpeter@918:     ///
kpeter@918:     /// This limit controls the running time and the success of the
kpeter@918:     /// algorithm. For larger values, the algorithm runs slower, but it more
kpeter@918:     /// likely finds larger cliques. For smaller values, the algorithm is
kpeter@918:     /// faster but probably gives worse results.
alpar@1092:     ///
kpeter@918:     /// The default value is \c -1, which means that number of steps
kpeter@918:     /// is not limited explicitly. However, the number of iterations is
kpeter@918:     /// limited and each iteration performs a finite number of search steps.
kpeter@918:     ///
kpeter@918:     /// \warning You should specify a reasonable limit for the number of
kpeter@918:     /// iterations and/or the number of search steps.
kpeter@918:     ///
kpeter@918:     /// \return <tt>(*this)</tt>
kpeter@918:     ///
kpeter@918:     /// \sa iterationLimit(int)
kpeter@918:     /// \sa sizeLimit(int)
kpeter@918:     GrossoLocatelliPullanMc& stepLimit(int limit) {
kpeter@918:       _step_limit = limit;
kpeter@918:       return *this;
kpeter@918:     }
alpar@1092: 
kpeter@918:     /// \brief Sets the desired clique size.
kpeter@918:     ///
kpeter@918:     /// This function sets the desired clique size that serves as a search
kpeter@918:     /// limit. If a clique of this size (or a larger one) is found, then the
kpeter@918:     /// algorithm terminates.
alpar@1092:     ///
kpeter@918:     /// This function is especially useful if you know an exact upper bound
alpar@1092:     /// for the size of the cliques in the graph or if any clique above
kpeter@918:     /// a certain size limit is sufficient for your application.
alpar@1092:     ///
kpeter@918:     /// The default value is \c -1, which means that the size limit is set to
kpeter@918:     /// the number of nodes in the graph.
kpeter@918:     ///
kpeter@918:     /// \return <tt>(*this)</tt>
kpeter@918:     ///
kpeter@918:     /// \sa iterationLimit(int)
kpeter@918:     /// \sa stepLimit(int)
kpeter@918:     GrossoLocatelliPullanMc& sizeLimit(int limit) {
kpeter@918:       _size_limit = limit;
kpeter@918:       return *this;
kpeter@918:     }
alpar@1092: 
kpeter@918:     /// \brief The maximum number of iterations.
kpeter@918:     ///
kpeter@918:     /// This function gives back the maximum number of iterations.
kpeter@918:     /// \c -1 means that no limit is specified.
kpeter@918:     ///
kpeter@918:     /// \sa iterationLimit(int)
kpeter@918:     int iterationLimit() const {
kpeter@918:       return _iteration_limit;
kpeter@918:     }
alpar@1092: 
kpeter@918:     /// \brief The maximum number of search steps.
kpeter@918:     ///
kpeter@918:     /// This function gives back the maximum number of search steps.
kpeter@918:     /// \c -1 means that no limit is specified.
kpeter@918:     ///
kpeter@918:     /// \sa stepLimit(int)
kpeter@918:     int stepLimit() const {
kpeter@918:       return _step_limit;
kpeter@918:     }
alpar@1092: 
kpeter@918:     /// \brief The desired clique size.
kpeter@918:     ///
kpeter@918:     /// This function gives back the desired clique size that serves as a
kpeter@918:     /// search limit. \c -1 means that this limit is set to the number of
kpeter@918:     /// nodes in the graph.
kpeter@918:     ///
kpeter@918:     /// \sa sizeLimit(int)
kpeter@918:     int sizeLimit() const {
kpeter@918:       return _size_limit;
kpeter@918:     }
kpeter@904: 
kpeter@904:     /// \brief Runs the algorithm.
kpeter@904:     ///
kpeter@918:     /// This function runs the algorithm. If one of the specified limits
kpeter@918:     /// is reached, the search process terminates.
kpeter@904:     ///
kpeter@904:     /// \param rule The node selection rule. For more information, see
kpeter@904:     /// \ref SelectionRule.
kpeter@904:     ///
kpeter@918:     /// \return The termination cause of the search. For more information,
kpeter@918:     /// see \ref TerminationCause.
kpeter@918:     TerminationCause run(SelectionRule rule = PENALTY_BASED)
kpeter@904:     {
kpeter@904:       init();
kpeter@904:       switch (rule) {
kpeter@904:         case RANDOM:
kpeter@918:           return start<RandomSelectionRule>();
kpeter@904:         case DEGREE_BASED:
kpeter@918:           return start<DegreeBasedSelectionRule>();
kpeter@918:         default:
kpeter@918:           return start<PenaltyBasedSelectionRule>();
kpeter@904:       }
kpeter@904:     }
kpeter@904: 
kpeter@904:     /// @}
kpeter@904: 
kpeter@904:     /// \name Query Functions
kpeter@918:     /// The results of the algorithm can be obtained using these functions.\n
alpar@1092:     /// The run() function must be called before using them.
kpeter@918: 
kpeter@904:     /// @{
kpeter@904: 
kpeter@904:     /// \brief The size of the found clique
kpeter@904:     ///
kpeter@904:     /// This function returns the size of the found clique.
kpeter@904:     ///
kpeter@904:     /// \pre run() must be called before using this function.
kpeter@904:     int cliqueSize() const {
kpeter@904:       return _best_size;
kpeter@904:     }
kpeter@904: 
kpeter@904:     /// \brief Gives back the found clique in a \c bool node map
kpeter@904:     ///
kpeter@904:     /// This function gives back the characteristic vector of the found
kpeter@904:     /// clique in the given node map.
kpeter@904:     /// It must be a \ref concepts::WriteMap "writable" node map with
kpeter@904:     /// \c bool (or convertible) value type.
kpeter@904:     ///
kpeter@904:     /// \pre run() must be called before using this function.
kpeter@904:     template <typename CliqueMap>
kpeter@904:     void cliqueMap(CliqueMap &map) const {
kpeter@904:       for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@904:         map[n] = static_cast<bool>(_best_clique[_id[n]]);
kpeter@904:       }
kpeter@904:     }
kpeter@904: 
kpeter@904:     /// \brief Iterator to list the nodes of the found clique
kpeter@904:     ///
kpeter@904:     /// This iterator class lists the nodes of the found clique.
kpeter@904:     /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
kpeter@904:     /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
kpeter@904:     ///
kpeter@904:     /// The following example prints out the IDs of the nodes in the found
kpeter@904:     /// clique.
kpeter@904:     /// \code
kpeter@904:     ///   GrossoLocatelliPullanMc<Graph> mc(g);
kpeter@904:     ///   mc.run();
kpeter@904:     ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
kpeter@904:     ///        n != INVALID; ++n)
kpeter@904:     ///   {
kpeter@904:     ///     std::cout << g.id(n) << std::endl;
kpeter@904:     ///   }
kpeter@904:     /// \endcode
kpeter@904:     class CliqueNodeIt
kpeter@904:     {
kpeter@904:     private:
kpeter@904:       NodeIt _it;
kpeter@904:       BoolNodeMap _map;
kpeter@904: 
kpeter@904:     public:
kpeter@904: 
kpeter@904:       /// Constructor
kpeter@904: 
kpeter@904:       /// Constructor.
kpeter@904:       /// \param mc The algorithm instance.
kpeter@904:       CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
kpeter@904:        : _map(mc._graph)
kpeter@904:       {
kpeter@904:         mc.cliqueMap(_map);
kpeter@904:         for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
kpeter@904:       }
kpeter@904: 
kpeter@904:       /// Conversion to \c Node
kpeter@904:       operator Node() const { return _it; }
kpeter@904: 
kpeter@904:       bool operator==(Invalid) const { return _it == INVALID; }
kpeter@904:       bool operator!=(Invalid) const { return _it != INVALID; }
kpeter@904: 
kpeter@904:       /// Next node
kpeter@904:       CliqueNodeIt &operator++() {
kpeter@904:         for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
kpeter@904:         return *this;
kpeter@904:       }
kpeter@904: 
kpeter@904:       /// Postfix incrementation
kpeter@904: 
kpeter@904:       /// Postfix incrementation.
kpeter@904:       ///
kpeter@904:       /// \warning This incrementation returns a \c Node, not a
kpeter@904:       /// \c CliqueNodeIt as one may expect.
kpeter@904:       typename GR::Node operator++(int) {
kpeter@904:         Node n=*this;
kpeter@904:         ++(*this);
kpeter@904:         return n;
kpeter@904:       }
kpeter@904: 
kpeter@904:     };
kpeter@904: 
kpeter@904:     /// @}
kpeter@904: 
kpeter@904:   private:
alpar@1092: 
kpeter@918:     // Initialize search options and limits
kpeter@918:     void initOptions() {
kpeter@918:       // Search options
kpeter@918:       _delta_based_restart = true;
kpeter@918:       _restart_delta_limit = 4;
alpar@1092: 
kpeter@918:       // Search limits
kpeter@918:       _iteration_limit = 1000;
kpeter@918:       _step_limit = -1;             // this is disabled by default
kpeter@918:       _size_limit = -1;             // this is disabled by default
kpeter@918:     }
kpeter@904: 
kpeter@904:     // Adds a node to the current clique
kpeter@904:     void addCliqueNode(int u) {
kpeter@904:       if (_clique[u]) return;
kpeter@904:       _clique[u] = true;
kpeter@904:       _size++;
kpeter@904:       BoolVector &row = _gr[u];
kpeter@904:       for (int i = 0; i != _n; i++) {
kpeter@904:         if (!row[i]) _delta[i]++;
kpeter@904:       }
kpeter@904:     }
kpeter@904: 
kpeter@904:     // Removes a node from the current clique
kpeter@904:     void delCliqueNode(int u) {
kpeter@904:       if (!_clique[u]) return;
kpeter@904:       _clique[u] = false;
kpeter@904:       _size--;
kpeter@904:       BoolVector &row = _gr[u];
kpeter@904:       for (int i = 0; i != _n; i++) {
kpeter@904:         if (!row[i]) _delta[i]--;
kpeter@904:       }
kpeter@904:     }
kpeter@904: 
kpeter@904:     // Initialize data structures
kpeter@904:     void init() {
kpeter@904:       _n = countNodes(_graph);
kpeter@904:       int ui = 0;
kpeter@904:       for (NodeIt u(_graph); u != INVALID; ++u) {
kpeter@904:         _id[u] = ui++;
kpeter@904:       }
kpeter@904:       _gr.clear();
kpeter@904:       _gr.resize(_n, BoolVector(_n, false));
kpeter@904:       ui = 0;
kpeter@904:       for (NodeIt u(_graph); u != INVALID; ++u) {
kpeter@904:         for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
kpeter@904:           int vi = _id[_graph.runningNode(e)];
kpeter@904:           _gr[ui][vi] = true;
kpeter@904:           _gr[vi][ui] = true;
kpeter@904:         }
kpeter@904:         ++ui;
kpeter@904:       }
kpeter@904: 
kpeter@904:       _clique.clear();
kpeter@904:       _clique.resize(_n, false);
kpeter@904:       _size = 0;
kpeter@904:       _best_clique.clear();
kpeter@904:       _best_clique.resize(_n, false);
kpeter@904:       _best_size = 0;
kpeter@904:       _delta.clear();
kpeter@904:       _delta.resize(_n, 0);
kpeter@904:       _tabu.clear();
kpeter@904:       _tabu.resize(_n, false);
kpeter@904:     }
kpeter@904: 
kpeter@904:     // Executes the algorithm
kpeter@904:     template <typename SelectionRuleImpl>
kpeter@918:     TerminationCause start() {
kpeter@918:       if (_n == 0) return SIZE_LIMIT;
kpeter@904:       if (_n == 1) {
kpeter@904:         _best_clique[0] = true;
kpeter@904:         _best_size = 1;
kpeter@918:         return SIZE_LIMIT;
kpeter@904:       }
kpeter@904: 
kpeter@918:       // Iterated local search algorithm
kpeter@918:       const int max_size = _size_limit >= 0 ? _size_limit : _n;
kpeter@918:       const int max_restart = _iteration_limit >= 0 ?
kpeter@918:         _iteration_limit : std::numeric_limits<int>::max();
kpeter@918:       const int max_select = _step_limit >= 0 ?
kpeter@918:         _step_limit : std::numeric_limits<int>::max();
kpeter@918: 
kpeter@904:       SelectionRuleImpl sel_method(*this);
kpeter@918:       int select = 0, restart = 0;
kpeter@904:       IntVector restart_nodes;
kpeter@918:       while (select < max_select && restart < max_restart) {
kpeter@904: 
kpeter@904:         // Perturbation/restart
kpeter@918:         restart++;
kpeter@918:         if (_delta_based_restart) {
kpeter@904:           restart_nodes.clear();
kpeter@904:           for (int i = 0; i != _n; i++) {
kpeter@918:             if (_delta[i] >= _restart_delta_limit)
kpeter@904:               restart_nodes.push_back(i);
kpeter@904:           }
kpeter@904:         }
kpeter@904:         int rs_node = -1;
kpeter@904:         if (restart_nodes.size() > 0) {
kpeter@904:           rs_node = restart_nodes[_rnd[restart_nodes.size()]];
kpeter@904:         } else {
kpeter@904:           rs_node = _rnd[_n];
kpeter@904:         }
kpeter@904:         BoolVector &row = _gr[rs_node];
kpeter@904:         for (int i = 0; i != _n; i++) {
kpeter@904:           if (_clique[i] && !row[i]) delCliqueNode(i);
kpeter@904:         }
kpeter@904:         addCliqueNode(rs_node);
kpeter@904: 
kpeter@904:         // Local search
kpeter@904:         _tabu.clear();
kpeter@904:         _tabu.resize(_n, false);
kpeter@904:         bool tabu_empty = true;
kpeter@904:         int max_swap = _size;
kpeter@904:         while (select < max_select) {
kpeter@904:           select++;
kpeter@904:           int u;
kpeter@904:           if ((u = sel_method.nextFeasibleAddNode()) != -1) {
kpeter@904:             // Feasible add move
kpeter@904:             addCliqueNode(u);
kpeter@904:             if (tabu_empty) max_swap = _size;
kpeter@904:           }
kpeter@904:           else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
kpeter@904:             // Feasible swap move
kpeter@904:             int v = -1;
kpeter@904:             BoolVector &row = _gr[u];
kpeter@904:             for (int i = 0; i != _n; i++) {
kpeter@904:               if (_clique[i] && !row[i]) {
kpeter@904:                 v = i;
kpeter@904:                 break;
kpeter@904:               }
kpeter@904:             }
kpeter@904:             addCliqueNode(u);
kpeter@904:             delCliqueNode(v);
kpeter@904:             _tabu[v] = true;
kpeter@904:             tabu_empty = false;
kpeter@904:             if (--max_swap <= 0) break;
kpeter@904:           }
kpeter@904:           else if ((u = sel_method.nextAddNode()) != -1) {
kpeter@904:             // Non-feasible add move
kpeter@904:             addCliqueNode(u);
kpeter@904:           }
kpeter@904:           else break;
kpeter@904:         }
kpeter@904:         if (_size > _best_size) {
kpeter@904:           _best_clique = _clique;
kpeter@904:           _best_size = _size;
kpeter@918:           if (_best_size >= max_size) return SIZE_LIMIT;
kpeter@904:         }
kpeter@904:         sel_method.update();
kpeter@904:       }
kpeter@904: 
kpeter@918:       return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
kpeter@904:     }
kpeter@904: 
kpeter@904:   }; //class GrossoLocatelliPullanMc
kpeter@904: 
kpeter@904:   ///@}
kpeter@904: 
kpeter@904: } //namespace lemon
kpeter@904: 
kpeter@904: #endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H