neo4jtreecyphergraph-theory

Finding lowest common ancestor for more than two nodes

Finding lowest common ancestor for two nodes is:

MATCH (c {id: id1})<-[*]-(x)-[*]->(d {id: id2}) RETURN x

How can we extend this to find lowest common ancestor given a list of ids in a directed tree graph?

Solution

  • Updated answer

    To get the lowest common ancestor of all of the nodes whose ids are supplied in a single list:

    WITH [10, 2] AS ids
UNWIND ids AS id1
UNWIND ids AS id2
WITH id1, id2 WHERE id1 <> id2
MATCH ({id: id1})<--*(x)-->*({id: id2})
WITH collect(DISTINCT x) AS candidates
UNWIND candidates AS c
WITH c WHERE all(d IN candidates WHERE EXISTS { (c)-->*(d) })
RETURN candidate

    These are the steps:

    1. Form a Cartesian product of the node ids, minus the diagonal, with each pair in variables id1 and id2.

    2. Find the lowest ancestor of each pair of node ids. Collect these into a list of distinct nodes assigned to variable candidates. Our answer must be one of these nodes.

    3. Unwind these candidates and filter on the candidate that has all the other nodes as a descendent (or is itself). Only one node will satisfy this condition.

    This uses a quantified relationships, which requires version 5.9+. For earlier versions you can replace the pattern in the MATCH statement with the pattern ({id: id1})<-[*0..]-(x)-[*0..]->({id: id2}).