Proposal: Relax restriction on vertex IDs
CameronBieganek opened this issue · 2 comments
I've been thinking about API design changes that would make the AbstractGraph
interface more generic and make it easier to create graphs with meta-data. I was thinking about something along the lines of
abstract type AbstractGraph{L, V, E} end
where L
is a vertex label type, V
is a vertex (or vertex meta-data) type, and E
is an edge (or edge meta-data) type, with some associated machinery for handling vertex labels.
However, after thinking about it for a while, I think that would actually be more restrictive than what we need. I think there are basically only two things that we need in order to make the AbstractGraph
API more generic:
- Allow each concrete subtype of
AbstractGraph
to choose its own vertex label typeL
.- Some subtypes of
AbstractGraph
could allow the user to decide the type of the vertex label, for example, a graph typeNotSimpleGraph{L, V, E}
.
- Some subtypes of
- Add
add_vertex!
,rem_vertex!
,add_edge!
, andrem_edge!
as optional parts of the API that should be implemented for mutable graphs.
I think including the graph modifying verbs in the API would allow individual graphs to decide whether or not they want to use consecutive integer labels (or, of course, non-integer labels).
In order to allow for arbitrary vertex label types, the signature for add_vertex!
would have to change to this:
add_vertex!(g, v)
I don't think that would be too much of an imposition for SimpleGraphs
, since under the current API I have to immediately call nv(g)
in order to figure out the integer code for the newly added vertex. So the usage pattern for SimpleGraphs
would change from this:
added = add_vertex!(g)
if added
v = nv(g)
else
# recover
end
to this:
v = nv(g) + 1
added = add_vertex!(g, v)
if !added
# recover
end
Although I guess then you would need to manually check for integer overflow in nv(g) + 1
... 🤔
With the add_vertex!(g, v)
version of the API, v
is meant to be a vertex label, so this might be a stretch of the API definition, but perhaps there could be a SimpleGraph
method like add_vertex(g, Increment())
, which at least maintains the arity of add_vertex!
.
Or maybe SimpleGraph
s could leave checking for integer overflow to the user. typemax(Int64) ≈ 9.2 * 10^19
, so that seems big enough for most use cases. Then the API for add_vertex!(g, v)
could be the following:
- If
v
already exists ing
, thenadd_vertex!(g, v)
is a no-op. - If
v
does not already exist ing
and is a valid label, thenv
is added tog
.- For a
SimpleGraph{T}
, the only valid label isnv(g) + T(1)
. - For a
SimpleGraph{T}
, it's possible to havenv(g) + T(1) <= 0
, which would probably result in aBoundsError
, but it's up to the user to worry about that.
- For a
Question: With the above change to the add_vertex!
API, would we still need to return false
when add_vertex!(g, v)
is a no-op? Or could we always return nothing
from add_vertex!(g, v)
?
I realize this would be a pretty big change to the codebase. But this is a feature that I would definitely like to have, so I might be able to find some time to help contribute it.
I think that at this point you'd probably be better off reviving Graphs.jl. It did all of this. I'm pretty sure consecutive one-based vertices are assumed in a few core functions, and lots of non-core functions. It'd be a ton of work to rewrite, and right now my availability is a bit limited.
Just popping by to say this looks a lot like https://github.com/simonschoelly/SimpleValueGraphs.jl