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:  sage9.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: 
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:2 Changed 3 years ago by
Authors:  → Markus Wageringel 

Branch:  → u/ghmwageringel/res_bfs_order_28674 
Commit:  → 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:  a7a9d6665141a0cbbdae34877479786279e6d003 → 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:  new → 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:  Sébastien Labbé vklein John Palmieri Travis Scrimshaw 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:  95ed2c047cfb494a692edaa47773620248671251 → 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:  → Travis Scrimshaw 

Status:  needs_review → 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:  Travis Scrimshaw → Travis Scrimshaw, Sébastien Labbé 

Thanks for the reviews.
comment:13 Changed 3 years ago by
Branch:  u/ghmwageringel/res_bfs_order_28674 → a7ae8bf948b326c8fd11aa5c4dfe1db7fa50f26b 

Resolution:  → fixed 
Status:  positive_review → 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.