1.1 --- a/doc/groups.dox Tue Jun 22 16:13:00 2010 +0200
1.2 +++ b/doc/groups.dox Fri Jul 23 06:29:37 2010 +0200
1.3 @@ -551,12 +551,16 @@
1.4 */
1.5
1.6 /**
1.7 -@defgroup approx Approximation Algorithms
1.8 +@defgroup approx_algs Approximation Algorithms
1.9 @ingroup algs
1.10 \brief Approximation algorithms.
1.11
1.12 This group contains the approximation and heuristic algorithms
1.13 implemented in LEMON.
1.14 +
1.15 +<b>Maximum Clique Problem</b>
1.16 + - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
1.17 + Grosso, Locatelli, and Pullan.
1.18 */
1.19
1.20 /**
2.1 --- a/doc/references.bib Tue Jun 22 16:13:00 2010 +0200
2.2 +++ b/doc/references.bib Fri Jul 23 06:29:37 2010 +0200
2.3 @@ -297,5 +297,18 @@
2.4 school = {University College},
2.5 address = {Dublin, Ireland},
2.6 year = 1991,
2.7 - month = sep,
2.8 + month = sep
2.9 }
2.10 +
2.11 +%%%%% Other algorithms %%%%%
2.12 +
2.13 +@article{grosso08maxclique,
2.14 + author = {Andrea Grosso and Marco Locatelli and Wayne Pullan},
2.15 + title = {Simple ingredients leading to very efficient
2.16 + heuristics for the maximum clique problem},
2.17 + journal = {Journal of Heuristics},
2.18 + year = 2008,
2.19 + volume = 14,
2.20 + number = 6,
2.21 + pages = {587--612}
2.22 +}
3.1 --- a/lemon/Makefile.am Tue Jun 22 16:13:00 2010 +0200
3.2 +++ b/lemon/Makefile.am Fri Jul 23 06:29:37 2010 +0200
3.3 @@ -90,6 +90,7 @@
3.4 lemon/gomory_hu.h \
3.5 lemon/graph_to_eps.h \
3.6 lemon/grid_graph.h \
3.7 + lemon/grosso_locatelli_pullan_mc.h \
3.8 lemon/hartmann_orlin_mmc.h \
3.9 lemon/howard_mmc.h \
3.10 lemon/hypercube_graph.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/grosso_locatelli_pullan_mc.h Fri Jul 23 06:29:37 2010 +0200
4.3 @@ -0,0 +1,680 @@
4.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library.
4.7 + *
4.8 + * Copyright (C) 2003-2010
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
4.23 +#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
4.24 +
4.25 +/// \ingroup approx_algs
4.26 +///
4.27 +/// \file
4.28 +/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
4.29 +/// for the maximum clique problem
4.30 +
4.31 +#include <vector>
4.32 +#include <limits>
4.33 +#include <lemon/core.h>
4.34 +#include <lemon/random.h>
4.35 +
4.36 +namespace lemon {
4.37 +
4.38 + /// \addtogroup approx_algs
4.39 + /// @{
4.40 +
4.41 + /// \brief Implementation of the iterated local search algorithm of Grosso,
4.42 + /// Locatelli, and Pullan for the maximum clique problem
4.43 + ///
4.44 + /// \ref GrossoLocatelliPullanMc implements the iterated local search
4.45 + /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
4.46 + /// \e clique \e problem \ref grosso08maxclique.
4.47 + /// It is to find the largest complete subgraph (\e clique) in an
4.48 + /// undirected graph, i.e., the largest set of nodes where each
4.49 + /// pair of nodes is connected.
4.50 + ///
4.51 + /// This class provides a simple but highly efficient and robust heuristic
4.52 + /// method that quickly finds a large clique, but not necessarily the
4.53 + /// largest one.
4.54 + ///
4.55 + /// \tparam GR The undirected graph type the algorithm runs on.
4.56 + ///
4.57 + /// \note %GrossoLocatelliPullanMc provides three different node selection
4.58 + /// rules, from which the most powerful one is used by default.
4.59 + /// For more information, see \ref SelectionRule.
4.60 + template <typename GR>
4.61 + class GrossoLocatelliPullanMc
4.62 + {
4.63 + public:
4.64 +
4.65 + /// \brief Constants for specifying the node selection rule.
4.66 + ///
4.67 + /// Enum type containing constants for specifying the node selection rule
4.68 + /// for the \ref run() function.
4.69 + ///
4.70 + /// During the algorithm, nodes are selected for addition to the current
4.71 + /// clique according to the applied rule.
4.72 + /// In general, the PENALTY_BASED rule turned out to be the most powerful
4.73 + /// and the most robust, thus it is the default option.
4.74 + /// However, another selection rule can be specified using the \ref run()
4.75 + /// function with the proper parameter.
4.76 + enum SelectionRule {
4.77 +
4.78 + /// A node is selected randomly without any evaluation at each step.
4.79 + RANDOM,
4.80 +
4.81 + /// A node of maximum degree is selected randomly at each step.
4.82 + DEGREE_BASED,
4.83 +
4.84 + /// A node of minimum penalty is selected randomly at each step.
4.85 + /// The node penalties are updated adaptively after each stage of the
4.86 + /// search process.
4.87 + PENALTY_BASED
4.88 + };
4.89 +
4.90 + private:
4.91 +
4.92 + TEMPLATE_GRAPH_TYPEDEFS(GR);
4.93 +
4.94 + typedef std::vector<int> IntVector;
4.95 + typedef std::vector<char> BoolVector;
4.96 + typedef std::vector<BoolVector> BoolMatrix;
4.97 + // Note: vector<char> is used instead of vector<bool> for efficiency reasons
4.98 +
4.99 + const GR &_graph;
4.100 + IntNodeMap _id;
4.101 +
4.102 + // Internal matrix representation of the graph
4.103 + BoolMatrix _gr;
4.104 + int _n;
4.105 +
4.106 + // The current clique
4.107 + BoolVector _clique;
4.108 + int _size;
4.109 +
4.110 + // The best clique found so far
4.111 + BoolVector _best_clique;
4.112 + int _best_size;
4.113 +
4.114 + // The "distances" of the nodes from the current clique.
4.115 + // _delta[u] is the number of nodes in the clique that are
4.116 + // not connected with u.
4.117 + IntVector _delta;
4.118 +
4.119 + // The current tabu set
4.120 + BoolVector _tabu;
4.121 +
4.122 + // Random number generator
4.123 + Random _rnd;
4.124 +
4.125 + private:
4.126 +
4.127 + // Implementation of the RANDOM node selection rule.
4.128 + class RandomSelectionRule
4.129 + {
4.130 + private:
4.131 +
4.132 + // References to the algorithm instance
4.133 + const BoolVector &_clique;
4.134 + const IntVector &_delta;
4.135 + const BoolVector &_tabu;
4.136 + Random &_rnd;
4.137 +
4.138 + // Pivot rule data
4.139 + int _n;
4.140 +
4.141 + public:
4.142 +
4.143 + // Constructor
4.144 + RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
4.145 + _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.146 + _rnd(mc._rnd), _n(mc._n)
4.147 + {}
4.148 +
4.149 + // Return a node index for a feasible add move or -1 if no one exists
4.150 + int nextFeasibleAddNode() const {
4.151 + int start_node = _rnd[_n];
4.152 + for (int i = start_node; i != _n; i++) {
4.153 + if (_delta[i] == 0 && !_tabu[i]) return i;
4.154 + }
4.155 + for (int i = 0; i != start_node; i++) {
4.156 + if (_delta[i] == 0 && !_tabu[i]) return i;
4.157 + }
4.158 + return -1;
4.159 + }
4.160 +
4.161 + // Return a node index for a feasible swap move or -1 if no one exists
4.162 + int nextFeasibleSwapNode() const {
4.163 + int start_node = _rnd[_n];
4.164 + for (int i = start_node; i != _n; i++) {
4.165 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
4.166 + }
4.167 + for (int i = 0; i != start_node; i++) {
4.168 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
4.169 + }
4.170 + return -1;
4.171 + }
4.172 +
4.173 + // Return a node index for an add move or -1 if no one exists
4.174 + int nextAddNode() const {
4.175 + int start_node = _rnd[_n];
4.176 + for (int i = start_node; i != _n; i++) {
4.177 + if (_delta[i] == 0) return i;
4.178 + }
4.179 + for (int i = 0; i != start_node; i++) {
4.180 + if (_delta[i] == 0) return i;
4.181 + }
4.182 + return -1;
4.183 + }
4.184 +
4.185 + // Update internal data structures between stages (if necessary)
4.186 + void update() {}
4.187 +
4.188 + }; //class RandomSelectionRule
4.189 +
4.190 +
4.191 + // Implementation of the DEGREE_BASED node selection rule.
4.192 + class DegreeBasedSelectionRule
4.193 + {
4.194 + private:
4.195 +
4.196 + // References to the algorithm instance
4.197 + const BoolVector &_clique;
4.198 + const IntVector &_delta;
4.199 + const BoolVector &_tabu;
4.200 + Random &_rnd;
4.201 +
4.202 + // Pivot rule data
4.203 + int _n;
4.204 + IntVector _deg;
4.205 +
4.206 + public:
4.207 +
4.208 + // Constructor
4.209 + DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
4.210 + _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.211 + _rnd(mc._rnd), _n(mc._n), _deg(_n)
4.212 + {
4.213 + for (int i = 0; i != _n; i++) {
4.214 + int d = 0;
4.215 + BoolVector &row = mc._gr[i];
4.216 + for (int j = 0; j != _n; j++) {
4.217 + if (row[j]) d++;
4.218 + }
4.219 + _deg[i] = d;
4.220 + }
4.221 + }
4.222 +
4.223 + // Return a node index for a feasible add move or -1 if no one exists
4.224 + int nextFeasibleAddNode() const {
4.225 + int start_node = _rnd[_n];
4.226 + int node = -1, max_deg = -1;
4.227 + for (int i = start_node; i != _n; i++) {
4.228 + if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
4.229 + node = i;
4.230 + max_deg = _deg[i];
4.231 + }
4.232 + }
4.233 + for (int i = 0; i != start_node; i++) {
4.234 + if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
4.235 + node = i;
4.236 + max_deg = _deg[i];
4.237 + }
4.238 + }
4.239 + return node;
4.240 + }
4.241 +
4.242 + // Return a node index for a feasible swap move or -1 if no one exists
4.243 + int nextFeasibleSwapNode() const {
4.244 + int start_node = _rnd[_n];
4.245 + int node = -1, max_deg = -1;
4.246 + for (int i = start_node; i != _n; i++) {
4.247 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.248 + _deg[i] > max_deg) {
4.249 + node = i;
4.250 + max_deg = _deg[i];
4.251 + }
4.252 + }
4.253 + for (int i = 0; i != start_node; i++) {
4.254 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.255 + _deg[i] > max_deg) {
4.256 + node = i;
4.257 + max_deg = _deg[i];
4.258 + }
4.259 + }
4.260 + return node;
4.261 + }
4.262 +
4.263 + // Return a node index for an add move or -1 if no one exists
4.264 + int nextAddNode() const {
4.265 + int start_node = _rnd[_n];
4.266 + int node = -1, max_deg = -1;
4.267 + for (int i = start_node; i != _n; i++) {
4.268 + if (_delta[i] == 0 && _deg[i] > max_deg) {
4.269 + node = i;
4.270 + max_deg = _deg[i];
4.271 + }
4.272 + }
4.273 + for (int i = 0; i != start_node; i++) {
4.274 + if (_delta[i] == 0 && _deg[i] > max_deg) {
4.275 + node = i;
4.276 + max_deg = _deg[i];
4.277 + }
4.278 + }
4.279 + return node;
4.280 + }
4.281 +
4.282 + // Update internal data structures between stages (if necessary)
4.283 + void update() {}
4.284 +
4.285 + }; //class DegreeBasedSelectionRule
4.286 +
4.287 +
4.288 + // Implementation of the PENALTY_BASED node selection rule.
4.289 + class PenaltyBasedSelectionRule
4.290 + {
4.291 + private:
4.292 +
4.293 + // References to the algorithm instance
4.294 + const BoolVector &_clique;
4.295 + const IntVector &_delta;
4.296 + const BoolVector &_tabu;
4.297 + Random &_rnd;
4.298 +
4.299 + // Pivot rule data
4.300 + int _n;
4.301 + IntVector _penalty;
4.302 +
4.303 + public:
4.304 +
4.305 + // Constructor
4.306 + PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
4.307 + _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
4.308 + _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
4.309 + {}
4.310 +
4.311 + // Return a node index for a feasible add move or -1 if no one exists
4.312 + int nextFeasibleAddNode() const {
4.313 + int start_node = _rnd[_n];
4.314 + int node = -1, min_p = std::numeric_limits<int>::max();
4.315 + for (int i = start_node; i != _n; i++) {
4.316 + if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
4.317 + node = i;
4.318 + min_p = _penalty[i];
4.319 + }
4.320 + }
4.321 + for (int i = 0; i != start_node; i++) {
4.322 + if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
4.323 + node = i;
4.324 + min_p = _penalty[i];
4.325 + }
4.326 + }
4.327 + return node;
4.328 + }
4.329 +
4.330 + // Return a node index for a feasible swap move or -1 if no one exists
4.331 + int nextFeasibleSwapNode() const {
4.332 + int start_node = _rnd[_n];
4.333 + int node = -1, min_p = std::numeric_limits<int>::max();
4.334 + for (int i = start_node; i != _n; i++) {
4.335 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.336 + _penalty[i] < min_p) {
4.337 + node = i;
4.338 + min_p = _penalty[i];
4.339 + }
4.340 + }
4.341 + for (int i = 0; i != start_node; i++) {
4.342 + if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
4.343 + _penalty[i] < min_p) {
4.344 + node = i;
4.345 + min_p = _penalty[i];
4.346 + }
4.347 + }
4.348 + return node;
4.349 + }
4.350 +
4.351 + // Return a node index for an add move or -1 if no one exists
4.352 + int nextAddNode() const {
4.353 + int start_node = _rnd[_n];
4.354 + int node = -1, min_p = std::numeric_limits<int>::max();
4.355 + for (int i = start_node; i != _n; i++) {
4.356 + if (_delta[i] == 0 && _penalty[i] < min_p) {
4.357 + node = i;
4.358 + min_p = _penalty[i];
4.359 + }
4.360 + }
4.361 + for (int i = 0; i != start_node; i++) {
4.362 + if (_delta[i] == 0 && _penalty[i] < min_p) {
4.363 + node = i;
4.364 + min_p = _penalty[i];
4.365 + }
4.366 + }
4.367 + return node;
4.368 + }
4.369 +
4.370 + // Update internal data structures between stages (if necessary)
4.371 + void update() {}
4.372 +
4.373 + }; //class PenaltyBasedSelectionRule
4.374 +
4.375 + public:
4.376 +
4.377 + /// \brief Constructor.
4.378 + ///
4.379 + /// Constructor.
4.380 + /// The global \ref rnd "random number generator instance" is used
4.381 + /// during the algorithm.
4.382 + ///
4.383 + /// \param graph The undirected graph the algorithm runs on.
4.384 + GrossoLocatelliPullanMc(const GR& graph) :
4.385 + _graph(graph), _id(_graph), _rnd(rnd)
4.386 + {}
4.387 +
4.388 + /// \brief Constructor with random seed.
4.389 + ///
4.390 + /// Constructor with random seed.
4.391 + ///
4.392 + /// \param graph The undirected graph the algorithm runs on.
4.393 + /// \param seed Seed value for the internal random number generator
4.394 + /// that is used during the algorithm.
4.395 + GrossoLocatelliPullanMc(const GR& graph, int seed) :
4.396 + _graph(graph), _id(_graph), _rnd(seed)
4.397 + {}
4.398 +
4.399 + /// \brief Constructor with random number generator.
4.400 + ///
4.401 + /// Constructor with random number generator.
4.402 + ///
4.403 + /// \param graph The undirected graph the algorithm runs on.
4.404 + /// \param random A random number generator that is used during the
4.405 + /// algorithm.
4.406 + GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
4.407 + _graph(graph), _id(_graph), _rnd(random)
4.408 + {}
4.409 +
4.410 + /// \name Execution Control
4.411 + /// @{
4.412 +
4.413 + /// \brief Runs the algorithm.
4.414 + ///
4.415 + /// This function runs the algorithm.
4.416 + ///
4.417 + /// \param step_num The maximum number of node selections (steps)
4.418 + /// during the search process.
4.419 + /// This parameter controls the running time and the success of the
4.420 + /// algorithm. For larger values, the algorithm runs slower but it more
4.421 + /// likely finds larger cliques. For smaller values, the algorithm is
4.422 + /// faster but probably gives worse results.
4.423 + /// \param rule The node selection rule. For more information, see
4.424 + /// \ref SelectionRule.
4.425 + ///
4.426 + /// \return The size of the found clique.
4.427 + int run(int step_num = 100000,
4.428 + SelectionRule rule = PENALTY_BASED)
4.429 + {
4.430 + init();
4.431 + switch (rule) {
4.432 + case RANDOM:
4.433 + return start<RandomSelectionRule>(step_num);
4.434 + case DEGREE_BASED:
4.435 + return start<DegreeBasedSelectionRule>(step_num);
4.436 + case PENALTY_BASED:
4.437 + return start<PenaltyBasedSelectionRule>(step_num);
4.438 + }
4.439 + return 0; // avoid warning
4.440 + }
4.441 +
4.442 + /// @}
4.443 +
4.444 + /// \name Query Functions
4.445 + /// @{
4.446 +
4.447 + /// \brief The size of the found clique
4.448 + ///
4.449 + /// This function returns the size of the found clique.
4.450 + ///
4.451 + /// \pre run() must be called before using this function.
4.452 + int cliqueSize() const {
4.453 + return _best_size;
4.454 + }
4.455 +
4.456 + /// \brief Gives back the found clique in a \c bool node map
4.457 + ///
4.458 + /// This function gives back the characteristic vector of the found
4.459 + /// clique in the given node map.
4.460 + /// It must be a \ref concepts::WriteMap "writable" node map with
4.461 + /// \c bool (or convertible) value type.
4.462 + ///
4.463 + /// \pre run() must be called before using this function.
4.464 + template <typename CliqueMap>
4.465 + void cliqueMap(CliqueMap &map) const {
4.466 + for (NodeIt n(_graph); n != INVALID; ++n) {
4.467 + map[n] = static_cast<bool>(_best_clique[_id[n]]);
4.468 + }
4.469 + }
4.470 +
4.471 + /// \brief Iterator to list the nodes of the found clique
4.472 + ///
4.473 + /// This iterator class lists the nodes of the found clique.
4.474 + /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
4.475 + /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
4.476 + ///
4.477 + /// The following example prints out the IDs of the nodes in the found
4.478 + /// clique.
4.479 + /// \code
4.480 + /// GrossoLocatelliPullanMc<Graph> mc(g);
4.481 + /// mc.run();
4.482 + /// for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
4.483 + /// n != INVALID; ++n)
4.484 + /// {
4.485 + /// std::cout << g.id(n) << std::endl;
4.486 + /// }
4.487 + /// \endcode
4.488 + class CliqueNodeIt
4.489 + {
4.490 + private:
4.491 + NodeIt _it;
4.492 + BoolNodeMap _map;
4.493 +
4.494 + public:
4.495 +
4.496 + /// Constructor
4.497 +
4.498 + /// Constructor.
4.499 + /// \param mc The algorithm instance.
4.500 + CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
4.501 + : _map(mc._graph)
4.502 + {
4.503 + mc.cliqueMap(_map);
4.504 + for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
4.505 + }
4.506 +
4.507 + /// Conversion to \c Node
4.508 + operator Node() const { return _it; }
4.509 +
4.510 + bool operator==(Invalid) const { return _it == INVALID; }
4.511 + bool operator!=(Invalid) const { return _it != INVALID; }
4.512 +
4.513 + /// Next node
4.514 + CliqueNodeIt &operator++() {
4.515 + for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
4.516 + return *this;
4.517 + }
4.518 +
4.519 + /// Postfix incrementation
4.520 +
4.521 + /// Postfix incrementation.
4.522 + ///
4.523 + /// \warning This incrementation returns a \c Node, not a
4.524 + /// \c CliqueNodeIt as one may expect.
4.525 + typename GR::Node operator++(int) {
4.526 + Node n=*this;
4.527 + ++(*this);
4.528 + return n;
4.529 + }
4.530 +
4.531 + };
4.532 +
4.533 + /// @}
4.534 +
4.535 + private:
4.536 +
4.537 + // Adds a node to the current clique
4.538 + void addCliqueNode(int u) {
4.539 + if (_clique[u]) return;
4.540 + _clique[u] = true;
4.541 + _size++;
4.542 + BoolVector &row = _gr[u];
4.543 + for (int i = 0; i != _n; i++) {
4.544 + if (!row[i]) _delta[i]++;
4.545 + }
4.546 + }
4.547 +
4.548 + // Removes a node from the current clique
4.549 + void delCliqueNode(int u) {
4.550 + if (!_clique[u]) return;
4.551 + _clique[u] = false;
4.552 + _size--;
4.553 + BoolVector &row = _gr[u];
4.554 + for (int i = 0; i != _n; i++) {
4.555 + if (!row[i]) _delta[i]--;
4.556 + }
4.557 + }
4.558 +
4.559 + // Initialize data structures
4.560 + void init() {
4.561 + _n = countNodes(_graph);
4.562 + int ui = 0;
4.563 + for (NodeIt u(_graph); u != INVALID; ++u) {
4.564 + _id[u] = ui++;
4.565 + }
4.566 + _gr.clear();
4.567 + _gr.resize(_n, BoolVector(_n, false));
4.568 + ui = 0;
4.569 + for (NodeIt u(_graph); u != INVALID; ++u) {
4.570 + for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
4.571 + int vi = _id[_graph.runningNode(e)];
4.572 + _gr[ui][vi] = true;
4.573 + _gr[vi][ui] = true;
4.574 + }
4.575 + ++ui;
4.576 + }
4.577 +
4.578 + _clique.clear();
4.579 + _clique.resize(_n, false);
4.580 + _size = 0;
4.581 + _best_clique.clear();
4.582 + _best_clique.resize(_n, false);
4.583 + _best_size = 0;
4.584 + _delta.clear();
4.585 + _delta.resize(_n, 0);
4.586 + _tabu.clear();
4.587 + _tabu.resize(_n, false);
4.588 + }
4.589 +
4.590 + // Executes the algorithm
4.591 + template <typename SelectionRuleImpl>
4.592 + int start(int max_select) {
4.593 + // Options for the restart rule
4.594 + const bool delta_based_restart = true;
4.595 + const int restart_delta_limit = 4;
4.596 +
4.597 + if (_n == 0) return 0;
4.598 + if (_n == 1) {
4.599 + _best_clique[0] = true;
4.600 + _best_size = 1;
4.601 + return _best_size;
4.602 + }
4.603 +
4.604 + // Iterated local search
4.605 + SelectionRuleImpl sel_method(*this);
4.606 + int select = 0;
4.607 + IntVector restart_nodes;
4.608 +
4.609 + while (select < max_select) {
4.610 +
4.611 + // Perturbation/restart
4.612 + if (delta_based_restart) {
4.613 + restart_nodes.clear();
4.614 + for (int i = 0; i != _n; i++) {
4.615 + if (_delta[i] >= restart_delta_limit)
4.616 + restart_nodes.push_back(i);
4.617 + }
4.618 + }
4.619 + int rs_node = -1;
4.620 + if (restart_nodes.size() > 0) {
4.621 + rs_node = restart_nodes[_rnd[restart_nodes.size()]];
4.622 + } else {
4.623 + rs_node = _rnd[_n];
4.624 + }
4.625 + BoolVector &row = _gr[rs_node];
4.626 + for (int i = 0; i != _n; i++) {
4.627 + if (_clique[i] && !row[i]) delCliqueNode(i);
4.628 + }
4.629 + addCliqueNode(rs_node);
4.630 +
4.631 + // Local search
4.632 + _tabu.clear();
4.633 + _tabu.resize(_n, false);
4.634 + bool tabu_empty = true;
4.635 + int max_swap = _size;
4.636 + while (select < max_select) {
4.637 + select++;
4.638 + int u;
4.639 + if ((u = sel_method.nextFeasibleAddNode()) != -1) {
4.640 + // Feasible add move
4.641 + addCliqueNode(u);
4.642 + if (tabu_empty) max_swap = _size;
4.643 + }
4.644 + else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
4.645 + // Feasible swap move
4.646 + int v = -1;
4.647 + BoolVector &row = _gr[u];
4.648 + for (int i = 0; i != _n; i++) {
4.649 + if (_clique[i] && !row[i]) {
4.650 + v = i;
4.651 + break;
4.652 + }
4.653 + }
4.654 + addCliqueNode(u);
4.655 + delCliqueNode(v);
4.656 + _tabu[v] = true;
4.657 + tabu_empty = false;
4.658 + if (--max_swap <= 0) break;
4.659 + }
4.660 + else if ((u = sel_method.nextAddNode()) != -1) {
4.661 + // Non-feasible add move
4.662 + addCliqueNode(u);
4.663 + }
4.664 + else break;
4.665 + }
4.666 + if (_size > _best_size) {
4.667 + _best_clique = _clique;
4.668 + _best_size = _size;
4.669 + if (_best_size == _n) return _best_size;
4.670 + }
4.671 + sel_method.update();
4.672 + }
4.673 +
4.674 + return _best_size;
4.675 + }
4.676 +
4.677 + }; //class GrossoLocatelliPullanMc
4.678 +
4.679 + ///@}
4.680 +
4.681 +} //namespace lemon
4.682 +
4.683 +#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
5.1 --- a/test/CMakeLists.txt Tue Jun 22 16:13:00 2010 +0200
5.2 +++ b/test/CMakeLists.txt Fri Jul 23 06:29:37 2010 +0200
5.3 @@ -31,6 +31,7 @@
5.4 kruskal_test
5.5 maps_test
5.6 matching_test
5.7 + max_clique_test
5.8 min_cost_arborescence_test
5.9 min_cost_flow_test
5.10 min_mean_cycle_test
6.1 --- a/test/Makefile.am Tue Jun 22 16:13:00 2010 +0200
6.2 +++ b/test/Makefile.am Fri Jul 23 06:29:37 2010 +0200
6.3 @@ -33,6 +33,7 @@
6.4 test/kruskal_test \
6.5 test/maps_test \
6.6 test/matching_test \
6.7 + test/max_clique_test \
6.8 test/min_cost_arborescence_test \
6.9 test/min_cost_flow_test \
6.10 test/min_mean_cycle_test \
6.11 @@ -84,6 +85,7 @@
6.12 test_maps_test_SOURCES = test/maps_test.cc
6.13 test_mip_test_SOURCES = test/mip_test.cc
6.14 test_matching_test_SOURCES = test/matching_test.cc
6.15 +test_max_clique_test_SOURCES = test/max_clique_test.cc
6.16 test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
6.17 test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
6.18 test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
7.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
7.2 +++ b/test/max_clique_test.cc Fri Jul 23 06:29:37 2010 +0200
7.3 @@ -0,0 +1,176 @@
7.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
7.5 + *
7.6 + * This file is a part of LEMON, a generic C++ optimization library.
7.7 + *
7.8 + * Copyright (C) 2003-2010
7.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
7.11 + *
7.12 + * Permission to use, modify and distribute this software is granted
7.13 + * provided that this copyright notice appears in all copies. For
7.14 + * precise terms see the accompanying LICENSE file.
7.15 + *
7.16 + * This software is provided "AS IS" with no warranty of any kind,
7.17 + * express or implied, and with no claim as to its suitability for any
7.18 + * purpose.
7.19 + *
7.20 + */
7.21 +
7.22 +#include <sstream>
7.23 +#include <lemon/list_graph.h>
7.24 +#include <lemon/full_graph.h>
7.25 +#include <lemon/grid_graph.h>
7.26 +#include <lemon/lgf_reader.h>
7.27 +#include <lemon/grosso_locatelli_pullan_mc.h>
7.28 +
7.29 +#include "test_tools.h"
7.30 +
7.31 +using namespace lemon;
7.32 +
7.33 +char test_lgf[] =
7.34 + "@nodes\n"
7.35 + "label max_clique\n"
7.36 + "1 0\n"
7.37 + "2 0\n"
7.38 + "3 0\n"
7.39 + "4 1\n"
7.40 + "5 1\n"
7.41 + "6 1\n"
7.42 + "7 1\n"
7.43 + "@edges\n"
7.44 + " label\n"
7.45 + "1 2 1\n"
7.46 + "1 3 2\n"
7.47 + "1 4 3\n"
7.48 + "1 6 4\n"
7.49 + "2 3 5\n"
7.50 + "2 5 6\n"
7.51 + "2 7 7\n"
7.52 + "3 4 8\n"
7.53 + "3 5 9\n"
7.54 + "4 5 10\n"
7.55 + "4 6 11\n"
7.56 + "4 7 12\n"
7.57 + "5 6 13\n"
7.58 + "5 7 14\n"
7.59 + "6 7 15\n";
7.60 +
7.61 +
7.62 +// Check with general graphs
7.63 +template <typename Param>
7.64 +void checkMaxCliqueGeneral(int max_sel, Param rule) {
7.65 + typedef ListGraph GR;
7.66 + typedef GrossoLocatelliPullanMc<GR> McAlg;
7.67 + typedef McAlg::CliqueNodeIt CliqueIt;
7.68 +
7.69 + // Basic tests
7.70 + {
7.71 + GR g;
7.72 + GR::NodeMap<bool> map(g);
7.73 + McAlg mc(g);
7.74 + check(mc.run(max_sel, rule) == 0, "Wrong clique size");
7.75 + check(mc.cliqueSize() == 0, "Wrong clique size");
7.76 + check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
7.77 +
7.78 + GR::Node u = g.addNode();
7.79 + check(mc.run(max_sel, rule) == 1, "Wrong clique size");
7.80 + check(mc.cliqueSize() == 1, "Wrong clique size");
7.81 + mc.cliqueMap(map);
7.82 + check(map[u], "Wrong clique map");
7.83 + CliqueIt it1(mc);
7.84 + check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,
7.85 + "Wrong CliqueNodeIt");
7.86 +
7.87 + GR::Node v = g.addNode();
7.88 + check(mc.run(max_sel, rule) == 1, "Wrong clique size");
7.89 + check(mc.cliqueSize() == 1, "Wrong clique size");
7.90 + mc.cliqueMap(map);
7.91 + check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
7.92 + CliqueIt it2(mc);
7.93 + check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
7.94 +
7.95 + g.addEdge(u, v);
7.96 + check(mc.run(max_sel, rule) == 2, "Wrong clique size");
7.97 + check(mc.cliqueSize() == 2, "Wrong clique size");
7.98 + mc.cliqueMap(map);
7.99 + check(map[u] && map[v], "Wrong clique map");
7.100 + CliqueIt it3(mc);
7.101 + check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
7.102 + "Wrong CliqueNodeIt");
7.103 + }
7.104 +
7.105 + // Test graph
7.106 + {
7.107 + GR g;
7.108 + GR::NodeMap<bool> max_clique(g);
7.109 + GR::NodeMap<bool> map(g);
7.110 + std::istringstream input(test_lgf);
7.111 + graphReader(g, input)
7.112 + .nodeMap("max_clique", max_clique)
7.113 + .run();
7.114 +
7.115 + McAlg mc(g);
7.116 + check(mc.run(max_sel, rule) == 4, "Wrong clique size");
7.117 + check(mc.cliqueSize() == 4, "Wrong clique size");
7.118 + mc.cliqueMap(map);
7.119 + for (GR::NodeIt n(g); n != INVALID; ++n) {
7.120 + check(map[n] == max_clique[n], "Wrong clique map");
7.121 + }
7.122 + int cnt = 0;
7.123 + for (CliqueIt n(mc); n != INVALID; ++n) {
7.124 + cnt++;
7.125 + check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
7.126 + }
7.127 + check(cnt == 4, "Wrong CliqueNodeIt");
7.128 + }
7.129 +}
7.130 +
7.131 +// Check with full graphs
7.132 +template <typename Param>
7.133 +void checkMaxCliqueFullGraph(int max_sel, Param rule) {
7.134 + typedef FullGraph GR;
7.135 + typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
7.136 + typedef McAlg::CliqueNodeIt CliqueIt;
7.137 +
7.138 + for (int size = 0; size <= 40; size = size * 3 + 1) {
7.139 + GR g(size);
7.140 + GR::NodeMap<bool> map(g);
7.141 + McAlg mc(g);
7.142 + check(mc.run(max_sel, rule) == size, "Wrong clique size");
7.143 + check(mc.cliqueSize() == size, "Wrong clique size");
7.144 + mc.cliqueMap(map);
7.145 + for (GR::NodeIt n(g); n != INVALID; ++n) {
7.146 + check(map[n], "Wrong clique map");
7.147 + }
7.148 + int cnt = 0;
7.149 + for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
7.150 + check(cnt == size, "Wrong CliqueNodeIt");
7.151 + }
7.152 +}
7.153 +
7.154 +// Check with grid graphs
7.155 +template <typename Param>
7.156 +void checkMaxCliqueGridGraph(int max_sel, Param rule) {
7.157 + GridGraph g(5, 7);
7.158 + GridGraph::NodeMap<char> map(g);
7.159 + GrossoLocatelliPullanMc<GridGraph> mc(g);
7.160 + check(mc.run(max_sel, rule) == 2, "Wrong clique size");
7.161 + check(mc.cliqueSize() == 2, "Wrong clique size");
7.162 +}
7.163 +
7.164 +
7.165 +int main() {
7.166 + checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
7.167 + checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
7.168 + checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
7.169 +
7.170 + checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
7.171 + checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
7.172 + checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
7.173 +
7.174 + checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
7.175 + checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
7.176 + checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
7.177 +
7.178 + return 0;
7.179 +}