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)

Answer 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.