Cypher query to match/draw the path from a leave to the root node

[guinametal]

Hi all,

I have a tree Neo4j structured with a specific type of relation. The leaves of this tree are connected with a relation of a different type(I know that because of that, it's not technically a tree anymore). I want to select some of those leaves and, for each of them, I want to match the path from the selected leaves to the root node. The idea is to spot and highlight the least common ancestor in the visualization.

I'm struggling to build a cypher query to get the desired results by no success so far. I have tried cascading matches and patterns with no success so far. Any ideas?

Thanks in advance.

[andrew_bowman · Accepted solution]

I'm going to use this model for a tree:

(:Node)-[:HAS_CHILD]->(:Node)

If you have names or ids to lookup for the leaf nodes, we can use a query like this to find a path from each leaf to the root:

MATCH  path = (root)-[:HAS_CHILD*]->(leaf:Node)
WHERE leaf.name IN $leafNames AND NOT ()-[:HAS_CHILD]->(root)
...

$leafNames is a list parameter you pass in with the names (or whatever you're using for lookup) of your leaf nodes, and you should have an index for quick MATCH operations.

The root of a tree is defined by the fact that it isn't a child of any other node, so we ensure that pattern in the WHERE clause.

Once you have that, you can UNWIND nodes(path) to get all the nodes across all paths from all the given leaf nodes, and count them up to figure out which ones are common across all the leaf nodes. Then MATCH from them to the root, and the one that is at the greatest depth should be the lowest common ancestor. Alternately, if you trace back from any of your special leaf nodes to the root, the first of the common ancestors encountered should be the lowest common ancestor.

That query might look something like this:

MATCH  path = (root)-[:HAS_CHILD*]->(leaf:Node)
WHERE leaf.name IN $leafNames AND NOT ()-[:HAS_CHILD]->(root)
UNWIND nodes(path) as node
WITH node, count(node) as frequency
WHERE frequency = size($leafNames)
MATCH path = (root)-[:HAS_CHILD*]->(node)
WHERE NOT ()-[:HAS_CHILD]->(root)
RETURN node as lowestCommonAncestor
ORDER BY length(path) DESC
LIMIT 1

[jin_what]

Thanks, it helped alot

MATCH path = (root)-[:HAS_CHILD*]->(node)
WHERE NOT ()-[:HAS_CHILD]->(root) AND NOT node.name IN $leafNames
// you can add this condition if you want to exclude the node, which can be the common ancestor of the rest in the leaf group.(In other words, if you ONLY want to return the ANCESTORS of them)

RETURN node as lowestCommonAncestor
ORDER BY length(path) DESC
LIMIT 1

[song]

Thank you
I learned a lot.

[guinametal]

Thank you. Helped a lot!