Cycle Detection¶
Algorithm introduction¶
Cycle detection finds closed paths in a directed graph, where each path starts and ends at the same node and follows edge directions.
The procedure uses variable-length path expansion:
- Initialize each node with a single sequence containing only itself.
- Iteratively expand sequences along outgoing edges.
- If an expansion returns to the start node of a sequence, output a cycle candidate.
- Use a canonical filter (start node is the minimum ID in the cycle) to avoid duplicate outputs caused by rotation.
- Stop when no active sequence remains or a maximum depth is reached.
In each round, only nodes that receive newly expanded sequences remain active for the next frontier. If a branch reaches a node with no incoming updates, that branch is cleared immediately instead of continuing to iterate until the maximum depth.
The returned cycle list does not repeat the start node at the end. For example, 1->2->3->1 is returned as LIST[1,2,3]. If parallel edges exist, duplicate cycles can still appear because each edge path is expanded independently.
Data model¶
The following graph model is used:
- Nodes are represented by
cd_node. - Directed edges are represented by
cd_edge.
Steps¶
Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.
1. Prepare graph data¶
-
Create a graph type.
''' 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) } ''' -
Download these CSV files and save them with their original names in
examples/algorithms/cycle_detection/under your deployment directory:- cycle_detection_nodes.csv: Node data.
- cycle_detection_edges.csv: Edge data.
Preview the CSV files
cycle_detection_nodes.csvid 1 2 3 4 5 6 7 8 9 10cycle_detection_edges.csvsrc_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 -
Create a temporary graph and import data.
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" } } '''After the import succeeds, run this query in the console to check the node count:
''' USE #cycle_detection_g MATCH (n) RETURN count(n) AS node_count '''The expected
node_countis10. If it differs, check the files and import results before continuing.
2. Create a procedure¶
Choose an output option and run the procedure definition in that tab. Use the same option when calling it.
'''
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. Call the procedure¶
The following calls set the maximum path expansion depth to 10. Select the same output option used when creating the procedure.
'''
USE #cycle_detection_g
CALL cycle_detection(10)
FINISH
'''
This call writes the results to CSV files and does not return a table in the console.
On the Docker host, open the CSV files in examples/algorithms/cycle_detection/output/ under your deployment directory to view the results.
'''
USE #cycle_detection_g
CALL cycle_detection(10)
RETURN *
'''
Return:
+------------+
| cycle |
+------------+
| [3,4,5] |
| [1,2,3] |
| [7,9,10] |
| [6,7,8] |
| [7,8,9,10] |
+------------+
depth controls the maximum expansion depth. Increase it to search for longer cycles, but this also increases memory and compute cost.
Write results to a graph
If you want to persist the results in a graph instead of only exporting to files, see EXPORT.