Multigraph support

[mtfishman]

Hi @hexaeder,

Thanks again for the great package. We are currently using it very successfully as a backend for visualizing tensor networks in ITensors.jl (through add-on packages like ITensorGLMakie).

Do you support or plan to support plotting multigraphs? I see that Plots.jl has some support: https://docs.juliaplots.org/latest/graphrecipes/examples/#Multigraphs and there is a Multigraphs.jl package, but over all the support for multigraphs is a bit lacking in the Julia ecosystem. I imagine it doesn't need a special graph type, just some extra keyword arguments passed to graphplot optionally indicating the multiplicity (and maybe directions) of the edges.

For the application of tensor network visualization, directed multigraphs are quite common. Right now, out of simplicity, I just handle the multigraph case with a simple graph that has edge labels indicating there are multiple edges, but ultimately it would be nice to visualize multigraphs directly.

Time permitting, I would be interested in helping out with adding that as a feature (though I am not so familiar with the design and internals of Makie).

Cheers,
Matt

[mtfishman]

I suppose I missed the fact that DiGraphs that have nodes connected by two directed edges get plotted as multigraphs (#37, #48) so I guess this functionality is available in some form.

[hexaeder]

yeah, the assumptions inside GraphMakie arn't that strict, it should work with any subtype of AbstractGraph, I guess you could try with the Multigraph package. GraphMakie will just draw an line for each edge in the EdgeIterator (obtained by edges(g)). All the edge parameters (such as labels but also the parameter for curvy lines) can be given on a per-edge-basis as vector or dict.

I guess MultiGraphs defines such Edge Iterator. Probably the easiest solution would be to use the new interface created in #48 for that. That is, set a base distance of 1 for each edge and than go through the edge iterator. If you encounters a second edge for a previously seen pair of vertices set the distance to 2 and so on.

[hexaeder]

Well no, forget what i just said, Multigraphs does not work like this.

g = Multigraph(3)
add_edge!(g, 1, 2)
add_edge!(g, 1, 2)
add_edge!(g, 2, 3)

edges(g) |> collect

will instead return

2-element Vector{Any}:
 Multiple edge 1 => 2 with multiplicity 2
 Multiple edge 2 => 3 with multiplicity 1

which is a new edge type. Hm...

[mtfishman]

Perhaps internally it could take whatever input (Multigraph or a keyword argument of multiplicities of edges) and convert it into a special edge iterator that adds repeated edges according to the multiplicity?

[hexaeder]

Yeah i guess you'd have to define a new graph type which handles multiple edges as literal multiple edges instead of a single edge with multiplicity.

I guess there are points two make for both views. Simple example on how a wrapper like this could look.

using GraphMakie
using GLMakie
using Multigraphs
using Graphs

using Graphs.SimpleGraphs

struct MultigraphWrap{T} <: AbstractGraph{T}
    g::Multigraph{T}
end
Base.eltype(g::MultigraphWrap) = eltype(g.g)
Graphs.edgetype(g::MultigraphWrap) = edgetype(g.g)
Graphs.has_edge(g::MultigraphWrap, s, d) = has_edge(g.g, s, d)
Graphs.has_vertex(g::MultigraphWrap, i) = has_vertex(g.g, i)
Graphs.inneighbors(g::MultigraphWrap{T}, i) where T = inneighbors(g.g, i)
Graphs.outneighbors(g::MultigraphWrap{T}, i) where T = outneighbors(g.g, i)
Graphs.ne(g::MultigraphWrap) = mapreduce(e->e.mul, +, edges(g.g))
Graphs.nv(g::MultigraphWrap) = nv(g.g)
Graphs.vertices(g::MultigraphWrap) = vertices(g.g)
Graphs.is_directed(g::MultigraphWrap) = is_directed(g.g)

function Graphs.edges(g::MultigraphWrap)
    out = SimpleEdge[]
    for e in edges(g.g)
        for m in 1:e.mul
            push!(out, SimpleEdge(e.src, e.dst))
        end
    end
    return out
end

function gen_distances(g::MultigraphWrap; inc=.1)
    edgearray = edges(g)
    distances = zeros(length(edgearray))
    for i in 2:Base.length(edgearray)
        if edgearray[i] == edgearray[i-1]
            distances[i] = distances[i-1] + inc
        end
    end
    return distances
end

g = Multigraph(3)
add_edge!(g, 1, 2, 1) # one edge
add_edge!(g, 2, 3, 2) # two edges
add_edge!(g, 3, 1, 3) # three edges

gwrap = MultigraphWrap(g)
# random layout becaus adjecency matrix does not work on my type
# graphplot(gwrap; layout=_->Point2f.([(0,0),(1,1),(0,1)]), curve_distance=gen_distances(gwrap))

# update 27.01.2023
graphplot(gwrap; layout=_->Point2f.([(0,0),(1,1),(0,1)]),
          curve_distance=gen_distances(gwrap),
          curve_distance_usage=true)

[mtfishman]

Awesome! That looks straightforward.

Once we start adding multigraph visualization to our package, I'm happy to just include a wrapper type like that internally in our code (our multigraphs actually get determined implicitly by the tensor network where there are multiple indices contracted between pairs of tensors, so we would never really have a Multigraph explicitly to begin with, more like a metagraph which has an interpretation as a multigraph). But for more general functionality, would you envision GraphMakie depending on Multigraphs.jl, or some other interface? Personally I would vote for a keyword argument like edge_multiplicity which specifies the multiplicity of an edge, instead of making people use a special multigraph type.

[hexaeder]

Well, for the context of plotting I don't really like the approach of grouping multiple edges into one. There is a lot of code which depends on the fact that the EdgePlot draws exactly ne(g) plot elements and so forth. This is also implicitly assumed in all of the edge parameters (for example there can be exactly ne(g) edge labels, edge colors, ...).

Also, displaying the multiple edges as curvy lines would be yet another interface for that feature besides waypoints, tangents and curve_distance. At some point i becomes to messy. So I guess instead I'd vote for another Multigraphs package with the described functionality above. Or alternatively reach out to the maintainer of Multigraphs and ask what he thinks about another Multigraphs type with this slighly different appraoch. Both types could be quite easily converted into eachother.

[mtfishman]

Gotcha, I think I understand.

Perhaps one approach could be to make an extension package to GraphMakie, such as MultiGraphMakie.jl, that overloads graphplot for Multigraph. MultiGraphMakie.jl could define MultigraphWrap like above (as an internal type), and just forward graphplot(::Multigraph, ...) to graphplot(::MultigraphWrap, ...).

[mtfishman]

Does that sound reasonable? I suppose we would have to think about how keyword arguments like edge labels and things like that get forwarded.

[hexaeder]

Yeah something like this could work, but is probably harder to maintain instead of just exporting the wrapper (or better: an alternative Multigraph-type) to the end user and let them do the conversion of the arguments themself. For example one would need to "hand craft" conversion for every single new argument.

But let me know when you've found a nice solution for ITensor, maybe it is worth providing such wrapper types as part of GraphMakie, Multigraphs or as a separate package. Or even an extension/wrapper for the graphplot command.

[mtfishman]

For ITensor, I think I would just define something like MultigraphWrap internally and depend on MultiGraphs.jl, but not export any of that functionality, since we will have our own metagraph-like object for the external interface, so those just need to be used internally for conversions and forwarding to graphplot.

But for the sake of exposing multigraph plotting functionality through GraphMakie for a wider audience, perhaps a special Multigraph-like type which treats edge multiplicity explicitly in terms of multiple edges is best.

Based on the multigraphs example, it looks like Plots.jl/GraphRecipes.jl may handle edge multiplicity in a similar way you are proposing, but through an adjacency list. I suppose that is quite similar to handling it through an edge list.

@Roger-luo, @ChenZhao44, do you have an opinion about this?

[ChenZhao44]

Thanks for the visualization tool for Multigraphs.jl. The wrapper type seems the minimal way to do this because we return multiple edges when iterating egdes in a multigraph. I have only one suggestion about the wrapper. We can use

Graphs.ne(g::MultigraphWrap) = ne(g.g; count_mul = true)

instead of

Graphs.ne(g::MultigraphWrap) = mapreduce(e->e.mul, +, edges(g.g))

to get the number of simple edges.

As for ITensor.jl, I am not sure that Multigraphs.jl is enough for representing tensors. Because in Multigraphs.jl, we have only record the multiplicity of edges, so that all simple edges in a multiple edge are regarded as the same. While for tensor networks, we may want to differ those simple edges by assigning those simple edges to different indices. This requires the capability of storing meta information on each simple edge.

[mtfishman]

That is cleaner, thanks @ChenZhao44.

@ChenZhao44, @hexaeder, maybe an interface solution to this could be the following. What if GraphMakie had an internal edge iterator that defaulted to edges, but could be overloaded for special graph types like Multigraphs.Multigraph. For example:

# Internal fallback definition
graphmakie_edges(g) = edges(g)

# This could be overloaded externally
function GraphMakie.graphmakie_edges(g::Multigraphs.Multigraph)
    out = SimpleEdge[]
    for e in edges(g.g)
        for m in 1:e.mul
            push!(out, SimpleEdge(e.src, e.dst))
        end
    end
    return out
end

and additionally a similar graphplot_ne function. Internally, GraphMakie would then use graphmakie_edges and graphmakie_ne in place of Graphs.edges and Graphs.ne. Then, for graphs that don't follow exactly the expected interface of GraphMakie for edge iteration, there would be a minimal set of overloads that could be made externally, and a wrapper type wouldn't need to be made. These overloads could be defined either internally by GraphMakie if GraphMakie is willing to depend on a certain Graphs.jl-extended type, or by an external package that depends on GraphMakie (this could even be done by an interface package GraphMakieCore.jl that only defines the functions that need to be overloaded and the generic fallbacks, like the ChainRulesCore design, so then packages don't have to depend on a heavy-duty dependency but can opt-in to GraphMakie plotting).

@ChenZhao44, I was not suggesting or considering using Multigraphs.jl as a storage type for tensor networks. In practice, I am using a metagraph. More specifically, I am using a metagraph type like MetaGraphs.jl, but I am working on my own metagraph type that has a simpler interface, since I find the MetaGraph interface to be unnecessarily complicated for my use case. But in the end, it indeed is a wrapper around a Graph which has metadata with tensors on the nodes or lists of indices on the edges. In practice, to do the visualization, the tensor network object would get converted internally to a Graphs.SimpleGraph (or MultigraphWrap to visualize it as a multigraph) because that is what is expected by GraphMakie.

Perhaps, knowing now that GraphMakie accepts a generic AbstractGraph type, I can skip the conversion to SimpleGraph or MultigraphWrap and make my tensor network type a subtype of AbstractGraph with the correct edge iteration that is expected by GraphMakie. But anyway, that is an internal detail and the conversions are no big deal.

[filchristou]

letting you know that the code aboive doesn't work as it should

tested for

Status `/tmp/jl_hqA6OK/Project.toml`
  [e9467ef8] GLMakie v0.8.1
  [1ecd5474] GraphMakie v0.5.2
  [86223c79] Graphs v1.7.4
  [7ebac608] Multigraphs v0.3.0

any ideas why ?

[hexaeder]

Hm you need to use

graphplot(gwrap; layout=_->Point2f.([(0,0),(1,1),(0,1)]),
          curve_distance=gen_distances(gwrap),
          curve_distance_usage=true)

so explicitly set curve_distance_usage true. Default is automatic. Idea there is, that if you set curve_distance=10 for all edges, per default it should only bend directed edges if they have a counterpart (edge in opposite direction). Single individual lines stay straight.

GraphMakie.jl/src/recipes.jl

Lines 376 to 387 in 6c40e58

	cdu = getattr(attr.curve_distance_usage, i)
	if cdu === true
	curve_distance = getattr(attr.curve_distance, i, 0.0)
	elseif cdu === false
	curve_distance = 0.0
	elseif cdu === automatic
	if is_directed(g) && has_edge(g, dst(e), src(e))
	curve_distance = getattr(attr.curve_distance, i, 0.0)
	else
	curve_distance = 0.0
	end
	end

Not sure if this is the best possible default.

[filchristou]

@mtfishman Maybe this is of interest to you JuliaGraphs/MetaGraphsNext.jl#40 . My motivation is also to have a MetaGraph{Multigraph} kind of type.

I personally find it quite a big decision to migrate all edges() in graph_edges().
This sounds like making a rule out of an exception.

Maybe with the introduction of weak dependencies, we can again discuss about putting a weak dependency to Multigraphs.jl, and i.e. dealing with this as an exception. Basically wrapping it up around MultigraphWrap and forward it to graphplot.. ?

[hexaeder]

I think both are nearly interchangable. Either define plottable_edges with fallback on edges for all types and overload it in a package extension for MultiGraph. Or wrap the MultiGraph and redefine edges for the wrap in a package extension.
I agree that creating a new function seems like making a rule of an exeption and feels unecessarily complex for the default graph objects. However it has a slight advantage: its easier to expose the origin of the ordering to the users. The edge indices would allways follow the same iterator plottable_edges(g) which they can explicitly use while creating the other graphplot arguments. For multigrphs that would be nicer than relying on some internal wrapper graph type nobody knows.

Either way there probably needs to be a new curve_distance_usage = :pairwise which somehow enumerates the edge per nodepair and assigns individual distance (which is the maximum distance between straight line and curved line) such that the edges have a pairwise distance as specified in curve_distance. I think this would be the logical extension to what automatic is doing for graphs with atmost 2 edges but with a more descriptive name (i would remove automatic in favour of that)

(tbh I really hate the whole cuve_distance_usage parameter and i'd drop it entierely if we'd find a interface which is more straight forward)