All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
List of all members | Classes | Public Types | Public Member Functions
GrossoLocatelliPullanMc< GR > Class Template Reference

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

GrossoLocatelliPullanMciterationLimit (int limit)
 Sets the maximum number of iterations.
 
GrossoLocatelliPullanMcstepLimit (int limit)
 Sets the maximum number of search steps.
 
GrossoLocatelliPullanMcsizeLimit (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

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.

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 ( const GR &  graph)
inline

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

Parameters
graphThe undirected graph the algorithm runs on.
GrossoLocatelliPullanMc ( const GR &  graph,
int  seed 
)
inline

Constructor with random seed.

Parameters
graphThe undirected graph the algorithm runs on.
seedSeed 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.

Parameters
graphThe undirected graph the algorithm runs on.
randomA random number generator that is used during the algorithm.

Member Function Documentation

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)
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)
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)
int iterationLimit ( ) const
inline

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

See Also
iterationLimit(int)
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)
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)

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

Parameters
ruleThe node selection rule. For more information, see SelectionRule.
Returns
The termination cause of the search. For more information, see TerminationCause.
int cliqueSize ( ) const
inline

This function returns the size of the found clique.

Precondition
run() must be called before using this function.
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.