Opened 3 years ago

Closed 3 years ago

# RecursivelyEnumeratedSet: certified enumeration order

Reported by: Owned by: gh-mwageringel major sage-9.0 combinatorics slabbe, vklein, jhpalmieri, tscrim Markus Wageringel Travis Scrimshaw, Sébastien Labbé N/A a7ae8bf a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b

### Description

This ticket is a follow-up to #27967. It makes the following changes related to enumeration orders of `RecursivelyEnumeratedSet`:

• implements (and documents) a certified enumeration order for breadth-first search of recursively enumerated sets (left-to-right traversal). The graded case has already been implemented in #27967. In particular, this gives consistent results between Python 2 and 3, also for the generic and symmetric case.

(The depth-first search already returns consistent results – this ticket adds this fact to its documentation as well.)

• further optimizes the implementation of breadth-first search as suggested in 27967#comment:15. With this, elements are generally returned much earlier during the search: by an entire generation earlier. In other words, it is possible to explore one level further before potentially running out of memory.
• implements a custom breadth-first search iterator for `RecursivelyEnumeratedSet_symmetric` (this is necessary because the previous implementation was based on `graded_component()` which returns unordered sets). As a result, `_breadth_first_search_iterator_from_graded_component_iterator()` is not used anymore and therefore removed.
• fixes an off-by-one error in the `max_depth` of the breadth-first iterator for RES of `symmetric` structure:
```sage: f = lambda a: [a-1, a+1]
sage: C = RecursivelyEnumeratedSet([0], f)
sage: D = RecursivelyEnumeratedSet([0], f, structure='symmetric')
[-2, -1, 0, 1, 2]
sage: sorted(D.breadth_first_search_iterator(max_depth=2))  # should be the same
[-1, 0, 1]
```

### comment:1 Changed 3 years ago by gh-mwageringel

After these changes, only the `naive` enumeration order will give unordered results, as is clearly stated in its documentation, as well as the function `graded_component()` (and consequently `graded_component_iterator()` as well as `elements_of_depth_iterator()`), as `graded_component()` returns an unordered `set` of elements rather than an iterator of its elements.

Moreover, this ticket should allow to revert the workaround implemented in #28227 and might also help with #28539/#28653.

Version 1, edited 3 years ago by gh-mwageringel (previous) (next) (diff)

### comment:2 Changed 3 years ago by gh-mwageringel

• Authors set to Markus Wageringel
• Branch set to u/gh-mwageringel/res_bfs_order_28674
• Commit set to a7a9d6665141a0cbbdae34877479786279e6d003

New commits:

 ​a7a9d66 `28674: certified BFS enumeration for RecursivelyEnumeratedSet`

### comment:3 Changed 3 years ago by gh-mwageringel

Several doctests outside of `sets/recursively_enumerated_set.py` seem to rely on a coincidental non-certified BFS order and have to be updated as a result of these changes. With the current branch and Python 3, I get these failures:

```src/sage/algebras/quantum_groups/representations.py  # 3 doctests failed
src/sage/categories/crystals.py  # 6 doctests failed
src/sage/categories/regular_crystals.py  # 2 doctests failed
src/sage/combinat/crystals/subcrystal.py  # 1 doctest failed
src/sage/combinat/root_system/integrable_representations.py  # 4 doctests failed
src/sage/groups/perm_gps/permgroup.py  # 1 doctest failed
```

### comment:4 Changed 3 years ago by git

• Commit changed from a7a9d6665141a0cbbdae34877479786279e6d003 to 95ed2c047cfb494a692edaa47773620248671251

Branch pushed to git repo; I updated commit sha1. New commits:

 ​95ed2c0 `28674: update doctests for new RES enumeration order`

### comment:5 Changed 3 years ago by gh-mwageringel

• Status changed from new to needs_review

I have updated all the failing doctests, most of them related to subcrystals.

Now ptestlong passes on my end, with both python 2 and 3. This is ready for review if the patchbot is happy.

### comment:6 Changed 3 years ago by gh-mwageringel

• Cc slabbe vklein jhpalmieri tscrim added

### comment:7 Changed 3 years ago by tscrim

LGTM but IMO a documentation fix should be done first:

```-        - ``max_depth`` -- (Default: ``None``) Specifies the maximal depth
-          to which elements are computed. If None, the value of
-          ``self._max_depth`` is used.
+        - ``max_depth`` -- (default: ``self._max_depth``) specifies the
+          maximal depth to which elements are computed
```

(I know it is not like this elsewhere, but I don't think that is a good reason to perpetuate the practice of breaking from the recommended formatting style.)

### comment:8 Changed 3 years ago by git

• Commit changed from 95ed2c047cfb494a692edaa47773620248671251 to a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b

Branch pushed to git repo; I updated commit sha1. New commits:

 ​a7ae8bf `28674: adjust documentation formatting`

### comment:9 Changed 3 years ago by gh-mwageringel

Indeed. Thank you for the feedback. I have updated the documentation accordingly.

### comment:10 Changed 3 years ago by tscrim

• Reviewers set to Travis Scrimshaw
• Status changed from needs_review to positive_review

LGTM.

### comment:11 Changed 3 years ago by slabbe

I just reviewed the code. Doctests work on my side. Thanks for working on that.

### comment:12 Changed 3 years ago by gh-mwageringel

• Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Sébastien Labbé

Thanks for the reviews.

### comment:13 Changed 3 years ago by vbraun

• Branch changed from u/gh-mwageringel/res_bfs_order_28674 to a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.