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

[gdalle]

Thanks for your work @CameronBieganek !

@gvdr

May I ask you to elaborate on the difference between your proposal and GraphsBase?

I’ll do my best to outline the differences based on both project descriptions.
Keep in mind that GraphsBase.jl and GraphInterface.jl are just preliminary proposals (at least that’s how I view them), so in the end I hope there will be just one package which does whatever the community thinks is best.
There are plenty of open GraphsBase.jl issues you can weigh in on, in addition to the current thread.

TLDR: GraphInterface.jl sounds cool, and I’m excited to look at the code! However, there are some key aspects that GraphsBase.jl aims at tackling:

• support for metadata (to decrease user confusion)
• support for multigraphs (which makes sense e.g. for transportation, where you can have various edges between 2 nodes)
• interface with optional parts, formally specified and with tests (I’m betting on Interfaces.jl to help us get there)

What do people here think?

@CameronBieganek

GraphTypes <- GraphInterface -> GraphAlgorithms

GraphsBase.jl will probably contain an interface and base types.
The idea is to offer at the very least SimpleGraph, SimpleWeightedGraph and MetaGraph in one place, hoping that the overhead of these struct definitions is fairly negligible.

@CameronBieganek

The interface allows vertices to be of any type.

Same in GraphsBase.jl, that is indeed one of the main goals.

@CameronBieganek

Edges are iterable. To retrieve the vertices that define an edge e, use u, v = e.

Possible in GraphsBase.jl, although edges can be arbitrary objects.

@CameronBieganek

Vertex and edge membership can be tested with v in vertices(g) and e in edges(g), respectively.

Possible in GraphsBase.jl, but we would like to try and handle edge multiplicity, which raises the question of how to check if two edges are “equal”.

@CameronBieganek

Vertex and edge metadata are not needed for writing generic graph algorithms, so they are explicitly excluded from the AbstractGraph interface.

Strong disagreement 1: last time I checked there were 15 different packages for graphs with metadata, which is immensely confusing for the users. I think the only way to prevent that is to offer a common interface and a solid default MetaGraph type.

@CameronBieganek

There are no optional methods in the interface. For clarity and simplicity, all types that implement AbstractGraph are assumed to be mutable.

Strong disagreement 2, some graph types simply do not support vertex addition (think of GridGraphs.jl). The question of interfaces with optional parts is an unsolved one at the moment, but I’ve been working closely with @Raf on his package Interfaces.jl, which will soon be usable for graphs.

@CameronBieganek

I only implemented an undirected graph type in GraphTypes.jl, so I haven’t really fleshed out the interface for directed graphs in GraphInterface.jl. Probably a few more methods will need to be added, like is_directed, in_neighbors, and out_neighbors.

GraphsBase.jl takes directedness into account but the best mechanism for traits-based dispatch is not yet clear. In addition, the question of directed vs undirected edges has never been handled consistently.

@CameronBieganek

As you can see, the performance of GraphTypes.jl + GraphAlgorithms.jl is currently noticeably worse than the performance of Graphs.jl.

That is also the main worry for GraphsBase.jl, and a good first step would be to clean up the Graphs.jl benchmarks. We also need to define the basic algorithms that we want to test for regressions in a 2.0 interface (cause we won’t be able to test them all while we iterate on the design).

@CameronBieganek

Perhaps one way to improve the performance would be to use the equivalent of a Graphs.SimpleGraph under the hood, and then add two methods to the AbstractGraph interface:

That is an interesting suggestion! There was an old branch of mine on MetaGraphsNext.jl which took an atlernate route:

• keep all algorithms defined on integers
• add a macro to be able to call them and retrieve their results with actual vertex objects

dijkstra(g, 1, 2)
@labels dijkstra(g, 'a', 'b')