Multiplicity

[gdalle]

Opening this to keep track of issues related to multiple edges or layers

Related

• Proposals for Graphs.jl 2.0 from the perspective of MultilayerGraphs.jl Graphs.jl#165
• [Port] Fallback for all edge operations Graphs.jl#39

[mofeing]

In my mind, there are two ways to implement multigraphs:

• Store multiplicity in the edge
• Store multiplicity in the graph

Store multiplicity in the edge

A MultiEdge type could be implemented for this. Exact equality relations must be thought but I would suggest viewing simple edges as the collection of all multi edges, so one could implement it like:

struct MultiEdge{T,EdgeType<:AbstractEdge{T}} <: AbstractEdge{T}
    edge::EdgeType
    mul::T
end

Base.in(a::MultiEdge, b::AbstractEdge) = a.edge == b

The consequences of this strategy is that each multiedge instance is a different entity with no knowledge about its siblings. For example, if we have multiple edges like $(a,b,1)$, $(a,b,2)$ and $(a,b,3)$ and we remove the edge with multiplicity $2$, then the remaining multiplicities will be $1$ and $3$ which are no longer a continuous range. This would affect us on how we count the new multiplicity for when we want to add a new edge or just counting the cardinality: we would require to iterate through all the keys of the edges.
The good thing is that if we have some edge_metadata::Dict{MultiEdge,Metadata} in the graph, then we don't need to update the keys.

Store multiplicity in the graph

Here the multiplicity of each edge would be managed by a MultiSet (basically a Dict{EdgeType,Integer}). The pros are that now is easier to push!/pop! edges while keeping their multiplicities in the 1:M range. The bad thing is that if we remove an edge, we need to update the keys of an hypothetical edge_metadata::Dict{Tuple{EdgeType,Integer},Metadata} dictionary.

struct MultiGraph{T,EdgeType<:AbstractEdge{T}}
    vertices::Set{T}
    edges::MultiSet{EdgeType}
end

Maybe we need a mix of the two above?