Skip to content

Conversation

cyrilbouvier
Copy link
Contributor

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

  • 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

Previous commit changed the order of the output of
neighbor_[in|out]_iterator which changed the order of the output of 4
tests
Copy link

github-actions bot commented Jun 10, 2024

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

Copy link
Contributor

@grhkm21 grhkm21 left a 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

@cyrilbouvier
Copy link
Contributor Author

Was the previous version deterministic at all? I thought set has random order

I think set is deterministic (like dict): if you do list(set([<input list>])), you always get the same order, just not the same as the input list.

@dcoudert
Copy link
Contributor

I think the set(...) was here to prevent reporting twice a same vertex, and this has been implemented long before Cython supports yield statements. It seems that the proposed change works well. However, could you double check that it's ok with all backends, and with digraphs with loops / multiple edges.

@cyrilbouvier
Copy link
Contributor Author

I think the set(...) was here to prevent reporting twice a same vertex, and this has been implemented long before Cython supports yield statements. It seems that the proposed change works well. However, could you double check that it's ok with all backends, and with digraphs with loops / multiple edges.

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).

Copy link
Contributor

@dcoudert dcoudert left a 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.

vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 16, 2024
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
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 16, 2024
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
@vbraun vbraun merged commit ca110c5 into sagemath:develop Jun 22, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

5 participants