Algorithm to find lowest common ancestor in directed acyclic graph?

Question

Imagine a directed acyclic graph as follows, where:

• "A" is the root (there is always exactly one root)
• each node knows its parent(s)
• the node names are arbitrary - nothing can be inferred from them
• we know from another source that the nodes were added to the tree in the order A to G (e.g. they are commits in a version control system)

What algorithm could I use to determine the lowest common ancestor (LCA) of two arbitrary nodes, for example, the common ancestor of:

• B and E is B
• D and F is B

Note:

• There is not necessarily a single path to a given node from the root (e.g. "G" has two paths), so you can't simply traverse paths from root to the two nodes and look for the last equal element
• I've found LCA algorithms for trees, especially binary trees, but they do not apply here because a node can have multiple parents (i.e. this is not a tree)

Solution 1

Den Roman's link (Archived version) seems promising, but it seemed a little bit complicated to me, so I tried another approach. Here is a simple algorithm I used:

Let say you want to compute LCA(x,y) with x and y two nodes. Each node must have a value color and count, resp. initialized to white and 0.

1. Color all ancestors of x as blue (can be done using BFS)
2. Color all blue ancestors of y as red (BFS again)
3. For each red node in the graph, increment its parents' count by one

Each red node having a count value set to 0 is a solution.

There can be more than one solution, depending on your graph. For instance, consider this graph:

LCA(4,5) possible solutions are 1 and 2.

Note it still work if you want find the LCA of 3 nodes or more, you just need to add a different color for each of them.

Solution 2

I was looking for a solution to the same problem and I found a solution in the following paper:

http://dx.doi.org/10.1016/j.ipl.2010.02.014

In short, you are not looking for the lowest common ancestor, but for the lowest SINGLE common ancestor, which they define in this paper.

Solution 3

I know it's and old question and pretty good discussion, but since I had some similar problem to solve I came across JGraphT's Lowest Common Ancestor algorithms, thought this might be of help:

• NativeLcaFinder
• TarjanLowestCommonAncestor

Solution 4

Just some wild thinking. What about using both input nodes as roots, and doing two BFS simultaneously step by step. At a certain step, when there are overlapping in their BLACK sets (recording visited nodes), algorithm stops and the overlapped nodes are their LCA(s). In this way, any other common ancestors will have longer distances than what we have discovered.

Solution 5

Assume that you want to find the ancestors of x and y in a graph.

Maintain an array of vectors- parents (storing parents of each node).

1. Firstly do a bfs(keep storing parents of each vertex) and find all the ancestors of x (find parents of x and using parents, find all the ancestors of x) and store them in a vector. Also, store the depth of each parent in the vector.

2. Find the ancestors of y using same method and store them in another vector. Now, you have two vectors storing the ancestors of x and y respectively along with their depth.

3. LCA would be common ancestor with greatest depth. Depth is defined as longest distance from root(vertex with in_degree=0). Now, we can sort the vectors in decreasing order of their depths and find out the LCA. Using this method, we can even find multiple LCA's (if there).

View more solutions