abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
Loading...
Searching...
No Matches
TomitaSekiMc< GR > Class Template Reference

The exact maximum clique algorithm of Tomita and Seki. More...

#include <lemon/tomita_seki_mc.h>

Public Types

typedef GR Graph
 The undirected graph type of the algorithm.

Public Member Functions

 TomitaSekiMc (const GR &graph)
 Constructor.
TomitaSekiMc & treeLimit (long long limit)
 Set the limit on the nodes of the search tree.
bool run ()
 Run the algorithm.
Query Functions

The results of the last run().

int cliqueSize () const
 The size of the clique found.
long long treeSize () const
 The number of nodes of the search tree of the last run.
template< typename CliqueMap >
void cliqueMap (CliqueMap &map) const
 Gives back the clique found in a bool node map.

Detailed Description

template< typename GR >
class lemon::TomitaSekiMc< GR >

This class finds a maximum clique of an undirected graph by the branch and bound of Tomita and Seki (MCQ): the candidates that may extend the current clique are colored greedily, so that those of the same color are not adjacent, and a branch is cut as soon as the current clique and the number of colors of its candidates cannot exceed the best clique found. Unlike GrossoLocatelliPullanMc, a heuristic, it proves that the clique it finds is maximum, in time that may grow exponentially with the size of the graph; a limit on the number of nodes of the search tree stops it early, with the best clique found.

Template Parameters
GRThe undirected graph type the algorithm runs on.

Constructor & Destructor Documentation

◆ TomitaSekiMc()

template< typename GR >
TomitaSekiMc ( const GR & graph)
inlineexplicit

Constructor.

Parameters
graphThe undirected graph the algorithm runs on.

Member Function Documentation

◆ treeLimit()

template< typename GR >
TomitaSekiMc & treeLimit ( long long limit)
inline

This function sets the largest number of nodes of the search tree, i.e., of the cliques that the search extends, after which run() stops; a negative one, the default, is no limit.

◆ run()

template< typename GR >
bool run ( )
inline
Returns
true if the clique found is proved maximum, false if the limit on the search tree stopped the search first.

◆ cliqueMap()

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

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