Skip to content
This repository has been archived by the owner on Oct 8, 2021. It is now read-only.

[BUG] adjacency_matrix fails for SimpleGraph with self-loops (Julia 1.7) #1594

Open
mtfishman opened this issue Sep 17, 2021 · 4 comments · May be fixed by #1595
Open

[BUG] adjacency_matrix fails for SimpleGraph with self-loops (Julia 1.7) #1594

mtfishman opened this issue Sep 17, 2021 · 4 comments · May be fixed by #1595
Labels
bug confirmed bug producing incorrect results

Comments

@mtfishman
Copy link

mtfishman commented Sep 17, 2021 •
edited
Loading

Description of bug
adjacency_matrix fails for SimpleGraph with self-loops in Julia 1.7.

How to reproduce

julia> versioninfo()
Julia Version 1.7.0-rc1
Commit 9eade6195e (2021-09-12 06:45 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Xeon(R) E-2176M  CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-12.0.1 (ORCJIT, skylake)
Environment:
  JULIA_EDITOR = vim

(@v1.7) pkg> st LightGraphs
      Status `~/.julia/environments/v1.7/Project.toml`
  [093fc24a] LightGraphs v1.3.5

julia> using LightGraphs

julia> g = Graph(Edge.([1 => 2, 2 => 3]))
{3, 2} undirected simple Int64 graph

julia> adjacency_matrix(g)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 4 stored entries:
 ⋅  1  ⋅
 1  ⋅  1
 ⋅  1  ⋅

julia> add_edge!(g, 1 => 1)
true

julia> adjacency_matrix(g)
ERROR: ArgumentError: Illegal buffers for SparseMatrixCSC construction 3 [1, 3, 5, 6] [1, 2, 1, 3, 2] [1, 1, 1, 1, 1, 1]
Stacktrace:
 [1] SparseMatrixCSC
   @ /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.7/SparseArrays/src/sparsematrix.jl:29 [inlined]
 [2] SparseArrays.SparseMatrixCSC(m::Int64, n::Int64, colptr::Vector{Int64}, rowval::Vector{Int64}, nzval::Vector{Int64})
   @ SparseArrays /buildworker/worker/package_linux64/build/usr/share/julia/stdlib/v1.7/SparseArrays/src/sparsematrix.jl:44
 [3] _adjacency_matrix(g::SimpleGraph{Int64}, T::DataType, neighborfn::typeof(inneighbors), nzmult::Int64)
   @ LightGraphs.LinAlg ~/.julia/packages/LightGraphs/IgJif/src/linalg/spectral.jl:63
 [4] #adjacency_matrix#2
   @ ~/.julia/packages/LightGraphs/IgJif/src/linalg/spectral.jl:25 [inlined]
 [5] adjacency_matrix (repeats 2 times)
   @ ~/.julia/packages/LightGraphs/IgJif/src/linalg/spectral.jl:20 [inlined]
 [6] top-level scope
   @ REPL[35]:1

It seems to work fine for directed graphs:

julia> g = DiGraph(Edge.([1 => 2, 2 => 3]))
{3, 2} directed simple Int64 graph

julia> adjacency_matrix(g)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 2 stored entries:
 ⋅  1  ⋅
 ⋅  ⋅  1
 ⋅  ⋅  ⋅

julia> add_edge!(g, 1 => 1)
true

julia> adjacency_matrix(g)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 3 stored entries:
 1  1  ⋅
 ⋅  ⋅  1
 ⋅  ⋅  ⋅
@mtfishman mtfishman added the bug confirmed bug producing incorrect results label Sep 17, 2021
@mtfishman
Copy link
Author

Related to JuliaGraphs/NetworkLayout.jl#41.

@mtfishman
Copy link
Author

Also works fine with Julia 1.6:

julia> versioninfo()
Julia Version 1.6.2
Commit 1b93d53fc4 (2021-07-14 15:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Xeon(R) E-2176M  CPU @ 2.70GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-11.0.1 (ORCJIT, skylake)
Environment:
  JULIA_EDITOR = vim

(@v1.6) pkg> st LightGraphs
      Status `~/.julia/environments/v1.6/Project.toml`
  [093fc24a] LightGraphs v1.3.5

julia> using LightGraphs

julia> g = Graph(Edge.([1 => 2, 2 => 3]))
{3, 2} undirected simple Int64 graph

julia> adjacency_matrix(g)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 4 stored entries:
 ⋅  1  ⋅
 1  ⋅  1
 ⋅  1  ⋅

julia> add_edge!(g, 1 => 1)
true

julia> adjacency_matrix(g)
3×3 SparseArrays.SparseMatrixCSC{Int64, Int64} with 5 stored entries:
 2  1  ⋅
 1  ⋅  1
 ⋅  1  ⋅

so maybe an issue with SparseArrays?

@mtfishman
Copy link
Author

It looks like the error in Julia 1.7 is caused by stricter checks in the SparseMatrixCSC constructor introduced in this PR: JuliaLang/julia#40523

However, my guess is that it is more an issue on the LightGraphs side on how it is using the constructor here: https://github.com/JuliaGraphs/LightGraphs.jl/blob/b210395e8cbd109dc04c286f8af0c267cad47a85/src/linalg/spectral.jl#L53-L72 in the case of self-loops when the graph is undirected.

@mtfishman mtfishman mentioned this issue Sep 17, 2021
Closed
@mtfishman
Copy link
Author

mtfishman commented Sep 17, 2021 •
edited
Loading

Adding a line like:

            if !(T <: Bool) && !is_directed(g)
                nz -= 1
            end

after line 57 seems to help. I think the issue is that the original definition of nz is double counting the self-loops as nonzero values in the sparse matrix, which is being caught in the updated SparseMatrixCSC constructor.

@mtfishman mtfishman linked a pull request Sep 17, 2021 that will close this issue
Open
@mtfishman mtfishman changed the title [BUG] adjacency_matrix fails for SimpleGraph with self-loops [BUG] adjacency_matrix fails for SimpleGraph with self-loops (Julia 1.7) Sep 17, 2021
@mtfishman mtfishman mentioned this issue Oct 20, 2021
Merged
@gdalle gdalle mentioned this issue Nov 11, 2021
Closed
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
bug confirmed bug producing incorrect results
Projects
None yet
Milestone
No milestone
1 participant
@mtfishman