跳到内容

图的连通分量

来源: R/components.R, R/structural-properties.R
components.Rd

计算图的最大（弱或强）连通分量

用法

component_distribution(graph, cumulative = FALSE, mul.size = FALSE, ...)

largest_component(graph, mode = c("weak", "strong"))

components(graph, mode = c("weak", "strong"))

is_connected(graph, mode = c("weak", "strong"))

count_components(graph, mode = c("weak", "strong"))

参数

graph

要分析的图。

cumulative

逻辑值，如果为 TRUE，则计算累积分布（相对频率）。

mul.size

逻辑值。如果为 TRUE，则相对频率将乘以簇大小。

...

传递给 cluster 的其他属性，目前只有 mode 有意义。

mode

字符串，可以是 “weak” 或 “strong”。对于有向图，“weak” 表示弱连通分量，“strong” 表示强连通分量。对于无向图，它将被忽略。

值

对于 is_connected()，是一个逻辑常量。

对于 components()，是一个包含三个组件的命名列表

membership

数值向量，给出每个顶点所属的簇 ID。

csize

数值向量，给出簇的大小。

no

数值常量，簇的数量。

对于 count_components()，返回一个整数常量。

对于 component_distribution()，是一个包含相对频率的数值向量。向量的长度是最大分量的大小加一。请注意（由于目前未知的原因），向量的第一个元素是大小为零的簇的数量，所以这始终为零。

对于 largest_component()，是图的最大连通分量。

详细信息

is_connected() 决定图是弱连通还是强连通。空图被认为是断开的。

components() 查找图的最大（弱或强）连通分量。

count_components() 几乎与 components() 相同，但只返回找到的簇的数量，而不是返回实际的簇。

component_distribution() 为最大连通分量大小创建直方图。

largest_component() 返回图的最大连通分量。对于有向图，可以选择最大的弱连通或强连通分量。如果大小相同，则返回按顶点 ID 顺序的第一个分量。返回的图中不保留原始图中的顶点 ID。

弱连通分量是通过简单的广度优先搜索找到的。强连通分量是通过两次连续的深度优先搜索实现的。

参见

decompose(), subcomponent(), groups()

连通分量 articulation_points(), biconnected_components(), decompose(), is_biconnected()

其他 structural.properties: bfs(), connect(), constraint(), coreness(), degree(), dfs(), distance_table(), edge_density(), feedback_arc_set(), feedback_vertex_set(), girth(), is_acyclic(), is_dag(), is_matching(), k_shortest_paths(), knn(), reciprocity(), subcomponent(), subgraph(), topo_sort(), transitivity(), unfold_tree(), which_multiple(), which_mutual()

作者

Gabor Csardi csardi.gabor@gmail.com

is_connected().

示例


g <- sample_gnp(20, 1 / 20)
clu <- components(g)
groups(clu)
#> $`1`
#>  [1]  1  3  4  5  6  7  8  9 10 12 13 14 18 19
#> 
#> $`2`
#> [1] 2
#> 
#> $`3`
#> [1] 11
#> 
#> $`4`
#> [1] 15
#> 
#> $`5`
#> [1] 16
#> 
#> $`6`
#> [1] 17
#> 
#> $`7`
#> [1] 20
#> 
largest_component(g)
#> IGRAPH 3591021 U--- 14 14 -- Erdos-Renyi (gnp) graph
#> + attr: name (g/c), type (g/c), loops (g/l), p (g/n)
#> + edges from 3591021:
#>  [1]  2-- 4  4-- 5  2-- 6  2-- 7  1-- 8  2-- 8  2--10  3--12  7--12  9--12
#> [11] 11--12  9--13 10--13  4--14