find_cliques

find_cliques(G, nodes=None)

返回无向图中的所有最大组。

对于每个节点 n ，a N的最大团 是包含以下内容的最大完全子图 n 。最大的最大派系有时被称为 最大派系 。

此函数返回一个迭代器，每个迭代器都是一个节点列表。它是一个迭代实现，因此不应该受到递归深度问题的影响。

此函数接受 nodes 只有包含所有这些的最大派系 nodes 都被退回了。如果需要一些特定的小集团，它可以大大加快运行时间。

参数

G网络X图表

无向图。

nodes列表，可选(默认=无)

如果提供，则仅提供 最大团 包含中的所有节点 nodes 。如果 nodes 本身不是一个集团，则会引发ValueError。

返回

迭代器

极大团上的迭代器，每个团都是中的节点列表 G 。如果 nodes 中的所有节点的最大团 nodes 都被退回了。集团的顺序是武断的。

加薪

ValueError

如果 nodes 不是一个小圈子。

参见

find_cliques_recursive

同一算法的递归版本。

笔记

要获得所有最大群体的列表，请使用 list(find_cliques(G)) 是的。但是，请注意，在最坏的情况下，此列表的长度可以是图中节点数的指数。此函数通过仅在搜索期间将当前候选节点列表保留在内存中，避免将所有团存储在内存中。

该实现基于Bron和KerBosch(1973)发布的算法。 [1], 由富田、田中和高桥改编(2006) [2] 并在《卡泽尔与卡兰德》(2008)中进行了讨论 [3]. 它本质上是展开引用中使用的递归，以避免递归堆栈深度问题(有关递归实现，请参见 find_cliques_recursive() )。

该算法忽略了自循环和平行边，因为通常不使用这些边定义群。

工具书类

1

bron，c.和kerbosch，j.“算法457：寻找无向图的所有组别”。 ACM的通信 16，9（1973年9月），575-577.<http://portal.acm.org/ci典.cfm？doid=362342.362367>

2

Etsuji Tomita、Akira Tanaka、Haruhisa Takahashi，“产生所有最大群体和计算实验的最坏情况下的时间复杂性”， 理论计算机科学 ，第363卷，第1期，计算与组合学，第10届计算与组合学国际年会（Cocoon 2004），2006年10月25日，第28-42页<https://doi.org/10.1016/j.tcs.2006.06.015>

3

F.Cazals，C.Karande，“关于报告最大派系问题的说明”， 理论计算机科学 ，第407卷，第1-3期，2008年11月6日，第564-568页，<https://doi.org/10.1016/j.tcs.2008.05.010>