![]() |
abLEMON 1.9.0-101-gccb8629
A maintained fork of LEMON
|
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. | |
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.
| GR | The undirected graph type the algorithm runs on. |
|
inlineexplicit |
Constructor.
| graph | The undirected graph the algorithm runs on. |
|
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.
|
inline |
true if the clique found is proved maximum, false if the limit on the search tree stopped the search first.
|
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.