# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1279859377 -7200
# Node ID c279b19abc62e8e4af4f66240cd22186284749e4
# Parent  24b3f18ed9e2bea99ab482c493c3db769362ecf0
Add a heuristic algorithm for the max clique problem (#380)

diff -r 24b3f18ed9e2 -r c279b19abc62 doc/groups.dox
--- a/doc/groups.dox	Tue Jun 22 16:13:00 2010 +0200
+++ b/doc/groups.dox	Fri Jul 23 06:29:37 2010 +0200
@@ -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.
+
+<b>Maximum Clique Problem</b>
+  - \ref GrossoLocatelliPullanMc An efficient heuristic algorithm of
+    Grosso, Locatelli, and Pullan.
 */
 
 /**
diff -r 24b3f18ed9e2 -r c279b19abc62 doc/references.bib
--- a/doc/references.bib	Tue Jun 22 16:13:00 2010 +0200
+++ b/doc/references.bib	Fri Jul 23 06:29:37 2010 +0200
@@ -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 -r 24b3f18ed9e2 -r c279b19abc62 lemon/Makefile.am
--- a/lemon/Makefile.am	Tue Jun 22 16:13:00 2010 +0200
+++ b/lemon/Makefile.am	Fri Jul 23 06:29:37 2010 +0200
@@ -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 -r 24b3f18ed9e2 -r c279b19abc62 lemon/grosso_locatelli_pullan_mc.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/grosso_locatelli_pullan_mc.h	Fri Jul 23 06:29:37 2010 +0200
@@ -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 <vector>
+#include <limits>
+#include <lemon/core.h>
+#include <lemon/random.h>
+
+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 <typename GR>
+  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<int> IntVector;
+    typedef std::vector<char> BoolVector;
+    typedef std::vector<BoolVector> BoolMatrix;
+    // Note: vector<char> is used instead of vector<bool> 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<int>::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<int>::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<int>::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<RandomSelectionRule>(step_num);
+        case DEGREE_BASED:
+          return start<DegreeBasedSelectionRule>(step_num);
+        case PENALTY_BASED:
+          return start<PenaltyBasedSelectionRule>(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 <typename CliqueMap>
+    void cliqueMap(CliqueMap &map) const {
+      for (NodeIt n(_graph); n != INVALID; ++n) {
+        map[n] = static_cast<bool>(_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<Graph> mc(g);
+    ///   mc.run();
+    ///   for (GrossoLocatelliPullanMc<Graph>::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 <typename SelectionRuleImpl>
+    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 -r 24b3f18ed9e2 -r c279b19abc62 test/CMakeLists.txt
--- a/test/CMakeLists.txt	Tue Jun 22 16:13:00 2010 +0200
+++ b/test/CMakeLists.txt	Fri Jul 23 06:29:37 2010 +0200
@@ -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 -r 24b3f18ed9e2 -r c279b19abc62 test/Makefile.am
--- a/test/Makefile.am	Tue Jun 22 16:13:00 2010 +0200
+++ b/test/Makefile.am	Fri Jul 23 06:29:37 2010 +0200
@@ -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 -r 24b3f18ed9e2 -r c279b19abc62 test/max_clique_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/max_clique_test.cc	Fri Jul 23 06:29:37 2010 +0200
@@ -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 <sstream>
+#include <lemon/list_graph.h>
+#include <lemon/full_graph.h>
+#include <lemon/grid_graph.h>
+#include <lemon/lgf_reader.h>
+#include <lemon/grosso_locatelli_pullan_mc.h>
+
+#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 <typename Param>
+void checkMaxCliqueGeneral(int max_sel, Param rule) {
+  typedef ListGraph GR;
+  typedef GrossoLocatelliPullanMc<GR> McAlg;
+  typedef McAlg::CliqueNodeIt CliqueIt;
+  
+  // Basic tests
+  {
+    GR g;
+    GR::NodeMap<bool> 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<GR::Node>(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<bool> max_clique(g);
+    GR::NodeMap<bool> 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 <typename Param>
+void checkMaxCliqueFullGraph(int max_sel, Param rule) {
+  typedef FullGraph GR;
+  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
+  typedef McAlg::CliqueNodeIt CliqueIt;
+  
+  for (int size = 0; size <= 40; size = size * 3 + 1) {
+    GR g(size);
+    GR::NodeMap<bool> 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 <typename Param>
+void checkMaxCliqueGridGraph(int max_sel, Param rule) {
+  GridGraph g(5, 7);
+  GridGraph::NodeMap<char> map(g);
+  GrossoLocatelliPullanMc<GridGraph> mc(g);
+  check(mc.run(max_sel, rule) == 2, "Wrong clique size");
+  check(mc.cliqueSize() == 2, "Wrong clique size");
+}
+
+
+int main() {
+  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
+  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
+  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
+
+  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
+  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
+  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
+                       
+  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
+  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
+  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
+                       
+  return 0;
+}