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

• Common interface for graphs with metadata #35
• [Port] Proposal: relax restriction on vertex IDs #57

Add easier access to edges

• [Port] Fallback for all edge operations #39
• Working with edge indices #127
• Coherent return types for Kruskal vs Prim #130

Relax restrictions on vertex indices & iterators

• Implicit graph structure #109
• add_vertex! should return the added vertex. #122

Clarify support (or lack thereof) for multigraphs

• Fix A* implementation #125

Settle the question of flows and matchings

• Move code from GraphFlows and GraphsMatching to GraphsOptim #108

Improve usability of shortest paths

• Standardized output for shortest path algorithms #77

Improve code style

• [Port] Add JuliaFormatter template #66

Fix heisenbugs in Parallel tests

• Move broken Parallel.gdistances function to Experimental submodule #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
• [Port] Inconsistency about weights #45
• Implicit graph structure #109
• Fix A* implementation #125 add get_edge function ?
• IsMutable trait #92
• take inspiration from the generic API of the boost graph library

Consider returning only vertices for algorithms that return an induced subgraph

• [BUG] biconnected_components loses some edges - should we return only vertices ? #13
• Change A* output to a vector of tuples #116

consistent approach for graph direction

• Consistent approach to 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

• Feature Request: Iterator 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 JuliaData/DataAPI.jl#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.