You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Currently, if you give pll_utree_unroot an rtree that has a non-leaf subtree on the left child (as defined in the newick string), it will set the virtual root to point to the utree_node that is toward the edge on which the rtree root would have been before:
R
/ \
A B
vroot = A , where A->back = B
However, when you execute a postorder traversal on a utree, the subtree that is traversed first is vroot->back (see https://github.com/BenoitMorel/libpll/blob/repeats/src/utree.c#L426)
In this case, after unrooting, vroot->back would point to B, which is the right subtree from the newick perspective.
This means that a rooted tree ((A,B),(C,D)) after being read in and unrooted, would be traversed in the same order as the unrooted tree ((C,D),A,B), when presumably the user would expect the traversal order to be identical to a tree (A,B,(C,D)).
While traversal order should not matter in most scenarios, and the lack of proper ordering can be seen as a weakness of newick, it would be good to have some consistency here. It certainly makes maintaining order in this edge case a little easier.
Proposed fix:
In the "left child isn't leaf" case of pll_utree_unroot, make the function return vroot->next instead of vroot (where vroot is the utree_node connecting subtree A to subtree B from the previous example).
In the case where the left child of the rooted tree root is aleaf, no change is needed as this node's back pointer refers to the left subtree.
The text was updated successfully, but these errors were encountered:
Currently, if you give
pll_utree_unroot
an rtree that has a non-leaf subtree on the left child (as defined in the newick string), it will set the virtual root to point to theutree_node
that is toward the edge on which the rtree root would have been before:vroot = A
, whereA->back = B
However, when you execute a postorder traversal on a utree, the subtree that is traversed first is
vroot->back
(see https://github.com/BenoitMorel/libpll/blob/repeats/src/utree.c#L426)In this case, after unrooting,
vroot->back
would point toB
, which is the right subtree from the newick perspective.This means that a rooted tree
((A,B),(C,D))
after being read in and unrooted, would be traversed in the same order as the unrooted tree((C,D),A,B)
, when presumably the user would expect the traversal order to be identical to a tree(A,B,(C,D))
.While traversal order should not matter in most scenarios, and the lack of proper ordering can be seen as a weakness of newick, it would be good to have some consistency here. It certainly makes maintaining order in this edge case a little easier.
Proposed fix:
In the "left child isn't leaf" case of
pll_utree_unroot
, make the function returnvroot->next
instead ofvroot
(wherevroot
is theutree_node
connecting subtreeA
to subtreeB
from the previous example).In the case where the left child of the rooted tree root is aleaf, no change is needed as this node's
back
pointer refers to the left subtree.The text was updated successfully, but these errors were encountered: