修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交

搜索
v4.0
    v4.0

    连通分量

    概述

    连通分量算法(Connected Component)用来统计当前图集中连通分量的个数,是考察图的连通性(Connectivity)的一种指标。

    连通分量是一个颗粒度较粗的计量方式,如果一张图的连通分量个数没有发生变化,从宏观上讲可以认为该图的拓扑特性没有发生变化。

    基本概念

    连通图

    在无向图中,如果任意两个节点之间都存在路径,则称该图是连通的。下图中的红、绿两个节点之间不存在路径,因此该图不是连通的。

    在有向图中,如果任意两个节点之间都至少在一个方向上有路径,则称该图是弱连通图;如果在两个方向上都有路径,则称该图是强连通图。由该定义可知,强连通图必然满足弱连通图的条件。

    上图中的节点对 (1,4)(2,4)(3,4) 只存在单向路径,该图仅满足弱连通图的条件。如果在原图上添加一条边,再次计算可得到:

    修改后,图中所有节点对之间都存在双向路径,因此为强连通图。

    有向图中对弱连通图的判断标准还可以理解为:忽略图中边的方向,判断任意两点之间是否存在路径。

    连通分量

    连通分量是指图中能够连通的极大子图。根据连通图的定义,有向图中的连通分量也可分为弱连通分量(Weakly Connected Component)和强连通分量(Strongly Connected Component)。

    上面的例子对同一张图分别进行了强、弱连通分量的计算。结果表明,原图可划分为 3 个强连通分量,或 2 个弱连通分量。由于强连通分量的判断条件比弱连通分量更苛刻,有向图中的强连通分量的个数总是大于等于弱连通分量的个数。

    特殊处理

    孤点、不连通图

    图中的每个孤点都是一个独立的连通分量,既是强连通分量,也是弱连通分量。

    本算法计算图中连通分量的个数,若当前图集为全连通图,那么连通分量为 1。

    自环边

    自环边不影响图的连通性,即不参与连通分量的计算。

    有向边

    强连通分量的计算依赖有向边的方向;弱连通分量的计算会忽略边的方向。

    结果和统计值

    以下面的图为例,在图上运行连通分量算法:

    算法结果 1:计算全图的弱联通分量,根据算法执行方式,返回 _idcommunity_id 两列或 _uuidcommunity_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:计算全图的强联通分量,根据算法执行方式,返回 _idcommunity_id 两列或 _uuidcommunity_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, _uuidcommunity_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
    
    请完成以下信息后可下载此书
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写