Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/cycle_detection/
Documentation version: v5.3.2

# 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:

1. Initialize each node with a single sequence containing only itself.
2. Iteratively expand sequences along outgoing edges.
3. If an expansion returns to the start node of a sequence, output a cycle candidate.
4. Use a canonical filter (start node is the minimum ID in the cycle) to avoid duplicate outputs caused by rotation.
5. 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](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/) to check where to run commands and how the directory is mounted.

### 1. Prepare graph data

1. 

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

````

2. 

Download these CSV files and save them with their original names in `examples/algorithms/cycle_detection/` under your deployment directory:

  - [cycle_detection_nodes.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/cycle_detection/cycle_detection_nodes.csv): Node data.
  - [cycle_detection_edges.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/cycle_detection/cycle_detection_edges.csv): Edge data.

Preview the CSV files

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 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_count` is `10`. If it differs, [check the files and import results](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) 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.

Export to fileExport to table

````
'''
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.

Export to fileExport to table

````
'''
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](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/).