Skip to content
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

finish implementation and cythoning of remaining basal methods #21

Open
9 of 17 tasks
wasade opened this issue Jul 27, 2016 · 2 comments
Open
9 of 17 tasks

finish implementation and cythoning of remaining basal methods #21

wasade opened this issue Jul 27, 2016 · 2 comments

Comments

@wasade
Copy link
Member

wasade commented Jul 27, 2016

  • preorder (note, generally using the select version right now)
  • postorder (note, generally using the select version right now)
  • levelnext
  • levelprev
  • isancestor
  • subtree (note, would be useful to have a getsubtree as well)
  • levelancestor
  • levelleftmost
  • levelrightmost
  • degree
  • child
  • childrank
  • lca
  • deepestnode
  • height
  • mincount
  • minselect
@wasade
Copy link
Member Author

wasade commented Aug 25, 2016

mincount and minselect are not optimized algorithmically, and so more aggressive cythoning has been deferred. It should be possible to leverage the binary tree for both of these operations. Impact: degree and childrank use mincount. child uses minselect

@wasade
Copy link
Member Author

wasade commented Aug 25, 2016

The following methods are deferred for implementation as they are not done yet, and not needed right now:

  • levelprev (defined as levelprev(i) = open(bwdsearch(i, 0)+1))
  • levelleftmost (defined as levelleftmost(d) = fwdsearch(0, d))
  • levelrightmost (defined as levelrightmost(d) = open(bwdsearch(2n + 1, d)))
  • degree (defined as degree(i) = mincount(i + 1, close(i) − 1))
  • child (defined as child(i, q) = minselect(i+1, close(i)−1, q−1)+1 for q > 1)
  • childrank (defined as childrank(i) = mincount(parent(i) + 1, i) + 1; unless B[i − 1] = 1 (in which case childrank(i) = 1))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant