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:
maxLengthis required. Only cycles of at mostmaxLengthrelationships 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
maxCyclescycles fails instead of returning a partial answer. You never get a silently truncated list. RaisemaxCyclesup to 2,000, or narrow what is searched withlabels,relationshipTypes,excludeNodeIds,excludeRelationshipIdsor a smallermaxLength.
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 |