环检测（Cycle Detection）

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

算法简介

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

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

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

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

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

数据模型

本文使用如下图模型：

• 使用cd_node表示点。
• 使用cd_edge表示有向边。

操作步骤

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

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：点数据。
   • 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。点数不符时，先按文件问题排查检查文件和导入结果。

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。