jlapeyre:
But, 1) GraphsIO does not currently support reading attributes, so I would have to introduce a new dependency and extend the interface of loadgraph . 2) which attribute-bearing Julia structure is best for this is not clear, probably MetaGraphs .
In a hypothetical version 2.0 of Graphs.jl, it would be nice to make the AbstractGraph interface more generic so that it is easier to use graph metadata. Right now there are various issues with attempting to use metadata or attempting to use labels for vertices that are not integers. There are some old issues in the LightGraphs.jl repo that I opened a while ago:
opened 11:12PM - 24 Jun 21 UTC
discussion
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
```julia
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:
```julia
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:
```julia
added = add_vertex!(g)
if added
v = nv(g)
else
# recover
end
```
to this:
```julia
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 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.
opened 06:59PM - 14 Dec 20 UTC
closed 06:17PM - 15 Feb 21 UTC
I know that `add_vertex!` is not part of the `AbstractGraph` interface, but the … documentation seems to use an implicit assumption that when you add a vertex to a graph, it is denoted by the integer `|V| + 1`, where `|V|` is the number of vertices in the graph before the new vertex is added. Is this behavior assumed to apply to any `AbstractGraph`? Of course, the examples in the documentation use `SimpleGraphs`, so it's not clear if this assumption applies to any `AbstractGraph` or only to any `AbstractSimpleGraph`.
For example, if this behavior is not guaranteed for an AbstractGraph, then the value of `added` in the code below is undefined:
```julia
struct SomeGraph <: AbstractGraph
# etc
end
g = SomeGraph(2)
add_edge!(g, 1, 2)
add_vertex!(g)
added = add_edge!(g, 1, 2)
```
In other words, without the guarantee above, it's possible that when `add_vertex!` is called above the new vertex is given label `1` and the old vertex labels are incremented by 1, e.g. `1 -> 2` and `2 -> 3`. If that were the case, then the second `add_edge!` would be successful and we would have `added == true`, and the list of edges would now be `[Edge(1, 2), Edge(2, 3)]`. However, if the new vertex index is `3`, then the second `add_edge!` would be unsuccessful and we would have `added == false`, and the list of edges would be `[Edge(1, 2)]`.
More generally speaking, it's rather difficult to keep track of vertices if we don't know what happens to vertex labels/indices when we add a new vertex.
In my opinion, add_vertex!, rem_vertex!, add_edge!, and rem_edge! all need to be added as optional parts of the AbstractGraph interface. There needs to be a generic API for those functions that can apply to any mutable graph.
3 Likes