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

Refactor internals of adjacency matrix representation #36

Closed
pnevyk opened this issue Jan 8, 2023 · 0 comments · Fixed by #42
Closed

Refactor internals of adjacency matrix representation #36

pnevyk opened this issue Jan 8, 2023 · 0 comments · Fixed by #42

Comments

@pnevyk
Copy link
Owner

pnevyk commented Jan 8, 2023

The main two goals of the refactoring are:

  1. Reduce the scope and complexity of the code that uses unsafe.
  2. Make the utility functions public so they can be reused by other matrix-like representations.

Reducing scope of unsafe

The internals of AdjMatrix use unsafe code for two reasons:

  1. The possibility to "detach" edge presence information from the edge data, so that implementation of Neighbors does not cause "E does not live long enough" error.
  2. A space reduction, where Vec<Option<E>> would need extra byte(s) for every item in a lot of practical cases (where a memory layout optimization would not help). Although the real performance effect was not benchmarked!

To be more confident in the correctness as well as reduce stress while making changes in the future, the scope and complexity of the code using unsafe should be reduced.

There should be a new Vec-like type encapsulating the BitVec, Vec<MaybeUninit<T>> pair. The API surface should be as minimal as possible while still supporting the needs of the AdjMatrix implementation. And it should still be possible to get reference to the underlying BitVec which does not have any generics. Since the implementation will not need to care about anything matrix-related, the implementation should be more straightforward and much easier to reason about. Anyway, miri should be used to ensure correctness.

Exposing utility functions

There are some useful functions that help with storing matrix-like data in a linear vector, namely:

  • size_of -- calculating needed size of the vector given number of vertices and graph being directed or undirected
  • resize -- Resizing the vector to a new size, correctly moving existing edge data. Although this function needs to be made edge container agnostic.
  • index & coords -- Functions that can convert edge coordinates (source vertex and destination vertex) to the vector index and vice versa.

These should be publicly available so they can be used by external implementations.

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

Successfully merging a pull request may close this issue.

1 participant