如果您查看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。因此,例如:
enumerate_all_cliques(G)
[[a,b,c],[a,b],[b,c,d]] => [[[a,b,c],[b,c,d]]
最快的pythonic方法是什么?
有一个功能:networkx.algorithms.clique.find_cliques,是的,尽管名称中没有“ maximal”,但它仅返回最大集团。它的运行速度应比任何过滤方法快得多。
networkx.algorithms.clique.find_cliques
如果发现名称令人困惑(我愿意),则可以重命名:
from networkx.algorithms.clique import find_cliques as maximal_cliques