Add requirement that mutations are sorted by time

[jeromekelleher]

A though: once this is implemented, we should have sort_tables sort mutations by time, which satisfies the current requirement that parents come before children, but would make the ordering produced by sort_tables less ambiguous (not totally, if in discrete time, though). Perhaps we should make "sorted by time" a requirement of the mutation table, also.

Originally posted by @petrelharp in #513 (comment)

[jeromekelleher]

This seems like a sensible thing to do, to me, and we'll regret it if we miss the opportunity to set this constraint while we're adding the field. We just need to think through the consequences.

[petrelharp]

Ah, this would close #27 .

[benjeffery]

Started looking into this. One question is how we deal with unknowns - based on the "parents before children" requirement we have to include unknown times in a place that is consistent with that requirement. That means doing more than a simple comparison of time, but instead following each mutations parents to see which one is in the parent chain of the other. Am I getting that right?

[mufernando]

@benjeffery , I started looking into this in #715 (see also issue #705). Could use your help there, I've been busy with some other things this week.

[jeromekelleher]

Started looking into this. One question is how we deal with unknowns - based on the "parents before children" requirement we have to include unknown times in a place that is consistent with that requirement. That means doing more than a simple comparison of time, but instead following each mutations parents to see which one is in the parent chain of the other. Am I getting that right?

I think to the thing to do with UNKNOWN_TIME is to duplicate the old behaviour. So, the goal would be to keep the code exactly the same semantically if an old tree sequence was read in (which didn't have times), and then only have different behaviour when we do know the times. This should be easy enough to do within the comparison func. The only tricky bit is dealing with how to compare known and unknown times - but I guess the only thing to do there is to treat them both as unknown and not compare the time at all.

[benjeffery]

Thanks for pointing that out @mufernando. I think it's best to do each change to the sorting requirements as a separate sub-PR to #705. This prevents PRs and their discussions getting too large. I'll do a PR for this mutation time issue if that's good with you?

[mufernando]

Sounds good to me! Thanks!

[petrelharp]

Actually, we realized in #705 that the only thing we needed to do was to sort the mutations, so we can close that one in favor of this one. Let's see, here's the things we have available to sort on (after sorting by site; the discussion is how to order the mutations that all have the same site):

• time (maybe)
• node
• parent mutation id
• original mutation id (ie order in the table before sorting)

Observations:

1. Sorting on (time, parent), with missing times incomparable, would suffice to ensure that things are ordered by time, and that parents come before children even if times are missing, as long as mutation parents are present.
2. Sorting on (time, original id) would also ensure this, as long as mutation parents came before children in the original table; and what we did before is just maintain original order, so sort on just original id.
3. Neither of these give you a canonical ordering; so we're proposing in make sort stricter #705 sorting on (time, parent, node) to make it canonical.

So I guess that here you could sort on (time, original id) to keep it as close to the original as possible. But I think we do want to move to (time, parent, node), so why not do that now?