Fix error in implementation of Erdos-Gallai condition in isgraphical #415
Conversation
Fixes JuliaGraphs#400 Fix `isgraphical` function to correctly handle non-graphical sequences. # Error in current implementation `mindeg` is computed globally at the start using `min(i, sorted_degs[i])` for all indices. However, the Erdös-Gallai condition requires dynamically calculating `min(r, sorted_degs[i])` for vertices after the current index `r`. # What changed * Update the Erdös-Gallai condition check to calculate the sum of the minimum of r and the degrees of the vertices. * Add a test case in `test/connectivity.jl` to verify that `isgraphical` returns false for the sequence [4,2,2,2,0]. --- For more details, open the [Copilot Workspace session](https://copilot-workspace.githubnext.com/JuliaGraphs/Graphs.jl/issues/400?shareId=XXXX-XXXX-XXXX-XXXX).
Codecov ReportAll modified and coverable lines are covered by tests ✅
Additional details and impacted files@@ Coverage Diff @@
## master #415 +/- ##
==========================================
- Coverage 97.30% 97.30% -0.01%
==========================================
Files 117 117
Lines 6948 6943 -5
==========================================
- Hits 6761 6756 -5
Misses 187 187 ☔ View full report in Codecov by Sentry. |
|
Thank you. I think this is the second bug in this algorithm in a short while. I think we might have mixed up the indices for the summation on the right hand side of the formula. |
| cum_min -= mindeg[r] | ||
| cond = cur_sum <= (r * (r - 1) + cum_min) | ||
| # Calculate the sum of the minimum of r and the degrees of the vertices | ||
| mid_deg_sum = sum([min(r, sorted_degs[i]) for i in (r + 1):n]) |
There was a problem hiding this comment.
Doing it this way makes the algorithm run in O(n^2) time. I think we might be able to avoid this by using the fact that we only need to consider in each iteration those degrees that are smaller than r. And for the other m degrees we can just add m * r to the sum. Using the factor that the degrees are sorted we can slide from the right hand side.
And we should be able to avoid a vector for each iteration.
Do you feel up for it? Otherwise I will give it a try.
There was a problem hiding this comment.
Thanks for the comment, then we need a pointer to track the index. I will make a revision over the weekend, along with some benchmark results.
Fixes #400
Fix
isgraphicalfunction to correctly handle non-graphical sequences.Error in current implementation
mindegis computed globally at the start usingmin(i, sorted_degs[i])for all indices. However, the Erdös-Gallai condition requires dynamically calculatingmin(r, sorted_degs[i])for vertices after the current indexr.What changed
Update the Erdös-Gallai condition check to calculate the sum of the minimum of r and the degrees of the vertices.
Add a test case in
test/connectivity.jlto verify thatisgraphicalreturns false for the sequence [4,2,2,2,0].For more details, open the Copilot Workspace session.