Open gdalle opened 9 months ago
In my mind, there are two ways to implement multigraphs:
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.
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?
Opening this to keep track of issues related to multiple edges or layers
Related