# conncomp
图的连通分量
函数库: TyMath
# 语法
bins,binsizes = conncomp(G)
bins,binsizes = conncomp(G,outputform)
bins,binsizes = conncomp(G,type)
bins,binsizes = conncomp(G,outputform,type)
# 说明
bins,binsizes = conncomp(G) 以 bin 形式返回图 G 的连通分量。bin 编号指示图中的每个节点所属的分量。以 binsize 返回连通分量的大小。binsize[i] 会给出分量 i 中的节点数量。该方法默认返回 bins 的向量类型，且对于有向图找的是强连通分量。示例
如果 G 是无向图，则有路径相连的两个节点属于同一分量；
如果 G 是有向图，则仅当两个节点之间存在一条双向连接路径时，这两个节点才属于同一强分量。
bins,binsizes = conncomp(G，outputform) 使用 outputform 指定返回 bins 的格式，默认为 "vector" 。
bins,binsizes = conncomp(G，type) 使用 type 指定有向图时寻找的是强连通分量还是弱连通分量，默认为 "strong" 。示例
bins,binsizes = conncomp(G,outputform,type)使用一个或多个名称-值对组参量指定的其他选项。例如，conncomp(G,"vector","cell") 返回一个元胞数组来描述连通分量。
# 示例
查找图分量
创建一个具有三个连通分量的无向图。使用 conncomp 确定每个节点所属的分量。
using TyMath
G = Graph([1,1,4],[2,3,5],[1,1,1],6);
bins,binsizes = conncomp(G)
bins = 6-element Vector{Int64}:
1
1
1
2
2
3
binsizes = 3-element Vector{Int64}:
3
2
1
强和弱图分量
创建一个有向图，然后计算强连通分量和弱连通分量。弱连通分量会忽略连接边的方向。
using TyMath
s = [1,2,2,3,3,3,4,5,5,5,8,8];
t = [2,3,4,1,4,5,5,3,6,7,9,10];
G = DiGraph(s,t);
str_bins,str_binsizes = conncomp(G)
str_bins = 10-element Vector{Int64}:
4
4
4
4
4
6
5
1
3
2
str_binsizes = 6-element Vector{Int64}:
1
1
1
5
1
1
weak_bins,weak_binsizes = conncomp(G,"weak")
weak_bins = 10-element Vector{Int64}:
1
1
1
1
1
1
1
2
2
2
weak_binsizes = 2-element Vector{Int64}:
7
3
基于大小放弃图分量
使用 conncomp 的第二个输出提取图的最大分量或删除低于某个大小的分量。
创建一个有向图。该图有一个大分量、一个小分量和几个只包含一个节点的分量。
using TyMath
s = [1,2,2,3,3,3,4,5,5,5,8,8,9];
t = [2,3,4,1,4,5,5,3,6,7,9,10,10];
G = DiGraph(s,t,Float64[],20);
bin,binsize = conncomp(G,"weak")
bin = 20-element Vector{Int64}:
1
1
1
1
1
1
1
2
2
2
3
4
5
6
7
8
9
10
11
12
binsize = 12-element Vector{Int64}:
7
3
1
1
1
1
1
1
1
1
1
1
使用 binsize 提取图的最大分量。idx 是一个逻辑索引，指示每个节点是否属于最大分量。subgraph 函数从 G 中提取由 idx 选择的节点。
idx = binsize[bin] .== maximum(binsize);
SG = subgraph(G, idx);
binsizes 的一个类似用途是根据大小滤出分量。此过程与提取最大分量类似，不过在这一示例中，每个节点可以属于满足大小要求的任何分量。
滤出 G 中少于 3 个节点的任何分量。idx 是逻辑索引，指示每个节点是否属于具有 3 个或更多节点的分量。
idx = binsize[bin] .>= 3;
SG = subgraph(G, idx);
# 输入参数
G - 输入图Graph 对象 | DiGraph 对象
outputform - 输出的类型"vector" （默认） | "tuple"
输出的类型，指定为 "vector"（默认值）或 "tuple"。outputform 指定为 "vector" 后 bins 是数值向量，指示每个节点所属的连通分量。指定为 "tuple" 后 bins 是元组，bins[j] 包含属于分量 j 的所有节点的节点 ID。
示例： bins = conncomp(G,"vector")
type - 连通分量的类型"strong" （默认） | "weak"
注意
type 仅适用于使用 DiGraph 创建的有向图。
连通分量的类型，指定为 "strong"（默认值）或 "weak" 。type 指定为 "strong" 后仅当两个节点之间存在一条双向连接路径时，这两个节点才属于同一连通分量。指定为 "weak" 后只要两个节点之间存在一条连接路径（无论边的方向如何），这两个节点即属于同一连通分量。
示例： bins = conncomp(G,"weak") 计算有向图 G 的弱连通分量。
# 输出参数
bins - 连通分量向量 | 元组
连通分量，以向量或元组形式返回。bin 编号将图中的每个节点分配给一个连通分量：
如果 outputform 是 "vector"（默认值），则 bins 是数值向量，指示每个节点所属的连通分量 (bin)；
如果 outputform 是 "tuple"，则 bins 是元组，bins[j] 包含属于分量 j 的所有节点的节点 ID。
binsizes - 每个连通分量的大小向量
每个连通分量的大小，以向量形式返回。binsizes[i] 给出分量 i 中的元素数量。binsizes 的长度等于连通分量的数目 maximum(bins)。
# 详细信息
弱连通分量
只要两个节点之间存在一条连接路径（无论边的方向如何），这两个节点即属于同一弱连通分量。两个弱连通分量之间不存在任何边。
强和弱分量的概念仅适用于有向图，因为它们对于无向图来说是等价的。
强连通分量
当两个节点之间存在双向连接路径时，这两个节点属于同一强连通分量。两个强连通分量之间可以有边，但这些连接边永远不能构成循环。
强连通分量的 bin 编号方式是：连接两个分量的任何边都是从 bin 编号较小的分量指向 bin 编号较大的分量。
强和弱分量的概念仅适用于有向图，因为它们对于无向图来说是等价的。