Add a Tree.generate_star method #934

hyanwong · 2020-10-25T15:08:36Z

Description

Add Tree.create_star, Tree.create_balanced, and Tree.create_empty methods, as discussed on Slack.

The Tree.create_empty method is perhaps unlikely to be widely used, but I think is useful for completeness, and will also come in handy for testing (for example, I only just noticed that we currently bomb out with a non-obvious message when trying to plot an empty TS).

Happy to make these class methods if that is preferred.

hyanwong · 2020-10-25T15:09:46Z

Leaving as a draft until #930 is merged, so I can uncomment a test for span in the unit tests.

AdminBot-tskit · 2020-10-25T15:10:01Z

📖 Docs for this PR can be previewed here

jeromekelleher

Looks good, thanks @hyanwong. These will be really handy, I think. The main feedback is we shouldn't have special cases, and try to make simple rules about the number of nodes and edges returned hold for all n >= 0.

I agree it's nice to have all these have a common prefix. I'm not so sure about "create_" though; perhaps "make_"?

I'm not sure how useful the empty one is to be honest, it's already a one-liner, and I don't think the equivalances you're stating will hold once the special cases at 1 and 0 have been removed.

jeromekelleher · 2020-10-25T17:08:43Z

python/tests/test_topology.py

+    """
+
+    def test_star_equivalent(self):
+        for extra_params in [{}]:  # , {'span':2.5}]: # Add after #930 is merged


There's only one extra param, so loop seems unnecessary and makes the code less readable

I've just uncommented the bit with "span" in, so it will test with with the default, and with a span now.

python/tests/test_topology.py

python/tskit/trees.py

jeromekelleher · 2020-10-25T17:16:39Z

python/tskit/trees.py

+            flags=np.full(n, NODE_IS_SAMPLE, dtype=np.uint32),
+            time=np.zeros(n),
+        )
+        if n > 1:


I don't think we should make this exception. We should always return a tree with num_leaves + 1 nodes and num_leaves edges. (which holds true for all num_leaves >= 0, right?)

I was trying to match unrank, @jeromekelleher . For num_leaves=1 that produces a TS with a single node and no edges. I think this is the right behaviour. We don't really want a unary node as the root, do we - it would be removed by simplify() if we were to run that on the TS anyway.

Hmm. Maybe we should just raise a ValueError if n < 2 for now, and avoid this discussion. It's not particularly interesting what the semantics are in these degenerate cases and we can always fix them later if it does become important.

Yep, could do, I suppose.

jeromekelleher · 2020-10-25T17:21:08Z

python/tskit/trees.py

+    @staticmethod
+    def create_star(n, *, span=1, branch_length=1, record_provenance=True):
+        """
+        Create a single :class:<Tree> and associated tree sequence where the ``n``


Delete "and associated tree sequence" - see the note below.

python/tskit/trees.py

jeromekelleher · 2020-10-25T17:26:24Z

python/tskit/trees.py

+        )
+        if n & (n - 1) != 0:
+            raise ValueError("n must be an integer power of 2")
+        if n > 1:


Again, I don't like the special case. We shouldn't need it here, right?

jeromekelleher · 2020-10-25T17:26:33Z

python/tskit/trees.py

+            raise ValueError("n must be an integer power of 2")
+        if n > 1:
+            merge_nodes = list(range(n))
+            while len(merge_nodes):


len(merge_nodes) > 0

hyanwong · 2020-10-25T17:41:40Z

I agree it's nice to have all these have a common prefix. I'm not so sure about "create_" though; perhaps "make_"?

Or generate? Happy with any of those.

I'm not sure how useful the empty one is to be honest, it's already a one-liner, and I don't think the equivalances you're stating will hold once the special cases at 1 and 0 have been removed.

I think it's useful so that we can test e.g. tskit.Tree.generate_empty().draw_text() and so on, which we have currently failed to do. It's also useful to be able to compare things to an empty TS, unless there is already some function to check if a TS is empty (didn't check, sorry!)

jeromekelleher · 2020-10-25T19:28:17Z

It's also useful to be able to compare things to an empty TS, unless there is already some function to check if a TS is empty (didn't check, sorry!)

