GrossoLocatelliPullanMc

Declared in lemon/grosso_locatelli_pullan_mc.h, in the group Approximation Algorithms; the same class on the Doxygen site.

template< typename GR >
class GrossoLocatelliPullanMc

Implementation of the iterated local search algorithm of Grosso, Locatelli, and Pullan for the maximum clique problem.

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.

Note

GrossoLocatelliPullanMc provides three different node selection rules, from which the most powerful one is used by default. For more information, see SelectionRule.

Template Parameters:

GR – The undirected graph type the algorithm runs on.

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.

inline GrossoLocatelliPullanMc & iterationLimit( int limit )

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 1000. -1 means that number of iterations is not limited.

See also

stepLimit(int)

See also

sizeLimit(int)

Warning

You should specify a reasonable limit for the number of iterations and/or the number of search steps.

Returns:

(*this)

inline GrossoLocatelliPullanMc & penaltyDelay( int pd )

Sets the penalty delay of the PENALTY_BASED rule.

This function sets the penalty delay pd of the PENALTY_BASED rule, which updates the penalties after each iteration as DLS-MC does (Pullan and Hoos, 2006): the penalties of the nodes of the current clique increase by one, and every pd iterations all the positive penalties decrease by one. With pd = 1 an increase is undone at once, and the rule selects as RANDOM does; larger values keep the nodes of the recent cliques out of the next ones for longer. The best value depends on the graph (DLS-MC uses values from 1 to about 50).

The default value is 2.

Returns:

(*this)

inline GrossoLocatelliPullanMc & stepLimit( int limit )

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

See also

sizeLimit(int)

Warning

You should specify a reasonable limit for the number of iterations and/or the number of search steps.

Returns:

(*this)

inline GrossoLocatelliPullanMc & sizeLimit( int limit )

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 -1, which means that the size limit is set to the number of nodes in the graph.

See also

stepLimit(int)

Returns:

(*this)

inline int iterationLimit() const

The maximum number of iterations.

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

inline int stepLimit() const

The maximum number of search steps.

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

See also

stepLimit(int)

inline int sizeLimit() const

The desired clique size.

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)

inline TerminationCause run( SelectionRule rule = PENALTY_BASED )

Runs the algorithm.

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.

Query Functions

The results of the algorithm can be obtained using these functions.

The

run() function must be called before using them.

inline int cliqueSize() const

The size of the found clique.

This function returns the size of the found clique.

Pre:

run() must be called before using this function.

template< typename CliqueMap >
inline void cliqueMap( CliqueMap & map ) const

Gives back the found clique in a bool node map.

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.

Pre:

run() must be called before using this function.

Public Types

enum SelectionRule

Constants for specifying the node selection rule.

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.

Values:

enumerator RANDOM

A node is selected randomly without any evaluation at each step.

enumerator DEGREE_BASED

A node of maximum degree is selected randomly at each step.

enumerator 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 TerminationCause

Constants for the causes of search termination.

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

Values:

enumerator ITERATION_LIMIT

The iteration count limit is reached.

enumerator STEP_LIMIT

The step count limit is reached.

enumerator SIZE_LIMIT

The clique size limit is reached.

Public Functions

inline GrossoLocatelliPullanMc( const GR & graph )

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

Parameters:

graph – The undirected graph the algorithm runs on.

inline GrossoLocatelliPullanMc( const GR & graph , int seed )

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.

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

Constructor with random number generator.

Parameters:
  • graph – The undirected graph the algorithm runs on.

  • random – A random number generator, a copy of which is used during the algorithm.

class CliqueNodeIt

Iterator to list the nodes of the found clique.

This iterator class lists the nodes of the found clique. Before using it, you must allocate a GrossoLocatelliPullanMc instance and call its run() method.

The following example prints out the IDs of the nodes in the found clique.

GrossoLocatelliPullanMc< Graph > mc( g );
mc.run();
for( GrossoLocatelliPullanMc< Graph >::CliqueNodeIt n( mc ) ;
     n != INVALID ;
     ++n )
{
 std::cout << g.id( n ) << std::endl;
 }

Public Functions

inline CliqueNodeIt( const GrossoLocatelliPullanMc & mc )

Constructor.

Parameters:

mc – The algorithm instance.

inline operator Node() const

Conversion to Node.

inline bool operator==(Invalid) const
inline bool operator!=(Invalid) const
inline CliqueNodeIt & operator++()

Next node.

inline GR::Node operator++(int)

Postfix incrementation.

Warning

This incrementation returns a Node, not a CliqueNodeIt as one may expect.