template<typename GR>
class lemon::GrossoLocatelliPullanMc< GR >
GrossoLocatelliPullanMc implements the iterated local search algorithm of Grosso, Locatelli, and Pullan for solving the maximum clique problem [20]. It is to find the largest complete subgraph (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 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.
- Template Parameters
-
| 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 SelectionRule.
Enum type containing constants for specifying the node selection rule for the 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 run() function with the proper parameter.
- Enumerator:
| RANDOM |
A node is selected randomly without any evaluation at each step.
|
| DEGREE_BASED |
A node of maximum degree is selected randomly at each step.
|
| PENALTY_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.
|
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 1000. -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.
- Returns
(*this)
- See Also
- stepLimit(int)
-
sizeLimit(int)
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 -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.
- Returns
(*this)
- See Also
- iterationLimit(int)
-
sizeLimit(int)
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 -1, which means that the size limit is set to the number of nodes in the graph.
- Returns
(*this)
- See Also
- iterationLimit(int)
-
stepLimit(int)
1.8.2