Is a vertex newly added to an AbstractGraph guaranteed to have a vertex index |V| + 1 ?

[CameronBieganek]

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:

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.

[sbromberger]

I think this might be a fair assumption for SimpleGraphs and SimpleDiGraphs, but it certainly cannot hold for all AbstractGraphs. However, we don't explicitly make this guarantee. I don't think it can even hold generally for AbstractSimpleGraphs.

[jpfairbanks]

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.

Yes, that would be very difficult. If any implementations differed from the current (nonstandardized) behavior, if someone had a graph type that did something like your suggested shifting strategy, they would have to support some API for keeping track of the other vertices. Currently given the fact that vertices(g) are assumed to be contiguous integers 1:nv(g) anything other than appending vertices at the end, would be very inefficient. If we were to open the API to more general vertex sets, there would be more room for creativity here, but that would break a lot of assumptions throughout the codebase.

[sbromberger]

Currently given the fact that vertices(g) are assumed to be contiguous integers 1:nv(g)

This is only an assumption that holds for SimpleGraphs, right? I'm not sure we require this in any of the core code.

[matbesancon]

Currently given the fact that vertices(g) are assumed to be contiguous integers 1:nv(g)

This is the default case but can be overwritten by graphs, so it should not be used as an assumption

[o314]

May be it would be simple someday to assume that :

• indices are countable rather than contiguous. (eg finite eg. always ?)
• countable indices may be sparse or dense.
  • sparse indices can be converted eg. compressed to dense easily (in less than 20 sloc)

Those stuff may be tracked with a type parameter turned on and off if needed.

That may not be an internal feature but it may be a good boundary when one load a bunch of data, apply some big computing to it, and save it back.

[sbromberger]

I'm going to close this out because it doesn't represent anything we can take action on at this point. Thanks.