More combinatorial functions

[jeromekelleher]

Adds some more generators for common tree shapes, and makes some overall improvements to the combintorics code.

Supersedes #944

PR Checklist:

• Tests that fully cover new/changed functionality.
• Documentation including tutorial content if appropriate.
• Changelogs, if there are API changes.

[AdminBot-tskit]

📖 Docs for this PR can be previewed here

[codecov]

Codecov Report

Merging #1026 (645ae81) into main (e5ef2d5) will increase coverage by 0.02%.
The diff coverage is 100.00%.

@@            Coverage Diff             @@
##             main    #1026      +/-   ##
==========================================
+ Coverage   93.69%   93.71%   +0.02%     
==========================================
  Files          26       26              
  Lines       20848    20920      +72     
  Branches      859      875      +16     
==========================================
+ Hits        19533    19606      +73     
  Misses       1277     1277              
+ Partials       38       37       -1     

Flag	Coverage Δ
c-tests	92.49% <ø> (ø)
lwt-tests	93.58% <ø> (ø)
python-c-tests	94.90% <100.00%> (+0.04%)	⬆️
python-tests	98.61% <100.00%> (+0.04%)	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

Impacted Files	Coverage Δ
python/tskit/combinatorics.py	99.16% <100.00%> (+0.09%)	⬆️
python/tskit/trees.py	97.46% <100.00%> (+0.05%)	⬆️

---

Continue to review full report at Codecov.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update e5ef2d5...645ae81. Read the comment docs.

[jeromekelleher]

This is ready for review now I think. The main thing that's added is the generate_balanced function, which can do arbitrary arities, .e.g:

       15             
  ┏━━━━━╋━━━━━━┓      
  ┃     ┃     14      
  ┃     ┃   ┏━┳┻━━┓   
 11    12   ┃ ┃  13   
┏━╋━┓ ┏━╋━┓ ┃ ┃ ┏━╋━━┓
0 1 2 3 4 5 6 7 8 9 10

I've made sure that the generated trees are identical to the trees we'd get from unrank, and documented how we allocate internal nodes there.

@daniel-goldstein, would you mind taking a quick look here to makre sure I haven't done anything silly?

[jeromekelleher]

@benjeffery - any idea how we should do abstract test classes using pytest? It's annoying me that we need to duplicate the code for tests like test_provenance here. I'd have done a Mixin class here in the old days, so that all the test classes inherit the test, but the test isn't executed on the abstract class.

Also, good to get your thoughts on the style that's evolving here for pytest...

[benjeffery]

Well you can still use a Mixin if you like! Often i think a plain function at module-level is simpler, but there are times Mixins feel right.

Generally i think the tests here look good - using the parameterisation decorator is good as it isolates failing cases easily, note that if you want all combinations you can stack the decorator. Also I like that we're grouping tests by class.

[jeromekelleher]

@benjeffery, any chance of another look at the tests? I'm quite pleased how this turned out, might be quite a nice pattern to adopt/adapt elsewhere?

[benjeffery]

@benjeffery, any chance of another look at the tests? I'm quite pleased how this turned out, might be quite a nice pattern to adopt/adapt elsewhere?

I've just realised another way to do this as you can parameterise a whole class:

@pytest.mark.parametrize('method', ["flip", "catch", "hurl"])
class TestCommonsStuff:
    def test_foobar(self, method):
        assert ....
    def test_other(self, method):
        assert ....

and then put the specific tests in their own class.

It is a matter of taste as always - I find what you have already very clear.

[jeromekelleher]

Good idea @benjeffery! I think I'll stick with the subclasses here as it's nice to be able to tack on extra specific tests as well as the common ones.

[jeromekelleher]

Thanks for the feedback, I've addressed your comments @hyanwong. I'm marked this as "merge-ready" so it just needs an approval and it'll go in.

[daniel-goldstein]

Sorry spent all yesterday moving out for the holidays. I can still give it a look now if you'd like

[jeromekelleher]

Sorry spent all yesterday moving out for the holidays. I can still give it a look now if you'd like

That would be great, thanks @daniel-goldstein! No particular hurry.

[daniel-goldstein]

This looks really great! Loving the pytest decorators. Just one little comment

[daniel-goldstein]

Can you do this instead with yield from itertools.islice(lst, chunk_size)?

[jeromekelleher]

Hey, good idea. No, I don't think islice will do it, the semantics of what we want are really quite specific in order to line up with the unranked trees. numpy has a function which almost does what we want, but not quite.