JuliaGraphs / GraphPlot.jl

Graph visualization for Julia.
http://JuliaGraphs.github.io/GraphPlot.jl/
Other
200 stars 62 forks source link

fix stress layout #193

Open GiggleLiu opened 1 year ago

GiggleLiu commented 1 year ago

List of changes

  1. Fix the incorrect implementation of stress layout,
  2. Speed up the code.

In the paper "Graph Drawing by Stress Majorization", it is mentioned that the expect distance matrix δ (or dij in the paper) should be the graph theoretical distance, rather than the uniform matrix implemented in the original implementation. image

The current implementation is also more than 10x faster for large graphs in my test case.

Example

The visualization of a chain like graph

Before the change

image

After the change

image

etiennedeg commented 2 months ago

For directed graphs, we want to ignore directedness. We would need an efficient wrapper for that instead of allocating a new graph.

GiggleLiu commented 2 months ago

For directed graphs, we want to ignore directedness. We would need an efficient wrapper for that instead of allocating a new graph.

Sorry, I am not very familiar with directed graphs. Any comments on how to implement the suggested change?

etiennedeg commented 2 months ago

We would need to write

if is_directed(g)
    g = Graph(g)
end

before computing δ, but this is dramatic for big graphs since it will fully allocate a new graph. We need here a wrapper around g that simulates an undirected graph without allocating. This wrapper would be of general interest for Graphs.jl, so I will add it.