What are the practical applications of the lowest common ancestor algorithms? [closed]

Question

I was having a look at this question and then reading about Tarjan's least common ancestors algorithm. I never came across any applications of LCA algorithms before.

Where are such LCA algorithms commonly used?

Wapiti

Spatial data structure trees in scientific computing, suffix trees for strings in computational biology, etc. Forgot the details, sorry, but it's definitely useful. – Hohenstaufen

Answer 1

In compilers, the LCA of two basic blocks is a place you can put a computation so it is available to both. This might be useful for eliminating common subexpressions, or inserting phi-node for SSA conversion. These algorithms are well evolved and highly optimized, though, so the LCA itself may be hard to see, e.g., SSA and PRE

Winnie

Answer 2

Don't know where it is used, but I have a couple ideas where it might get used:

• computer graphics: often 3D sceneries get split into cubes which form a tree structure. If you have an object which is contained in two such cubes a LCA algorithm gives you the smallest containing larger cube.

• analysis of gens in order to find the relationships between species and their lowest common ancestor

• merge algorithms of version control systems

Indissoluble

thanks! version control -> three way merge: en.wikipedia.org/wiki/Merge_(revision_control)#Three-way_merge – Wapiti

It is also useful for certain kinds of string processing when looking for root words for different suffixes. – Pincers

Answer 3

I just wrote a blog post about how I had to implement my own algorithm for this problem (extended to a set of nodes with an arbitrary length) for a taxonomy tree in the context of metagenomics:

http://blog.bio4j.com/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

Cheers,

Pablo

Coelenteron