Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[BUG] isgraphical returns true for a non-graphical sequence #400

Open
dave-ck opened this issue Sep 23, 2024 · 6 comments
Open

[BUG] isgraphical returns true for a non-graphical sequence #400

dave-ck opened this issue Sep 23, 2024 · 6 comments
Labels
bug Something isn't working good first issue Good for newcomers help wanted Extra attention is needed

Comments

@dave-ck
Copy link

dave-ck commented Sep 23, 2024

Description of bug, expected and actual behavior
isgraphical returns true for a non-graphical sequence, namely [4,2,2,2,0]. It should return false on this input.

How to reproduce
Call the function isgraphical on input [4,2,2,2,0].

Code demonstrating bug

using Graphs

println(isgraphical([4,2,2,2])) # should print false, prints false
println(isgraphical([4,2,2,2,0])) # should print false, prints true
println(isgraphical([4,2,2,2,0]) == isgraphical([4,2,2,2])) # should definitely print true, prints false

Version information

Julia Version 1.10.4
Commit 48d4fd4843 (2024-06-04 10:41 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Windows (x86_64-w64-mingw32)
  CPU: 16 × AMD Ryzen 7 5800H with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, znver3)
Threads: 1 default, 0 interactive, 1 GC (on 16 virtual cores)   
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS =

Output of ]status Graphs is [86223c79] Graphs v1.9.0.

Additional context
I at first thought the implementation allowed self-loops, in which case the sequence can be realized by (for example) the graph on vertices a,b,c,d,e with edges a-a, a-b, b-c, a-c, a-d, d-d.
However, [4,2,2,2] returns false (as it should if we disallow self-loops).
The implementation should be consistent (optionally with a flag to allow or disallow self-loops, if this is a needed feature).

If the bug is limited to cases where there is a vertex of degree zero, an easy fix would be to add the line

degs = [deg for deg in degs if deg > 0]

at the beginning of the function (e.g. after checking the sum of degrees is even, and before the sequence length is computed).

@dave-ck dave-ck added the bug Something isn't working label Sep 23, 2024
@dave-ck
Copy link
Author

dave-ck commented Sep 23, 2024

Quick note: isdigraphical([4,2,2,2,0],[4,2,2,2,0]) correctly returns false. In general, (if the digraphical function is correctly implemented - I only checked that sequence), a fix can be to simply assign: isgraphical(seq) = isdigraphical(seq, seq).

@gdalle gdalle changed the title [BUG] [BUG] isgraphical returns true for a non-graphical sequence Sep 23, 2024
@gdalle
Copy link
Member

gdalle commented Sep 25, 2024

Thanks for reporting this, and sorry for the lack of reactivity in this part of the ecosystem!

I'm not familiar with this function, but from what I read on the Wikipedia page of the Erdos-Gallai theorem (referenced in the docstring), that theorem only applies to simple graphs. This means self-loops should be disallowed. On the other hand, degrees equal to zero appear to be supported.

Can you spot something wrong in the implementation? If so, a fix would be welcome and easy to review I think:

function isgraphical(degs::AbstractVector{<:Integer})
# Check whether the degree sequence is empty
!isempty(degs) || return true
# Check whether the sum of degrees is even
iseven(sum(degs)) || return false
# Check that all degrees are non negative and less than n-1
n = length(degs)
all(0 .<= degs .<= n - 1) || return false
# Sort the degree sequence in non-increasing order
sorted_degs = sort(degs; rev=true)
# Compute the length of the degree sequence
cur_sum = zero(UInt64)
# Compute the minimum of each degree and the corresponding index
mindeg = Vector{UInt64}(undef, n)
@inbounds for i in 1:n
mindeg[i] = min(i, sorted_degs[i])
end
# Check if the degree sequence satisfies the Erdös-Gallai condition
cum_min = sum(mindeg)
@inbounds for r in 1:(n - 1)
cur_sum += sorted_degs[r]
cum_min -= mindeg[r]
cond = cur_sum <= (r * (r - 1) + cum_min)
cond || return false
end
return true
end

@simonschoelly
Copy link
Member

It would be very nice if we had a flag to allow or disallows self-loops. A while ago I tried to come up with a variant of the Erdős–Gallai for self-loops but I did not succeed so far. And I also could not find anything in the literature.

Until we do so we should explicitly state in the documentation that this does not work for self-loops.

@simonschoelly
Copy link
Member

This paper might have some solution. One difference there is that for Graphs.jl we only add 1 to the degree of a vertex if it has a self-loop. But that paper (and I think in general the literature might do that) adds 2 to the degree.

@simonschoelly
Copy link
Member

So for a quick solution we should state in the documentation that self-loops and multiple edges are not allowed.

@simonschoelly simonschoelly added good first issue Good for newcomers help wanted Extra attention is needed labels Nov 20, 2024
@simonschoelly
Copy link
Member

See also #303

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working good first issue Good for newcomers help wanted Extra attention is needed
Projects
None yet
Development

No branches or pull requests

3 participants