Tskit: Check if a tree (or ts) is multi-root?

[hyanwong]

Whenever I look at the docs for num_roots the bit that says "Requires O(number of roots) time." puts me off using this route to check if I have a multiroot tree - I'm worried about how inefficient it might be. Yet sometimes I don't want the actual root, I just want to assert that I'm dealing with a single root tree. Might it be useful therefore to have an "is_multiroot()` method on a tree?

I also wonder if this is something we want to check for all the trees in a TS, and if so, it there's a more efficient way of doing this than just going through the trees one-by-one.

[jeromekelleher]

This would be useful to have all right. We could implement a has_single_root (or something) function in O(1) time per tree. No way of avoiding iterating over the trees though, we can't tell anything about roots without building the trees.

Any better terminology that has_single_root? monorooted, uniroot...

[jeromekelleher]

The function looks something like

def has_single_root(self):
    ret = False
    if self.left_root != tskit.NULL:
        ret = self.right_sib(self.left_root) == tskit.NULL
    return ret

[hyanwong]

"has_one_root" is shorter to type, if you don't want the opposite ("is_multiroot")

[jeromekelleher]

I don't have much of an opinion to be honest, they're all more or less the same. Thoughts anyone else?

[jeromekelleher]

Could have two properties singly_rooted, multiply_rooted on the Tree class.

[hyanwong]

I don't have a strong opinion either. Whatever others think is clearest.

[jeromekelleher]

@petrelharp, @benjeffery any opinions here? I think a property (or two) on the Tree class is the way to go. What should it/they be called?

[petrelharp]

I'm not clear on the motivation, because when would you be checking if there's only one root but simultaneously be worried that there's a large number of them? But, leaving that aside, I think just one property is fine, and I like multiply_rooted.

[jeromekelleher]

because when would you be checking if there's only one root but simultaneously be worried that there's a large number of them?

Suppose you're iterating over the trees in a ts with 1M samples where we've snipped out the centromere. Having a O(1) way of knowing we're in a missing-data tree would be handy.

[benjeffery]

I like a property on Tree. I'm not sure multiply_rooted on its own would do though, as a Tree that is not multiply_rooted can have zero or one roots. I personally prefer has_single_root and has_multiple_roots but only very marginally.

[jeromekelleher]

I like has_single_root and has_multiple_roots too, it's pretty unambiguous what these properties should mean then.

[hyanwong]

While we are on this PR, I think it would be useful to have Tree.is_root(u) to match Tree.is_leaf(u) etc. This is slightly different, of course, because a tree can be a root in one tree and not in the next. It's just a wrapper for something like Tree.parent(u) == tskit.NULL (although we also need to check that the node is actually in this tree)

[jeromekelleher]

That's a different issue @hyanwong, can you open another issue for it please? This isn't as straightforward as you think, given the definition of a root.