Multigraphs?

[eahenle]

Beautiful plots!

Is it possible (or is a PR welcome) to add support for graphs with multiple edges between node pairs? I have two use cases in mind: illustrating Euler's "Bridges of Koenigsberg" problem, and rendering chemical structure graphs including double bonds.

[JuliaMLTools]

Interesting! I think we could probably do this now using a single adjacency matrix and edge vector features. Can you post a sample multigraph image here similar to what you have in mind? If so, I'll try to reproduce using EuclidGraphs.jl. Thank you!

[eahenle]

The "Bridges of Koenigsberg" graph is something like this:

Euler wanted to know if he could cross all seven bridges that connect four parts of Koenigsberg (now Kaliningrad) separated by the Pregolya river, without crossing any bridge more than once (proved it's impossible, basically inventing graph theory in the process). Without the ability to have "parallel" edges between nodes, the correct topology can't be built.

An example of a molecule might be like cyclopentadiene--graph on the left, o-chem line drawing (H atoms/nodes are implicit) on the right:

Ideally, instead of curved parallel edges, these would be actually parallel, as in the line drawing.
[img edited to correct error in molecular graph even though probably no one would have been bothered...]

One more potential use case would be directed graphs like this:

The edge AC is a nice "vanilla" situation of a weighted, directed edge. Edges AB and BA are technically distinct, but they have equal weights, so it's again no problem. But edges BC and CB have unequal weights, so they need to be handled as parallel edges.

[JuliaMLTools]

Got it! After thinking about it more, it would indeed require multiple adjacency matrices as input (as opposed to just one). It is doable, and we could generate some beautiful graphs with that! The "EdgeStyle" struct would need some type of field(s) that allowed adjusting the control points of a Bézier curve connecting the two vertices. Let me think about for a few days! I appreciate the feedback.

[eahenle]

Are you thinking something like using a Vector{Matrix{Bool}} and treating each element like a "layer" of the graph? I imagined using just a single Matrix{Int}, which stores the edge multiplicity between two nodes (0 for no edge, 1 for a single edge, 2 for a pair of parallel edges, etc.). Maybe symmetric if an undirected graph, asymmetric if directed.

Excited to see how it works out! Let me know if I can help out with a PR (in a few weeks... major deadlines approach, haha)

[JuliaMLTools]

Yes, Vector{Matrix{Bool}} or Array{Bool, 3}. Also, the "edge_style" function could have "graph_idx" passed as an argument, and each "edge style" could have a "source node angle" and a "destination node angle", with a bezier curve interpolating between those source/sink angles. The example below would be a multigraph of two graphs (two stacked adjacency matrices)... the 1st graph would have lines between the nodes; the 2nd graph would have 30° arcs between the nodes. Thoughts?

EuclidGraph(
    triangle, 
    adj_mat=rand(0:1, 3, 3, 2),
    edge_style=(graph_idx, edge) -> EdgeStyle(
          src_angle=(graph_idx == 1 ? 0 : 30),
          dst_angle=(graph_idx == 1 ? 0 : 30),
    ),
)

[eahenle]

I like it! Styles apply to separate layers, and keeps the interface simple.