Generating an empty ts is pretty trivial: tskit.TableCollection(1).tree_sequence() - but I don't feel particularly strongly about having an x_empty function or not. I'm not sure "empty" is the right word anyway (it's implying there's something in the tree), it's more like a "null" tree. I'm not sure it's worth the discussion of the semantics to include it.

hyanwong · 2020-10-26T09:26:05Z

Generating an empty ts is pretty trivial: tskit.TableCollection(1).tree_sequence() - but I don't feel particularly strongly about having an x_empty function or not.

That's not an obvious calling convention to people unfamiliar with tables. E.g. I might hope to get an empty ("null") TS by simply calling tskit.TreeSequence() with no params (and I did try that, when messing around). I only added it so that I could be explicit. But maybe it should be possible to create null objects by doing tskit.TreeSequence() and tskit.Tree()?

I'm not sure "empty" is the right word anyway (it's implying there's something in the tree), it's more like a "null" tree. I'm not sure it's worth the discussion of the semantics to include it.

It never struck me as lacking before. But I do think we have somewhat overlooked at the behaviour of various tskit functions for "null" tree sequences & trees, so this was a first step in doing something about that.

jeromekelleher · 2020-10-26T13:12:00Z

But maybe it should be possible to create null objects by doing tskit.TreeSequence() and tskit.Tree()

The semantics around object initialisation are extremely tricky because of the interaction with the C API and Python C API. I'd rather avoid this can of worms for now.

hyanwong · 2020-10-27T17:57:59Z

So it's not obvious to me how to create semi-balanced trees that match unrank(N - 1) without doing some sort of recursion. Given that there's disagreement over these "semi-balanced" trees anyway, I've simply removed the generate_balanced code. I'll put it in a different PR so we can discuss it there. I think this PR, that now just has generate_star, is therefore ready to merge @jeromekelleher

jeromekelleher

Looks great, thanks @hyanwong. Just need to fix up the changelog and we're good to merge.

python/CHANGELOG.rst

hyanwong marked this pull request as draft October 25, 2020 15:09

jeromekelleher requested changes Oct 25, 2020

View reviewed changes

hyanwong force-pushed the example-trees branch from 7078b48 to abe3920 Compare October 27, 2020 17:54

hyanwong force-pushed the example-trees branch 2 times, most recently from 901139a to b1914e0 Compare October 27, 2020 18:05

hyanwong marked this pull request as ready for review October 27, 2020 18:09

hyanwong mentioned this pull request Oct 27, 2020

Generate balanced tree #944

Closed

hyanwong changed the title ~~Add a Tree.create_star method~~ Add a Tree.generate_star method Oct 27, 2020

jeromekelleher reviewed Oct 28, 2020

View reviewed changes

python/CHANGELOG.rst Outdated Show resolved Hide resolved

Add a Tree.create_star method

ecaa210

hyanwong force-pushed the example-trees branch from b1914e0 to ecaa210 Compare October 28, 2020 10:24

jeromekelleher approved these changes Oct 28, 2020

View reviewed changes

jeromekelleher added the AUTOMERGE-REQUESTED label Oct 28, 2020

mergify bot merged commit 9248fb3 into tskit-dev:main Oct 28, 2020

mergify bot removed the AUTOMERGE-REQUESTED label Oct 28, 2020

hyanwong deleted the example-trees branch November 4, 2020 14:47

Add a Tree.generate_star method #934

Add a Tree.generate_star method #934

Uh oh!

Conversation

hyanwong commented Oct 25, 2020

Description

Uh oh!

hyanwong commented Oct 25, 2020

Uh oh!

AdminBot-tskit commented Oct 25, 2020

Uh oh!

jeromekelleher left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hyanwong Oct 25, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hyanwong commented Oct 25, 2020

Uh oh!

jeromekelleher commented Oct 25, 2020

Uh oh!

hyanwong commented Oct 26, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jeromekelleher commented Oct 26, 2020

Uh oh!

hyanwong commented Oct 27, 2020

Uh oh!

jeromekelleher left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

hyanwong Oct 25, 2020 •

edited

Loading

hyanwong commented Oct 26, 2020 •

edited

Loading