Lowest common ancestor (accelerator)

Question

Is there a built-in method in boost to search for the lowest common ancestor of two or more nodes in the tree (which is an instance of boost :: graph)?

If not, I would appreciate suggestions on the best way to do this. Wikipedia claims there is an efficient algorithm to achieve this O (1) times (with preprocessing O (n)), but it does not describe the algorithms.

Answer 1

Algorithm found on Wikipedia :

function TarjanOLCA(u) MakeSet(u); u.ancestor := u; for each v in u.children do TarjanOLCA(v); Union(u,v); Find(u).ancestor := u; u.colour := black; for each v such that {u,v} in P do if v.colour == black print "Tarjan Least Common Ancestor of " + u + " and " + v + " is " + Find(v).ancestor + "."; 

Answer 2

I found the following site that can answer your question: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

The basic idea is to convert the question “Lowest Common Ancestor” to another, “Minimum Range Request”, then use the O (N) + O (1) approach to solve the problem. I did not look into it completely, but it looks pretty well documented and worthy of attention.