#28674 closed enhancement (fixed)

RecursivelyEnumeratedSet: certified enumeration order

Reported by: gh-mwageringel Owned by:
Priority: major Milestone: sage-9.0
Component: combinatorics Keywords:
Cc: slabbe, vklein, jhpalmieri, tscrim Merged in:
Authors: Markus Wageringel Reviewers: Travis Scrimshaw, Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: a7ae8bf (Commits, GitHub, GitLab) Commit: a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b
Dependencies: Stopgaps:

Status badges

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')
sage: sorted(C.breadth_first_search_iterator(max_depth=2))
[-2, -1, 0, 1, 2]
sage: sorted(D.breadth_first_search_iterator(max_depth=2))  # should be the same
[-1, 0, 1]

Change History (13)

comment:1 Changed 21 months 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.

Last edited 21 months ago by gh-mwageringel (previous) (diff)

comment:2 Changed 21 months 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:

a7a9d6628674: certified BFS enumeration for RecursivelyEnumeratedSet

comment:3 Changed 21 months 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 21 months ago by git

  • Commit changed from a7a9d6665141a0cbbdae34877479786279e6d003 to 95ed2c047cfb494a692edaa47773620248671251

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

95ed2c028674: update doctests for new RES enumeration order

comment:5 Changed 21 months 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 21 months ago by gh-mwageringel

  • Cc slabbe vklein jhpalmieri tscrim added

comment:7 Changed 21 months 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 21 months ago by git

  • Commit changed from 95ed2c047cfb494a692edaa47773620248671251 to a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b

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

a7ae8bf28674: adjust documentation formatting

comment:9 Changed 21 months ago by gh-mwageringel

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

comment:10 Changed 21 months ago by tscrim

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

LGTM.

comment:11 Changed 21 months ago by slabbe

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

comment:12 Changed 21 months ago by gh-mwageringel

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

Thanks for the reviews.

comment:13 Changed 21 months 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.