Skip to content

Use Incremental algorithm for computing tree ranks on tree sequences #671

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
daniel-goldstein opened this issue Jun 5, 2020 · 0 comments
Labels
enhancement New feature or request

Comments

@daniel-goldstein
Copy link
Member

One can compute the combinatorial rank of a tree with Tree.rank (see here). Currently, this is only used for very small trees, but if a user wanted to count unique topologies in a tree sequence with larger numbers of samples, t.rank() for t in ts.trees() would be very wasteful and slow. Calculating tree ranks is done leaves->root so, like typical incremental algorithms, only an upward traversal after an SPR is needed to adjust the rank during a tree transition. The simple incremental algorithm to generate per-tree ranks in a tree sequence would follow almost exactly the same approach as counting species tree topologies, except:

  • the per node state would be a RankTree instead of a TopologyCounter
  • per-root state would not be merged since multiply-rooted trees cannot be ranked, it would likely have to return a list of ranks that maps to the roots of the current tree
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants