LEMON/LEMON-official Changeset - r1026:9312d6c89d02

Repositories » LEMON » LEMON-official

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

Changeset - r1026:9312d6c89d02

« 1024:745312
« 1025:140c95

1030:a80381 »

r1026:9312d6c89d02

Mon, 10 Jan 2011 09:34:50

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 11 0

merge default

4 files changed with 270 insertions and 94 deletions:

doc/coding_style.dox

doc/groups.dox

lemon/capacity_scaling.h

lemon/core.h

lemon/cost_scaling.h

lemon/cycle_canceling.h

lemon/euler.h

lemon/grosso_locatelli_pullan_mc.h

194

lemon/network_simplex.h

lemon/path.h

test/max_clique_test.cc

↑ Collapse diff ↑

0 comments (0 inline)

@@ -98,10 +98,10 @@
 		\subsection pri-loc-var Private member variables
 		Private member variables should start with underscore
+		Private member variables should start with underscore.
 		\code
-		_start_with_underscores
+		_start_with_underscore
 		\endcode
 		\subsection cs-excep Exceptions

@@ -406,10 +406,10 @@
 		 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
 		   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
 		In general NetworkSimplex is the most efficient implementation,
 		but in special cases other algorithms could be faster.
 		In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
 		implementations, but the other two algorithms could be faster in special cases.
 		For example, if the total supply and/or capacities are rather small,
 		CapacityScaling is usually the fastest algorithm (without effective scaling).
