diff --git a/doc/groups.dox b/doc/groups.dox
--- a/doc/groups.dox
+++ b/doc/groups.dox
@@ -551,12 +551,16 @@
*/
/**
-@defgroup approx Approximation Algorithms
+@defgroup approx_algs Approximation Algorithms
@ingroup algs
\brief Approximation algorithms.
This group contains the approximation and heuristic algorithms
implemented in LEMON.
+
+Maximum Clique Problem
+ - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
+ Grosso, Locatelli, and Pullan.
*/
/**
diff --git a/doc/references.bib b/doc/references.bib
--- a/doc/references.bib
+++ b/doc/references.bib
@@ -297,5 +297,18 @@
school = {University College},
address = {Dublin, Ireland},
year = 1991,
- month = sep,
+ month = sep
}
+
+%%%%% Other algorithms %%%%%
+
+@article{grosso08maxclique,
+ author = {Andrea Grosso and Marco Locatelli and Wayne Pullan},
+ title = {Simple ingredients leading to very efficient
+ heuristics for the maximum clique problem},
+ journal = {Journal of Heuristics},
+ year = 2008,
+ volume = 14,
+ number = 6,
+ pages = {587--612}
+}
diff --git a/lemon/Makefile.am b/lemon/Makefile.am
--- a/lemon/Makefile.am
+++ b/lemon/Makefile.am
@@ -90,6 +90,7 @@
lemon/gomory_hu.h \
lemon/graph_to_eps.h \
lemon/grid_graph.h \
+ lemon/grosso_locatelli_pullan_mc.h \
lemon/hartmann_orlin_mmc.h \
lemon/howard_mmc.h \
lemon/hypercube_graph.h \
diff --git a/lemon/grosso_locatelli_pullan_mc.h b/lemon/grosso_locatelli_pullan_mc.h
new file mode 100644
--- /dev/null
+++ b/lemon/grosso_locatelli_pullan_mc.h
@@ -0,0 +1,680 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
+#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
+
+/// \ingroup approx_algs
+///
+/// \file
+/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
+/// for the maximum clique problem
+
+#include
+#include
+#include
+#include
+
+namespace lemon {
+
+ /// \addtogroup approx_algs
+ /// @{
+
+ /// \brief Implementation of the iterated local search algorithm of Grosso,
+ /// Locatelli, and Pullan for the maximum clique problem
+ ///
+ /// \ref GrossoLocatelliPullanMc implements the iterated local search
+ /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
+ /// \e clique \e problem \ref grosso08maxclique.
+ /// It is to find the largest complete subgraph (\e clique) in an
+ /// undirected graph, i.e., the largest set of nodes where each
+ /// pair of nodes is connected.
+ ///
+ /// This class provides a simple but highly efficient and robust heuristic
+ /// method that quickly finds a large clique, but not necessarily the
+ /// largest one.
+ ///
+ /// \tparam GR The undirected graph type the algorithm runs on.
+ ///
+ /// \note %GrossoLocatelliPullanMc provides three different node selection
+ /// rules, from which the most powerful one is used by default.
+ /// For more information, see \ref SelectionRule.
+ template
+ class GrossoLocatelliPullanMc
+ {
+ public:
+
+ /// \brief Constants for specifying the node selection rule.
+ ///
+ /// Enum type containing constants for specifying the node selection rule
+ /// for the \ref run() function.
+ ///
+ /// During the algorithm, nodes are selected for addition to the current
+ /// clique according to the applied rule.
+ /// In general, the PENALTY_BASED rule turned out to be the most powerful
+ /// and the most robust, thus it is the default option.
+ /// However, another selection rule can be specified using the \ref run()
+ /// function with the proper parameter.
+ enum SelectionRule {
+
+ /// A node is selected randomly without any evaluation at each step.
+ RANDOM,
+
+ /// A node of maximum degree is selected randomly at each step.
+ DEGREE_BASED,
+
+ /// A node of minimum penalty is selected randomly at each step.
+ /// The node penalties are updated adaptively after each stage of the
+ /// search process.
+ PENALTY_BASED
+ };
+
+ private:
+
+ TEMPLATE_GRAPH_TYPEDEFS(GR);
+
+ typedef std::vector IntVector;
+ typedef std::vector BoolVector;
+ typedef std::vector BoolMatrix;
+ // Note: vector is used instead of vector for efficiency reasons
+
+ const GR &_graph;
+ IntNodeMap _id;
+
+ // Internal matrix representation of the graph
+ BoolMatrix _gr;
+ int _n;
+
+ // The current clique
+ BoolVector _clique;
+ int _size;
+
+ // The best clique found so far
+ BoolVector _best_clique;
+ int _best_size;
+
+ // The "distances" of the nodes from the current clique.
+ // _delta[u] is the number of nodes in the clique that are
+ // not connected with u.
+ IntVector _delta;
+
+ // The current tabu set
+ BoolVector _tabu;
+
+ // Random number generator
+ Random _rnd;
+
+ private:
+
+ // Implementation of the RANDOM node selection rule.
+ class RandomSelectionRule
+ {
+ private:
+
+ // References to the algorithm instance
+ const BoolVector &_clique;
+ const IntVector &_delta;
+ const BoolVector &_tabu;
+ Random &_rnd;
+
+ // Pivot rule data
+ int _n;
+
+ public:
+
+ // Constructor
+ RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
+ _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
+ _rnd(mc._rnd), _n(mc._n)
+ {}
+
+ // Return a node index for a feasible add move or -1 if no one exists
+ int nextFeasibleAddNode() const {
+ int start_node = _rnd[_n];
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0 && !_tabu[i]) return i;
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0 && !_tabu[i]) return i;
+ }
+ return -1;
+ }
+
+ // Return a node index for a feasible swap move or -1 if no one exists
+ int nextFeasibleSwapNode() const {
+ int start_node = _rnd[_n];
+ for (int i = start_node; i != _n; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
+ }
+ return -1;
+ }
+
+ // Return a node index for an add move or -1 if no one exists
+ int nextAddNode() const {
+ int start_node = _rnd[_n];
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0) return i;
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0) return i;
+ }
+ return -1;
+ }
+
+ // Update internal data structures between stages (if necessary)
+ void update() {}
+
+ }; //class RandomSelectionRule
+
+
+ // Implementation of the DEGREE_BASED node selection rule.
+ class DegreeBasedSelectionRule
+ {
+ private:
+
+ // References to the algorithm instance
+ const BoolVector &_clique;
+ const IntVector &_delta;
+ const BoolVector &_tabu;
+ Random &_rnd;
+
+ // Pivot rule data
+ int _n;
+ IntVector _deg;
+
+ public:
+
+ // Constructor
+ DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
+ _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
+ _rnd(mc._rnd), _n(mc._n), _deg(_n)
+ {
+ for (int i = 0; i != _n; i++) {
+ int d = 0;
+ BoolVector &row = mc._gr[i];
+ for (int j = 0; j != _n; j++) {
+ if (row[j]) d++;
+ }
+ _deg[i] = d;
+ }
+ }
+
+ // Return a node index for a feasible add move or -1 if no one exists
+ int nextFeasibleAddNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, max_deg = -1;
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ return node;
+ }
+
+ // Return a node index for a feasible swap move or -1 if no one exists
+ int nextFeasibleSwapNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, max_deg = -1;
+ for (int i = start_node; i != _n; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
+ _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
+ _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ return node;
+ }
+
+ // Return a node index for an add move or -1 if no one exists
+ int nextAddNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, max_deg = -1;
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0 && _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0 && _deg[i] > max_deg) {
+ node = i;
+ max_deg = _deg[i];
+ }
+ }
+ return node;
+ }
+
+ // Update internal data structures between stages (if necessary)
+ void update() {}
+
+ }; //class DegreeBasedSelectionRule
+
+
+ // Implementation of the PENALTY_BASED node selection rule.
+ class PenaltyBasedSelectionRule
+ {
+ private:
+
+ // References to the algorithm instance
+ const BoolVector &_clique;
+ const IntVector &_delta;
+ const BoolVector &_tabu;
+ Random &_rnd;
+
+ // Pivot rule data
+ int _n;
+ IntVector _penalty;
+
+ public:
+
+ // Constructor
+ PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
+ _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
+ _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
+ {}
+
+ // Return a node index for a feasible add move or -1 if no one exists
+ int nextFeasibleAddNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, min_p = std::numeric_limits::max();
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ return node;
+ }
+
+ // Return a node index for a feasible swap move or -1 if no one exists
+ int nextFeasibleSwapNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, min_p = std::numeric_limits::max();
+ for (int i = start_node; i != _n; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
+ _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
+ _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ return node;
+ }
+
+ // Return a node index for an add move or -1 if no one exists
+ int nextAddNode() const {
+ int start_node = _rnd[_n];
+ int node = -1, min_p = std::numeric_limits::max();
+ for (int i = start_node; i != _n; i++) {
+ if (_delta[i] == 0 && _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ for (int i = 0; i != start_node; i++) {
+ if (_delta[i] == 0 && _penalty[i] < min_p) {
+ node = i;
+ min_p = _penalty[i];
+ }
+ }
+ return node;
+ }
+
+ // Update internal data structures between stages (if necessary)
+ void update() {}
+
+ }; //class PenaltyBasedSelectionRule
+
+ public:
+
+ /// \brief Constructor.
+ ///
+ /// Constructor.
+ /// The global \ref rnd "random number generator instance" is used
+ /// during the algorithm.
+ ///
+ /// \param graph The undirected graph the algorithm runs on.
+ GrossoLocatelliPullanMc(const GR& graph) :
+ _graph(graph), _id(_graph), _rnd(rnd)
+ {}
+
+ /// \brief Constructor with random seed.
+ ///
+ /// Constructor with random seed.
+ ///
+ /// \param graph The undirected graph the algorithm runs on.
+ /// \param seed Seed value for the internal random number generator
+ /// that is used during the algorithm.
+ GrossoLocatelliPullanMc(const GR& graph, int seed) :
+ _graph(graph), _id(_graph), _rnd(seed)
+ {}
+
+ /// \brief Constructor with random number generator.
+ ///
+ /// Constructor with random number generator.
+ ///
+ /// \param graph The undirected graph the algorithm runs on.
+ /// \param random A random number generator that is used during the
+ /// algorithm.
+ GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
+ _graph(graph), _id(_graph), _rnd(random)
+ {}
+
+ /// \name Execution Control
+ /// @{
+
+ /// \brief Runs the algorithm.
+ ///
+ /// This function runs the algorithm.
+ ///
+ /// \param step_num The maximum number of node selections (steps)
+ /// during the search process.
+ /// This parameter controls the running time and the success of the
+ /// algorithm. For larger values, the algorithm runs slower but it more
+ /// likely finds larger cliques. For smaller values, the algorithm is
+ /// faster but probably gives worse results.
+ /// \param rule The node selection rule. For more information, see
+ /// \ref SelectionRule.
+ ///
+ /// \return The size of the found clique.
+ int run(int step_num = 100000,
+ SelectionRule rule = PENALTY_BASED)
+ {
+ init();
+ switch (rule) {
+ case RANDOM:
+ return start(step_num);
+ case DEGREE_BASED:
+ return start(step_num);
+ case PENALTY_BASED:
+ return start(step_num);
+ }
+ return 0; // avoid warning
+ }
+
+ /// @}
+
+ /// \name Query Functions
+ /// @{
+
+ /// \brief The size of the found clique
+ ///
+ /// This function returns the size of the found clique.
+ ///
+ /// \pre run() must be called before using this function.
+ int cliqueSize() const {
+ return _best_size;
+ }
+
+ /// \brief Gives back the found clique in a \c bool node map
+ ///
+ /// This function gives back the characteristic vector of the found
+ /// clique in the given node map.
+ /// It must be a \ref concepts::WriteMap "writable" node map with
+ /// \c bool (or convertible) value type.
+ ///
+ /// \pre run() must be called before using this function.
+ template
+ void cliqueMap(CliqueMap &map) const {
+ for (NodeIt n(_graph); n != INVALID; ++n) {
+ map[n] = static_cast(_best_clique[_id[n]]);
+ }
+ }
+
+ /// \brief Iterator to list the nodes of the found clique
+ ///
+ /// This iterator class lists the nodes of the found clique.
+ /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
+ /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
+ ///
+ /// The following example prints out the IDs of the nodes in the found
+ /// clique.
+ /// \code
+ /// GrossoLocatelliPullanMc mc(g);
+ /// mc.run();
+ /// for (GrossoLocatelliPullanMc::CliqueNodeIt n(mc);
+ /// n != INVALID; ++n)
+ /// {
+ /// std::cout << g.id(n) << std::endl;
+ /// }
+ /// \endcode
+ class CliqueNodeIt
+ {
+ private:
+ NodeIt _it;
+ BoolNodeMap _map;
+
+ public:
+
+ /// Constructor
+
+ /// Constructor.
+ /// \param mc The algorithm instance.
+ CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
+ : _map(mc._graph)
+ {
+ mc.cliqueMap(_map);
+ for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
+ }
+
+ /// Conversion to \c Node
+ operator Node() const { return _it; }
+
+ bool operator==(Invalid) const { return _it == INVALID; }
+ bool operator!=(Invalid) const { return _it != INVALID; }
+
+ /// Next node
+ CliqueNodeIt &operator++() {
+ for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
+ return *this;
+ }
+
+ /// Postfix incrementation
+
+ /// Postfix incrementation.
+ ///
+ /// \warning This incrementation returns a \c Node, not a
+ /// \c CliqueNodeIt as one may expect.
+ typename GR::Node operator++(int) {
+ Node n=*this;
+ ++(*this);
+ return n;
+ }
+
+ };
+
+ /// @}
+
+ private:
+
+ // Adds a node to the current clique
+ void addCliqueNode(int u) {
+ if (_clique[u]) return;
+ _clique[u] = true;
+ _size++;
+ BoolVector &row = _gr[u];
+ for (int i = 0; i != _n; i++) {
+ if (!row[i]) _delta[i]++;
+ }
+ }
+
+ // Removes a node from the current clique
+ void delCliqueNode(int u) {
+ if (!_clique[u]) return;
+ _clique[u] = false;
+ _size--;
+ BoolVector &row = _gr[u];
+ for (int i = 0; i != _n; i++) {
+ if (!row[i]) _delta[i]--;
+ }
+ }
+
+ // Initialize data structures
+ void init() {
+ _n = countNodes(_graph);
+ int ui = 0;
+ for (NodeIt u(_graph); u != INVALID; ++u) {
+ _id[u] = ui++;
+ }
+ _gr.clear();
+ _gr.resize(_n, BoolVector(_n, false));
+ ui = 0;
+ for (NodeIt u(_graph); u != INVALID; ++u) {
+ for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
+ int vi = _id[_graph.runningNode(e)];
+ _gr[ui][vi] = true;
+ _gr[vi][ui] = true;
+ }
+ ++ui;
+ }
+
+ _clique.clear();
+ _clique.resize(_n, false);
+ _size = 0;
+ _best_clique.clear();
+ _best_clique.resize(_n, false);
+ _best_size = 0;
+ _delta.clear();
+ _delta.resize(_n, 0);
+ _tabu.clear();
+ _tabu.resize(_n, false);
+ }
+
+ // Executes the algorithm
+ template
+ int start(int max_select) {
+ // Options for the restart rule
+ const bool delta_based_restart = true;
+ const int restart_delta_limit = 4;
+
+ if (_n == 0) return 0;
+ if (_n == 1) {
+ _best_clique[0] = true;
+ _best_size = 1;
+ return _best_size;
+ }
+
+ // Iterated local search
+ SelectionRuleImpl sel_method(*this);
+ int select = 0;
+ IntVector restart_nodes;
+
+ while (select < max_select) {
+
+ // Perturbation/restart
+ if (delta_based_restart) {
+ restart_nodes.clear();
+ for (int i = 0; i != _n; i++) {
+ if (_delta[i] >= restart_delta_limit)
+ restart_nodes.push_back(i);
+ }
+ }
+ int rs_node = -1;
+ if (restart_nodes.size() > 0) {
+ rs_node = restart_nodes[_rnd[restart_nodes.size()]];
+ } else {
+ rs_node = _rnd[_n];
+ }
+ BoolVector &row = _gr[rs_node];
+ for (int i = 0; i != _n; i++) {
+ if (_clique[i] && !row[i]) delCliqueNode(i);
+ }
+ addCliqueNode(rs_node);
+
+ // Local search
+ _tabu.clear();
+ _tabu.resize(_n, false);
+ bool tabu_empty = true;
+ int max_swap = _size;
+ while (select < max_select) {
+ select++;
+ int u;
+ if ((u = sel_method.nextFeasibleAddNode()) != -1) {
+ // Feasible add move
+ addCliqueNode(u);
+ if (tabu_empty) max_swap = _size;
+ }
+ else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
+ // Feasible swap move
+ int v = -1;
+ BoolVector &row = _gr[u];
+ for (int i = 0; i != _n; i++) {
+ if (_clique[i] && !row[i]) {
+ v = i;
+ break;
+ }
+ }
+ addCliqueNode(u);
+ delCliqueNode(v);
+ _tabu[v] = true;
+ tabu_empty = false;
+ if (--max_swap <= 0) break;
+ }
+ else if ((u = sel_method.nextAddNode()) != -1) {
+ // Non-feasible add move
+ addCliqueNode(u);
+ }
+ else break;
+ }
+ if (_size > _best_size) {
+ _best_clique = _clique;
+ _best_size = _size;
+ if (_best_size == _n) return _best_size;
+ }
+ sel_method.update();
+ }
+
+ return _best_size;
+ }
+
+ }; //class GrossoLocatelliPullanMc
+
+ ///@}
+
+} //namespace lemon
+
+#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -31,6 +31,7 @@
kruskal_test
maps_test
matching_test
+ max_clique_test
min_cost_arborescence_test
min_cost_flow_test
min_mean_cycle_test
diff --git a/test/Makefile.am b/test/Makefile.am
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -33,6 +33,7 @@
test/kruskal_test \
test/maps_test \
test/matching_test \
+ test/max_clique_test \
test/min_cost_arborescence_test \
test/min_cost_flow_test \
test/min_mean_cycle_test \
@@ -84,6 +85,7 @@
test_maps_test_SOURCES = test/maps_test.cc
test_mip_test_SOURCES = test/mip_test.cc
test_matching_test_SOURCES = test/matching_test.cc
+test_max_clique_test_SOURCES = test/max_clique_test.cc
test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
diff --git a/test/max_clique_test.cc b/test/max_clique_test.cc
new file mode 100644
--- /dev/null
+++ b/test/max_clique_test.cc
@@ -0,0 +1,176 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2010
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include
+#include
+#include
+#include
+#include
+#include
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+char test_lgf[] =
+ "@nodes\n"
+ "label max_clique\n"
+ "1 0\n"
+ "2 0\n"
+ "3 0\n"
+ "4 1\n"
+ "5 1\n"
+ "6 1\n"
+ "7 1\n"
+ "@edges\n"
+ " label\n"
+ "1 2 1\n"
+ "1 3 2\n"
+ "1 4 3\n"
+ "1 6 4\n"
+ "2 3 5\n"
+ "2 5 6\n"
+ "2 7 7\n"
+ "3 4 8\n"
+ "3 5 9\n"
+ "4 5 10\n"
+ "4 6 11\n"
+ "4 7 12\n"
+ "5 6 13\n"
+ "5 7 14\n"
+ "6 7 15\n";
+
+
+// Check with general graphs
+template
+void checkMaxCliqueGeneral(int max_sel, Param rule) {
+ typedef ListGraph GR;
+ typedef GrossoLocatelliPullanMc McAlg;
+ typedef McAlg::CliqueNodeIt CliqueIt;
+
+ // Basic tests
+ {
+ GR g;
+ GR::NodeMap map(g);
+ McAlg mc(g);
+ check(mc.run(max_sel, rule) == 0, "Wrong clique size");
+ check(mc.cliqueSize() == 0, "Wrong clique size");
+ check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
+
+ GR::Node u = g.addNode();
+ check(mc.run(max_sel, rule) == 1, "Wrong clique size");
+ check(mc.cliqueSize() == 1, "Wrong clique size");
+ mc.cliqueMap(map);
+ check(map[u], "Wrong clique map");
+ CliqueIt it1(mc);
+ check(static_cast(it1) == u && ++it1 == INVALID,
+ "Wrong CliqueNodeIt");
+
+ GR::Node v = g.addNode();
+ check(mc.run(max_sel, rule) == 1, "Wrong clique size");
+ check(mc.cliqueSize() == 1, "Wrong clique size");
+ mc.cliqueMap(map);
+ check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
+ CliqueIt it2(mc);
+ check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
+
+ g.addEdge(u, v);
+ check(mc.run(max_sel, rule) == 2, "Wrong clique size");
+ check(mc.cliqueSize() == 2, "Wrong clique size");
+ mc.cliqueMap(map);
+ check(map[u] && map[v], "Wrong clique map");
+ CliqueIt it3(mc);
+ check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,
+ "Wrong CliqueNodeIt");
+ }
+
+ // Test graph
+ {
+ GR g;
+ GR::NodeMap max_clique(g);
+ GR::NodeMap map(g);
+ std::istringstream input(test_lgf);
+ graphReader(g, input)
+ .nodeMap("max_clique", max_clique)
+ .run();
+
+ McAlg mc(g);
+ check(mc.run(max_sel, rule) == 4, "Wrong clique size");
+ check(mc.cliqueSize() == 4, "Wrong clique size");
+ mc.cliqueMap(map);
+ for (GR::NodeIt n(g); n != INVALID; ++n) {
+ check(map[n] == max_clique[n], "Wrong clique map");
+ }
+ int cnt = 0;
+ for (CliqueIt n(mc); n != INVALID; ++n) {
+ cnt++;
+ check(map[n] && max_clique[n], "Wrong CliqueNodeIt");
+ }
+ check(cnt == 4, "Wrong CliqueNodeIt");
+ }
+}
+
+// Check with full graphs
+template
+void checkMaxCliqueFullGraph(int max_sel, Param rule) {
+ typedef FullGraph GR;
+ typedef GrossoLocatelliPullanMc McAlg;
+ typedef McAlg::CliqueNodeIt CliqueIt;
+
+ for (int size = 0; size <= 40; size = size * 3 + 1) {
+ GR g(size);
+ GR::NodeMap map(g);
+ McAlg mc(g);
+ check(mc.run(max_sel, rule) == size, "Wrong clique size");
+ check(mc.cliqueSize() == size, "Wrong clique size");
+ mc.cliqueMap(map);
+ for (GR::NodeIt n(g); n != INVALID; ++n) {
+ check(map[n], "Wrong clique map");
+ }
+ int cnt = 0;
+ for (CliqueIt n(mc); n != INVALID; ++n) cnt++;
+ check(cnt == size, "Wrong CliqueNodeIt");
+ }
+}
+
+// Check with grid graphs
+template
+void checkMaxCliqueGridGraph(int max_sel, Param rule) {
+ GridGraph g(5, 7);
+ GridGraph::NodeMap map(g);
+ GrossoLocatelliPullanMc mc(g);
+ check(mc.run(max_sel, rule) == 2, "Wrong clique size");
+ check(mc.cliqueSize() == 2, "Wrong clique size");
+}
+
+
+int main() {
+ checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::RANDOM);
+ checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::DEGREE_BASED);
+ checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::PENALTY_BASED);
+
+ checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::RANDOM);
+ checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED);
+ checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED);
+
+ checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::RANDOM);
+ checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED);
+ checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED);
+
+ return 0;
+}