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

开发者_如何学编程 As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

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?

---

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

---

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

---

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