概述
连通分量算法(Connected Component)用来统计当前图集中连通分量的个数,是考察图的连通性(Connectivity)的一种指标。
连通分量是一个颗粒度较粗的计量方式,如果一张图的连通分量个数没有发生变化,从宏观上讲可以认为该图的拓扑特性没有发生变化。
基本概念
连通图
在无向图中,如果任意两个节点之间都存在路径,则称该图是连通的。下图中的红、绿两个节点之间不存在路径,因此该图不是连通的。
在有向图中,如果任意两个节点之间都至少在一个方向上有路径,则称该图是弱连通图;如果在两个方向上都有路径,则称该图是强连通图。由该定义可知,强连通图必然满足弱连通图的条件。
上图中的节点对 (1,4)
、(2,4)
和 (3,4)
只存在单向路径,该图仅满足弱连通图的条件。如果在原图上添加一条边,再次计算可得到:
修改后,图中所有节点对之间都存在双向路径,因此为强连通图。
有向图中对弱连通图的判断标准还可以理解为:忽略图中边的方向,判断任意两点之间是否存在路径。
连通分量
连通分量是指图中能够连通的极大子图。根据连通图的定义,有向图中的连通分量也可分为弱连通分量(Weakly Connected Component)和强连通分量(Strongly Connected Component)。
上面的例子对同一张图分别进行了强、弱连通分量的计算。结果表明,原图可划分为 3 个强连通分量,或 2 个弱连通分量。由于强连通分量的判断条件比弱连通分量更苛刻,有向图中的强连通分量的个数总是大于等于弱连通分量的个数。
特殊处理
孤点、不连通图
图中的每个孤点都是一个独立的连通分量,既是强连通分量,也是弱连通分量。
本算法计算图中连通分量的个数,若当前图集为全连通图,那么连通分量为 1。
自环边
自环边不影响图的连通性,即不参与连通分量的计算。
有向边
强连通分量的计算依赖有向边的方向;弱连通分量的计算会忽略边的方向。
结果和统计值
以下面的图为例,在图上运行连通分量算法:
算法结果 1:计算全图的弱联通分量,根据算法执行方式,返回 _id
、community_id
两列或 _uuid
、community_id
两列
_uuid | _id | community_id |
---|---|---|
8 | Sam | 0 |
7 | Mark | 0 |
2 | Anna | 2 |
1 | Alice | 2 |
3 | Zoe | 2 |
4 | Lee | 5 |
5 | Park | 5 |
6 | Joe | 5 |
算法统计值 1:弱联通分量个数 community_count
community_count |
---|
3 |
算法结果 2:计算全图的强联通分量,根据算法执行方式,返回 _id
、community_id
两列或 _uuid
、community_id
两列
_uuid | _id | community_id |
---|---|---|
8 | Sam | 0 |
7 | Mark | 0 |
2 | Anna | 2 |
1 | Alice | 3 |
3 | Zoe | 4 |
4 | Lee | 5 |
5 | Park | 6 |
6 | Joe | 7 |
算法统计值 2:强联通分量个数 community_count
community_count |
---|
7 |
命令和参数配置
- 命令:
algo(connected_component)
params()
参数配置项如下:
名称 |
类型 |
默认值 |
规范 |
描述 |
---|---|---|---|---|
cc_type | int | 1 | 1 或 2 | 1 或忽略代表计算弱连通分量 WCC,2 代表计算强连通分量 SCC |
limit | int | -1 | >=-1 | 需要返回的结果条数,-1 或忽略表示返回所有结果 |
order | string | / | ASC/DESC,大小写不敏感 | 对返回结果进行排序;忽略表示不排序 |
示例:计算全图的弱连通分量
algo(connected_component).params({
cc_type: 1
}) as wcc
return wcc
算法执行
任务回写
1. 文件回写
配置项 | 各列数据 |
---|---|
filename_community_id | _id ,community_id |
filename_ids | community_id ,_id ,_id ,... |
filename_num | community_id ,count |
示例:计算全图的强连通分量,将算法结果分别回写至名为 info、members 和 count 的文件
algo(connected_component).params({
cc_type: 2
}).write({
file:{
filename_community_id: "info",
filename_ids: "members",
filename_num: "count"
}
})
2. 属性回写
配置项 | 回写内容 | 类型 | 数据类型 |
---|---|---|---|
property | community_id |
点属性 | int64 |
示例:计算全图的强连通分量,将社区号回写至名为 community_id 的点属性
algo(connected_component).params({
cc_type: 2
}).write({
db:{
property: "community_id"
}
})
3. 统计回写
统计项名称 | 数据类型 | 描述 |
---|---|---|
community_count |
int | 社区数量 |
示例:计算全图的强连通分量,将算法统计值回写至任务信息
algo(connected_component).params({
cc_type: 2
}).write()
直接返回
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode | 点及其社区号 | _uuid , community_id |
1 | KV | 社区数量 | community_count |
示例:计算全图的强连通分量,将算法结果和统计值分别定义为别名 r1 和 r2 并返回
algo(connected_component).params({
cc_type: 2
}) as r1, r2
return r1, r2
流式返回
stream()
参数配置项如下:
名称 | 类型 | 默认值 | 规范 | 描述 |
---|---|---|---|---|
mode | int | 1 | 1 或 2 | 1 或忽略代表返回各点的社区号,2 代表返回各社区的点数量 |
别名序号 |
类型 | 描述 | 列名 |
---|---|---|---|
0 | []perNode 或 []perCommunity | 点及其社区号或社区号及其点数量 | community_id , _uuid 或 community_id , count |
示例:计算全图的弱连通分量,将算法结果定义为别名 communities,返回各社区号及其点数量,按点数量降序排列
algo(connected_component).params({
order: "desc"
}).stream({
mode: 2
}) as communities
return communities
实时统计
别名序号 | 类型 | 描述 | 列名 |
---|---|---|---|
0 | KV | 社区数量 | community_count |
示例:计算全图的弱连通分量,将算法统计值定义为别名 count 并返回
algo(connected_component).params().stats() as count
return count