Hi, all! I’ve created a new package GraphInterface.jl as a proposal for the new `AbstractGraph`

interface for Graphs.jl version 2.0. I know that there is ongoing work in the GraphsBase.jl repository on the new version 2.0 interface, but my proposal differs in some respects, so I felt it would be easiest to create my own repo containing my proposal. Please let me know what you all think about the inteface proposal in GraphInterface.jl.

The GraphInterface.jl package is a very minimal package containing mainly just function stubs and docstrings, along with a few convenience methods. An example type that implements the `AbstractGraph`

interface is given in a separate GraphTypes.jl repo. I’ve also implemented a few basic graph algorithms in a GraphAlgorithms.jl repo. The algorithms are implemented in accordance with the `AbstractGraph`

interface. (One of the algorithms is the Dijkstra shortest path algorithm. It was ported from Graphs.jl, and thus the Graphs.jl license is included in the GraphAlgorithms.jl license.) The dependency relation among the three packages is as follows:

```
GraphTypes <- GraphInterface -> GraphAlgorithms
```

where arrows point from dependencies to dependents. In other words, GraphTypes.jl and GraphAlgorithms.jl are independent of each other. (The Project.toml file for GraphAlgorithms.jl is misleading in this regard. I got tired of fiddling with local dependencies and just added GraphTypes.jl as a direct dependency so that I could get the unit tests running.)

A few points of interest regarding the interface:

- The interface allows vertices to be of any type. Or rather, a given graph instance will have a vertex type defined by
`eltype(vertices(g))`

. - Edges are iterable. To retrieve the vertices that define an edge
`e`

, use`u, v = e`

. - Vertex and edge membership can be tested with
`v in vertices(g)`

and`e in edges(g)`

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

interface. Graph types are, of course, free to implement their own interface for metadata if they so choose. - There are no optional methods in the interface. For clarity and simplicity, all types that implement
`AbstractGraph`

are assumed to be mutable. In other words, they must implement`add_vertex!`

,`add_edge!`

,`rem_vertex!`

,`rem_edge!`

, and`set_weight!`

. - 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`

.

Further details on the interface can be found in the README.md and docstrings for GraphInterface.jl.

Here is an example of the interface in action for the `Graph`

type from GraphTypes.jl:

## Example of interface implemented in GraphTypes.jl

```
julia> using GraphTypes
julia> g = Graph{Char}()
Graph:
Vertex type: Char
Number of vertices: 0
Number of edges: 0
julia> add_vertex!(g, 'a')
Graph:
Vertex type: Char
Number of vertices: 1
Number of edges: 0
julia> add_edge!(g, 'b', 'c')
Graph:
Vertex type: Char
Number of vertices: 3
Number of edges: 1
julia> add_edge!(g, Edge("cd"))
Graph:
Vertex type: Char
Number of vertices: 4
Number of edges: 2
julia> collect(vertices(g))
4-element Vector{Char}:
'a': ASCII/Unicode U+0061 (category Ll: Letter, lowercase)
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
'b': ASCII/Unicode U+0062 (category Ll: Letter, lowercase)
julia> collect(edges(g))
2-element Vector{Edge{Char}}:
c -- d
b -- c
julia> 'a' in vertices(g)
true
julia> Edge("bc") in edges(g)
true
julia> weight(g, 'b', 'c')
1.0
julia> neighbors(g, 'c')
Neighbors: {d, b}
julia> e = first(edges(g))
Edge:
c -- d
julia> u, v = e;
julia> u
'c': ASCII/Unicode U+0063 (category Ll: Letter, lowercase)
julia> v
'd': ASCII/Unicode U+0064 (category Ll: Letter, lowercase)
```

Finally, I ran a few benchmarks that compare the performance of GraphTypes.jl + GraphAlgorithms.jl to Graphs.jl. The results are summarized in the following table.

Algorithm | Graphs.jl (ms) | GraphTypes.jl + GraphAlgorithms.jl (ms) | Slowdown Factor |
---|---|---|---|

Dijkstra shortest path | 8.155 | 15.7 | 1.9 |

Graph union | 6.853 | 24.745 | 3.6 |

Graph intersection | 7.045 | 9.312 | 1.3 |

As you can see, the performance of GraphTypes.jl + GraphAlgorithms.jl is currently noticeably worse than the performance of Graphs.jl. But there are probably some ways to improve the performance. Suggestions and PRs are welcome.

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:

`coded(g::AbstractGraph)`

: Returns an object that satisfies the immutable portions of the interface (but not`add_vertex!`

,`rem_vertex!`

, etc) and has integer vertices from`1:nv(g)`

.`mapper(g::AbstractGraph)`

: Returns a bijection that translates back-and-forth between vertices (which are of type`eltype(vertices(g))`

) and integer vertex codes (from`1:nv(g)`

).

That way we keep the generic interface of GraphInterface.jl, but under the hood algorithms can still use simple integer coded graphs with vertices from `1:nv(g)`

. I think that approach would preserve most of the performance seen in Graphs.jl.