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

  • Z时代
  • 2024-01-10
  • 分类：问答

如果您查看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

我想过滤掉所有适当的子clicli。但是您可以看到它很烂，因为我不得不对其进行两次过滤。这不是很优雅。因此，问题在于，给定对象列表（整数，字符串）的列表，这些列表是图中的节点标签；enumerate_all_cliques(G)完全返回此标签列表列表。现在，根据此列表列表，筛选出所有适当的子clicli。因此，例如：

[[a，b，c]，[a，b]，[b，c，d]] => [[[a，b，c]，[b，c，d]]

最快的pythonic方法是什么？

回答：

有一个功能：networkx.algorithms.clique.find_cliques，是的，尽管名称中没有“

maximal”，但它仅返回最大集团。它的运行速度应比任何过滤方法快得多。

如果发现名称令人困惑（我愿意），则可以重命名：

from networkx.algorithms.clique import find_cliques as maximal_cliques

以上是 如何使用networkx + python枚举图中的所有*最大*集团？ 的全部内容， 来源链接： utcz.com/qa/403106.html

回到顶部