Neo4j: Return only root nodes from possible child paths

Question

I have a set of (n) values which all have corresponding nodes in my graph. I start with unknown relationships to each other. (see start nodes in blue)

I want to find, as simply as possible, is if any of the value/nodes are children of any of the others then applying these rules to filter the results:

If the node is a child then discard it. (white nodes)
If the node is a root then return it. (green nodes)
If the node does not have any children also return it. (green node 673)

There can be up to 50 starting nodes. I've tried iterating through them comparing two at a time discarding them if they are a child - but the number of iterations quickly gets out of hand in larger sets. I'm hoping there is some graph magic I've overlooked. Cypher please!

Thanks!

Is this filtering only with respect to the starting nodes (meaning we don't care if they're parents or children of other nodes that aren't in the set of starting nodes)? — InverseFalcon
Yes the only nodes that are considered are those in the starting set. There are other nodes in the graph related to the starting set but they are all ignored. Any parent child relations within the starting set will be sequential meaning there will not be unspecified nodes in between a parent in the start set and a child in the start set. — Damon

stdob-- stdob-- · Accepted Answer · 2018-05-28T09:37:57

Let's say that you have an input parameter nids - set of values for the id property of node, target nodes have the label Node, the relationship between nodes is of type hasChild.

Then you need to find such nodes corresponding to the input set, and which do not have parents from the nodes corresponding to the input set:

UNWIND {nids} as nid
MATCH (N:Node {id: nid})
OPTIONAL MATCH (N:Node {id: nid})<-[:hasChild]-(P:Node) WHERE P.id IN {nids}
WITH N, collect(P) AS ts WHERE size(ts) = 0
RETURN N

And do not forget to add an index to the id property for the node:

CREATE INDEX ON :Node(id)

Neo4j: Return only root nodes from possible child paths

1 Answers