Roadmap for Graphs.jl 2.0

[gdalle]

Recently, a lot of interesting but compatibility-breaking suggestions have emerged when dealing with specific issues. In order for these ideas not to be forgotten, here is a thread where we can start to organize major changes with a possible 2.0 release in mind.

[gdalle]

Here are a few topics that seem important to discuss, in no particular order. Feel free to add your own!

Support vertex and edge metadata

• 35

• 57

Add easier access to edges

• 39

• 127

• 130

Relax restrictions on vertex indices & iterators

• 109

• 122

Clarify support (or lack thereof) for multigraphs

• 125

Settle the question of flows and matchings

• 108

Improve usability of shortest paths

• 77

Improve code style

• 66

Fix heisenbugs in Parallel tests

• 94

[Tokazama]

It would be nice for us to use a generic interface to metadata that's not exclusive to graphs.

[jpfairbanks]

I would add higher order networks to this list. Simplicial Sets (Vertices, Edges, Triangles, Tetrahedra ...), Hypergraphs (V, S\subset Powerset(V)), Directed Hypergraphs, Bipartite graphs, etc would be good to think about.

[etiennedeg]

Clarify the API of all hidden assumptions, make the API complete

• Clarify support (or lack thereof) for multigraphs
• Support vertex and edge metadata

• 45

• 109

• 125 add get_edge function ?

• 92

• take inspiration from the generic API of the boost graph library

Consider returning only vertices for algorithms that return an induced subgraph

• 13

• 116

consistent approach for graph direction

• 69 add a wrapper type for specifying direction instead of a keyword. Also define a wrapper for undirected version of a directed graph.

New Features (Not specifically 2.0, but could be nice goals)

Provide basic and generic features for graph traversal

• 106

  Basic support for planarity, bipartite graphs, DAG, trees...

  Support for graph views (for filtering operations on edges or vertices, or light contraction operations)

[etiennedeg]

@Tokazama Have you a more precise idea of your suggestion ? I'm not sure to understand what it would looks like.

[Tokazama]

In terms of trait support I'd like to suggest two things:

1. We are working very hard to create a lightweight core package for ArrayInterface.jl that contains traits for mutability, resizing, etc.
2. Something comparable to IndexStyle for graphs. I did a quick gist using GraphStyle a while ago. We could account for direct access to edges across different graph structures using this without creating a complex type hierarchy.

[Tokazama]

@Tokazama Have you a more precise idea of your suggestion ? I'm not sure to understand what it would looks like.

This is a very rough draft of a generic interface for metadata I've been working on. My OSS time has been severely limited the past month due to a short term shift in my work schedule, so not much progress has been made. I think I need to write up a more exhaustive proposal describing the issue that needs to be solved with some input from other interested developers (it's a bit high level for most users). I've thought about putting something on discourse but I fear getting input from everybody that happens upon it will be a bit distracting.

[Tokazama]

There's discussion related to metadata here https://github.com/JuliaData/DataAPI.jl/issues/22

[filchristou]

Regarding the multigraphs, I have the impression it would be fairly easy to have support in the Graphs.jl Have a look at WrappedMultiGraphs.jl. Basically, this package kills this if statement and deals with the repercussions. I think something like that could be incorporated in Graphs.jl and possibly provide a trait IsMulti similar to IsDirected.

[gdalle]

I'll take a look!