GrossoLocatelliPullanMc implements the iterated local search algorithm of Grosso, Locatelli, and Pullan for solving the maximum clique problem grosso08maxclique. 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.
GR | The undirected graph type the algorithm runs on. |
#include <lemon/grosso_locatelli_pullan_mc.h>
Classes | |
class | CliqueNodeIt |
Iterator to list the nodes of the found clique. More... | |
Public Types | |
enum | SelectionRule { RANDOM, DEGREE_BASED, PENALTY_BASED } |
Constants for specifying the node selection rule. More... | |
enum | TerminationCause { ITERATION_LIMIT, STEP_LIMIT, SIZE_LIMIT } |
Constants for the causes of search termination. More... | |
Public Member Functions | |
GrossoLocatelliPullanMc (const GR &graph) | |
Constructor. | |
GrossoLocatelliPullanMc (const GR &graph, int seed) | |
Constructor with random seed. | |
GrossoLocatelliPullanMc (const GR &graph, const Random &random) | |
Constructor with random number generator. | |
Execution Control | |
The run() function can be used to execute the algorithm. | |
GrossoLocatelliPullanMc & | iterationLimit (int limit) |
Sets the maximum number of iterations. | |
GrossoLocatelliPullanMc & | stepLimit (int limit) |
Sets the maximum number of search steps. | |
GrossoLocatelliPullanMc & | sizeLimit (int limit) |
Sets the desired clique size. | |
int | iterationLimit () const |
The maximum number of iterations. | |
int | stepLimit () const |
The maximum number of search steps. | |
int | sizeLimit () const |
The desired clique size. | |
TerminationCause | run (SelectionRule rule=PENALTY_BASED) |
Runs the algorithm. | |
Query Functions | |
The results of the algorithm can be obtained using these functions. | |
int | cliqueSize () const |
The size of the found clique. | |
template<typename CliqueMap > | |
void | cliqueMap (CliqueMap &map) const |
Gives back the found clique in a bool node map. |
enum 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.
enum TerminationCause |
Enum type containing constants for the different causes of search termination. The run() function returns one of these values.
GrossoLocatelliPullanMc | ( | const GR & | graph | ) | [inline] |
Constructor. The global random number generator instance is used during the algorithm.
graph | The undirected graph the algorithm runs on. |
GrossoLocatelliPullanMc | ( | const GR & | graph, |
int | seed | ||
) | [inline] |
Constructor with random seed.
graph | The undirected graph the algorithm runs on. |
seed | Seed value for the internal random number generator that is used during the algorithm. |
GrossoLocatelliPullanMc | ( | const GR & | graph, |
const Random & | random | ||
) | [inline] |
Constructor with random number generator.
graph | The undirected graph the algorithm runs on. |
random | A random number generator that is used during the algorithm. |
GrossoLocatelliPullanMc& iterationLimit | ( | int | limit | ) | [inline] |
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.
(*this)
GrossoLocatelliPullanMc& stepLimit | ( | int | limit | ) | [inline] |
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.
(*this)
GrossoLocatelliPullanMc& sizeLimit | ( | int | limit | ) | [inline] |
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.
(*this)
int iterationLimit | ( | ) | const [inline] |
This function gives back the maximum number of iterations. -1
means that no limit is specified.
int stepLimit | ( | ) | const [inline] |
This function gives back the maximum number of search steps. -1
means that no limit is specified.
int sizeLimit | ( | ) | const [inline] |
This function gives back the desired clique size that serves as a search limit. -1
means that this limit is set to the number of nodes in the graph.
TerminationCause run | ( | SelectionRule | rule = PENALTY_BASED | ) | [inline] |
This function runs the algorithm. If one of the specified limits is reached, the search process terminates.
rule | The node selection rule. For more information, see SelectionRule. |
int cliqueSize | ( | ) | const [inline] |
This function returns the size of the found clique.