What are the practical applications of the lowest common ancestor algorithms? [closed]
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
精彩评论