+		\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
 		*/
 		/**
@@ -471,7 +471,7 @@
 		- \ref HowardMmc Howard's policy iteration algorithm
 		  \ref dasdan98minmeancycle.
-		In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
+		In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
 		most efficient one, though the best known theoretical bound on its running
 		time is exponential.
 		Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
@@ -539,7 +539,7 @@
 		*/
 		/**
-		@defgroup planar Planarity Embedding and Drawing
+		@defgroup planar Planar Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing

@@ -89,8 +89,8 @@
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  /// \warning This algorithm does not support negative costs for
 		  /// arcs having infinite upper bound.
 		#ifdef DOXYGEN
 		  template <typename GR, typename V, typename C, typename TR>
 		#else
@@ -423,7 +423,7 @@
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.

@@ -447,7 +447,7 @@
+		  }
 		  /// Check whether a graph is undirected.
+		  /// \brief Check whether a graph is undirected.
 		  ///
 		  /// This function returns \c true if the given graph is undirected.
 		#ifdef DOXYGEN

@@ -97,6 +97,9 @@
 		  /// can be viewed as the generalization of the \ref Preflow
 		  /// "preflow push-relabel" algorithm for the maximum flow problem.
 		  ///
 		  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
 		  /// implementations available in LEMON for this problem.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
 		  /// executed using the \ref run() function. If some parameters are not
@@ -116,8 +119,8 @@
 		  /// \warning Both \c V and \c C must be signed number types.
 		  /// \warning All input data (capacities, supply values, and costs) must
 		  /// be integer.
 		  /// \warning This algorithm does not support negative costs for such
 		  /// arcs that have infinite upper bound.
 		  /// \warning This algorithm does not support negative costs for
 		  /// arcs having infinite upper bound.
 		  ///
 		  /// \note %CostScaling provides three different internal methods,
 		  /// from which the most efficient one is used by default.
@@ -179,7 +182,7 @@
 		    /// in their base operations, which are used in conjunction with the
 		    /// relabel operation.
 		    /// By default, the so called \ref PARTIAL_AUGMENT
-		    /// "Partial Augment-Relabel" method is used, which proved to be
+		    /// "Partial Augment-Relabel" method is used, which turned out to be
 		    /// the most efficient and the most robust on various test inputs.
 		    /// However, the other methods can be selected using the \ref run()
 		    /// function with the proper parameter.
@@ -448,7 +451,7 @@
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.

RhodeCode

Login to your account

@@ -36,7 +36,7 @@
 		  ///Euler tour iterator for digraphs.
-		  /// \ingroup graph_prop
+		  /// \ingroup graph_properties
 		  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
 		  ///graph (if there exists) and it converts to the \c Arc type of the digraph.
 		  ///

@@ -46,8 +46,12 @@
 		  /// 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.
 		  ///
@@ -84,6 +88,22 @@
 		      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);
@@ -93,6 +113,7 @@
 		    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;
@@ -100,6 +121,15 @@
 		    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;
@@ -380,7 +410,9 @@
 		    /// \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.
 		    ///
@@ -391,7 +423,9 @@
 		    /// 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.
 		    ///
@@ -402,43 +436,155 @@
 		    /// 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
@@ -531,6 +677,18 @@
 		  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;
@@ -586,30 +744,32 @@
 		    // 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);
+		          }
+		        }
@@ -663,12 +823,12 @@
 		        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

@@ -47,10 +47,10 @@
 		  /// linear programming simplex method directly for the minimum cost
 		  /// flow problem.
 		  ///
 		  /// In general, %NetworkSimplex is the fastest implementation available
 		  /// in LEMON for this problem.
 		  /// Moreover, it supports both directions of the supply/demand inequality
 		  /// constraints. For more information, see \ref SupplyType.
 		  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
 		  /// implementations available in LEMON for this problem.
 		  /// Furthermore, this class supports both directions of the supply/demand
 		  /// inequality constraints. For more information, see \ref SupplyType.
 		  ///
 		  /// Most of the parameters of the problem (except for the digraph)
 		  /// can be given using separate functions, and the algorithm can be
@@ -126,7 +126,7 @@
 		    /// implementations that significantly affect the running time
 		    /// of the algorithm.
 		    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
-		    /// proved to be the most efficient and the most robust on various
+		    /// turend out to be the most efficient and the most robust on various
 		    /// test inputs.
 		    /// However, another pivot rule can be selected using the \ref run()
 		    /// function with the proper parameter.
@@ -735,6 +735,8 @@
 		    /// of the algorithm.
 		    ///
 		    /// \return <tt>(*this)</tt>
 		    ///
 		    /// \sa supplyType()
 		    template<typename SupplyMap>
 		    NetworkSimplex& supplyMap(const SupplyMap& map) {
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
@@ -751,7 +753,7 @@
 		    /// calling \ref run(), the supply of each node will be set to zero.
 		    ///
 		    /// Using this function has the same effect as using \ref supplyMap()
-		    /// with such a map in which \c k is assigned to \c s, \c -k is
 		    /// with a map in which \c k is assigned to \c s, \c -k is
 		    /// assigned to \c t and all other nodes have zero supply value.
 		    ///
 		    /// \param s The source node.

@@ -43,7 +43,7 @@
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence, it
+		  /// LEMON path type stores just this list. As a consequence, it
 		  /// cannot enumerate the nodes of the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
@@ -135,7 +135,7 @@
 		    /// \brief Reset the path to an empty one.
 		    void clear() { head.clear(); tail.clear(); }
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
@@ -143,7 +143,7 @@
 		        *(tail.begin() + (n - head.size()));
+		    }
-		    /// \brief Initialize arc iterator to point to the nth arc
+		    /// \brief Initialize arc iterator to point to the n-th arc
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    ArcIt nthIt(int n) const {
@@ -231,7 +231,7 @@
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
@@ -327,14 +327,14 @@
 		    /// \brief Reset the path to an empty one.
 		    void clear() { data.clear(); }
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      return data[n];
+		    }
-		    /// \brief  Initializes arc iterator to point to the nth arc.
+		    /// \brief  Initializes arc iterator to point to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
@@ -395,7 +395,7 @@
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot store the source.
 		  ///
@@ -504,9 +504,9 @@
 		      Node *node;
 		    };
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
-		    /// This function looks for the nth arc in O(n) time.
+		    /// This function looks for the n-th arc in O(n) time.
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      Node *node = first;
@@ -516,7 +516,7 @@
 		      return node->arc;
+		    }
-		    /// \brief Initializes arc iterator to point to the nth arc.
+		    /// \brief Initializes arc iterator to point to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      Node *node = first;
 		      for (int i = 0; i < n; ++i) {
@@ -735,7 +735,7 @@
 		  /// \tparam GR The digraph type in which the path is.
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores just this list. As a consequence it
+		  /// LEMON path type stores just this list. As a consequence it
 		  /// cannot enumerate the nodes in the path and the source node of
 		  /// a zero length path is undefined.
 		  ///
@@ -831,14 +831,14 @@
 		      int idx;
 		    };
-		    /// \brief The nth arc.
+		    /// \brief The n-th arc.
 		    ///
 		    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
 		    const Arc& nth(int n) const {
 		      return arcs[n];
+		    }
-		    /// \brief The arc iterator pointing to the nth arc.
+		    /// \brief The arc iterator pointing to the n-th arc.
 		    ArcIt nthIt(int n) const {
 		      return ArcIt(*this, n);
+		    }
@@ -1042,7 +1042,7 @@
 		  /// \brief Class which helps to iterate through the nodes of a path
 		  ///
 		  /// In a sense, the path can be treated as a list of arcs. The
-		  /// lemon path type stores only this list. As a consequence, it
+		  /// LEMON path type stores only this list. As a consequence, it
 		  /// cannot enumerate the nodes in the path and the zero length paths
 		  /// cannot have a source node.
 		  ///

@@ -58,7 +58,7 @@
 		// 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;
@@ -68,12 +68,13 @@
 		    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");
@@ -82,7 +83,7 @@
 		          "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");
@@ -90,7 +91,7 @@
 		    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");
@@ -110,7 +111,8 @@
 		      .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) {
@@ -127,7 +129,7 @@
 		// 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;
@@ -136,7 +138,7 @@
 		    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) {
@@ -150,27 +152,37 @@
 		// 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;
+		}