How to modify the Bron-Kerbosch algorithm to output a list of lists (or dict of lists) of cliques, based on a clique size?
For example for the reference implementation from here - https://stackoverflow.com/a/59339555/7865680,
N = {
i: set(num for num, j in enumerate(row) if j)
for i, row in enumerate(adj_matrix)
}
print(N)
# {0: {1, 4}, 1: {0, 2, 4}, 2: {1, 3}, 3: {2, 4, 5}, 4: {0, 1, 3}, 5: {3}}
def BronKerbosch1(P, R=None, X=None):
P = set(P)
R = set() if R is None else R
X = set() if X is None else X
if not P and not X:
yield R
while P:
v = P.pop()
yield from BronKerbosch1(
P=P.intersection(N[v]), R=R.union([v]), X=X.intersection(N[v]))
X.add(v)
P = N.keys()
print(list(BronKerbosch1(P)))
# [{0, 1, 4}, {1, 2}, {2, 3}, {3, 4}, {3, 5}]
for a graph
it should output instead of
[{0, 1, 4}, {1, 2}, {2, 3}, {3, 4}, {3, 5}]
list of lists (sets)
[ [[1, 2], [2, 3], [3, 4], [3, 5]], [[0, 1, 4]] ]
or dict of lists (sets)
{ "2": [[1, 2], [2, 3], [3, 4], [3, 5]], "3": [[0, 1, 4]]]
To get a dict of lists, you can bootstrap it during the process and return it only at the end :
def BronKerbosch1(P, R=None, X=None, grp={}):
P = set(P)
R = R or set()
X = X or set()
if not P and not X:
grp.setdefault(len(R), []).append(list(R))
while P:
v = P.pop()
grp = BronKerbosch1(
P=P.intersection(N[v]), R=R.union([v]), X=X.intersection(N[v]))
X.add(v)
return grp
Output :
out = BronKerbosch1(P)
print(out) # {3: [[0, 1, 4]], 2: [[1, 2], [2, 3], [3, 4], [3, 5]]}
If the order of the keys (i.e, sizes) matters, use dict(sorted(BronKerbosch1(P).items()))
:
print(out) # {2: [[1, 2], [2, 3], [3, 4], [3, 5]], 3: [[0, 1, 4]]}