Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Distance among trees

by jmerelo (Sexton)
on Nov 19, 2001 at 18:21 UTC ( #126264=perlquestion: print w/replies, xml ) Need Help??

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";
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
      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.
        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,


        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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://126264]
Approved by root
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (3)
As of 2020-06-05 19:27 GMT
Find Nodes?
    Voting Booth?
    Do you really want to know if there is extraterrestrial life?

    Results (40 votes). Check out past polls.