Skip to content

improve graph backends to fix bug in lex_BFS #39935

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.

Sign up for GitHub

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

Jump to bottom
Merged
merged 4 commits into from
Apr 29, 2025
Merged

improve graph backends to fix bug in lex_BFS #39935

merged 4 commits into from
Apr 29, 2025
+92 −15

Conversation

dcoudert
Copy link
Contributor

Fixes #39934.

We ensure that the sparse/dense/static_sparse graph backends have the methods needed in lex_BFS and slice_decomposition.

📝 Checklist

  • The title is concise and informative.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation and checked the documentation preview.

⌛ Dependencies

@dcoudert dcoudert self-assigned this Apr 12, 2025
@github-actions GitHub Actions
Copy link

github-actions bot commented Apr 13, 2025 •
edited
Loading

Documentation preview for this PR (built with commit 8253903; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@dcoudert
Copy link
Contributor Author

@cyrilbouvier, can you check this PR. A segmentation fault occurs with immutable graphs but I don't understand what's going on. As you can see, the behavior is somewhat random but will eventually crash.
Help is more than welcome.

sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
---------------------------------------------------------------------------
SignalError                               Traceback (most recent call last)
Cell In[2], line 1
----> 1 G.lex_BFS(algorithm="fast")

File ~/sage/src/sage/graphs/traversals.pyx:500, in sage.graphs.traversals.lex_BFS()
    498 else:
    499     initial_v_int = -1
--> 500 sig_on()
    501 extended_lex_BFS(cg, sigma_int, NULL, initial_v_int, &pred, NULL, NULL)
    502 sig_off()

SignalError: Segmentation fault
sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
[None, 0, 0, 0, 4]
sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
[0, 1, 2, 3, 4]

@dcoudert
Copy link
Contributor Author

Got it ! The number of arcs in StaticSparseCGraph was not properly initialized.

@cyrilbouvier
Copy link
Contributor

@cyrilbouvier, can you check this PR. A segmentation fault occurs with immutable graphs but I don't understand what's going on. As you can see, the behavior is somewhat random but will eventually crash. Help is more than welcome.

sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
---------------------------------------------------------------------------
SignalError                               Traceback (most recent call last)
Cell In[2], line 1
----> 1 G.lex_BFS(algorithm="fast")

File ~/sage/src/sage/graphs/traversals.pyx:500, in sage.graphs.traversals.lex_BFS()
    498 else:
    499     initial_v_int = -1
--> 500 sig_on()
    501 extended_lex_BFS(cg, sigma_int, NULL, initial_v_int, &pred, NULL, NULL)
    502 sig_off()

SignalError: Segmentation fault
sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
[None, 0, 0, 0, 4]
sage: G = Graph(graphs.HouseGraph(), immutable=True)
sage: G.lex_BFS(algorithm="fast")
[0, 1, 2, 3, 4]

Sorry for not replying earlier, I was on holidays.
Thanks for fixing the issue, I will try to review the PR this week.

cyrilbouvier
cyrilbouvier approved these changes Apr 22, 2025
View reviewed changes
Copy link
Contributor

@cyrilbouvier cyrilbouvier left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM.
The failing CI does not seem related to this PR (error is no space left on device., looks more like an error with the CI or runner)

src/sage/graphs/graph_decompositions/slice_decomposition.pyx
Comment on lines +435 to +438
sig_on()
extended_lex_BFS(cg, sigma, NULL, initial_v_int, NULL,
&(self.xslice_len), &lex_label)
sig_off()
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

More a naive question than a remark: why sig_on/sig_off are needed here ?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't think it's mandatory, but in case of failure it helps locating the issue in this call.

@dcoudert
Copy link
Contributor Author

Thanks for the review. I set this PR to positive review on your behalf.

@vbraun vbraun merged commit 82553b1 into sagemath:develop Apr 29, 2025
22 of 23 checks passed
@darijgr darijgr mentioned this pull request Jul 27, 2025
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
1 more reviewer

@cyrilbouvier cyrilbouvier cyrilbouvier approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees

@dcoudert dcoudert

Labels
c: graph theory t: bug
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

lex_BFS fails with immutable graphs
3 participants
@dcoudert @cyrilbouvier @vbraun