search

JuliaGraphs / NetworkLayout.jl

Layout algorithms for graphs and trees in pure Julia.
Other
96 stars 22 forks source link

Stack overflow in Spring & SFDP layouts #67

Open kenahoo opened 2 weeks ago

kenahoo commented 2 weeks ago

I have some somewhat-large graph data that I'm attempting to do partial layouts on, and I'm hitting StackOverflowErrors when I try. I'm attaching the data, and here's the code I'm using for layout:

using GraphIO.EdgeList, Graphs
using NetworkLayout
using GeometryBasics: Point
using JSON3

println("Loading data")
g = loadgraph("graph.e", EdgeListFormat())
pin = identity.(JSON3.read("pin.json"))
initialpos = identity.(JSON3.read("initialpos.json"))

println("Running layout")
# Both of the following fail
NetworkLayout.sfdp(g; pin, initialpos, iterations = 5)
NetworkLayout.spring(g; pin, initialpos, initialtemp = 3.940695496278636, iterations = 5)

data.tgz

Any thoughts? I did also try converting g to an undirected graph, but that doesn't seem to make any difference.

hexaeder commented 1 week ago

Can you post the output of ] st and ] st -m so we can see all package versions? And also the stacktrace? The code you posted just works for me....

kenahoo commented 1 week ago

Here you go:

julia> NetworkLayout.spring(g; pin, initialpos, initialtemp = 3.940695496278636, iterations = 5)
ERROR: StackOverflowError:

(tmp) pkg> st
Status `/private/tmp/Project.toml`
  [5c1252a2] GeometryBasics v0.4.11
  [aa1b3936] GraphIO v0.7.0
  [86223c79] Graphs v1.12.0
  [0f8b85d8] JSON3 v1.14.0
  [46757867] NetworkLayout v0.4.6

(tmp) pkg> st -m
Status `/private/tmp/Manifest.toml`
  [ec485272] ArnoldiMethod v0.4.0
  [34da2185] Compat v4.16.0
  [187b0558] ConstructionBase v1.5.8
  [9a962f9c] DataAPI v1.16.0
  [864edb3b] DataStructures v0.18.20
  [e2d170a0] DataValueInterfaces v1.0.0
  [8bb1440f] DelimitedFiles v1.9.1
  [411431e0] Extents v0.1.4
  [68eda718] GeoFormatTypes v0.4.2
  [cf35fbd7] GeoInterface v1.3.7
  [5c1252a2] GeometryBasics v0.4.11
  [aa1b3936] GraphIO v0.7.0
  [86223c79] Graphs v1.12.0
  [d25df0c9] Inflate v0.1.5
  [c8e1da08] IterTools v1.10.0
  [82899510] IteratorInterfaceExtensions v1.0.0
  [692b3bcd] JLLWrappers v1.6.0
  [0f8b85d8] JSON3 v1.14.0
  [1914dd2f] MacroTools v0.5.13
  [46757867] NetworkLayout v0.4.6
  [bac558e1] OrderedCollections v1.6.3
  [69de0a69] Parsers v2.8.1
  [aea7be01] PrecompileTools v1.2.1
  [21216c6a] Preferences v1.4.3
  [ae029012] Requires v1.3.0
  [699a6c99] SimpleTraits v0.9.4
  [90137ffa] StaticArrays v1.9.7
  [1e83bf80] StaticArraysCore v1.4.3
  [09ab397b] StructArrays v0.6.18
  [856f2bd8] StructTypes v1.11.0
  [3783bdb8] TableTraits v1.0.1
  [bd369af6] Tables v1.12.0
  [5ae413db] EarCut_jll v2.2.4+0
  [0dad84c5] ArgTools v1.1.1
  [56f22d72] Artifacts
  [2a0f44e3] Base64
  [ade2ca70] Dates
  [8ba89e20] Distributed
  [f43a241f] Downloads v1.6.0
  [7b1f6079] FileWatching
  [b77e0a4c] InteractiveUtils
  [b27032c2] LibCURL v0.6.4
  [76f85450] LibGit2
  [8f399da3] Libdl
  [37e2e46d] LinearAlgebra
  [56ddb016] Logging
  [d6f4376e] Markdown
  [a63ad114] Mmap
  [ca575930] NetworkOptions v1.2.0
  [44cfe95a] Pkg v1.10.0
  [de0858da] Printf
  [3fa0cd96] REPL
  [9a3f8284] Random
  [ea8e919c] SHA v0.7.0
  [9e88b42a] Serialization
  [1a1011a3] SharedArrays
  [6462fe0b] Sockets
  [2f01184e] SparseArrays v1.10.0
  [10745b16] Statistics v1.10.0
  [fa267f1f] TOML v1.0.3
  [a4e569a6] Tar v1.10.0
  [cf7118a7] UUIDs
  [4ec0a83e] Unicode
  [e66e0078] CompilerSupportLibraries_jll v1.1.1+0
  [deac9b47] LibCURL_jll v8.4.0+0
  [e37daf67] LibGit2_jll v1.6.4+0
  [29816b5a] LibSSH2_jll v1.11.0+1
  [c8ffd9c3] MbedTLS_jll v2.28.2+1
  [14a3606d] MozillaCACerts_jll v2023.1.10
  [4536629a] OpenBLAS_jll v0.3.23+4
  [bea87d4a] SuiteSparse_jll v7.2.1+1
  [83775a58] Zlib_jll v1.2.13+1
  [8e850b90] libblastrampoline_jll v5.11.0+0
  [8e850ede] nghttp2_jll v1.52.0+1
  [3f19e933] p7zip_jll v17.4.0+2

