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

# 环检测（Cycle Detection）

本文介绍有向图中的环检测算法，并演示如何用 GQL 实现。

## 算法简介

环检测用于在有向图中查找闭环路径，即路径起点和终点为同一顶点，且路径方向与边方向一致。

本文中的过程实现采用变长路径扩展策略：

1. 为每个源点初始化一个仅包含自身的序列。
2. 沿出边迭代扩展序列。
3. 如果扩展回到序列源点，则输出一个候选环。
4. 使用规范化过滤条件（环中起点为最小 ID）消除因循环位移导致的重复输出。
5. 当没有活动序列或达到最大深度时停止。

每一轮中，只有接收到新扩展序列的点会进入下一轮活动集。若某条分支到达一个没有新入边更新的点，该分支会立即清空，而不会继续迭代到最大深度。

返回结果中的`cycle`列表不会在末尾重复起点。例如，`1->2->3->1`返回为`LIST[1,2,3]`。若图中存在平行边，由于每条边路径独立扩展，仍可能出现重复环。

## 数据模型

本文使用如下图模型：

- 使用`cd_node`表示点。
- 使用`cd_edge`表示有向边。

## 操作步骤

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

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

1. 

创建图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS cycle_detection_gt AS {
  NODE TYPE cd_node (LABEL cd_node {id INT PRIMARY KEY}),
  EDGE TYPE cd_edge (cd_node)-[LABEL cd_edge {MULTIEDGE KEY()}]->(cd_node)
}
'''

````

2. 

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

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

查看 CSV 内容

cycle_detection_nodes.csv

````
id
1
2
3
4
5
6
7
8
9
10

````

cycle_detection_edges.csv

````
src_id,dst_id
1,2
2,3
3,1
3,4
4,5
5,3
5,6
6,7
7,8
8,6
2,6
4,7
7,9
9,10
10,7
8,9

````

3. 

创建临时图并导入数据。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #cycle_detection_g TYPED cycle_detection_gt

````

````
'''
USE #cycle_detection_g IMPORT INTO GRAPH {
  NODE (v@cd_node{id: id}) FROM DATAFILE {
    FORMAT: "csv",
    PATH: "file:///examples/algorithms/cycle_detection/cycle_detection_nodes.csv"
  },
  EDGE (id:src_id)-[e@cd_edge{}]->(id:dst_id) FROM DATAFILE {
    FORMAT: "csv",
    PATH: "file:///examples/algorithms/cycle_detection/cycle_detection_edges.csv"
  }
}
'''

````

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

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

````

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

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

选择一种输出方式，执行对应页签中的过程定义。后续调用时使用相同方式。

导出至文件导出至表

````
'''
CREATE OR REPLACE PROCEDURE cycle_detection (depth INT64) RETURNS () AS {
  VALUE frontier ACTIVE_SET
  VALUE has_active OrAgg = true
  VALUE iter INT64 = 0

  FILE cycles_file {cycle LIST<INT64>} = DATAFILE {
      PATH: "file:///examples/algorithms/cycle_detection/output",
      FORMAT: "CSV"
  }

  NODE VALUE curr_list ListAgg<LIST<INT64>>
  NODE VALUE new_list ListAgg<LIST<INT64>>

  MATCH (s)
  PER NODE (s) {
    SET s.@curr_list = [[s.id]]
  }
  FINALLY {
    SET frontier = s
  }

  WHILE @has_active = true AND iter < depth THEN {
    SET @has_active = false

    MATCH (s)-[e]->(t)
    WHERE s IN frontier
    PER PATH {
      VALUE t_id INT64 = t.id
      VALUE curr_sequences LIST<LIST<INT64>> = s.@curr_list
      VALUE seq_idx INT64 = 0
      VALUE seq_count INT64 = length(curr_sequences)

      WHILE seq_idx < seq_count THEN {
        VALUE sequence LIST<INT64> = curr_sequences[seq_idx]
        VALUE t_is_min BOOL = true
        VALUE v_idx INT64 = 0
        VALUE seq_len INT64 = length(sequence)

        IF t_id = sequence[0] THEN {
          WHILE v_idx < seq_len THEN {
            VALUE v_id INT64 = sequence[v_idx]
            IF v_id < t_id THEN {
              SET t_is_min = false
              BREAK
            }
            SET v_idx = v_idx + 1
          }

          IF t_is_min = true THEN {
            EXPORT sequence INTO cycles_file
          }
        } ELSE {
          VALUE contains_id BOOL = false
          VALUE c_idx INT64 = 0
          WHILE c_idx < seq_len THEN {
            IF sequence[c_idx] = t_id THEN {
              SET contains_id = true
              BREAK
            }
            SET c_idx = c_idx + 1
          }

          IF contains_id = false THEN {
            SET t.@new_list += (sequence || [t_id])
          }
        }

        SET seq_idx = seq_idx + 1
      }
    }
    PER NODE (s) {
      SET s.@curr_list = []
    }
    FINALLY {
      SET frontier = t
    }

    MATCH (t)
    WHERE t IN frontier
    PER NODE (t) {
      SET t.@curr_list = t.@new_list
      SET t.@new_list = []
    }

    MATCH (t)
    WHERE t IN frontier AND t.@curr_list.size() > 0
    PER NODE (t) {
      SET @has_active += true
    }
    FINALLY {
      SET frontier = t
    }

    SET iter = iter + 1
  }
}
'''

````

````
'''
CREATE OR REPLACE PROCEDURE cycle_detection (depth INT64) RETURNS (cycle LIST<INT64>) AS {
  VALUE frontier ACTIVE_SET
  VALUE has_active OrAgg = true
  VALUE iter INT64 = 0

  TABLE cycles_table TYPED TABLE {cycle LIST<INT64>}

  NODE VALUE curr_list ListAgg<LIST<INT64>>
  NODE VALUE new_list ListAgg<LIST<INT64>>

  MATCH (s)
  PER NODE (s) {
    SET s.@curr_list = [[s.id]]
  }
  FINALLY {
    SET frontier = s
  }

  WHILE @has_active = true AND iter < depth THEN {
    SET @has_active = false

    MATCH (s)-[e]->(t)
    WHERE s IN frontier
    PER PATH {
      VALUE t_id INT64 = t.id
      VALUE curr_sequences LIST<LIST<INT64>> = s.@curr_list
      VALUE seq_idx INT64 = 0
      VALUE seq_count INT64 = length(curr_sequences)

      WHILE seq_idx < seq_count THEN {
        VALUE sequence LIST<INT64> = curr_sequences[seq_idx]
        VALUE t_is_min BOOL = true
        VALUE v_idx INT64 = 0
        VALUE seq_len INT64 = length(sequence)

        IF t_id = sequence[0] THEN {
          WHILE v_idx < seq_len THEN {
            VALUE v_id INT64 = sequence[v_idx]
            IF v_id < t_id THEN {
              SET t_is_min = false
              BREAK
            }
            SET v_idx = v_idx + 1
          }

          IF t_is_min = true THEN {
            EXPORT sequence INTO cycles_table
          }
        } ELSE {
          VALUE contains_id BOOL = false
          VALUE c_idx INT64 = 0
          WHILE c_idx < seq_len THEN {
            IF sequence[c_idx] = t_id THEN {
              SET contains_id = true
              BREAK
            }
            SET c_idx = c_idx + 1
          }

          IF contains_id = false THEN {
            SET t.@new_list += (sequence || [t_id])
          }
        }

        SET seq_idx = seq_idx + 1
      }
    }
    PER NODE (s) {
      SET s.@curr_list = []
    }
    FINALLY {
      SET frontier = t
    }

    MATCH (t)
    WHERE t IN frontier
    PER NODE (t) {
      SET t.@curr_list = t.@new_list
      SET t.@new_list = []
    }

    MATCH (t)
    WHERE t IN frontier AND t.@curr_list.size() > 0
    PER NODE (t) {
      SET @has_active += true
    }
    FINALLY {
      SET frontier = t
    }

    SET iter = iter + 1
  }

  FOR r IN cycles_table
  RETURN r.cycle AS cycle
}
'''

````

### 3. 调用过程

以下调用将最大路径扩展深度设为`10`。选择与创建过程时相同的输出方式。

导出至文件导出至表

````
'''
USE #cycle_detection_g
CALL cycle_detection(10)
FINISH
'''

````

此调用将结果写入 CSV，控制台不返回结果表。

在宿主机的部署目录下，打开`examples/algorithms/cycle_detection/output/`中的 CSV 文件查看结果。

````
'''
USE #cycle_detection_g
CALL cycle_detection(10)
RETURN *
'''

````

返回：

````
+------------+
| cycle      |
+------------+
| [3,4,5]    |
| [1,2,3]    |
| [7,9,10]   |
| [6,7,8]    |
| [7,8,9,10] |
+------------+

````

`depth`用于控制最大扩展深度。增大该值可搜索更长的环，但会增加内存与计算开销。

将结果写入图中

如果希望将结果持久化到图，而不仅导出到文件，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。