Path & Algorithm Procedures

Algorithm Procedures

algo.allsimplepaths()

Find all simple paths (without repeated nodes) between two nodes.

Syntax: CALL algo.allsimplepaths(startNode, endNode, relTypes, maxDepth) YIELD path

Parameters:

Parameter Type Description

startNode

Node

Starting node

endNode

Node

Target node

relTypes

String/List

Relationship type(s) to traverse

maxDepth

Integer

Maximum path length

Returns: path - Each simple path found

APOC Compatible: apoc.algo.allSimplePaths

MATCH (a:Person {name: 'Alice'}), (b:Person {name: 'Bob'})
CALL algo.allsimplepaths(a, b, 'KNOWS', 5) YIELD path
RETURN path

See reference/graph-algorithms/path-finding.adoc#algo-all-simple-paths in the Graph Algorithms appendix for full parameter reference and examples.

algo.astar()

Find the shortest path using A* algorithm with optional geographic heuristics.

Syntax: CALL algo.astar(startNode, endNode, relType, weightProperty, [latProperty], [lonProperty]) YIELD path, weight

Parameters:

Parameter Type Description

startNode

Node

Starting node

endNode

Node

Target node

relType

String

Relationship type to traverse

weightProperty

String

Edge property to use as weight

latProperty

String

Optional - Node property for latitude (for geographic heuristic)

lonProperty

String

Optional - Node property for longitude (for geographic heuristic)

Returns:

  • path - The shortest path

  • weight - Total path weight

APOC Compatible: apoc.algo.aStar

MATCH (a:City {name: 'Seattle'}), (b:City {name: 'Miami'})
CALL algo.astar(a, b, 'FLIGHT', 'distance', 'lat', 'lon') YIELD path, weight
RETURN path, weight

See reference/graph-algorithms/path-finding.adoc#algo-astar in the Graph Algorithms appendix for full parameter reference and examples.

algo.dijkstra()

Find the shortest weighted path between two nodes using Dijkstra’s algorithm.

Syntax: CALL algo.dijkstra(startNode, endNode, relType, weightProperty, [direction]) YIELD path, weight

Parameters:

Parameter Type Description

startNode

Node

Starting node

endNode

Node

Target node

relType

String

Relationship type to traverse

weightProperty

String

Edge property to use as weight

direction

String

Optional - Traversal direction ("OUT", "IN", "BOTH", default: "BOTH")

Returns:

  • path - The shortest path

  • weight - Total path weight

APOC Compatible: apoc.algo.dijkstra

MATCH (a:City {name: 'New York'}), (b:City {name: 'Los Angeles'})
CALL algo.dijkstra(a, b, 'ROAD', 'distance') YIELD path, weight
RETURN path, weight

See reference/graph-algorithms/path-finding.adoc#algo-dijkstra in the Graph Algorithms appendix for full parameter reference and examples.

Path Functions (Extended)

