Opened 3 years ago
Closed 3 years ago
#28674 closed enhancement (fixed)
RecursivelyEnumeratedSet: certified enumeration order
Reported by:  ghmwageringel  Owned by:  

Priority:  major  Milestone:  sage9.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: 
Description
This ticket is a followup to #27967. It makes the following changes related to enumeration orders of RecursivelyEnumeratedSet
:
 implements (and documents) a certified enumeration order for breadthfirst search of recursively enumerated sets (lefttoright 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 depthfirst search already returns consistent results – this ticket adds this fact to its documentation as well.)
 further optimizes the implementation of breadthfirst 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 breadthfirst search iterator for
RecursivelyEnumeratedSet_symmetric
(this is necessary because the previous implementation was based ongraded_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 offbyone error in the
max_depth
of the breadthfirst iterator for RES ofsymmetric
structure:
sage: f = lambda a: [a1, 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
comment:2 Changed 3 years ago by
 Branch set to u/ghmwageringel/res_bfs_order_28674
 Commit set to a7a9d6665141a0cbbdae34877479786279e6d003
New commits:
a7a9d66  28674: certified BFS enumeration for RecursivelyEnumeratedSet

comment:3 Changed 3 years ago by
Several doctests outside of sets/recursively_enumerated_set.py
seem to rely on a coincidental noncertified 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
 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
 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
 Cc slabbe vklein jhpalmieri tscrim added
comment:7 Changed 3 years ago by
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
 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
Indeed. Thank you for the feedback. I have updated the documentation accordingly.
comment:10 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM.
comment:11 Changed 3 years ago by
I just reviewed the code. Doctests work on my side. Thanks for working on that.
comment:12 Changed 3 years ago by
 Reviewers changed from Travis Scrimshaw to Travis Scrimshaw, Sébastien Labbé
Thanks for the reviews.
comment:13 Changed 3 years ago by
 Branch changed from u/ghmwageringel/res_bfs_order_28674 to a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b
 Resolution set to fixed
 Status changed from positive_review to closed
After these changes, only the
naive
enumeration order will give unordered results, as is clearly stated in its documentation, as well as the functiongraded_component()
(and consequentlygraded_component_iterator()
as well aselements_of_depth_iterator()
), asgraded_component()
returns an unorderedset
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.