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

# K-Hop 遍历

本文介绍 K-Hop 遍历算法，并演示如何用 GQL 实现该算法。

## 算法介绍

K-Hop 遍历遍历用于枚举从源点出发在 K 条边以内可达的点。

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

更多信息，请参见 [K-Hop 遍历](https://zh.wikipedia.org/wiki/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2)。

## 数据模型

为了在 GQL 中实现 K-Hop 遍历算法，使用以下数据模型创建图类型：

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

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

## 过程实现[]()

为了计算 K-Hop 遍历结果，创建一个[过程](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/k_hop/#procedure_implement)。下文将介绍该过程的关键组成部分及其工作原理。

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

- `source_id`：`INT64`类型。 起始扩展的点 ID。
- `k`：`INT64`类型。 从源点出发的最大跳数。

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

 | 变量名 | 变量类型 | 描述
 | `frontier` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前跳层的活跃点集合。
 | `step` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 从源点出发的当前跳数。
 | `has_next` | [原始值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/value-variable/) | 当前层是否扩展到了新点。
 | `result_ids` | 全局 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 跨所有跳数累积的已访问点 ID 列表。
 | `visited` | 点绑定 [SumAgg 聚合值变量](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/variable-definition/agg/sum_agg/) | 每点标志：该点已被访问。

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

1. 将源点标记为`visited`，加入`result_ids`，并设为初始`frontier`。
2. 对每个跳步（最多`k`次），扩展`frontier`：找到所有未访问邻居，标记为`visited`，加入`result_ids`，设为新的`frontier`。
3. 当`has_next`为 false（无新点）或`step`等于`k`时停止。
4. 返回 k 跳以内所有访问点的 ID 列表。

## 操作步骤

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

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

1. 

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

````
'''
CREATE GRAPH TYPE IF NOT EXISTS k_hop_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/k_hop/`：

  - [k_hop_node.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/k_hop/k_hop_node.csv)：点数据。
  - [k_hop_edge.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/k_hop/k_hop_edge.csv)：边数据。

查看 CSV 内容

k_hop_node.csv

````
id,rating
1,0
2,2
3,1
4,0
5,0
6,2
7,1
8,2
9,0
10,1
11,0
12,2
13,1
14,1
15,0
16,2
17,0
18,1
19,2
20,0
21,2
22,1
23,0
24,1

````

k_hop_edge.csv

````
src_id,dst_id,weight
1,2,4
1,3,2
1,4,7
1,5,9
2,3,1
2,4,6
2,5,5
2,6,2
3,4,3
3,5,4
3,6,8
4,6,2
4,7,6
4,8,5
5,6,4
5,8,7
5,9,6
6,8,1
6,9,5
6,10,6
7,9,2
7,10,9
8,9,3
8,11,6
8,12,4
9,10,4
9,12,7
9,13,2
10,12,1
10,13,8
10,14,4
11,12,2
11,14,5
11,15,7
12,14,3
12,15,6
12,16,5
13,15,2
13,16,7
14,15,4
14,17,8
14,18,2
15,16,1
15,18,5
15,19,3
16,18,3
16,19,6
17,18,2
17,20,7
17,21,5
18,19,4
18,21,9
18,22,6
19,21,1
19,22,5
20,21,3
20,23,6
20,24,8
21,22,2
21,23,4
21,24,7
22,24,4
23,24,1

````

3. 

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

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #k_hop_graph TYPED k_hop_graph_type

````

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

````

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

````
'''
USE #k_hop_graph
MATCH (n)
RETURN count(n) AS node_count
'''

````

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

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

创建实现 K-Hop 遍历算法的过程。关于该过程的更多信息，请参见[过程实现](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/k_hop/#procedure_implement)。 

````
'''
CREATE OR REPLACE PROCEDURE k_hop(source_id INT64, k INT64)
RETURNS (vertex_ids LIST<INT64>)
COMMENT "Return the deduplicated exact k-hop reachable vertices from source_id in a directed graph whose vertex primary key is id. Vertices reached within fewer than k hops are excluded."
AS {
  VALUE frontier ACTIVE_SET

  VALUE step INT64 = 0
  VALUE has_next OrAgg = false
  VALUE result_ids ListAgg<INT64>

  NODE VALUE visited OrAgg = false

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    SET s.@visited = true
  }
  FINALLY {
    SET frontier = s
  }

  WHILE step < k THEN {
    SET @has_next = false
    SET step = step + 1

    MATCH (s)-[e]->(t)
    WHERE s IN frontier AND t.@visited = false
    PER PATH {
      SET t.@visited += true
      SET @has_next += true
    }
    FINALLY {
      SET frontier = t
    }

    IF @has_next = false THEN {
      BREAK
    }
  }

  IF step = k THEN {
    MATCH (n)
    WHERE n IN frontier
    PER NODE (n) {
      SET @result_ids += n.id
    }
  }

  RETURN @result_ids AS vertex_ids
}
'''

````

### 3. 调用过程[]()

从点`1`开始扩展，返回最多`2`跳内访问到的点 ID。

````
USE #k_hop_graph CALL k_hop(1, 2) RETURN vertex_ids

````

返回：

````
+--------------+
| vertex_ids   |
+--------------+
| [7, 8, 9, 6] |
+--------------+

````

保存结果到文件或图中

如需将返回的结果保存为 CSV 文件或写入图，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。导出字段应与返回列及目标属性对应。