Changes in root order of trees.

[molpopgen]

Preface: I'm posting this first as a discussion as I'm not sure it is an issue ("bug"). Some of the recent changelog content alludes to this, but I find it a bit cryptic and am unsure that it is related.

The order of root traversal has changed from Python 0.3.7 to 0.4.0, presumably due to the introduction of "virtual roots" in C API 0.99.15.

Take the following code:

import tskit

tc = tskit.TableCollection(1000.)

tc.nodes.add_row(time=2.)
tc.nodes.add_row(time=1.)

for _ in range(4):
    tc.nodes.add_row(flags=tskit.NODE_IS_SAMPLE, time=0.)

tc.edges.add_row(500., 1000., 0, 1)
tc.edges.add_row(0., 500., 0, 2)
tc.edges.add_row(0., 1000., 0, 3)
tc.edges.add_row(500., 1000., 1, 2)
tc.edges.add_row(0., 1000., 1, 4)
tc.edges.add_row(0., 1000., 1, 5)

tc.sort()

ts = tc.tree_sequence()

print(ts.draw_text())

for t in ts.trees():
    for r in t.roots:
        print(r)

The tree sequence is:

2.00┊  0      ┊     0   ┊  
    ┊ ┏┻┓     ┊   ┏━┻━┓ ┊  
1.00┊ ┃ ┃  1  ┊   1   ┃ ┊  
    ┊ ┃ ┃ ┏┻┓ ┊ ┏━╋━┓ ┃ ┊  
0.00┊ 2 3 4 5 ┊ 2 4 5 3 ┊  
    0        500      1000

With tskit 0.3.7, the root orders are:

0
1
0

With 0.4.0, the root orders are:

1
0
0

If one digs around more (data not shown), the different outputs are due to the different definitions of the left root of a tree that I believe arises from the latest C API.

If this is expected, yay! If not...

I ran into this writing various tests of preorder traversal and got confused, and the preorder output for the first tree differs between the two python versions as one would expect given the different order of visiting roots.

[petrelharp]

Well-spotted. FWIW, I don't think we've written anywhere that roots of trees will come in any particular order (and I'd argue against painting ourselves into that corner unless there's a good reason for it?), so I don't think tihs is a bug.

[molpopgen]

That's right, and there's not a canonical definition for the ordering in these cases of incomplete trees. The issue has to do with client code, like the rust interface, and anyone else who's doing anything where they are trying to use the C interface to double check. I guess this means that anyone testing note orders should store what the roots are and then test the node order for each root within a tree.

[jeromekelleher]

This is expected - basically the old ordering was arbitrary, but now roots are treated in the same way as all other nodes and the ordering arises in the same way the left-to-right ordering for any other node. So, it's documented as arbitrary (but very unlikely to change, in practise) but does depend on which direction you've built the tree from (i.e., whether you've iterated from the left or the right).

I thought we'd got that into the changelog, but it must have gotten lost somewhere.

[molpopgen]

There is some mention of this in the changelog, but I didn't find it very clear.

[benjeffery]

Very happy to change the changelog if you have a better wording.