Skip to content

Cycle Detection

A simple directed cycle starts and ends at the same node, follows every relationship in its direction, and visits no other node twice. Self-loops (a -> a), two-cycles (a -> b -> a) and longer cycles all count. Direction matters: a -> b -> c -> a is a cycle, while a -> b <- c -> a is not.

Two procedures work on a subgraph of your graph:

Procedure Returns
algo.cycle.exists One hasCycle boolean.
algo.cycle.simpleCycles One row per simple cycle, with the node IDs and relationship IDs along it.

Both procedures consider only the nodes and relationships the caller can read. Under row-level security they see the same data a MATCH query does.

Version requirement

Cycle detection from Cypher is available in PuppyGraph 1.20.0 and later.

Syntax

CALL algo.cycle.exists({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD hasCycle
RETURN hasCycle
CALL algo.cycle.simpleCycles({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  maxLength: 10,
  maxCycles: 100
})
YIELD vertexList, edgeList, length
RETURN vertexList, edgeList, length

The values in the map can be literals or query parameters, such as $labels. List only the columns you need after YIELD. A call without YIELD returns every column the procedure produces, and YIELD length AS cycleLength renames a column.

An unknown argument name, an argument of the wrong type, an out-of-range value, or a missing required argument is refused with a message that names the argument.

Note

In PuppyGraph 1.20.0, put a WITH directly before a MATCH that follows CALL ... YIELD, even when an UNWIND comes in between. The join example below uses WITH for that reason.

Sample graph

The examples on this page use the following graph. Each example is a complete query that runs as written once the graph is modeled with the Person and Account node labels and the KNOWS and TRANSFERRED_TO relationship types, using the properties in the tables below.

id name
a Alice
b Bob
c Carol
d Dave
id from to weight
k1 a a 1.0
k2 a b 2.0
k3 b a 1.0
k4 b c 1.0
k5 c d 3.0
k6 d b 1.0
id owner
x Ada
y Ben
z Cora
id from to amount
t1 x y 10.0
t2 y z 5.0
t3 z x 1.0
voided-1 y x 100.0

Node IDs use the form Person[a], the value id(n) returns. Relationship IDs use the form KNOWS[k1], the value id(r) returns.

Parameters

Name Type Default Applies to Meaning
labels list of strings required both Node labels to search.
relationshipTypes list of strings required both Relationship types to follow.
excludeNodeIds list of strings [] both Node IDs to leave out, such as Person[c].
excludeRelationshipIds list of strings [] both Relationship IDs to leave out, such as KNOWS[k6].
maxLength integer, 1 to 1000 required for simpleCycles simpleCycles Longest cycle to return, counted in relationships. exists does not accept it.
maxCycles integer, 1 to 2000 100 simpleCycles How many cycles the call may return.

labels and relationshipTypes must be non-empty lists. A null value for any argument is refused.

Output

algo.cycle.exists answers one question: is there a directed cycle anywhere in the selected subgraph? It takes no maxLength or maxCycles and does not list the cycles. It yields:

Column Type Meaning
hasCycle boolean true if at least one directed cycle exists in the selected subgraph.

The call always returns exactly one row.

algo.cycle.simpleCycles yields:

Column Type Meaning
vertexList list of strings The node IDs on the cycle, in visiting order.
edgeList list of strings The relationship IDs on the cycle. edgeList[i] runs from vertexList[i] to vertexList[i + 1], and the last one runs back to vertexList[0].
length integer The number of relationships, which equals the number of nodes.

The first node is not repeated at the end of vertexList.

One row per cycle

Each cycle (a distinct sequence of relationships) is returned once, not once per starting point. A row's vertexList starts at the lexicographically smallest node ID on the cycle, so a -> b -> a and b -> a -> b are the same row: ['Person[a]', 'Person[b]']. Several rows can have the same vertexList: when several relationships in the same direction can serve as the same step of a cycle, each distinct sequence of relationships is returned as a separate row.

Relationships are matched by direction, so two relationships between the same nodes can form a cycle when they point opposite ways. The accounts below have one relationship from x to y and one from y to x, which form a two-cycle, plus a three-cycle through all three accounts.

CALL algo.cycle.simpleCycles({
  labels: ['Account'],
  relationshipTypes: ['TRANSFERRED_TO'],
  maxLength: 4
})
YIELD vertexList, edgeList, length
RETURN vertexList, edgeList, length
ORDER BY length, vertexList
vertexList edgeList length
['Account[x]', 'Account[y]'] ['TRANSFERRED_TO[t1]', 'TRANSFERRED_TO[voided-1]'] 2
['Account[x]', 'Account[y]', 'Account[z]'] ['TRANSFERRED_TO[t1]', 'TRANSFERRED_TO[t2]', 'TRANSFERRED_TO[t3]'] 3

Bounds and errors

simpleCycles states its bounds explicitly, so an empty result is unambiguous:

  • maxLength is required. Only cycles of at most maxLength relationships are returned. An empty result means there is no directed cycle within that length, not that the graph has no cycles.
  • A call that finds more than maxCycles cycles fails instead of returning a partial answer. You never get a silently truncated list. Raise maxCycles up to 2,000, or narrow what is searched with labels, relationshipTypes, excludeNodeIds, excludeRelationshipIds or a smaller maxLength.

maxCycles is also the ceiling on one call: it can return at most 2,000 rows. A larger graph needs several calls, but a narrower selection changes which cycles can be found: a cycle that crosses two selections is not returned by either one. Split the graph so that every cycle you need stays inside one selection.

exists takes no maxLength or maxCycles and does not list cycles, so it answers even when a listing would exceed 2,000 rows.

A call is refused, with a message that names the problem, when the procedure name is unknown, when YIELD names a column the procedure does not produce, or when an argument is missing, unknown, of the wrong type or out of range.

Sizing

Raising maxCycles or maxLength uses more memory, and on a dense graph time grows quickly with maxLength. If a call is slow, lower maxLength first, then narrow the labels and relationship types. The query timeout is the hard stop on a call, so a search that finds no cycle within maxLength can still run until the timeout.

On a large cyclic graph, run exists first to confirm that cycles are there, then call simpleCycles with a small maxLength and exclude the regions you do not care about.

Examples

Does the graph contain a cycle?

CALL algo.cycle.exists({
  labels: ['Person'],
  relationshipTypes: ['KNOWS']
})
YIELD hasCycle
RETURN hasCycle
hasCycle
true

List the cycles, shortest first

CALL algo.cycle.simpleCycles({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  maxLength: 6
})
YIELD vertexList, edgeList, length
RETURN vertexList, edgeList, length
ORDER BY length, vertexList
vertexList edgeList length
['Person[a]'] ['KNOWS[k1]'] 1
['Person[a]', 'Person[b]'] ['KNOWS[k2]', 'KNOWS[k3]'] 2
['Person[b]', 'Person[c]', 'Person[d]'] ['KNOWS[k4]', 'KNOWS[k5]', 'KNOWS[k6]'] 3

Leave out a relationship

The voided-1 relationship is excluded, so the two-cycle it forms is no longer returned. The three-cycle remains.

CALL algo.cycle.simpleCycles({
  labels: ['Account'],
  relationshipTypes: ['TRANSFERRED_TO'],
  excludeRelationshipIds: ['TRANSFERRED_TO[voided-1]'],
  maxLength: 8
})
YIELD vertexList, edgeList
RETURN vertexList, edgeList
vertexList edgeList
['Account[x]', 'Account[y]', 'Account[z]'] ['TRANSFERRED_TO[t1]', 'TRANSFERRED_TO[t2]', 'TRANSFERRED_TO[t3]']

Join the cycles back to their nodes

Use WITH to carry each node ID from UNWIND into the following MATCH, then count how often each node appears on a cycle.

CALL algo.cycle.simpleCycles({
  labels: ['Person'],
  relationshipTypes: ['KNOWS'],
  maxLength: 8,
  maxCycles: 50
})
YIELD vertexList
UNWIND vertexList AS vertexId
WITH vertexId
MATCH (p:Person)
WHERE id(p) = vertexId
RETURN p.name AS name, count(*) AS appearances
ORDER BY appearances DESC, name
name appearances
Alice 2
Bob 2
Carol 1
Dave 1