Recursive traversals

Recursive queries let you follow a path to a specific depth without spelling out every hop.

Family tree example

person records linked by child_of:

CREATE |person:1..16|;
-- parents of person:1
RELATE person:1->child_of->[person:2, person:3];
-- grandparents of person:1
RELATE person:2->child_of->[person:4, person:5];
RELATE person:3->child_of->[person:6, person:7];
-- great-grandparents of person:1
RELATE person:4->child_of->[person:8, person:9];
RELATE person:5->child_of->[person:10, person:11];
RELATE person:6->child_of->[person:12, person:13];
RELATE person:7->child_of->[person:14, person:15];

You can repeat the path manually:

SELECT 
    ->child_of->person AS parents,
    ->child_of->person->child_of->person AS grandparents,
    ->child_of->person->child_of->person->child_of->person AS great_grandparents
FROM ONLY person:1;

Or use recursive path repetition:

SELECT 
    @.{1}->child_of->person AS parents,
    @.{2}->child_of->person AS grandparents,
    @.{3}->child_of->person AS great_grandparents
FROM ONLY person:1;

Recursive syntax can also return a single nested object that repeats down a path:

-- Range to start at a depth of one, try to go down to depth of three
SELECT @.{3}.{
    id,
	-- At each depth, use this path to reach the next one
    parents: ->child_of->person.@
} FROM person:1;

Starting from a record id:

person:1.{3}.{
    id,
    parents: ->child_of->person.@
};

Recursive paths are defined in idioms and are not limited to graph traversal. A record link recurses through the same syntax, with no edges involved:

CREATE cat:one   SET likes = cat:two;
CREATE cat:two   SET likes = cat:three;
CREATE cat:three SET likes = cat:one;

cat:one.{1..3}.likes;

Output

cat:one

What a recursive path needs at each step is a record, or an array of records. That is what a link and an edge have in common. A step landing on any other value ends the query rather than continuing. See Behaviour of recursive queries.

Trees of any depth

A tree, such as a set of categories or a folder structure, can be stored as one record per node with a child_of edge to its parent. Each node can then be read on its own like any other record, and a recursive path reads the tree in either direction without knowing its depth:

CREATE node:root, node:a, node:b, node:a1, node:a2, node:a1x;
RELATE [node:a, node:b]->child_of->node:root;
RELATE [node:a1, node:a2]->child_of->node:a;
RELATE node:a1x->child_of->node:a1;

-- Every ancestor of a node, nearest first
node:a1x.{..+collect}(->child_of->node);
//- [node:a1, node:a, node:root]

-- Every descendant of a node. Possible output, since the order of
-- siblings follows the IDs of their edges
node:root.{..+collect}(<-child_of<-node);
//- [node:a, node:b, node:a1, node:a2, node:a1x]

To get the tree or a subtree back in its nested shape, use .@ to repeat the same structure at each level:

node:a.{..}.{ id, children: <-child_of<-node.@ };

Possible output

{
	children: [
		{
			children: [
				{ children: [], id: node:a1x }
			],
			id: node:a1
		},
		{ children: [], id: node:a2 }
	],
	id: node:a
}

Moving a subtree is one change: delete the node's child_of edge and relate it to its new parent. A path without an upper bound stops at a depth of 256.

Family tree example

Trees of any depth

Further reading