这些函数查找无向图中的所有团、最大团或所有极大团。还可以计算最大团的大小。
测试一个顶点集内的所有顶点对是否相邻，即它们是否构成一个团。空集和单例集被认为是团。
用法
cliques(graph, min = 0, max = 0)
largest_cliques(graph)
max_cliques(graph, min = NULL, max = NULL, subset = NULL, file = NULL)
count_max_cliques(graph, min = NULL, max = NULL, subset = NULL)
clique_num(graph)
largest_weighted_cliques(graph, vertex.weights = NULL)
weighted_clique_num(graph, vertex.weights = NULL)
clique_size_counts(graph, min = 0, max = 0, maximal = FALSE)
is_clique(graph, candidate, directed = FALSE)参数
- graph
输入图。
- min
数值常数，要查找的团大小的下限。
NULL表示没有限制，即与 0 相同。- max
数值常数，要查找的团大小的上限。
NULL表示没有限制。- subset
如果不是
NULL，则必须是顶点 ID 的向量，如果是命名图，则可以是数值或符号。该算法仅从这些顶点运行，因此仅返回所有极大团的子集。有关详细信息，请参见 Eppstein 论文。此参数可以轻松地并行查找极大团。- file
如果不是
NULL，则必须是文件名，即字符标量。算法的输出将写入此文件。（如果该文件存在，则将被覆盖。）每个团将是文件中的单独一行，其中包含其顶点的数字 ID，并以空格分隔。- vertex.weights
顶点权重向量。如果图具有
weight顶点属性，则默认情况下会使用此属性。如果图没有weight顶点属性，并且此参数为NULL，则假定每个顶点的权重为 1。请注意，当前加权团查找器的实现仅支持正整数权重。- maximal
指定是查找所有加权团 (
FALSE) 还是仅查找极大团 (TRUE)。- candidate
要测试是否为团的顶点集。
- directed
是否考虑边的方向。
值
cliques()、largest_cliques() 和 clique_num() 返回包含顶点 ID 数值向量的列表。每个列表元素都是一个团，即类 igraph.vs 的顶点序列。
如果 max_cliques() 的 file 参数不是 NULL，则它会不可见地返回 NULL。在这种情况下，输出将写入指定的文件。
clique_num() 和 count_max_cliques() 返回整数标量。
clique_size_counts() 返回一个数值向量，其中包含团的大小，使得第 i 个项目属于大小为 i 的团。当前会截断尾随零，但这在以后的版本中可能会更改。
如果候选顶点集构成一个团，则 is_clique() 返回 TRUE。
详细信息
cliques() 查找输入图中的所有完全子图，并遵守 min 和 max 参数中给出的尺寸限制。
largest_cliques() 查找输入图中所有最大的团。如果不存在包含更多顶点的其他团，则该团是最大的。
max_cliques() 查找输入图中所有极大的团。如果不能将其扩展为更大的团，则该团是极大的。最大的团始终是极大的，但是极大团不一定是最大的。
count_max_cliques() 计算极大团的数量。
clique_num() 计算最大团的大小。
clique_size_counts() 返回一个数值向量，表示给定最小和最大团大小之间的团大小的直方图。
is_clique() 测试顶点集中的所有顶点对是否已连接。
参考文献
对于极大团，实现了以下算法：David Eppstein、Maarten Loffler、Darren Strash：在接近最佳的时间内列出稀疏图中的所有极大团。https://arxiv.org/abs/1006.5440
参见
其他团：is_complete()、ivs()、weighted_cliques()
作者
Tamas Nepusz ntamas@gmail.com 和 Gabor Csardi csardi.gabor@gmail.com
C 库中的相关文档
cliques(), largest_cliques(), clique_number(), largest_weighted_cliques(), weighted_clique_number(), maximal_cliques_hist(), clique_size_hist(), is_clique().
示例
# this usually contains cliques of size six
g <- sample_gnp(100, 0.3)
clique_num(g)
#> [1] 7
cliques(g, min = 6)
#> [[1]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 27 34 39 62 63 97
#>
#> [[2]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 27 39 62 63 76 97
#>
#> [[3]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 27 39 63 76 97
#>
#> [[4]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 18 27 63 76 97
#>
#> [[5]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 32 63 76 81 97
#>
#> [[6]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 3 40 63 69 78 97
#>
#> [[7]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 32 63 78 81 97
#>
#> [[8]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 8 22 93 95 96 100
#>
#> [[9]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 1 56 58 93 97 98
#>
#> [[10]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 13 23 49 56 58 80
#>
#> [[11]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 10 13 23 49 56 80
#>
#> [[12]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 13 23 30 49 56 80
#>
#> [[13]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 2 4 21 32 78 81
#>
#> [[14]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 21 32 78 81 97
#>
#> [[15]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 8 21 32 44 67 68
#>
#> [[16]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 24 25 52 59 88 97
#>
#> [[17]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 37 62 66 73 79 97
#>
#> [[18]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 66 78 81 97
#>
#> [[19]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 14 40 63 78 81 97
#>
#> [[20]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 32 63 78 81
#>
#> [[21]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 14 32 63 78 81 97
#>
#> [[22]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 14 32 63 78 81 97
#>
#> [[23]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 63 78 81 97
#>
#> [[24]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 32 63 78 97
#>
#> [[25]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 32 78 81 97
#>
#> [[26]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 14 32 63 81 97
#>
#> [[27]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 6 27 34 39 63 97
#>
#> [[28]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 27 39 63 76
#>
#> [[29]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 6 27 39 63 76 97
#>
#> [[30]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 6 27 39 63 76 97
#>
#> [[31]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 18 27 63 76
#>
#> [[32]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 6 18 27 63 76 97
#>
#> [[33]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 6 18 27 63 76 97
#>
#> [[34]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 27 63 76 97
#>
#> [[35]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 39 63 76 97
#>
#> [[36]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 18 63 76 97
#>
#> [[37]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 27 39 63 97
#>
#> [[38]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 18 27 63 97
#>
#> [[39]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 27 39 76 97
#>
#> [[40]]
#> + 6/100 vertices, from 5a471c1:
#> [1] 4 6 18 27 76 97
#>
largest_cliques(g)
#> [[1]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 97 14 81 78 63 32
#>
#> [[2]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 97 76 63 6 27 18
#>
#> [[3]]
#> + 7/100 vertices, from 5a471c1:
#> [1] 4 97 76 63 6 27 39
#>
# To have a bit less maximal cliques, about 100-200 usually
g <- sample_gnp(100, 0.03)
max_cliques(g)
#> [[1]]
#> + 1/100 vertex, from db23a05:
#> [1] 27
#>
#> [[2]]
#> + 1/100 vertex, from db23a05:
#> [1] 51
#>
#> [[3]]
#> + 1/100 vertex, from db23a05:
#> [1] 87
#>
#> [[4]]
#> + 1/100 vertex, from db23a05:
#> [1] 21
#>
#> [[5]]
#> + 1/100 vertex, from db23a05:
#> [1] 84
#>
#> [[6]]
#> + 1/100 vertex, from db23a05:
#> [1] 11
#>
#> [[7]]
#> + 2/100 vertices, from db23a05:
#> [1] 41 30
#>
#> [[8]]
#> + 2/100 vertices, from db23a05:
#> [1] 16 36
#>
#> [[9]]
#> + 2/100 vertices, from db23a05:
#> [1] 91 73
#>
#> [[10]]
#> + 2/100 vertices, from db23a05:
#> [1] 44 48
#>
#> [[11]]
#> + 2/100 vertices, from db23a05:
#> [1] 44 14
#>
#> [[12]]
#> + 2/100 vertices, from db23a05:
#> [1] 94 54
#>
#> [[13]]
#> + 2/100 vertices, from db23a05:
#> [1] 96 7
#>
#> [[14]]
#> + 2/100 vertices, from db23a05:
#> [1] 35 58
#>
#> [[15]]
#> + 2/100 vertices, from db23a05:
#> [1] 17 97
#>
#> [[16]]
#> + 2/100 vertices, from db23a05:
#> [1] 62 37
#>
#> [[17]]
#> + 2/100 vertices, from db23a05:
#> [1] 1 9
#>
#> [[18]]
#> + 2/100 vertices, from db23a05:
#> [1] 29 2
#>
#> [[19]]
#> + 2/100 vertices, from db23a05:
#> [1] 65 60
#>
#> [[20]]
#> + 2/100 vertices, from db23a05:
#> [1] 9 56
#>
#> [[21]]
#> + 2/100 vertices, from db23a05:
#> [1] 40 93
#>
#> [[22]]
#> + 2/100 vertices, from db23a05:
#> [1] 54 14
#>
#> [[23]]
#> + 2/100 vertices, from db23a05:
#> [1] 30 86
#>
#> [[24]]
#> + 2/100 vertices, from db23a05:
#> [1] 30 72
#>
#> [[25]]
#> + 2/100 vertices, from db23a05:
#> [1] 30 34
#>
#> [[26]]
#> + 2/100 vertices, from db23a05:
#> [1] 31 86
#>
#> [[27]]
#> + 2/100 vertices, from db23a05:
#> [1] 31 69
#>
#> [[28]]
#> + 2/100 vertices, from db23a05:
#> [1] 31 36
#>
#> [[29]]
#> + 2/100 vertices, from db23a05:
#> [1] 32 60
#>
#> [[30]]
#> + 2/100 vertices, from db23a05:
#> [1] 32 49
#>
#> [[31]]
#> + 2/100 vertices, from db23a05:
#> [1] 33 49
#>
#> [[32]]
#> + 2/100 vertices, from db23a05:
#> [1] 33 5
#>
#> [[33]]
#> + 2/100 vertices, from db23a05:
#> [1] 34 90
#>
#> [[34]]
#> + 2/100 vertices, from db23a05:
#> [1] 34 85
#>
#> [[35]]
#> + 2/100 vertices, from db23a05:
#> [1] 34 10
#>
#> [[36]]
#> + 2/100 vertices, from db23a05:
#> [1] 36 72
#>
#> [[37]]
#> + 2/100 vertices, from db23a05:
#> [1] 36 50
#>
#> [[38]]
#> + 2/100 vertices, from db23a05:
#> [1] 36 28
#>
#> [[39]]
#> + 2/100 vertices, from db23a05:
#> [1] 36 20
#>
#> [[40]]
#> + 2/100 vertices, from db23a05:
#> [1] 37 69
#>
#> [[41]]
#> + 2/100 vertices, from db23a05:
#> [1] 37 6
#>
#> [[42]]
#> + 2/100 vertices, from db23a05:
#> [1] 38 45
#>
#> [[43]]
#> + 3/100 vertices, from db23a05:
#> [1] 38 26 63
#>
#> [[44]]
#> + 2/100 vertices, from db23a05:
#> [1] 38 2
#>
#> [[45]]
#> + 2/100 vertices, from db23a05:
#> [1] 39 83
#>
#> [[46]]
#> + 2/100 vertices, from db23a05:
#> [1] 39 58
#>
#> [[47]]
#> + 2/100 vertices, from db23a05:
#> [1] 42 68
#>
#> [[48]]
#> + 2/100 vertices, from db23a05:
#> [1] 42 55
#>
#> [[49]]
#> + 2/100 vertices, from db23a05:
#> [1] 43 67
#>
#> [[50]]
#> + 2/100 vertices, from db23a05:
#> [1] 43 2
#>
#> [[51]]
#> + 2/100 vertices, from db23a05:
#> [1] 45 50
#>
#> [[52]]
#> + 2/100 vertices, from db23a05:
#> [1] 45 22
#>
#> [[53]]
#> + 2/100 vertices, from db23a05:
#> [1] 46 80
#>
#> [[54]]
#> + 2/100 vertices, from db23a05:
#> [1] 46 75
#>
#> [[55]]
#> + 2/100 vertices, from db23a05:
#> [1] 46 71
#>
#> [[56]]
#> + 2/100 vertices, from db23a05:
#> [1] 46 60
#>
#> [[57]]
#> + 2/100 vertices, from db23a05:
#> [1] 47 82
#>
#> [[58]]
#> + 2/100 vertices, from db23a05:
#> [1] 47 61
#>
#> [[59]]
#> + 2/100 vertices, from db23a05:
#> [1] 47 4
#>
#> [[60]]
#> + 2/100 vertices, from db23a05:
#> [1] 49 89
#>
#> [[61]]
#> + 2/100 vertices, from db23a05:
#> [1] 49 88
#>
#> [[62]]
#> + 2/100 vertices, from db23a05:
#> [1] 49 59
#>
#> [[63]]
#> + 2/100 vertices, from db23a05:
#> [1] 49 53
#>
#> [[64]]
#> + 2/100 vertices, from db23a05:
#> [1] 50 82
#>
#> [[65]]
#> + 2/100 vertices, from db23a05:
#> [1] 52 81
#>
#> [[66]]
#> + 2/100 vertices, from db23a05:
#> [1] 52 18
#>
#> [[67]]
#> + 2/100 vertices, from db23a05:
#> [1] 53 70
#>
#> [[68]]
#> + 2/100 vertices, from db23a05:
#> [1] 53 7
#>
#> [[69]]
#> + 2/100 vertices, from db23a05:
#> [1] 55 80
#>
#> [[70]]
#> + 2/100 vertices, from db23a05:
#> [1] 55 64
#>
#> [[71]]
#> + 2/100 vertices, from db23a05:
#> [1] 56 79
#>
#> [[72]]
#> + 2/100 vertices, from db23a05:
#> [1] 56 7
#>
#> [[73]]
#> + 2/100 vertices, from db23a05:
#> [1] 57 98
#>
#> [[74]]
#> + 2/100 vertices, from db23a05:
#> [1] 57 93
#>
#> [[75]]
#> + 2/100 vertices, from db23a05:
#> [1] 57 64
#>
#> [[76]]
#> + 2/100 vertices, from db23a05:
#> [1] 58 95
#>
#> [[77]]
#> + 2/100 vertices, from db23a05:
#> [1] 58 75
#>
#> [[78]]
#> + 2/100 vertices, from db23a05:
#> [1] 58 22
#>
#> [[79]]
#> + 2/100 vertices, from db23a05:
#> [1] 58 18
#>
#> [[80]]
#> + 2/100 vertices, from db23a05:
#> [1] 59 24
#>
#> [[81]]
#> + 2/100 vertices, from db23a05:
#> [1] 59 22
#>
#> [[82]]
#> + 2/100 vertices, from db23a05:
#> [1] 61 98
#>
#> [[83]]
#> + 3/100 vertices, from db23a05:
#> [1] 61 97 12
#>
#> [[84]]
#> + 3/100 vertices, from db23a05:
#> [1] 61 97 100
#>
#> [[85]]
#> + 2/100 vertices, from db23a05:
#> [1] 61 25
#>
#> [[86]]
#> + 2/100 vertices, from db23a05:
#> [1] 63 90
#>
#> [[87]]
#> + 2/100 vertices, from db23a05:
#> [1] 63 79
#>
#> [[88]]
#> + 2/100 vertices, from db23a05:
#> [1] 63 23
#>
#> [[89]]
#> + 2/100 vertices, from db23a05:
#> [1] 66 77
#>
#> [[90]]
#> + 2/100 vertices, from db23a05:
#> [1] 66 76
#>
#> [[91]]
#> + 2/100 vertices, from db23a05:
#> [1] 66 69
#>
#> [[92]]
#> + 2/100 vertices, from db23a05:
#> [1] 66 26
#>
#> [[93]]
#> + 2/100 vertices, from db23a05:
#> [1] 67 100
#>
#> [[94]]
#> + 2/100 vertices, from db23a05:
#> [1] 68 98
#>
#> [[95]]
#> + 2/100 vertices, from db23a05:
#> [1] 68 82
#>
#> [[96]]
#> + 2/100 vertices, from db23a05:
#> [1] 68 25
#>
#> [[97]]
#> + 2/100 vertices, from db23a05:
#> [1] 70 92
#>
#> [[98]]
#> + 2/100 vertices, from db23a05:
#> [1] 70 85
#>
#> [[99]]
#> + 2/100 vertices, from db23a05:
#> [1] 71 73
#>
#> [[100]]
#> + 2/100 vertices, from db23a05:
#> [1] 71 26
#>
#> [[101]]
#> + 2/100 vertices, from db23a05:
#> [1] 72 10
#>
#> [[102]]
#> + 2/100 vertices, from db23a05:
#> [1] 73 82
#>
#> [[103]]
#> + 2/100 vertices, from db23a05:
#> [1] 73 78
#>
#> [[104]]
#> + 2/100 vertices, from db23a05:
#> [1] 73 24
#>
#> [[105]]
#> + 2/100 vertices, from db23a05:
#> [1] 73 15
#>
#> [[106]]
#> + 2/100 vertices, from db23a05:
#> [1] 73 7
#>
#> [[107]]
#> + 2/100 vertices, from db23a05:
#> [1] 74 83
#>
#> [[108]]
#> + 2/100 vertices, from db23a05:
#> [1] 74 82
#>
#> [[109]]
#> + 2/100 vertices, from db23a05:
#> [1] 74 81
#>
#> [[110]]
#> + 2/100 vertices, from db23a05:
#> [1] 74 15
#>
#> [[111]]
#> + 2/100 vertices, from db23a05:
#> [1] 75 93
#>
#> [[112]]
#> + 2/100 vertices, from db23a05:
#> [1] 75 77
#>
#> [[113]]
#> + 2/100 vertices, from db23a05:
#> [1] 75 23
#>
#> [[114]]
#> + 2/100 vertices, from db23a05:
#> [1] 75 19
#>
#> [[115]]
#> + 2/100 vertices, from db23a05:
#> [1] 76 78
#>
#> [[116]]
#> + 2/100 vertices, from db23a05:
#> [1] 77 13
#>
#> [[117]]
#> + 2/100 vertices, from db23a05:
#> [1] 79 6
#>
#> [[118]]
#> + 2/100 vertices, from db23a05:
#> [1] 79 4
#>
#> [[119]]
#> + 2/100 vertices, from db23a05:
#> [1] 80 24
#>
#> [[120]]
#> + 2/100 vertices, from db23a05:
#> [1] 80 20
#>
#> [[121]]
#> + 2/100 vertices, from db23a05:
#> [1] 80 13
#>
#> [[122]]
#> + 2/100 vertices, from db23a05:
#> [1] 81 99
#>
#> [[123]]
#> + 2/100 vertices, from db23a05:
#> [1] 82 12
#>
#> [[124]]
#> + 2/100 vertices, from db23a05:
#> [1] 85 4
#>
#> [[125]]
#> + 2/100 vertices, from db23a05:
#> [1] 86 93
#>
#> [[126]]
#> + 2/100 vertices, from db23a05:
#> [1] 86 14
#>
#> [[127]]
#> + 2/100 vertices, from db23a05:
#> [1] 86 5
#>
#> [[128]]
#> + 2/100 vertices, from db23a05:
#> [1] 86 3
#>
#> [[129]]
#> + 2/100 vertices, from db23a05:
#> [1] 88 22
#>
#> [[130]]
#> + 2/100 vertices, from db23a05:
#> [1] 88 14
#>
#> [[131]]
#> + 2/100 vertices, from db23a05:
#> [1] 88 4
#>
#> [[132]]
#> + 2/100 vertices, from db23a05:
#> [1] 89 90
#>
#> [[133]]
#> + 2/100 vertices, from db23a05:
#> [1] 90 92
#>
#> [[134]]
#> + 2/100 vertices, from db23a05:
#> [1] 95 100
#>
#> [[135]]
#> + 2/100 vertices, from db23a05:
#> [1] 97 28
#>
#> [[136]]
#> + 2/100 vertices, from db23a05:
#> [1] 97 15
#>
#> [[137]]
#> + 2/100 vertices, from db23a05:
#> [1] 97 10
#>
#> [[138]]
#> + 2/100 vertices, from db23a05:
#> [1] 98 6
#>
#> [[139]]
#> + 2/100 vertices, from db23a05:
#> [1] 98 5
#>
#> [[140]]
#> + 2/100 vertices, from db23a05:
#> [1] 99 24
#>
#> [[141]]
#> + 2/100 vertices, from db23a05:
#> [1] 100 26
#>
#> [[142]]
#> + 2/100 vertices, from db23a05:
#> [1] 2 3
#>
#> [[143]]
#> + 2/100 vertices, from db23a05:
#> [1] 3 28
#>
#> [[144]]
#> + 2/100 vertices, from db23a05:
#> [1] 6 8
#>
#> [[145]]
#> + 2/100 vertices, from db23a05:
#> [1] 8 20
#>
#> [[146]]
#> + 2/100 vertices, from db23a05:
#> [1] 19 28
#>
# Check that all returned vertex sets are indeed cliques
all(sapply(max_cliques(g), function (c) is_clique(g, c)))
#> [1] TRUE