修改密码

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

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

搜索
    中文

      连通分量

      概述

      连通分量算法(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
      
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写