Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/strong_connected_component/
Documentation version: v5.3.2

# 强连通分量

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

## 算法介绍

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

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

更多信息，请参见[强连通分量](https://zh.wikipedia.org/wiki/%E5%BC%BA%E8%BF%9E%E9%80%9A%E5%88%86%E9%87%8F)。

## 数据模型

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

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

该图类型的完整定义，请参见[准备图数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/strong_connected_component/#1_prepare_graph_data)。

## 过程实现[]()

为了计算强连通分量结果，创建一个[过程](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/procedures/create/)。

关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/strong_connected_component/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

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

- 该过程不需要输入参数。

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

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

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

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

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

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)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/strong_connected_component/`：

  - [strong_connected_component_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/strong_connected_component/strong_connected_component_node.csv)：点数据。
  - [strong_connected_component_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/strong_connected_component/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

````

3. 

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

````
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`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

创建实现强连通分量算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/strong_connected_component/#procedure_implement)。 

````
'''
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](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。