pythonalgorithmgraphgraph-theoryclique

How to modify the Bron-Kerbosch algorithm to output a list of lists of cliques, based on a clique size?


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

enter image description here

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]]]


Solution

  • 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]]}