Vertices should have consistent indices during their lifetime

[henrik-wolf]

When writing code which mutates a graph instance multiple times, it quickly becomes very complicated to reason about which vertices after the deletion correspond to which vertices before. I believe it would be more natural to keep the "holes" created by deleting of vertices, and fill them again, when creating new ones. Together with the changes proposed in #122 we would be able to get the (now persistent) index of the added node without any extra call to nv(g) or stuff like that.

This change would probably be breaking, mainly because we would need the changes of #122, to retrieve the index where we added the vertex.
I can imagine that such a change might have some impact on memory, since the return value from vertices(g) could no longer be Base.OneTo(n) but has to be some array specifying the available indices. Also for things like adjacency matrices this might be problematic, since we would need to decide how to get rid of the "holes" in our indices.

What do you think? Am I missing something crucial here, that would become very complicated or even impossible to do with this approach?

[gdalle]

Basically this is a very breaking change and it is part of the discussion around Graphs 2.0 (see #128 or #35). At the moment all of our code is built around the assumption that vertices are contiguous from 1 to n, which enables numerous shortcuts and optimizations. Removing vertices preserves that, at the detriment of index stability

[gdalle]

Sounds like a job for https://github.com/JuliaGraphs/GraphsBase.jl

In particular see JuliaGraphs/GraphsBase.jl#3