Opened 3 years ago

Closed 3 years ago

#28674 closed enhancement (fixed)

RecursivelyEnumeratedSet: certified enumeration order

Reported by: Markus Wageringel Owned by:
Priority: major Milestone: sage-9.0
Component: combinatorics Keywords:
Cc: Sébastien Labbé, vklein, John Palmieri, Travis Scrimshaw 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


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 3 years ago by Markus Wageringel

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 3 years ago by Markus Wageringel (previous) (diff)

comment:2 Changed 3 years ago by Markus Wageringel

Authors: Markus Wageringel
Branch: u/gh-mwageringel/res_bfs_order_28674
Commit: a7a9d6665141a0cbbdae34877479786279e6d003

New commits:

a7a9d6628674: certified BFS enumeration for RecursivelyEnumeratedSet

comment:3 Changed 3 years ago by Markus Wageringel

Several doctests outside of sets/ 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/  # 3 doctests failed
src/sage/categories/  # 6 doctests failed
src/sage/categories/  # 2 doctests failed
src/sage/combinat/crystals/  # 1 doctest failed
src/sage/combinat/root_system/  # 4 doctests failed
src/sage/groups/perm_gps/  # 1 doctest failed

comment:4 Changed 3 years ago by git

Commit: a7a9d6665141a0cbbdae34877479786279e6d00395ed2c047cfb494a692edaa47773620248671251

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

95ed2c028674: update doctests for new RES enumeration order

comment:5 Changed 3 years ago by Markus Wageringel

Status: newneeds_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 Markus Wageringel

Cc: Sébastien Labbé vklein John Palmieri Travis Scrimshaw added

comment:7 Changed 3 years ago by Travis Scrimshaw

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: 95ed2c047cfb494a692edaa47773620248671251a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b

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

a7ae8bf28674: adjust documentation formatting

comment:9 Changed 3 years ago by Markus Wageringel

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

comment:10 Changed 3 years ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review


comment:11 Changed 3 years ago by Sébastien Labbé

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

comment:12 Changed 3 years ago by Markus Wageringel

Reviewers: Travis ScrimshawTravis Scrimshaw, Sébastien Labbé

Thanks for the reviews.

comment:13 Changed 3 years ago by Volker Braun

Branch: u/gh-mwageringel/res_bfs_order_28674a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.