The path. functions take any Cypher path: one bound by a MATCH pattern or shortestPath(), one a procedure yields (see reference/graph-algorithms/path-finding.adoc#graph-algo-path-value), or one another path. function returned. A value that is not a path is an error.

path.combine()

Combine two paths into one: the second path continues from where the first ends. The end node of path1 must be the start node of path2, otherwise it is an error; a null path returns the other one. path.combine([p1, p2, …​]) combines a list of paths in order.

Syntax: path.combine(path1, path2)

Returns: Path - Combined path

MATCH p1 = (a:N {id: 1})-[:R]->(b:N {id: 2}), p2 = (b)-[:R]->(c:N {id: 3})
RETURN path.combine(p1, p2) AS combined
Since v26.10.2. Earlier versions took a single argument (a list of paths) and refused the documented two-argument form.

APOC Compatible: apoc.path.combine

path.create()

Create a path from a start node and the relationships that continue it. Each relationship must touch the node the path has reached so far, in either direction, and the path continues to its other node; a null relationship is skipped.

Syntax: path.create(startNode, relationships)

Returns: Path - Created path

Since v26.10.2 the nodes of the path are the ones the relationships reach, and a relationship that does not continue the path is an error. Earlier versions returned a path holding the start node alone beside all the relationships.

APOC Compatible: apoc.path.create

path.elements()

Get all elements (nodes and relationships) of a path, in path order: [node, relationship, node, …​].

Syntax: path.elements(path)

Returns: List - List of nodes and relationships

APOC Compatible: apoc.path.elements

path.slice()

Get a slice of a path: the relationships from start (inclusive) to end (exclusive, the path’s length when omitted) and the nodes they join.

Syntax: path.slice(path, start, [end])

Returns: Path - Sliced path

APOC Compatible: apoc.path.slice

Path Expansion Procedures

Relationship and label filters

All the path expansion procedures read relationshipFilter and labelFilter in APOC’s syntax.

Relationship filter: [<]TYPE1[>]|[<]TYPE2[>]|…​

Entry Follows

TYPE

TYPE in both directions

TYPE>

TYPE outgoing only

<TYPE

TYPE incoming only

>

every relationship type, outgoing only

<

every relationship type, incoming only

| separates the alternatives of one hop, each with its own direction ('ROAD>|<RAIL'). A comma separates the hops of a repeating sequence: 'NEXT>,<FOLLOWS' follows NEXT outgoing on the first hop, FOLLOWS incoming on the second, NEXT outgoing on the third, and so on. A null or empty filter follows every relationship in both directions.

Label filter: [-/>]LABEL1|[-/>]LABEL2|…​

Entry Meaning

-Label

Denylist: no node of the path can carry the label

/Label

Termination: only paths ending at a node with the label are returned, and the expansion stops there

>Label

End node: only paths ending at a node with the label are returned, and the expansion continues past it if the allowlist lets it

+Label or Label

Allowlist: every node of the path must carry one of the labels

*

Any label

A:B

A node carrying both labels

Each entry carries its own operator, and the operators apply in the order denylist, termination, end node, allowlist, whatever order they are written in. A comma separates the filters of a repeating sequence, one per depth. A node carries a label when its type is, or extends, that vertex type, so a node with several labels matches each of them.

The filters do not apply to the start node unless filterStartNode: true is set. When the label filter names termination or end nodes, the zero-length path at the start node is not returned unless it qualifies.

Node lists: endNodes, terminatorNodes, allowlistNodes and denylistNodes are the operators >, /, + and - of the label filter, naming nodes instead of labels. Each takes a list of nodes (a single node is a list of one; whitelistNodes and blacklistNodes are the older names of the last two):

Option Meaning

denylistNodes

No node of the path can be one of them

terminatorNodes

Only paths ending at one of them are returned, and the expansion stops there

endNodes

Only paths ending at one of them are returned, and the expansion continues past it

allowlistNodes

Every node of the path must be one of them; the end and terminator nodes are allowed too

The lists combine with the label filter and with each other: a node is an answer, and the expansion goes on past it, only if every filter says so. A terminator node closer to the start than minLevel does not stop the expansion. The start node is left out of the denylist and the allowlist, and cannot be an end or terminator node, unless filterStartNode: true is set.

MATCH (a:City {name: 'A'}), (c:City {name: 'C'}), (p:City {name: 'P'})
CALL path.expandconfig(a, {relationshipFilter: 'ROAD>', endNodes: [c, p]}) YIELD path
RETURN path

Additional configuration options (path.expandconfig, path.spanningtree, path.subgraphall, path.subgraphnodes):

Option Default Description

sequence

Label and relationship filters alternating, one pair per step of a repeating sequence, for example 'Post, NEXT>, Reply, <FROM'. It takes precedence over relationshipFilter and labelFilter

filterStartNode

false

Whether the label filter and the node lists apply to the start node too

beginSequenceAtStart

true

Whether the first label filter of a sequence applies to the start node. When false, the sequence starts one hop away, and a sequence starts with a relationship filter

endNodes, terminatorNodes, allowlistNodes, denylistNodes

Node lists, see above

uniqueness

RELATIONSHIP_PATH

What the walk may visit more than once, see uniqueness. Only path.expandconfig honours it

optional

false

When the walk finds nothing, answer one row with a null path (or node) instead of none. Not read by path.subgraphall, whose answer is two lists

limit

no limit

The most paths (nodes, for path.subgraphnodes and path.subgraphall) to return. A negative value is no limit

maxLevel

no limit

The longest path. A negative value is no limit

Uniqueness. The uniqueness option of path.expandconfig takes APOC’s nine values, case-insensitively:

Value A walk may visit

RELATIONSHIP_PATH (default)

a node many times, but a relationship once per path: every trail is a path

NODE_PATH

a node once per path: every simple path is a path

NODE_GLOBAL

a node once in the whole walk: each node is reached once, along the first route to it (the shortest one when bfs is true)

NODE_LEVEL

a node once at each distance from the start

NODE_RECENT

a node again only after 10000 other nodes were visited

RELATIONSHIP_GLOBAL

a relationship once in the whole walk

RELATIONSHIP_LEVEL

a relationship once at each distance from the start

RELATIONSHIP_RECENT

a relationship again only after 10000 others were walked

NONE

anything

Whatever the value, the expansion never leaves a node by the relationship it arrived by. A value that is none of these is refused (uniqueness 'X' is not one of NODE_GLOBAL, …​); APOC quietly uses its default instead. The values scoped to a level or to the walk keep the first route that reaches a node or a relationship, so which of several equal routes they report depends on the order the expansion meets them in. path.spanningtree, path.subgraphnodes and path.subgraphall are always NODE_GLOBAL, as in APOC: the option is read and checked there, and does not change the answer.

The trails of a graph with cycles or with several routes to a node are exponential in the depth, and the default uniqueness returns all of them. Bound the walk with maxLevel and limit, or choose NODE_GLOBAL or NODE_PATH. The walk produces its paths as the query reads them, so a limit (or a LIMIT after the call) ends it early; the command timeout ends it too, and the branches it holds are charged to the query’s heap (arcadedb.queryMaxHeapElementsAllowedPerOp, arcadedb.queryMaxHeapRAM), so a walk too wide for them fails the query instead of the server. That includes a breadth-first walk of a very wide component, path.spanningtree included: a level with more branches than arcadedb.queryMaxHeapElementsAllowedPerOp (auto-scaled with the heap, never below 500000) fails with a heap-limit error that names the setting, which can be raised.

Every relationship type and label named in a filter must exist in the schema, and a name of the wrong kind is refused: relationshipFilter: 'ROADS' raises relationship type 'ROADS' does not exist rather than returning nothing. Neo4j answers such a filter with an empty result instead.

Before 26.10.2 the direction markers and the label operators were read as part of the name, so 'ROAD>' or '+Person' matched nothing and the procedures answered an empty result, and a comma in a filter separated alternatives rather than the hops of a sequence. Since 26.10.2 path.spanningtree, path.subgraphall and path.subgraphnodes also honour minLevel (0 includes the start node, 1 leaves it out, any other value is refused, as in APOC), and a config argument that is not a map is refused instead of being ignored.
Before 26.10.2 the node lists, uniqueness, optional and the negative maxLevel and limit were ignored. In path.expandconfig the breadth-first walk always reached each node once (what is now NODE_GLOBAL) and the depth-first walk, and path.expand, always walked each node once per path (NODE_PATH). The default is now APOC’s, so a call on a graph with a cycle or with several routes to a node returns more paths than before. To keep the old answer, add uniqueness: 'NODE_GLOBAL' to a call, and uniqueness: 'NODE_PATH' to a call with bfs: false. A path.expand(n, rels, labels, min, max) is path.expandconfig(n, {relationshipFilter: rels, labelFilter: labels, minLevel: min, maxLevel: max, bfs: false, uniqueness: 'NODE_PATH'}) as it used to answer.

path.expand()

Expand paths from a starting node following relationship types and node labels.

Syntax: CALL path.expand(startNode, relationshipFilter, labelFilter, minDepth, maxDepth) YIELD path

Parameters:

Parameter Type Description

startNode

Node

Starting node

relationshipFilter

String

Relationship types and directions, see filters (e.g., "KNOWS>|<WORKS_WITH")

labelFilter

String

Node label filter, see filters (e.g., "+Person")

minDepth

Integer

Minimum path length (a negative value is 0)

maxDepth

Integer

Maximum path length (a negative value is no limit)

Returns: path - Each expanded path

The walk is APOC’s for this form: breadth-first, over the trails of the graph (RELATIONSHIP_PATH uniqueness, see uniqueness), so a path may pass through a node more than once. Use path.expandconfig to choose another.

APOC Compatible: apoc.path.expand

MATCH (a:Person {name: 'Alice'})
CALL path.expand(a, 'KNOWS|WORKS_WITH', 'Person', 1, 3) YIELD path
RETURN path

path.expandconfig()

Expand paths using a configuration map for more control.

Syntax: CALL path.expandconfig(startNode, config) YIELD path

Configuration options:

Option Type Description

relationshipFilter

String/List

Relationship types and directions, see filters

labelFilter

String/List

Node label filter, see filters

sequence, filterStartNode, beginSequenceAtStart

See filters

endNodes, terminatorNodes, allowlistNodes, denylistNodes

List

Node lists, see filters

uniqueness

String

What the walk may visit more than once, see uniqueness (default: RELATIONSHIP_PATH)

minLevel

Integer

Minimum depth (default: 0)

maxLevel

Integer

Maximum depth (default: unlimited; a negative value is unlimited)

bfs

Boolean

Use BFS (true) or DFS (false) (default: true)

limit

Integer

Maximum number of paths to return (default: unlimited; a negative value is unlimited)

optional

Boolean

When no path is found, return one row with a null path (default: false)

Returns: path - Each expanded path

APOC Compatible: apoc.path.expandConfig

MATCH (a:Person {name: 'Alice'})
CALL path.expandconfig(a, {
  relationshipFilter: 'KNOWS|WORKS_WITH',
  labelFilter: 'Person',
  minLevel: 1,
  maxLevel: 3,
  bfs: true,
  limit: 100
}) YIELD path
RETURN path

path.spanningtree()

Get a spanning tree from the start node to all reachable nodes.

Syntax: CALL path.spanningtree(startNode [, config]) YIELD path

Returns: path - Each path in the spanning tree

APOC Compatible: apoc.path.spanningTree

MATCH (root:Category {name: 'Root'})
CALL path.spanningtree(root, {relationshipFilter: 'HAS_CHILD', maxLevel: 5}) YIELD path
RETURN path

path.subgraphall()

Get all nodes and relationships reachable from a starting node.

Syntax: CALL path.subgraphall(startNode [, config]) YIELD nodes, relationships

Returns:

  • nodes - List of all reachable nodes

  • relationships - List of every relationship between those nodes

APOC Compatible: apoc.path.subgraphAll

MATCH (a:Person {name: 'Alice'})
CALL path.subgraphall(a, {relationshipFilter: 'KNOWS', maxLevel: 2}) YIELD nodes, relationships
RETURN size(nodes) AS nodeCount, size(relationships) AS relCount
Yield only what you need. YIELD nodes on its own does not read a single edge record, while YIELD nodes, relationships has to load one per relationship in the component. On a large component that is the difference between a walk whose cost follows the number of nodes and one that follows the number of relationships.

nodes and relationships are returned in breadth-first order from the starting node. Before 26.10.1 the order was unspecified and effectively arbitrary.

relationships is every relationship, of any type, whose two endpoints are both in nodes, whatever the relationshipFilter that found the nodes, matching apoc.path.subgraphAll: with relationshipFilter: 'R>' a relationship of type S between two of the nodes is in the answer, though the walk did not follow it. A relationship that leads out of the subgraph is not, and neither is one that touches the start node when minLevel: 1 leaves it out of nodes. Before 26.10.2 the answer was the relationships the walk followed. Finding them reads the outgoing adjacency of each returned node (an entry per relationship, by the identity of its far end: the record of a relationship that leads out of the subgraph is never read), so a node with a very large number of relationships of filtered-out types pays for scanning them.

A node is reached only through a relationship whose record exists. When the record is gone but the adjacency lists of its two endpoints still name it (a dangling entry, left behind by an incomplete replication or a partially rolled-back transaction), the entry is skipped and reported in the log, by every path procedure alike: path.subgraphnodes, path.subgraphall, path.spanningtree and path.expandconfig return the same nodes, and each node of path.subgraphall is the start node or an endpoint of one of the relationships returned with it. Another, live, relationship to the same node still reaches it. The check asks the bucket whether the record exists, once per node reached, and reads no record. Before 26.11.1 path.subgraphnodes and path.subgraphall followed such an entry, and returned a node that no returned relationship touched.

Before 26.10.1, a labelFilter that excluded a neighbour could still leave the edge reaching it in relationships, even though that neighbour was missing from nodes.

path.subgraphnodes()

Get all nodes reachable from a starting node within configured constraints.

Syntax: CALL path.subgraphnodes(startNode [, config]) YIELD node

Returns: node - Each reachable node

APOC Compatible: apoc.path.subgraphNodes

MATCH (a:Person {name: 'Alice'})
CALL path.subgraphnodes(a, {relationshipFilter: 'KNOWS', maxLevel: 3}) YIELD node
RETURN node.name
Nodes are returned in breadth-first order from the starting node. Before 26.10.1 the order was unspecified.