RhodeCode

Private member variables should start with underscore.

_start_with_underscore

In general, \ref NetworkSimplex and \ref CostScaling are the most efficient

implementations, but the other two algorithms could be faster in special cases.

\ref CapacityScaling is usually the fastest algorithm (without effective scaling).

In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the

@defgroup planar Planar Embedding and Drawing

  /// \warning This algorithm does not support negative costs for

  /// arcs having infinite upper bound.

    /// with a map in which \c k is assigned to \c s, \c -k is

  /// \brief Check whether a graph is undirected.

  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest

  /// implementations available in LEMON for this problem.

  ///

  /// \warning This algorithm does not support negative costs for

  /// arcs having infinite upper bound.

    /// "Partial Augment-Relabel" method is used, which turned out to be

    /// with a map in which \c k is assigned to \c s, \c -k is

  /// \warning This algorithm does not support negative costs for

  /// arcs having infinite upper bound.

    /// is used, which is by far the most efficient and the most robust.

    /// with a map in which \c k is assigned to \c s, \c -k is

  /// \ingroup graph_properties

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

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

    /// turend out to be the most efficient and the most robust on various

    // Note: vector<signed char> is used instead of vector<ArcState> and

    ///

    /// \sa supplyType()

    /// with a map in which \c k is assigned to \c s, \c -k is

  /// LEMON path type stores just this list. As a consequence, it

    /// \brief The n-th arc.

    /// \brief Initialize arc iterator to point to the n-th arc

  /// LEMON path type stores just this list. As a consequence it

    /// \brief The n-th arc.

    /// \brief  Initializes arc iterator to point to the n-th arc.

  /// LEMON path type stores just this list. As a consequence it

    /// \brief The n-th arc.

    /// This function looks for the n-th arc in O(n) time.

    /// \brief Initializes arc iterator to point to the n-th arc.

  /// LEMON path type stores just this list. As a consequence it

    /// \brief The n-th arc.

    /// \brief The arc iterator pointing to the n-th arc.

  /// LEMON path type stores only this list. As a consequence, it

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