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

Contiguous vertices a requirement? #297

Open
mtiller opened this issue Sep 10, 2023 · 1 comment
Open

Contiguous vertices a requirement? #297

mtiller opened this issue Sep 10, 2023 · 1 comment

Comments

@mtiller
Copy link

mtiller commented Sep 10, 2023

I read through the documentation for Graphs.jl and I understood that the provided implementations of AbstractGraph (e.g, SimpleGraph) assumed that the vertices were contiguous and started from 1 (e.g. 1, 2, 3, ...). But I didn't realize this was a requirement. So I implemented all the necessary functions for a Graph where the vertices could be any set of integers (e.g.,, 2, 7, 25, ...). I was able to implement all the methods associated with the AbstractGraph type, but when I went to run dijkstra_shortest_paths), I immediately hit an error.

Looking at the code for dijkstra_shortest_path, it seems clear that it assumes this continguous from 1 semantics because it allocates the dist array as dists = fill(typemax(T), nvg) and then uses the vertices as indices into the dist array, e.g., dists[src] = zero(T). Since the array's indices must be contiguous starting from 1 (no?) this implies so must the vertices.

So either I'm missing something and disjointed sets of integers can be used as vertices (although I don't see how given the implementation of dijkstra_shortest_path, but I'm a newcomer to Julia so perhaps I'm overlooking something) or I missed something in the documentation that mentions that all graphs must have vertices must start from 1 and cannot be disjoint in which case I'm scratching my head as to why both nv and vertices functions are required (since vertices would always be 1:nv(g)).

Assuming I am correct and that it is assumed that vertices must be contiguous and start from 1, then it seems like there should be some mention of this here in the documentation, no?

@mtiller mtiller added the bug Something isn't working label Sep 10, 2023
@gdalle
Copy link
Member

gdalle commented Sep 10, 2023

From what I understand, contiguous vertices should not be required in theory, but are required in practice by an unknown subset of the library. I would very much welcome a PR clarifying this in the docs, while we wait for GraphsBase to take shape

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

3 participants