Re: Small puzzle

["Aaron J. Mackey" <amackey@pcbi.upenn.edu>]

> To optimize speed (at
> the expense of memory, of course), carry the list around with the node.

We do this in bioinformatics all the time (since Mark has described a 
tree, and not a graph, which is what we use for taxonomy-related 
queries).

Say that while you build your tree, assign each node into an array as 
you go; then for each node, store an ordered ancestral array of [ root, 
..., great-grandparent, grandparent, parent ] (or, if you're using a 
database backend as described in 
http://www.oreillynet.com/pub/a/network/2002/11/27/bioconf.html, you 
can simply query for this info).  Then it's simply a matter of 
"walking" the two ancestor arrays until there's a discrepancy (or the 
lists run out) - the last matching item in both arrays is the "Last 
Common Ancestor" [note that many other algorithms for calculating LCA 
are available].

Alternatively, you can build a transitive closure of the tree (e.g. 
with Graph::Directed) and ask for the node that is connected to both 
children with the least distance.  We do this in SQL as described in 
the reference above.

No code today, just thoughts.

-Aaron

-
**Majordomo list services provided by PANIX <URL:http://www.panix.com>**
**To Unsubscribe, send "unsubscribe phl" to majordomo@lists.pm.org**