Reducing edge crossings

[vyudu]

[question/feature request]

Hi, thank you for making this package. I am wondering whether there is some way to reduce the number of edge crossings in generated graphs? I have the following graph which should be "disentanglable" but ends up having a lot of crossings when laid out using Spring(). Is there some option that would reduce it (something similar to dot in Graphviz maybe)? Or a recommended layout option that would reduce it?

Basically I am wondering whether there is some generalizable approach here. The context is that this is a function that will produce a graph visualization for a reaction network, so I am hoping for something that would work for a wide range of graphs.

[asinghvi17]

Hey, do you have an MWE for this? There are a bunch of layout algorithms in NetworkLayout.jl as you might have seen...maybe you want https://juliagraphs.org/NetworkLayout.jl/dev/#Buchheim-Tree-Drawing instead if your graph is hierarchical in some way?

[vyudu]

I don't, but could try to make one if that'd help - what would an MWE look like for this? Just a simple graph that has crossings? Buchheim errors I think because there are cycles in this graph though (and trying the others it seems like SPDF() does better than Spring() but still has a few crossings).

[asinghvi17]

A graph that replicates all the properties you mention in the issue:

• Edges that cross each other when plotted
• Has cycles

would be a good first MWE, I think. Maybe just export the data you use to plot this somehow (could use JLD2 if the types aren't too esoteric/custom, otherwise just CSV for the attributes + some graph?

See https://juliagraphs.org/Graphs.jl/stable/first_steps/persistence/ for info on how to save graphs.

[vyudu]

repressilator.lgz.zip

Hopefully this works, this is the basic graph. To get this plot the code I used is here (basically it is wrapped in a type that allows plotting multiple edges, but that's not needed for this one).

[hexaeder]

Not on my computer so I cannot check your code right now. But did you try 'Stress' Layout? In my experience it is much better at entangeling, should probably replace spring as the default in the next breaking release.

Also, if your graph does not change, check out the pin and startpos keyword arguments for finetuning of layouts as well as trying random seeds.

[hexaeder]

EDIT: Nevermind, you Graph isn't a DAG.

Dot from GraphViz seems to be some optimization algo. The closest to that in Julia might be LayeredLayouts.jl with the zarate layout. Here is an example in the GraphMakie docs which uses this solver. This algorithm actually minimizes the Crossings but gets very slow for large graphs.

[vyudu]

When I tried Stress() with this graph I got an AssertionError: isfinite(s).

The pin and startpos tips are very helpful, thank you very much.

ERROR: AssertionError: isfinite(s)
Stacktrace:
  [1] stress(positions::Vector{Point{2, Float64}}, d::Matrix{Float64}, weights::Matrix{Float64})
    @ NetworkLayout ~/.julia/packages/NetworkLayout/tAjCi/src/stress.jl:180
  [2] iterate(iter::LayoutIterator{Stress{…}, SparseMatrixCSC{…}})
    @ NetworkLayout ~/.julia/packages/NetworkLayout/tAjCi/src/stress.jl:125
  [3] layout(alg::Stress{…}, adj_matrix::SparseMatrixCSC{…})
    @ NetworkLayout ~/.julia/packages/NetworkLayout/tAjCi/src/NetworkLayout.jl:83
  [4] layout
    @ ~/.julia/packages/NetworkLayout/tAjCi/ext/NetworkLayoutGraphsExt.jl:12 [inlined]
  [5] AbstractLayout
    @ ~/.julia/packages/NetworkLayout/tAjCi/src/NetworkLayout.jl:39 [inlined]
  [6] #19
    @ ~/.julia/packages/GraphMakie/JuRfL/src/recipes.jl:220 [inlined]
  [7] (::GraphMakie.var"#19#46")(arg1#230::CatalystGraphMakieExtension.MultiGraphWrap{…}, arg2#231::Stress{…})
    @ GraphMakie ./none:0
  [8] #map#13
    @ ~/.julia/packages/Observables/YdEbO/src/Observables.jl:570 [inlined]
  [9] map(f::GraphMakie.var"#19#46", arg1::Observable{CatalystGraphMakieExtension.MultiGraphWrap{…}}, args::Observable{Any})
    @ Observables ~/.julia/packages/Observables/YdEbO/src/Observables.jl:568
 [10] plot!(gp::Plot{graphplot, Tuple{CatalystGraphMakieExtension.MultiGraphWrap{Int64}}})
    @ GraphMakie ~/.julia/packages/GraphMakie/JuRfL/src/recipes.jl:213
 [11] connect_plot!(parent::Scene, plot::Plot{graphplot, Tuple{CatalystGraphMakieExtension.MultiGraphWrap{Int64}}})
    @ Makie ~/.julia/packages/Makie/pFPBw/src/interfaces.jl:395
 [12] plot!
    @ ~/.julia/packages/Makie/pFPBw/src/interfaces.jl:412 [inlined]
 [13] plot!(ax::Axis, plot::Plot{graphplot, Tuple{CatalystGraphMakieExtension.MultiGraphWrap{Int64}}})
    @ Makie ~/.julia/packages/Makie/pFPBw/src/figureplotting.jl:412
 [14] plot!(fa::Makie.FigureAxis, plot::Plot{graphplot, Tuple{CatalystGraphMakieExtension.MultiGraphWrap{Int64}}})
    @ Makie ~/.julia/packages/Makie/pFPBw/src/figureplotting.jl:407
 [15] _create_plot(F::Function, attributes::Dict{Symbol, Any}, args::CatalystGraphMakieExtension.MultiGraphWrap{Int64})
    @ Makie ~/.julia/packages/Makie/pFPBw/src/figureplotting.jl:318
 [16] #graphplot#15
    @ ~/.julia/packages/MakieCore/zO6H4/src/recipes.jl:188 [inlined]
 [17] top-level scope
    @ REPL[39]:1
Some type information was truncated. Use `show(err)` to see complete types.

[hexaeder]

Stress throwing an AssertionError is not good, I'd like to check on the graph and try to fix it in NetworkLayout.
Can you provide an MWE for that? Like taking the graph you have? Maybe calling adjacenecy_matrix on the graph you have and putting the result in the script directly. Would be much easier for me to reproduce in a self contained erroring script like

adjmat = [...]
g = SimpleGraph(adjmat)
graphplot(g; layout=Stress())

[vyudu]

OK, sorry, I realized that I was implementing adjacency_matrix incorrectly for my custom graph type that I used to plot the first one. The adjacency matrix it was building was for an unconnected graph and that's why it was giving the AssertionError (unless it should work for unconnected graphs? if not might be helpful to document that it only works for connected graphs). Building the adjmat correctly and plotting using Stress() does indeed make a nice graph with no crossings. Thank you.

[vyudu]

Though come to think of it, is there a way to implement Stress() so that it could be applied to each subnetwork of a graph if the given graph isn't connected? That would definitely be useful for my use case, where reaction networks are often disconnected but individual subnetworks are often large (and it'd be nice for them to be disentangled).

[hexaeder]

Hm in some sense the layout tries to keep neighbors close. If you have a disconnected graph, this logic does not work anymore because it would "blow away" the different parts. I think you'd need to build your own layout function

function mylayout(g::SimpleGraph)
     # do something with g, might call `Stress()(g_sub)` on the connected subgraphs `g_sub`
     return positions
end

Two options come to mind:

1. Use stress to solve all connected subgraphs separately. They will be all placed around (0,0) but you could check the minimum/maximum values of their node positions and create a composite layout by shifting all points of the sublayout to make sure they don't overlap.
2. Create a corresponding connected graph, by adding additional edges, maybe edges between the "main nodes" of each of the subnetworks? I don't know anything about reaction networks, so I have no idea if that would be possible. Then you could apply the stress layout to the new, temp graph and return the nodal positions. You only need to make sure that you're not actually mutating the graph passed to mylayout but rather work with a copy g_connected = copy(g); add_edge!(g_connected, ...). Since the number of nodes does not change, the resulting node positions are also a valid layout for the original graph g.

[hexaeder]

Looking at the code for Stress, it might be also enough to "pin" a vertice in each connected subgraph to ensure the layout does not "blow up"? This is a random guess though, might not be the case.

[hexaeder]

I created a PR which extends Stress to handle unconnected graphs.

It adds pairwise "ideal" distances between the unconnected vertices (before those where Inf). The distances are based on the number of connected components and the size of the individual components. I'd would be interested in hearing whether the chosen heuristics for this distance works for your graphs. The behavior can be fine tuned using uncon_dist keyword argument of the Stress layout:

- `uncon_dist=(maxdist, Ncomps)->maxdist*Ncomps^(1/3)`
  Per default, unconnected vertices in the graph get a pairwise "ideal" distance which scales
  with the number of connected components and the maximum distance within the components.

using CairoMakie,GraphMakie,NetworkLayout
sgkeys = [:bull, :chvatal, :cubical, :desargues,
            :diamond, :dodecahedral, :frucht, :heawood,
            :house, :housex, :icosahedral, :karate, :krackhardtkite,
            :moebiuskantor, :octahedral, :pappus, :petersen,
            :sedgewickmaze, :tetrahedral, :truncatedcube,
            :truncatedtetrahedron, :truncatedtetrahedron_dir, :tutte]
gs = filter(!is_directed, smallgraph.(sgkeys))
absdim = mapreduce(nv, +, gs)
adj = zeros(Int, absdim, absdim);
let i = 1
    for g in gs
        r = i:i+nv(g)-1
        adj[r, r] .= adjacency_matrix(g)
        i += nv(g)
    end
end
g = SimpleGraph(adj)
graphplot(g; layout=Stress())

[vyudu]

Sorry for the very belated reply. The intergraph distances seem to work quite well to me, but for larger node labels the subgraphs themselves seem to tend to get somewhat crowded (though this seems to happen for some of the other network layouts too, not just Stress()). Would there be a way to scale the graph to space out the nodes somewhat more in this kind of case?

[hexaeder]

Thanks for the feedback on the spacing!
Changing the spacing with the length of the text is not really possible unfortunatley. The problem here is, that the nodes and the text within them are always drawn the same size, regardless of zoom level (in pixel space). GraphMakie will first find the graph layout and then simply putting the nodes with labels on those positions.

In theory, it is possible to build layouts which respect nodesize. I think some of them might actually have the option for that (buchheim tree drawing takes a nodesize for example). However to do this effectively, you'd need to bring the text and the node markers to dataspace rather than pixel space, otherwise the node size changes with respect to the layout coordinates when zooming in and out of the figure, adjusting axis limits and so on.