Cypher - neo4j find recursive end nodes

Question

I'm trying to find all beginning nodes for a given node type, starting with any node in my database. These are nodes that have no relationships pointing to them.

I'm currently doing it manually, but need a recursive-type of statement to simplify and expand. Here is what I have so far, with a return statement describing what I need.

MATCH ((d1:Type1 {Name: "test1"}))
MATCH ((t1:Type2)-[:Rel1]->(h1:Type3))
MATCH ((d1)<-[ud1:Rel3]-(t1))
OPTIONAL MATCH ((h1)<-[:Rel1]-(t2:Type2))
OPTIONAL MATCH ((t2)<-[:Rel2]-(d2:Type1))
OPTIONAL MATCH ((d2)<-[ud2:Rel3]-(t3:Type2))
OPTIONAL MATCH ((t3)-[:Rel1]->(h2:Type3))
OPTIONAL MATCH ((h2)<-[:Rel1]-(t4:Type2))
OPTIONAL MATCH ((t4)<-[:Rel2]-(d3:Type1))
OPTIONAL MATCH ((d3)<-[ud3:Rel3]-(t5:Type2))

RETURN DISTINCT Type1.Name where there is no Rel3 relationship

The ask here is to navigate the recursive

Type1 < -  Type2 -> Type3 <- Type2 < - Type1 < - Type2 -> Type3 <- Type2

path, until there are no Type2s pointing to the Type1, and return the names of these Type1s.

So you want to return all Type1 nodes that don't have a Rel3 relationship? — Martin Preusse, May 09 '15 at 09:10

score 1 · Answer 1 · answered May 09 '15 at 12:01

Your query example is quite complex and contains stand-in types that make it a bit hard to understand.

I think this boils down to something quite simple, you should try this:

MATCH (startingPoint:Type1 { name: "test1" })
MATCH (startingPoint)-[:relType*]->(headNode)
OPTIONAL MATCH (headNode)-[f:relType]->()
WHERE f is null;

So all this does is match from a startingPoint through any number of relationships to a headNode. How do we know that the headNode is really at the beginning? Because we insist with the OPTIONAL MATCH that it cannot be connected to anything else further upstream. We attempt to match what would be another upstream match, and then insist with the WHERE clause that it must be missing, hence headNode is really "at the top".

Customize this with your own relTypes and labels, and you should be able to follow this pattern.

More broadly, when you're asking about a beginning node and it not having some relationships, See also this related question.

This is a great answer assuming there isn't a "middle" object in the model. I'm not sure if cypher has the syntax yet to handle this type of recursive multi-relationship traversal. See my answer for the workaround, as it just requires an additional create statement, then your solution. — Matt Kosovec, May 09 '15 at 15:58

score 1 · Answer 2 · edited May 23 '17 at 12:01

FrobberOfBits has a great answer, but doesn't address the need to navigate through mutiple nodes types recursively. I've still yet to see a syntax that allows for this type of recursive querying in Cypher.

The work around is to simply create a new relationship using the complex traversal, then use FrobberOfBits solution to find the headnode.

Here is what I came up with:

MATCH ((d1:Type1))
MATCH ((q1:Type2)-[:Rel1]->(p1:Type3))
MATCH ((d1)<-[ud1:Rel2]-(q1))
MATCH ((p1)<-[:Rel1]-(q2:Type2))
MATCH ((q2)<-[:Rel3]-(d2:Type1))
WITH  distinct d1 as child,d2 as parent
CREATE (child)<-[:ParentOf]-(parent)

This creates a new relationship type between two Type1s, removing the need to navigate through the different node types recursively, and simply allowing tree-traversal on a single node type (As FrobberOfBits masterfully explained)

Here is my resulting query using the types in the question and the above create statement, with an alternate syntax to Fibber's.

MATCH((d1:Type1 {Name: "test1"}))
OPTIONAL MATCH ((d1)<-[r1:Rel1*]-(d2:Type1))
WHERE NOT (d2)<--()
return distinct d2.Name

Sorry for the poor type masking! I should have been more creative with my aliasing.

Cypher - neo4j find recursive end nodes

2 Answers2