Here's also my version info:

julia> versioninfo()
Julia Version 1.10.5
Commit 6f3fdf7b362 (2024-08-27 14:19 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: macOS (arm64-apple-darwin22.4.0)
  CPU: 10 × Apple M1 Pro
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, apple-m1)
Threads: 1 default, 0 interactive, 1 GC (on 8 virtual cores)
Environment:
  JULIA_PKG_USE_CLI_GIT = true
kenahoo commented 1 week ago

Just to be clear - there doesn't seem to be any stack trace generated. If I catch the exception object, it looks like this:

(exception = StackOverflowError(), backtrace = Base.StackTraces.StackFrame[])
hexaeder commented 1 week ago 
using Pkg
pkg"activate --temp"
pkg"dev NetworkLayout"
pkg"add GraphIO, Graphs, GeometryBasics, JSON3"
using GraphIO.EdgeList, Graphs
using NetworkLayout
using GeometryBasics: Point
using JSON3

tmpdir = mktempdir()
dl = download("https://github.com/user-attachments/files/17196286/data.tgz", joinpath(tmpdir, "data.tgz"))
run(`tar -xzf $dl -C $tmpdir`)

gdat = joinpath(tmpdir, "graph.e")
pdat = joinpath(tmpdir, "pin.json")
idat = joinpath(tmpdir, "initialpos.json")
@assert isfile(gdat) && isfile(pdat) && isfile(idat)

println("Loading data")
g = loadgraph(gdat, EdgeListFormat())
pin = identity.(JSON3.read(pdat))
initialpos = identity.(JSON3.read(idat))

NetworkLayout.sfdp(g; pin, initialpos, iterations = 5)
NetworkLayout.spring(g; pin, initialpos, initialtemp = 3.940695496278636, iterations = 5)

here's a fully contained example including downloading and unzipping the data in a temp dir. Maybe others wanna try it out too. I still cannot reproduce, neither on 1.10 nor on 1.11...

On the first glance i could not find a recursion in the layouts. Does this happen also without pin/initial position or only if you provide those arguments?

kenahoo commented 1 week ago

My main use case is spring(), so I'll limit testing to that. It looks like if I omit the pin argument, it still fails, but if I also omit initialpos it starts succeeding:

julia> NetworkLayout.spring(g; initialpos, initialtemp = 3.940695496278636, iterations = 5)
ERROR: StackOverflowError:

julia> NetworkLayout.spring(g; initialtemp = 3.940695496278636, iterations = 5)
7181-element Vector{Point{2, Float64}}:
 [-0.6342386051062798, 0.6058030499561213]
 [0.18152490286302042, -0.4932759629105654]
 [0.5321571725614764, -0.932350047898484]
...

It also succeeds with just pin and no initialpos:

julia> NetworkLayout.spring(g; pin, initialtemp = 3.940695496278636, iterations = 5)
7181-element Vector{Point{2, Float64}}:
 [44.64559589000704, -93.22830854233274]
 [44.97752660055047, -93.29094193353777]
 [46.76745340178624, -97.55661876619855]
...
kenahoo commented 1 week ago

I also just checked with julia --startup-file=no in case that was doing something, but no difference.