RhodeCode

  /// method that quickly finds a quite large clique, but not necessarily the

  /// 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.

    /// \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

    };

    // The underlying graph

    // Search options

    bool _delta_based_restart;

    int _restart_delta_limit;

    // Search limits

    int _iteration_limit;

    int _step_limit;

    int _size_limit;

    {

      initOptions();

    }

    {

      initOptions();

    }

    {

      initOptions();

    }

    /// 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;

    }

    /// This function runs the algorithm. If one of the specified limits

    /// is reached, the search process terminates.

    /// \return The termination cause of the search. For more information,

    /// see \ref TerminationCause.

    TerminationCause run(SelectionRule rule = PENALTY_BASED)

          return start<RandomSelectionRule>();

          return start<DegreeBasedSelectionRule>();

        default:

          return start<PenaltyBasedSelectionRule>();

    /// The results of the algorithm can be obtained using these functions.\n

    /// The run() function must be called before using them. 

    // 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

    }

    TerminationCause start() {

      if (_n == 0) return SIZE_LIMIT;

        return SIZE_LIMIT;

      // 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();

      int select = 0, restart = 0;

      while (select < max_select && restart < max_restart) {

        restart++;

        if (_delta_based_restart) {

            if (_delta[i] >= _restart_delta_limit)

          if (_best_size >= max_size) return SIZE_LIMIT;

      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);

void checkMaxCliqueGeneral(Param rule) {

    mc.iterationLimit(50);

    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");

    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");

    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");

    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");

    mc.iterationLimit(50);

    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");

void checkMaxCliqueFullGraph(Param rule) {

    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");

void checkMaxCliqueGridGraph(Param rule) {

  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");

  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);

  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);

  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);

  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);

  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);

  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);

  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);

  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);

  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);