[RFC] GraphInterface.jl: An interface proposal for Graphs.jl version 2.0

[gdalle]

@CameronBieganek

Is there a particular reason not to just declare in the interface that edge types must be iterable? The syntax u, v = e seems pretty clean and elegant to me, and it avoids calling one vertex the source and one the destination.

This is just an oversight and rather easy to add. But I don’t see how it solves the problem for undirected edges?

@mtfishman

As @CameronBieganek alluded to in the first post, I think there are 3 main ways of making graph functions work with general vertices:

1. assume generic vertices but make no other assumptions, in which case it will likely involve a lot of mapping back and forth between vertices and parent vertices of some wrapped SimpleGraph within the code and be slower than necessary, but it will “just work” if there isn’t an underlying data structure with linear indexing,
2. wrap and unwrap the parent graph/vertices as pre- and post-processing, which requires a generic interface for wrapping and unwrapping graphs/vertices, or
3. allow some interface for directly accessing an underlying graph structure in a fast way with linear indexing (which probably also requires an interface for rewrapping/mapping the parent vertices, since many graph functions output lists of vertices or edges).

It’s a good summary!

At the moment I think GraphsBase.jl and GraphInterface.jl do 1, and we could add 2 without much sweat.
The trouble with 3 is that outneighbors / inneighbors (or outedges / inedges) are not necessarily indexable cleanly, or even at all. Some graph types generate them on the fly, and forcing indexation would be an additional interface constraint. But if we can manage that, I agree that it sounds like the best of both worlds.

Etienne’s original idea in GraphsBase.jl was to have a create_vertex_container(g, T) method that generates the best container with values of type T and keys of vertex type. That, way when Dijkstra wants to e.g. store vertex distances, it can do so in a Dict (default fallback) or in a Vector (if the vertices are contiguous integers) depending on what the graph type supports. This trick allows at least integer-based graphs to be fast, instead of everyone using dictionaries everywhere.

I opened an issue to discuss these integers-to-labels aspects.