如何使用networkx+python枚举图中的所有*maximal*团？

Question

如果你看https://en.wikipedia.org/wiki/Clique_problem，你会注意到集团和最大集团之间有区别。一个最大的集团不包含在其他集团中，只有它自己。所以我想要那些集团，但networkx似乎只提供：

networkx.algorithms.clique.enumerate_all_cliques(G)

所以我尝试了一个简单的for循环过滤机制（见下文）。在

def filter_cliques(self, cliques):
    # TODO: why do we need this?  Post in forum...
    res = []
    for C in cliques:
        C = set(C)
        for D in res:
            if C.issuperset(D) and len(C) != len(D):
                res.remove(D)
                res.append(C)
                break
            elif D.issuperset(C):
                break
        else:
            res.append(C)
    res1 = []
    for C in res:
        for D in res1:
            if C.issuperset(D) and len(C) != len(D):
                res1.remove(D)
                res1.append(C)
            elif D.issuperset(C):
                break
        else:
            res1.append(C)     
    return res1

我想过滤掉所有合适的子液。但正如你所见，它很糟糕，因为我必须过滤两次。不太雅致。所以，问题是，给定一个对象列表（整数、字符串），它们是图中的节点标签；enumerate_all_cliques(G)正好返回这个标签列表列表。现在，给出这个列表，过滤掉所有合适的子集合。例如：

[a，b，d]，[a，b，d]，[a，b，d]，[a，b，d]，[a，b，d]，[a，b，d]，[b，b，d]，[a，b，d]，[a，b，d]，[a，b，d]，[a，b，d]，[a，b

Python最快的方法是什么？在

Answer 1

这里有一个函数：^{}，是的，它只返回maximum团，尽管名称中没有“maximal”。它应该比任何过滤方法都快得多。在

如果您觉得名称令人困惑（我确实如此），您可以将其重命名：

from networkx.algorithms.clique import find_cliques as maximal_cliques