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

Faster hDAG construction #8

Open
willdumm opened this issue Mar 11, 2022 · 1 comment
Open

Faster hDAG construction #8

willdumm opened this issue Mar 11, 2022 · 1 comment
Labels
enhancement something to improve

Comments

@willdumm
Copy link
Collaborator

The method used to build the history DAG is slow (search entire DAG for duplicate nodes each time a history is added)

It certainly doesn't have to be this way. Let's think about this with the __getstate__ and __setstate__ implementations as inspiration.

@willdumm willdumm added the enhancement something to improve label Mar 11, 2022
@willdumm
Copy link
Collaborator Author

willdumm commented Mar 15, 2022

Certainly all DAG construction functions should be modified to expect only a generator containing trees, not an entire list, and iterate on that generator in a memory-efficient way.

Current situation:
IMG_0476

Goal: build each node only once.
Input: list of ete trees?

  • build node dictionary node_dict node -> node for existing DAG
  • for each ete tree:
    • Postorder traverse to build child clades at all nodes
    • Preorder traverse, adding each edge by looking up parent node in the node_dict (it must be there by preorder), looking up child node in node_dict, adding if necessary, and adding edge from parent to child

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

No branches or pull requests

1 participant