Perl: the Markov chain saw PerlMonks

### Distance among trees

by jmerelo (Sexton)
 on Nov 19, 2001 at 18:21 UTC 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;
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,

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.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://126264]
Approved by root
help
Chatterbox?
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
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Do you really want to know if there is extraterrestrial life?

Results (40 votes). Check out past polls.

Notices?