Proposals for Graphs.jl 2.0 from the perspective of MultilayerGraphs.jl

[InterdisciplinaryPhysicsTeam]

Hello,

Thanks for this beautiful ecosystem!

We are the developers of MultilayerGraphs.jl. As stated in the announcement and perhaps more apparent in the package tutorials, the way MultilayerGraphs.jl is implemented (i.e. by relying on Graphs.jl's extensions instead of reinventing every wheel) forced us to have various pieces of the Graphs.jl ecosystem work together. The package is still a work in progress, missing some multilayer graph-specific analytical tools and features, but we felt like it reached a state where it needed to be put out to get feedback and sum up our little experience developing it so far.

Thus we'd have some proposals. We will try to document these proposals referring to the issues listed here:

1. Regarding the generalization of vertex labels discussed in these three issues: Common interface for graphs with metadata and [Port] Proposal: relax restriction on vertex IDs, Discussion : API for Graphs.jl 2.0. Multilayer graphs come with the feature that they represent the same set of nodes in each of their layers (and interlayers). This prompted us to define our own vertex type MultilayerVertex{T} <: AbstractMultilayerVertex{T} <: AbstractVertex{T} which is basically a struct containing the standard Int vertex label and a Symbol stating the Layer the vertex belongs to. So a vertex becomes a representation of a node within a layer or interlayer of the multilayer graph. We then resorted to a strategy similar to this one to get back to the Int labels when necessary (which for interlayers don't coincide with the Int label of the common set of nodes), which we didn't find too clumsy. Since cases like ours where more complex vertex structures are needed do emerge, we'd propose to move our (one-liner) AbstractVertex{T} implementation to Graphs.jl. The T. in our case, is the node type (i.e. it is the usual consecutive Int label). Algorithms that do require ordered Int labels may either be reimplemented by the respective packages, or provide a Function that maps vertices to Int labels, as proposed here (or would a Dict/OrderedDict like we did be faster?);
2. Since, as stated above, all layers and interlayers are bound to be represented by a Graphs.jl's extensions, it would be nice if every extension had to implement some default constructors. It may also benefit other "wrapper" packages. In particular, we propose the following signatures:
   2.1 (nv::Int64, ne::Int64) for a random graph with nv vertices and ne nodes. It is already possible for Simple(Di)Graph, but since it is not required it doesn't work e.g. with SimpleWeightedGraphs.jl;
   2.2 (; T = ..., U = ..., ...) for a default empty graph with 0 nodes, 0 edges, and user-defined or default type parameters. This is in partial contradiction with Make zero function not mandatory for AbstractGraph interface, but could maybe be resolved by just requiring it for mutable graphs (see comment);
   2.3 (adjm) to construct a graph from its adjacency (weight) matrix/tensor;
   If accepted, these and the following requirements could be added to the requirements for extensions section;
3. Right now there is no standard API to get (and in some cases like ours also to set) the eltype of the weight matrix/tensor of a graph (defaulting to the eltype of the adjacency matrix when the graph is not weighted). It is also not required for such eltype to show in the type parameters of custom graph types also when it is settable by the user or not standard (although packages like SimpleWeightedGraphs.jl actually already do it). We think it would be nice if it was enforced by the requirements for extensions to include such type parameter in the type parameter signature of custom graphs (maybe it could go into the second place after the node label type T?), and if there were a method (like adjm_eltype and/or weight_eltype) to access it. We think such feature would make life easier for "wrapper" packages like ours (in our case it was about finding the minimum common adjm_eltype between layers and interlayers needed to properly type the adjacency tensor). Alternatively one may go down the route AbstractGraph{T <: AbstractVertex, E <: AbstractEdge} proposed here and maybe store the weight type (which defaults to the adjacency matrix's eltype when the graph is unweighted) as an edge type parameter?;
4. We do agree with the statement in [Port] Fallback for all edge operations, especially for the add_edge! and rem_edge! methods. Also, if the edge is weighted, it could be required another dispatch for add_edge! of the form add_edge!(g::G, src(e)::T, dst(e)::T, weight::U) where {T,U, G <: MyCustomGraph{T,U}} where I followed the type convention proposed in 3. The Add_edge! and rem_edge! functions should also mimic the behaviour of the Graphs.jl's ones, i.e. returning true when they succeed or false otherwise (or whatever other behaviour for these or similar functions will be agreed upon, like in the issue add_vertex! should return the added vertex.);
5. The are some issues regarding traits, such as IsMutable trait and the proposed traits in Discussion : API for Graphs.jl 2.0. It would be nice to have more traits (for example we had to implement the IsWeighted trait to differentiate between weighted and unweighted underlying graphs), but we noticed some drawbacks of the current traits implementation based on SimpleTraits.jl. It seems to be no longer actively maintained (see this and this), and it comes with the drawbacks of not allowing to dispatch on multiple traits at once. We think this could be a useful feature (for example to dispatch on directedness and weightedness, or the graph being meta/non-meta, etc.). A nice overview of many (all?) traits package can be found here, so moving to WhereTraits.jl could be worth considering even though we have never tried it. Otherwise, implementing Tim Holy Traits Trick from scratch may be not that hard, but then ambiguities may be more difficult to handle.

We will be glad to comply with whatever comes out of Inconsistency about weights and Implicit graph structure and all the aforementioned.

CC: @pitmonticone, @ClaudMor

[gdalle]

@InterdisciplinaryPhysicsTeam sorry for never answering. Thank you for these suggestions!

Development for GraphsBase.jl has been more active lately, and I've linked to this issue in the new repo so as to keep track