LEMON/LEMON-main Changeset - r918:8583fb74238c

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r918:8583fb74238c

« 917:4980b0

919:e0cef6 »

r918:8583fb74238c

Sat, 08 Jan 2011 15:52:07

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

Various search limits for the max clique alg (#405)

0 2 0

default

2 files changed with 225 insertions and 53 deletions:

lemon/grosso_locatelli_pullan_mc.h

194

test/max_clique_test.cc

↑ Collapse diff ↑

lemon/grosso_locatelli_pullan_mc.h

Show inline comments

 		/* -*- 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
+		  /// method that quickly finds a quite large clique, but not necessarily the
 		  /// largest one.
 		  /// The algorithm performs a certain number of iterations to find several
 		  /// cliques and selects the largest one among them. Various limits can be
 		  /// specified to control the running time and the effectiveness of the
 		  /// search process.
 		  ///
 		  /// \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
 		    };
 		    /// \brief Constants for the causes of search termination.
 		    ///
 		    /// Enum type containing constants for the different causes of search
 		    /// termination. The \ref run() function returns one of these values.
 		    enum TerminationCause {
 		      /// The iteration count limit is reached.
 		      ITERATION_LIMIT,
 		      /// The step count limit is reached.
 		      STEP_LIMIT,
 		      /// The clique size limit is reached.
 		      SIZE_LIMIT
 		    };
 		  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
 		    // The underlying graph
 		    const GR &_graph;
 		    IntNodeMap _id;
 		    // Internal matrix representation of the graph
 		    BoolMatrix _gr;
 		    int _n;
 		    // Search options
 		    bool _delta_based_restart;
 		    int _restart_delta_limit;
 		    // Search limits
 		    int _iteration_limit;
 		    int _step_limit;
 		    int _size_limit;
 		    // 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++) {
@@ -335,346 +365,476 @@
 		            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)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \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)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \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)
-		    {}
+		    {
 		      initOptions();
+		    }
 		    /// \name Execution Control
 		    /// The \ref run() function can be used to execute the algorithm.\n
 		    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
 		    /// \ref sizeLimit(int) can be used to specify various limits for the
 		    /// search process.
 		    /// @{
 		    /// \brief Sets the maximum number of iterations.
 		    ///
 		    /// This function sets the maximum number of iterations.
 		    /// Each iteration of the algorithm finds a maximal clique (but not
 		    /// necessarily the largest one) by performing several search steps
 		    /// (node selections).
 		    ///
 		    /// This limit 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.
 		    ///
 		    /// The default value is \c 1000.
 		    /// \c -1 means that number of iterations is not limited.
 		    ///
 		    /// \warning You should specify a reasonable limit for the number of
 		    /// iterations and/or the number of search steps.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa stepLimit(int)
 		    /// \sa sizeLimit(int)
 		    GrossoLocatelliPullanMc& iterationLimit(int limit) {
 		      _iteration_limit = limit;
 		      return *this;
+		    }
 		    /// \brief Sets the maximum number of search steps.
 		    ///
 		    /// This function sets the maximum number of elementary search steps.
 		    /// Each iteration of the algorithm finds a maximal clique (but not
 		    /// necessarily the largest one) by performing several search steps
 		    /// (node selections).
 		    ///
 		    /// This limit 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.
 		    ///
 		    /// The default value is \c -1, which means that number of steps
 		    /// is not limited explicitly. However, the number of iterations is
 		    /// limited and each iteration performs a finite number of search steps.
 		    ///
 		    /// \warning You should specify a reasonable limit for the number of
 		    /// iterations and/or the number of search steps.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa iterationLimit(int)
 		    /// \sa sizeLimit(int)
 		    GrossoLocatelliPullanMc& stepLimit(int limit) {
 		      _step_limit = limit;
 		      return *this;
+		    }
 		    /// \brief Sets the desired clique size.
 		    ///
 		    /// This function sets the desired clique size that serves as a search
 		    /// limit. If a clique of this size (or a larger one) is found, then the
 		    /// algorithm terminates.
 		    ///
 		    /// This function is especially useful if you know an exact upper bound
 		    /// for the size of the cliques in the graph or if any clique above
 		    /// a certain size limit is sufficient for your application.
 		    ///
 		    /// The default value is \c -1, which means that the size limit is set to
 		    /// the number of nodes in the graph.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa iterationLimit(int)
 		    /// \sa stepLimit(int)
 		    GrossoLocatelliPullanMc& sizeLimit(int limit) {
 		      _size_limit = limit;
 		      return *this;
+		    }
 		    /// \brief The maximum number of iterations.
 		    ///
 		    /// This function gives back the maximum number of iterations.
 		    /// \c -1 means that no limit is specified.
 		    ///
 		    /// \sa iterationLimit(int)
 		    int iterationLimit() const {
 		      return _iteration_limit;
+		    }
 		    /// \brief The maximum number of search steps.
 		    ///
 		    /// This function gives back the maximum number of search steps.
 		    /// \c -1 means that no limit is specified.
 		    ///
 		    /// \sa stepLimit(int)
 		    int stepLimit() const {
 		      return _step_limit;
+		    }
 		    /// \brief The desired clique size.
 		    ///
 		    /// This function gives back the desired clique size that serves as a
 		    /// search limit. \c -1 means that this limit is set to the number of
 		    /// nodes in the graph.
 		    ///
 		    /// \sa sizeLimit(int)
 		    int sizeLimit() const {
 		      return _size_limit;
+		    }
 		    /// \brief Runs the algorithm.
 		    ///
 		    /// This function runs the algorithm.
+		    /// This function runs the algorithm. If one of the specified limits
 		    /// is reached, the search process terminates.
 		    ///
 		    /// \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)
+		    /// \return The termination cause of the search. For more information,
 		    /// see \ref TerminationCause.
 		    TerminationCause run(SelectionRule rule = PENALTY_BASED)
+		    {
 		      init();
 		      switch (rule) {
 		        case RANDOM:
-		          return start<RandomSelectionRule>(step_num);
 		          return start<RandomSelectionRule>();
 		        case DEGREE_BASED:
 		          return start<DegreeBasedSelectionRule>(step_num);
 		        case PENALTY_BASED:
-		          return start<PenaltyBasedSelectionRule>(step_num);
+		          return start<DegreeBasedSelectionRule>();
 		        default:
 		          return start<PenaltyBasedSelectionRule>();
+		      }
 		      return 0; // avoid warning
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the algorithm can be obtained using these functions.\n
 		    /// The run() function must be called before using them.
 		    /// @{
 		    /// \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:
 		    // Initialize search options and limits
 		    void initOptions() {
 		      // Search options
 		      _delta_based_restart = true;
 		      _restart_delta_limit = 4;
 		      // Search limits
 		      _iteration_limit = 1000;
 		      _step_limit = -1;             // this is disabled by default
 		      _size_limit = -1;             // this is disabled by default
+		    }
 		    // 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;
 		    TerminationCause start() {
 		      if (_n == 0) return SIZE_LIMIT;
 		      if (_n == 1) {
 		        _best_clique[0] = true;
 		        _best_size = 1;
-		        return _best_size;
+		        return SIZE_LIMIT;
+		      }
 		      // Iterated local search
+		      // Iterated local search algorithm
 		      const int max_size = _size_limit >= 0 ? _size_limit : _n;
 		      const int max_restart = _iteration_limit >= 0 ?
 		        _iteration_limit : std::numeric_limits<int>::max();
 		      const int max_select = _step_limit >= 0 ?
 		        _step_limit : std::numeric_limits<int>::max();
 		      SelectionRuleImpl sel_method(*this);
 		      int select = 0;
+		      int select = 0, restart = 0;
 		      IntVector restart_nodes;
 		      while (select < max_select) {
 		      while (select < max_select && restart < max_restart) {
 		        // Perturbation/restart
-		        if (delta_based_restart) {
+		        restart++;
 		        if (_delta_based_restart) {
 		          restart_nodes.clear();
 		          for (int i = 0; i != _n; i++) {
-		            if (_delta[i] >= restart_delta_limit)
+		            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;
+		          if (_best_size >= max_size) return SIZE_LIMIT;
+		        }
 		        sel_method.update();
+		      }
-		      return _best_size;
+		      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
+		    }
 		  }; //class GrossoLocatelliPullanMc
 		  ///@}
 		} //namespace lemon
 		#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H

test/max_clique_test.cc

Show inline comments

@@ -13,164 +13,176 @@
 		 * 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) {
 		void checkMaxCliqueGeneral(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");
+		    mc.iterationLimit(50);
 		    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    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.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    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.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
 		    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.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    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");
+		    mc.iterationLimit(50);
 		    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
 		    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) {
 		void checkMaxCliqueFullGraph(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.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
 		    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) {
 		void checkMaxCliqueGridGraph(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");
 		  mc.iterationLimit(100);
 		  check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
 		  check(mc.cliqueSize() == 2, "Wrong clique size");
 		  mc.stepLimit(100);
 		  check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
 		  check(mc.cliqueSize() == 2, "Wrong clique size");
 		  mc.sizeLimit(2);
 		  check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
 		  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);
+		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
 		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
 		  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
 		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
 		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
-		  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
+		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
 		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
 		  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
 		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
 		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
-		  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
+		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
 		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
 		  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
 		  return 0;
+		}

0 comments (0 inline)

RhodeCode

Login to your account