list of sets of nodes each representing a maximal clique
auto g = Graph!int([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]); g.add(g.edge(0, 1)); g.add(g.edge(0, 2)); g.add(g.edge(1, 2)); g.add(g.edge(1, 7)); g.add(g.edge(1, 8)); g.add(g.edge(2, 3)); g.add(g.edge(3, 4)); g.add(g.edge(3, 5)); g.add(g.edge(3, 6)); g.add(g.edge(4, 5)); g.add(g.edge(4, 6)); g.add(g.edge(5, 6)); g.add(g.edge(6, 7)); g.add(g.edge(7, 8)); auto cliques = array(findAllCliques(g.adjacencyList())); assert(cliques == [ [0, 1, 2], [1, 7, 8], [2, 3], [3, 4, 5, 6], [6, 7], [9], ]);
Find all maximal cliques in a graph represented by adjacencyList. The implementation is based on version 1 of the Bron-Kerbosch algorithm [1].
[1]: Bron, C.; Kerbosch, J. (1973), "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM, 16 (9): 575–577, doi:10.1145/362342.362367.