8000 avoid some conversions to `short_digraph` when the input is an instance of `StaticSparseBackend` by dcoudert · Pull Request #39216 · sagemath/sage · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

avoid some conversions to short_digraph when the input is an instance of StaticSparseBackend #39216

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 15 commits into from
Feb 28, 2025
Merged

avoid some conversions to short_digraph when the input is an instance of StaticSparseBackend #39216

merged 15 commits into from
Feb 28, 2025

Conversation

dcoudert
Copy link
Contributor

Many methods convert the input graph to a short_digraph for faster operations. When the input is an instance of StaticSparseBackend, we can directly get the short_digraph and so avoid the extra cost of the conversion.
On the way, we fix some memory leaks as some instances of short_digraph were not freed.

In a follow-up PR, we will do more in distances_all_pairs.pyx, hyperbolicity.pyx and traversals.pyx.

📝 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 Dec 28, 2024
@github-actions GitHub Actions
Copy link
github-actions bot commented Dec 28, 2024 •
edited
Loading

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

This was referenced Dec 28, 2024
Merged
Merged
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 1, 2025
372c070 
sagemathgh-39217: improve graph traversal methods
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` when the
input graph is an instance of `StaticSparseBackend`.

Furthermore, we use the new `PairingHeap_of_n_integers` data structure
(sagemath#39046) instead of a `priority_queue` to emulate a max-heap. This is
slightly faster this way and cleaner.


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39217
Reported by: David Coudert
Reviewer(s): Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 3, 2025
6c348ba 
sagemathgh-39217: improve graph traversal methods
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` when the
input graph is an instance of `StaticSparseBackend`.

Furthermore, we use the new `PairingHeap_of_n_integers` data structure
(sagemath#39046) instead of a `priority_queue` to emulate a max-heap. This is
slightly faster this way and cleaner.


### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39217
Reported by: David Coudert
Reviewer(s): Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 20, 2025
d66587a 
sagemathgh-39223: avoid some conversions to `short_digraph` in `distances_all_pairs.pyx`
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` in
`distances_all_pairs.pyx` when the input graph is an instance of
`StaticSparseBackend`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39223
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 23, 2025
a584c91 
sagemathgh-39223: avoid some conversions to `short_digraph` in `distances_all_pairs.pyx`
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` in
`distances_all_pairs.pyx` when the input graph is an instance of
`StaticSparseBackend`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39223
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 25, 2025
a4b8e6d 
sagemathgh-39223: avoid some conversions to `short_digraph` in `distances_all_pairs.pyx`
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` in
`distances_all_pairs.pyx` when the input graph is an instance of
`StaticSparseBackend`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39223
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
vbraun pushed a commit to vbraun/sage that referenced this pull request Jan 26, 2025
999faf4 
sagemathgh-39223: avoid some conversions to `short_digraph` in `distances_all_pairs.pyx`
    
Similarly to sagemath#39216, we avoid the conversion to `short_digraph` in
`distances_all_pairs.pyx` when the input graph is an instance of
`StaticSparseBackend`.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

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

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#39223
Reported by: David Coudert
Reviewer(s): Frédéric Chapoton
@dcoudert dcoudert requested a review from fchapoton February 22, 2025 15:41
fchapoton
fchapoton reviewed Feb 23, 2025
View reviewed changes
fchapoton
fchapoton reviewed Feb 23, 2025
View reviewed changes
fchapoton
fchapoton reviewed Feb 23, 2025
View reviewed changes
fchapoton
fchapoton approved these changes Feb 25, 2025
View reviewed changes
Copy link
Contributor
@fchapoton fchapoton left a comment

Choose a reason for hiding this comment

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

ok, avanti

@dcoudert
Copy link
Contributor Author

Merci.

@vbraun vbraun merged commit a35838b into sagemath:develop Feb 28, 2025
24 of 25 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@fchapoton fchapoton fchapoton approved these changes

Assignees

@dcoudert dcoudert

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

Successfully merging this pull request may close these issues.
3 participants
@dcoudert @fchapoton @vbraun
0