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

Rename vec-tree to vec-digraph? #1

Open
WildCryptoFox opened this issue Jan 2, 2019 · 2 comments
Open

Rename vec-tree to vec-digraph? #1

WildCryptoFox opened this issue Jan 2, 2019 · 2 comments

Comments

@WildCryptoFox
Copy link

By definition trees contain zero cycles. The Index implements Copy, and the documentation mentions "cycles". This crate implements a directed graph.

If you'd like to restrict vec-tree to trees, make the Index non-Copy.

@ArnaudValensi
Copy link
Owner

There is a cycle because a parent needs a reference to a child and a child a reference to the parent. The index is copy, because we may want to store multiple copies of the index in our usage of this lib.
Because the goal of this lib is to make trees (and not graphs), we should add a test with some nodes cycling and fix the code to avoid this if needed.

@WildCryptoFox
Copy link
Author

WildCryptoFox commented Jan 8, 2019

@ArnaudValensi Are you sure you need parent pointers? If so, please keep them separate so the main parent -> children tree is easy to verify. Cycle detection is non-trivial and far from a cheap check in the general case. For trees the optimal solution is to use non-copy handles. For a DAG, enforce topological insertion order.

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

2 participants