Proposal: Relax restriction on vertex IDs

[CameronBieganek]

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 type L.
  • Some subtypes of AbstractGraph could allow the user to decide the type of the vertex label, for example, a graph type NotSimpleGraph{L, V, E}.
• Add add_vertex!, rem_vertex!, add_edge!, and rem_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 SimpleGraphs 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 in g, then add_vertex!(g, v) is a no-op.
• If v does not already exist in g and is a valid label, then v is added to g.
  • For a SimpleGraph{T}, the only valid label is nv(g) + T(1).
  • For a SimpleGraph{T}, it's possible to have nv(g) + T(1) <= 0, which would probably result in a BoundsError, but it's up to the user to worry about that.

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.

[sbromberger]

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.

[gdalle]

Just popping by to say this looks a lot like https://github.com/simonschoelly/SimpleValueGraphs.jl