find_cliques

find_cliques(G, nodes=None)

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

对于每个节点 n，n 的最大团是一个包含 n 的最大完全子图。最大的最大团有时被称为 最大团。

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

此函数接受一个 nodes 列表，并且只返回包含所有这些 nodes 的最大团。如果需要某些特定团，这可以显著加快运行时间。

Parameters:

GNetworkX 图

一个无向图。

nodes列表, 可选 (默认=None)

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

Returns:

迭代器

一个最大团的迭代器，每个团是 G 中的节点列表。如果提供了 nodes ，则只返回包含 nodes 中所有节点的最大团。团的顺序是任意的。

Raises:

ValueError

如果 nodes 不是一个团。

See also

find_cliques_recursive

相同算法的递归版本。

Notes

要获取所有最大团的列表，请使用 list(find_cliques(G)) 。然而，请注意，在最坏情况下，这个列表的长度可能是图中节点数量的指数倍。此函数通过仅在搜索期间保留当前候选节点列表来避免在内存中存储所有团。

此实现基于 Bron 和 Kerbosch (1973) [1] 发表的算法，由 Tomita, Tanaka 和 Takahashi (2006) [2] 改编，并在 Cazals 和 Karande (2008) [3] 中讨论。它基本上展开了参考文献中使用的递归，以避免递归栈深度问题（对于递归实现，请参阅 find_cliques_recursive() ）。

此算法忽略自环和平行边，因为团通常不定义为包含此类边。

References

[1]

Bron, C. 和 Kerbosch, J. “Algorithm 457: finding all cliques of an undirected graph”. Communications of the ACM 16, 9 (Sep. 1973), 575–577. <http://portal.acm.org/citation.cfm?doid=362342.362367>

[2]

Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, “The worst-case time complexity for generating all maximal cliques and computational experiments”, Theoretical Computer Science, Volume 363, Issue 1, Computing and Combinatorics, 10th Annual International Conference on Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28–42 <https://doi.org/10.1016/j.tcs.2006.06.015>

[3]

F. Cazals, C. Karande, “A note on the problem of reporting maximal cliques”, Theoretical Computer Science, Volume 407, Issues 1–3, 6 November 2008, Pages 564–568, <https://doi.org/10.1016/j.tcs.2008.05.010>

Examples

>>> from pprint import pprint  # 用于漂亮的字典格式化
>>> G = nx.karate_club_graph()
>>> sum(1 for c in nx.find_cliques(G))  # G 中最大团的数量
36
>>> max(nx.find_cliques(G), key=len)  # G 中最大的最大团
[0, 1, 2, 3, 13]

最大团的大小被称为图的 团数，可以直接通过以下方式找到：

>>> max(len(c) for c in nx.find_cliques(G))
5

还可以计算 G 中包含给定节点的最大团数量。以下代码生成一个以节点为键、值为包含该节点的最大团数量的字典：

>>> pprint({n: sum(1 for c in nx.find_cliques(G) if n in c) for n in G})
{0: 13,
 1: 6,
 2: 7,
 3: 3,
 4: 2,
 5: 3,
 6: 3,
 7: 1,
 8: 3,
 9: 2,
 10: 2,
 11: 1,
 12: 1,
 13: 2,
 14: 1,
 15: 1,
 16: 1,
 17: 1,
 18: 1,
 19: 2,
 20: 1,
 21: 1,
 22: 1,
 23: 3,
 24: 2,
 25: 2,
 26: 1,
 27: 3,
 28: 2,
 29: 2,
 30: 2,
 31: 4,
 32: 9,
 33: 14}

或者，类似地， G 中包含给定节点的最大团。例如，包含节点 31 的 4 个最大团：

>>> [c for c in nx.find_cliques(G) if 31 in c]
[[0, 31], [33, 32, 31], [33, 28, 31], [24, 25, 31]]