Least Common Ancestor - what is it, and a Least Common Ancestor algorithm implemented in Perl
Archive - Originally posted on "The Horse's Mouth" - 2010-11-11 07:37:59 - Graham Ellis
Imagine you have a tree - a series of leaves which join together as you head towards the root into bigger and bigger branches. The "Least Common Ancestor" is the point at which the branches from two leaves you have chosen come together. In computing, such a tree structure is very common - files and folders / directories, and heirarcies of classes, being two common examples.Over the past couple of days, I've received several requests through our enquiry page if it's possible to write a Least Common Ancestor program in Perl. It's rather odd to have received such a batch of questions, and I think that - somewhere in the world where our web site is used as a reference - this has been set as a class exercise. The easy answer is "Yes - you can write anything in Perl"; my longer answer the first time I was asked was "How much Perl do you know / can I help / do you even need to come and learn Perl on one of our Perl courses?". But I got no reply - not even an acknowldegement (and, by the way, for readers from non-English cultures, it's regarded as impolite to ask a question, have someone spend a lot of time writing and answer, and not even acknoledge the help / say "Thank you").
But ... I admit ... I was very interested in how easy the question was ... so when I woke this morning I set myself the challenge of writing a Least Common Ancestor program in Perl. The source code is [here]. Now - there are plenty of learned papers on efficient ways of doing this, with recursive code that looks very clever - but I came up with something much simpler.
1. Define all of the branch relationships in a hash
2. Generate two list of ancestor - one for the two start points you're interested in
3. Staring at the end of those lists, compare individual members until you find ones which are NOT common
... and the last common ancestor you found was also the LEAST common one.
The sample program worked with a single test case that I rushed through it; note that it needs further testing especially for special cases such as for leaves that have no common ancestor at all, and for leaves where one of the leaves actually given as an input is an ancestor of the other.
Should I have written the code? Should I pass on the URL of this item and the sample to my new enquirers and the original one? Well - I'm not going to start sending more emails to the first (rude?) chap / chapess. But this code is a useful example / algorithm I can make plenty of re-use of during demonstrations and courses. It illustrates topicalisation, named blocks of code (subs)i, hashes, lists, "here" documents, passing parameters by address, scoping of variable using "my" and much more. So it will be useful to other people who need it in a far wider area. If people who are looking for help with homework take a copy and hand it in (they should add my copyright notice to it, but probably wouldn't), then they only have themselves to blame when they end up learning little about Perl, and lots about how to steal other people's code. But - come to think of it - it's pretty efficient to re-use code provided that you do it legally!