jmerelo has asked for the wisdom of the Perl Monks concerning the following question:

Hi, I am trying to find an easy way to implement distance among trees, as in Tree::DAG_Node. I have found some info about Robinson-Foulds distance, but only in the shape of code, and I don't know exactly if it is what I'm looking for. Meanwhile, I make do with this: 
use Tree::DAG_Node;
use String::Approx qw(adist);
my $lol1=[['a','b'],['c','d'],['e']];
my $lol2=[['a','b','c'],['d'],['e']];
my $tree1 = Tree::DAG_Node->lol_to_tree( $lol1 );
my $tree2 = Tree::DAG_Node->lol_to_tree( $lol2 );
my $str1 = $tree1->tree_to_lol_notation();
my $str2 = $tree2->tree_to_lol_notation();
my $dist = adist( $str1, $str2 );
print "Distance between $str1 and $str2 is $dist\n";

[download]
But it's not exactly what I'm looking for, since changing a node from one subtree to another would give distance=7 (or 4 in the case above). Can anybody help me? Pointers to RF distance definition anywhere? Thanks!

Replies are listed 'Best First'.
Re: Distance among trees
by cacharbe (Curate) on Nov 19, 2001 at 18:44 UTC
[reply]
      Already followed those leads, even emailed the guy. Looks promising, but uses its own version of trees, creates "bipartition" of them, and does not contain a detailed explanation of the algorithm. I could try and glean it by following the code, but I'm not sure it's worth the while.
[reply]
        Looks like you're going to have to find a copy of "Lecture notes in mathematics" --Springer-Verlag, Germany(1979) to find out their proposed algorithm (or one of Foulds' other books, and he seems to have a few), but I found a text description of it here, pg. 4, and a subsequent discussion on the "Deltahedron Method" here, which does give an algorithm, but doesn't necessarily describe it as Foulds'.

        Hope that helps,

        C-.

        Update: After reading the Caccetta/Kusumah text, theirs might be a more interesting algorithm to attempt implementing if you are going to start from scratch.

[reply]

Back to Seekers of Perl Wisdom