TomitaSekiMc

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

template< typename GR >
class TomitaSekiMc

The exact maximum clique algorithm of Tomita and Seki.

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:

GR – The undirected graph type the algorithm runs on.

Query Functions

The results of the last run().

inline int cliqueSize() const

The size of the clique found.

inline long long treeSize() const

The number of nodes of the search tree of the last run.

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

Gives back the clique found in a bool node map.

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.

Public Types

typedef GR Graph

The undirected graph type of the algorithm.

Public Functions

inline explicit TomitaSekiMc( const GR & graph )

Constructor.

Parameters:

graph – The undirected graph the algorithm runs on.

inline TomitaSekiMc & treeLimit( long long limit )

Set the limit on the nodes of the search tree.

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.

inline bool run()

Run the algorithm.

Returns:

true if the clique found is proved maximum, false if the limit on the search tree stopped the search first.