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.-1means that number of iterations is not limited.See also
See also
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
See also
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
See also
- Returns:
(*this)
-
inline int iterationLimit() const
The maximum number of iterations.
This function gives back the maximum number of iterations.
-1means that no limit is specified.See also
-
inline int stepLimit() const
The maximum number of search steps.
This function gives back the maximum number of search steps.
-1means that no limit is specified.See also
-
inline int sizeLimit() const
The desired clique size.
This function gives back the desired clique size that serves as a search limit.
-1means that this limit is set to the number of nodes in the graph.See also
-
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
boolnode 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.
-
enumerator RANDOM
-
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.
-
enumerator ITERATION_LIMIT
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.
-
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 CliqueNodeIt & operator++()
Next node.
-
inline GR::Node operator++(int)
Postfix incrementation.
Warning
This incrementation returns a
Node, not aCliqueNodeItas one may expect.
-
inline CliqueNodeIt( const GrossoLocatelliPullanMc & mc )