如何修改 Bron-Kerbosch 算法以根据团大小输出团列表的列表？

Question

如何修改 Bron-Kerbosch 算法以根据团大小输出团列表的列表（或列表的字典）？

例如，这里的参考实现 - 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}]

图表

它应该输出而不是

[{0, 1, 4}, {1, 2}, {2, 3}, {3, 4}, {3, 5}]

列表列表（集合）

[ [[1, 2], [2, 3], [3, 4], [3, 5]], [[0, 1, 4]] ]

或列表（集）的字典

{ "2": [[1, 2], [2, 3], [3, 4], [3, 5]], "3": [[0, 1, 4]]]

Answer 1

要获取列表的字典，您可以稍微调整算法以产生

(len(R), R)

：

    if not P and not X:
        yield (len(R), R) # << here

然后，你可以引导字典：

out = {}

for (length, cliques) in BronKerbosch1(P):
    out.setdefault(length, []).append(cliques)
    
print(out) # {3: [{0, 1, 4}], 2: [{1, 2}, {2, 3}, {3, 4}, {3, 5}]}