强连通分量¶

本文介绍强连通分量算法，并演示如何用 GQL 实现该算法。

算法介绍¶

强连通分量用于识别有向图中任意两点互相可达的极大子图。

该过程将算法逻辑封装为可复用过程，可直接在图数据上执行并输出结果。

更多信息，请参见强连通分量。

数据模型¶

为了在 GQL 中实现强连通分量算法，使用以下数据模型创建图类型：

实体由类型为Node的点表示，点属性包括id和rating。
实体间关系由类型为Link的边表示，边属性包括weight。

该图类型的完整定义，请参见准备图数据。

过程实现 ¶

为了计算强连通分量结果，创建一个过程。

关于该过程的更多信息，请参见过程实现。下文将介绍该过程的关键组成部分及其工作原理。

该过程接受以下输入参数：

该过程不需要输入参数。

此外，在过程内部定义了以下变量：

变量名	变量类型	描述
`vertex_ids`	全局 SumAgg 聚合值变量	外层枢轴迭代所用的所有点 ID 列表。
`k_idx`	原始值变量	外层循环在 vertex_ids 中的当前索引。
`mid_id`	原始值变量	当前用于 SCC 前向/后向可达性扩展的枢轴点 ID。
`round`	原始值变量	当前外层循环轮次计数。
`max_round`	原始值变量	允许的最大外层轮次（安全上限）。
`changed`	原始值变量	当前轮可达性集合是否发生变化。
`k_reach`	全局 SumAgg 聚合值变量	从当前枢轴可达（及可回溯到枢轴）的全局点集合。
`reach`	点绑定 SumAgg 聚合值变量	从该点可达的点集合。
`component`	点绑定 SumAgg 聚合值变量	从该点可达的所有点中的最小 ID（用作 SCC 标签）。
`result_table`	表变量	存储 (vertex_id, component_id) 结果对的输出表。

以下步骤概述了该过程的逻辑：

以每个点为枢轴依次迭代；对每个枢轴，计算从它出发可达且能回溯到它的点集合。
该双向可达集合构成一个 SCC；以集合中最小 ID 作为该 SCC 的标签。
将已识别的 SCC 点从后续处理中移除，重复直至所有点均被分配。
返回所有点的（vertex_id、component_id）。

操作步骤¶

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

1. 准备图数据 ¶

创建一个与数据模型匹配的图类型。

'''
CREATE GRAPH TYPE IF NOT EXISTS strong_connected_component_graph_type AS {
    NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
    EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
}
'''

下载以下 CSV 文件，保留文件名，保存到部署目录下的examples/algorithms/strong_connected_component/：
- strong_connected_component_node.csv：点数据。
- strong_connected_component_edge.csv：边数据。
查看 CSV 内容
strong_connected_component_node.csv
```
id,rating
1,0
2,0
3,0
4,0
5,0
6,0
7,0
8,0
```
strong_connected_component_edge.csv
```
src_id,dst_id,weight
1,2,1
2,3,1
3,1,1
3,4,1
4,5,1
5,4,1
5,6,1
6,7,1
7,6,1
7,8,1
```

基于图类型创建临时图，并将数据文件加载到临时图中。

CREATE TEMPORARY GRAPH IF NOT EXISTS #strong_connected_component_graph TYPED strong_connected_component_graph_type

'''
USE #strong_connected_component_graph IMPORT INTO GRAPH {
      NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
          PATH: "file:///examples/algorithms/strong_connected_component/strong_connected_component_node.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      },
      EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
          PATH: "file:///examples/algorithms/strong_connected_component/strong_connected_component_edge.csv",
          FORMAT: "CSV",
          DELIMITER: ','
      }
  }
'''

导入成功后，在控制台执行以下查询核对点数：

'''
USE #strong_connected_component_graph
MATCH (n)
RETURN count(n) AS node_count
'''

node_count应为8。点数不符时，先按文件问题排查检查文件和导入结果。

2. 创建过程 ¶

创建实现强连通分量算法的过程。关于该过程的更多信息，请参见过程实现。

'''
CREATE OR REPLACE PROCEDURE strong_connected_component()
RETURNS (vertex_id INT64, component_id INT64)
COMMENT "Compute classic strongly connected components on a directed graph by transitive reachability closure plus mutual-reachability component propagation."
AS {
  VALUE vertex_ids ListAgg<INT64>
  VALUE k_idx INT64 = 0
  VALUE mid_id INT64 = 0
  VALUE round INT64 = 0
  VALUE max_round INT64 = 256
  VALUE changed OrAgg = true
  VALUE k_reach SetAgg<INT64>

  NODE VALUE reach SetAgg<INT64>
  NODE VALUE component MinAgg<INT64> = 9223372036854775807

  TABLE result_table TYPED TABLE {
    vertex_id INT64,
    component_id INT64
  }

  MATCH (n)
  PER NODE (n) {
    SET @vertex_ids += n.id
    SET n.@reach.clear()
    SET n.@reach += n.id
    SET n.@component = n.id
  }

  MATCH (s)-[e]->(t)
  PER PATH {
    SET s.@reach += t.id
  }

  WHILE k_idx < @vertex_ids.size() THEN {
    SET mid_id = @vertex_ids[k_idx]
    SET k_idx = k_idx + 1
    SET @k_reach.clear()

    MATCH (k)
    WHERE k.id = mid_id
    PER NODE (k) {
      SET @k_reach += k.@reach
    }

    MATCH (s)
    WHERE s.@reach.contains_key(mid_id)
    PER NODE (s) {
      SET s.@reach += @k_reach
    }
  }

  WHILE @changed AND round < max_round THEN {
    SET @changed = false
    SET round = round + 1

    MATCH (s)-[e]->(t)
    WHERE s.@reach.contains_key(t.id) AND t.@reach.contains_key(s.id)
    PER PATH {
      VALUE min_component INT64 = s.@component

      IF t.@component < min_component THEN {
        SET min_component = t.@component
      }

      IF min_component < s.@component THEN {
        SET s.@component += min_component
        SET @changed += true
      }

      IF min_component < t.@component THEN {
        SET t.@component += min_component
        SET @changed += true
      }
    }
  }

  MATCH (n)
  PER NODE (n) {
    EXPORT n.id, n.@component INTO result_table
  }

  FOR r IN result_table
  RETURN r.vertex_id AS vertex_id, r.component_id AS component_id
  ORDER BY component_id ASC, vertex_id ASC
}
'''

3. 调用过程 ¶

计算强连通分量，返回各点及其分量 ID。

USE #strong_connected_component_graph CALL strong_connected_component() RETURN vertex_id, component_id

返回：

展开查看返回

+-----------+--------------+
| vertex_id | component_id |
+-----------+--------------+
| 1         | 1            |
| 2         | 1            |
| 3         | 1            |
| 4         | 4            |
| 5         | 4            |
| 6         | 6            |
| 7         | 6            |
| 8         | 8            |
+-----------+--------------+

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 EXPORT。导出字段应与返回列及目标属性对应。

强连通分量¶

算法介绍¶

数据模型¶

过程实现¶

操作步骤¶

1. 准备图数据¶

2. 创建过程¶

3. 调用过程¶

过程实现 ¶

1. 准备图数据 ¶

2. 创建过程 ¶

3. 调用过程 ¶