-
-
Notifications
You must be signed in to change notification settings - Fork 657
Improve DiGraph neighbor iterators #38189
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
Improve DiGraph neighbor iterators #38189
Conversation
…r_[in|out]_iterator
Previous commit changed the order of the output of neighbor_[in|out]_iterator which changed the order of the output of 4 tests
Documentation preview for this PR (built with commit 802a79b; changes) is ready! 🎉 |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Looks good to me.
Was the previous version deterministic at all? I thought set
has random order
I think |
I think the |
I added tests to check that in the case of multiple edges, the neighbors are listed only once. I also added tests to check that the closed neighborhood is listed in the presence of loop(s). |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I did some tests with the current PR and this looks good to me. Thanks.
sagemathgh-38189: Improve DiGraph neighbor iterators <!-- ^ Please provide a concise and informative title. --> <!-- ^ Don't put issue numbers in the title, do this in the PR description below. --> <!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method to calculate 1 + 2". --> <!-- v Describe your changes below in detail. --> <!-- v Why is this change required? What problem does it solve? --> <!-- v If this PR resolves an open issue, please link to it here. For example, "Fixes sagemath#12345". --> Currently, in the Digraph class, the two methods `neighbor_out_iterator` and `neighbor_in_iterator` are just wrappers around low-level methods `_backend.iterator_out_nbrs` and `_backend.iterator_in_nbrs`. To build the iterator, the low-level iterator is first converted into a set and then converted back into an iterator using `iter()`. It does not seem efficient. This PR proposes to use `yield from` instead (see the very short commit 9a89251) As this modification changes the order of the output, the output of 4 tests need to be reorder (see commit 305b933). One can check that the lists contains the same elements, but not in the same order. ### 📝 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. - [ ] 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 <!-- 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#38189 Reported by: cyrilbouvier Reviewer(s): David Coudert, grhkm21
sagemathgh-38189: Improve DiGraph neighbor iterators <!-- ^ Please provide a concise and informative title. --> <!-- ^ Don't put issue numbers in the title, do this in the PR description below. --> <!-- ^ For example, instead of "Fixes sagemath#12345" use "Introduce new method to calculate 1 + 2". --> <!-- v Describe your changes below in detail. --> <!-- v Why is this change required? What problem does it solve? --> <!-- v If this PR resolves an open issue, please link to it here. For example, "Fixes sagemath#12345". --> Currently, in the Digraph class, the two methods `neighbor_out_iterator` and `neighbor_in_iterator` are just wrappers around low-level methods `_backend.iterator_out_nbrs` and `_backend.iterator_in_nbrs`. To build the iterator, the low-level iterator is first converted into a set and then converted back into an iterator using `iter()`. It does not seem efficient. This PR proposes to use `yield from` instead (see the very short commit 9a89251) As this modification changes the order of the output, the output of 4 tests need to be reorder (see commit 305b933). One can check that the lists contains the same elements, but not in the same order. ### 📝 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. - [ ] 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 <!-- 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#38189 Reported by: cyrilbouvier Reviewer(s): David Coudert, grhkm21
Currently, in the Digraph class, the two methods
neighbor_out_iterator
andneighbor_in_iterator
are just wrappers around low-level methods_backend.iterator_out_nbrs
and_backend.iterator_in_nbrs
. To build the iterator, the low-level iterator is first converted into a set and then converted back into an iterator usingiter()
. It does not seem efficient.This PR proposes to use
yield from
instead (see the very short commit 9a89251)As this modification changes the order of the output, the output of 4 tests need to be reorder (see commit 305b933). One can check that the lists contains the same elements, but not in the same order.
📝 Checklist
⌛ Dependencies