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

**URL:** https://discourse.julialang.org/t/rfc-graphinterface-jl-an-interface-proposal-for-graphs-jl-version-2-0/104518
**Category:** Graphs
**Tags:** lightgraphs, graphs
**Created:** [October 3, 2023, 1:03am UTC](https://discourse.julialang.org/t/rfc-graphinterface-jl-an-interface-proposal-for-graphs-jl-version-2-0/104518 "2023-10-03T01:03:36Z")
**Posts on this page:** 1
**Showing post:** 3

<div class="post-metadata">

### Author: ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [October 3, 2023, 7:17am UTC](https://discourse.julialang.org/t/rfc-graphinterface-jl-an-interface-proposal-for-graphs-jl-version-2-0/104518/3 "2023-10-03T07:17:15Z")

</div>

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](https://github.com/JuliaGraphs/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](https://github.com/rafaqz/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](https://github.com/JuliaGraphs/GraphsBase.jl/issues/20), 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](https://discourse.julialang.org/t/the-graphs-ecosystem/99463#the-list-2), 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](https://github.com/gdalle/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](https://github.com/rafaqz/Interfaces.jl), which will soon be [usable for graphs](https://github.com/rafaqz/Interfaces.jl/pull/16).
> 
> > [@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](https://github.com/JuliaGraphs/GraphsBase.jl/issues/12) is not yet clear. In addition, the question of [directed vs undirected edges](https://github.com/JuliaGraphs/GraphsBase.jl/issues/16) 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](https://github.com/JuliaGraphs/Graphs.jl/issues/310). 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
> 
> ```julia
> dijkstra(g, 1, 2)
> @labels dijkstra(g, 'a', 'b')
> 
> ```

---

_[View the full topic](https://discourse.julialang.org/t/rfc-graphinterface-jl-an-interface-proposal-for-graphs-jl-version-2-0/104518)._