Loading...
Searching...
No Matches
GrossoLocatelliPullanMc< GR > Class Template Reference
Algorithms » Approximation Algorithms

## Detailed Description

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

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.

`#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. The functions iterationLimit(int), stepLimit(int), and sizeLimit(int) can be used to specify various limits for the search process.
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. The run() function must be called before using them.
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.

## Member Enumeration Documentation

## SelectionRule

template<typename GR>

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.

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.

## TerminationCause

template<typename GR>

enum TerminationCause

Enum type containing constants for the different causes of search termination. The run() function returns one of these values.

Enumerator
ITERATION_LIMIT | The iteration count limit is reached.
STEP_LIMIT | The step count limit is reached.
SIZE_LIMIT | The clique size limit is reached.

## Constructor & Destructor Documentation

## GrossoLocatelliPullanMc() [1/3]

template<typename GR>

GrossoLocatelliPullanMc | ( | const GR & | graph | ) |

inline

Constructor. The global random number generator instance is used during the algorithm.

Parameters

  graph | The undirected graph the algorithm runs on.

## GrossoLocatelliPullanMc() [2/3]

template<typename GR>

GrossoLocatelliPullanMc | ( | const GR & | graph,
|  | int | seed )

inline

Constructor with random seed.

Parameters

  graph | The undirected graph the algorithm runs on.
  seed | Seed value for the internal random number generator that is used during the algorithm.

## GrossoLocatelliPullanMc() [3/3]

template<typename GR>

GrossoLocatelliPullanMc | ( | const GR & | graph,
|  | const Random & | random )

inline

Constructor with random number generator.

Parameters

  graph | The undirected graph the algorithm runs on.
  random | A random number generator that is used during the algorithm.

## Member Function Documentation

## iterationLimit() [1/2]

template<typename GR>

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.

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)

## stepLimit() [1/2]

template<typename GR>

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.

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)

## sizeLimit() [1/2]

template<typename GR>

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.

Returns
  (*this)

See also
  iterationLimit(int)
  stepLimit(int)

## iterationLimit() [2/2]

template<typename GR>

int iterationLimit | ( |  | ) | const

inline

This function gives back the maximum number of iterations. `-1` means that no limit is specified.

See also
  iterationLimit(int)

## stepLimit() [2/2]

template<typename GR>

int stepLimit | ( |  | ) | const

inline

This function gives back the maximum number of search steps. `-1` means that no limit is specified.

See also
  stepLimit(int)

## sizeLimit() [2/2]

template<typename GR>

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.

See also
  sizeLimit(int)

## run()

template<typename GR>

TerminationCause run | ( | SelectionRule | rule = PENALTY_BASED | ) |

inline

This function runs the algorithm. If one of the specified limits is reached, the search process terminates.

Parameters

  rule | The node selection rule. For more information, see SelectionRule.

Returns
  The termination cause of the search. For more information, see TerminationCause.

## cliqueSize()

template<typename GR>

int cliqueSize | ( |  | ) | const

inline

This function returns the size of the found clique.

Precondition
  run() must be called before using this function.

## cliqueMap()

template<typename GR>
template<typename CliqueMap>

void cliqueMap | ( | CliqueMap & | map | ) | const

inline

This function gives back the characteristic vector of the found clique in the given node map. It must be a writable node map with `bool` (or convertible) value type.

Precondition
  run() must be called before using this function.