#27967 closed enhancement (fixed)
Py3: Fix RecursivelyEnumeratedSet BFS for python3.
Reported by:  vklein  Owned by:  

Priority:  major  Milestone:  sage8.9 
Component:  python3  Keywords:  
Cc:  slabbe, chapoton, tscrim, nthiery  Merged in:  
Authors:  Vincent Klein, John Palmieri, Sébastien Labbé  Reviewers:  Vincent Klein, Markus Wageringel 
Report Upstream:  N/A  Work issues:  
Branch:  f2c51a8 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps:  #28351 
Description
In RecursivelyEnumeratedSet_graded.breadth_first_search_iterator, use list for next_level instead of set in order to iterate over his elements in the same order on each run. This fix python3 errors inthe combinat.root_system.weyl_group and root_lattice_realisations module.
But this modification causes some new doctests failures in weylgroup :
vklein@tuono:~/odk/sage$ sage t long src/sage/combinat/root_system/weyl_group.py too many failed tests, not using stored timings Running doctests with ID 20190611111520edaa5a63. Git branch: HEAD Using optional=build,cmake,dochtml,memlimit,mpir,primecount,python2,sage Doctesting 1 file. sage t long src/sage/combinat/root_system/weyl_group.py ********************************************************************** File "src/sage/combinat/root_system/weyl_group.py", line 1128, in sage.combinat.root_system.weyl_group.WeylGroup_permutation._coerce_map_from_ Failed example: W.has_coerce_map_from(W5) Expected: False Got: True ... File "src/sage/combinat/root_system/weyl_group.py", line 1157, in sage.combinat.root_system.weyl_group.WeylGroup_permutation.simple_reflection Failed example: **with W = WeylGroup(['A',4], implementation="permutation")** W.simple_reflections() Expected: Finite family {1: (1,11)(2,6)(7,9)(8,10)(12,16)(17,19)(18,20), 2: (1,6)(2,12)(3,7)(5,8)(11,16)(13,17)(15,18), 3: (2,7)(3,13)(4,5)(6,9)(12,17)(14,15)(16,19), 4: (3,5)(4,14)(7,8)(9,10)(13,15)(17,18)(19,20)} Got: Finite family {1: (1,11)(2,5)(6,8)(9,10)(12,15)(16,18)(19,20), 2: (1,5)(2,12)(3,6)(7,9)(11,15)(13,16)(17,19), 3: (2,6)(3,13)(4,7)(5,8)(12,16)(14,17)(15,18), 4: (3,7)(4,14)(6,9)(8,10)(13,17)(16,19)(18,20)}
I need help to look if the two results of W.simple_reflections()
are both correct or not and what's the result of W.has_coerce_map_from(W5)
is supposed to be.
Change History (45)
comment:1 Changed 3 years ago by
 Branch set to u/vklein/27967
comment:2 Changed 3 years ago by
 Commit set to 674343732acddd2667dd3b15145fb3f4382b739e
comment:3 Changed 3 years ago by
 Cc slabbe chapoton added
 Status changed from new to needs_info
comment:4 Changed 3 years ago by
 Cc tscrim added
comment:5 Changed 3 years ago by
Not clear to me that you can just replace set by list.. There could be repetitions..
comment:6 Changed 3 years ago by
I think repetitions are filtered:
if y is None or y in next_level: continue next_level.append(y)
comment:7 Changed 3 years ago by
 Milestone changed from sage8.8 to sage8.9
Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).
comment:8 Changed 3 years ago by
 Cc nthiery added
comment:9 Changed 3 years ago by
 Commit changed from 674343732acddd2667dd3b15145fb3f4382b739e to 0697a2334881b4ccb8aa8cb6da1a0c2a8d602be0
comment:10 followups: ↓ 11 ↓ 15 Changed 3 years ago by
 cdef set next_level + cdef list next_level + cdef set set_next_level
I do not like the idea of having two structures (list + set) to store the same elements. This may make the algorithm use twice as much memory. There must be a way to achieve this using only one.
Also, why should the enumeration order be certified? This is not claimed in the documentation. I know it would be very nice for the doctests of other codes using it, but I believe it is an error to expect such a thing. I would rather think the code using RES should fix themselves instead.
comment:11 in reply to: ↑ 10 Changed 3 years ago by
Also, why should the enumeration order be certified? This is not claimed in the documentation. I know it would be very nice for the doctests of other codes using it, but I believe it is an error to expect such a thing. I would rather think the code using RES should fix themselves instead.
The code using RES can't really fix that by sorting the results because the results are potentially too big and will take too much time to sort and therefore cancel the goal of using a generator.
The only other way i can think of now is tagging the tests with #py2 #py3 and hope order will remain the same across configuration and future python3 version.
comment:12 Changed 3 years ago by
Fixes for root_lattice_realizations are now in #28167.
comment:13 Changed 3 years ago by
I was thinking instead of these changes to fix doctest failures in weyl_group.py
. What do you think?

src/sage/combinat/root_system/weyl_group.py
diff git a/src/sage/combinat/root_system/weyl_group.py b/src/sage/combinat/root_system/weyl_group.py index 360d9bf320..e34dbe88b0 100644
a b class WeylGroup_gens(UniqueRepresentation, 355 355 EXAMPLES:: 356 356 357 357 sage: W = WeylGroup("B2", prefix="s") 358 sage: refdict = W.reflections(); refdict 358 sage: refdict = W.reflections() 359 sage: refdict # random 359 360 Finite family {(1, 1): s1, (0, 1): s2, (1, 1): s2*s1*s2, (1, 0): s1*s2*s1} 361 sage: [(a, refdict[a]) for a in sorted(dict(refdict))] 362 [((1, 0), s1*s2*s1), ((1, 1), s1), ((1, 1), s2*s1*s2), ((0, 1), s2)] 360 363 sage: [r+refdict[r].action(r) for r in refdict.keys()] 361 364 [(0, 0), (0, 0), (0, 0), (0, 0)] 362 365 … … class WeylGroup_permutation(UniqueRepresentation, PermutationGroup_generic): 1153 1156 EXAMPLES:: 1154 1157 1155 1158 sage: W = WeylGroup(['A',4], implementation="permutation") 1156 sage: W.simple_reflection(1) 1159 sage: a = W.simple_reflection(1) 1160 sage: a # random 1157 1161 (1,11)(2,6)(7,9)(8,10)(12,16)(17,19)(18,20) 1158 sage: W.simple_reflections() 1162 sage: a.is_reflection() 1163 True 1164 sage: W.simple_reflections() # random 1159 1165 Finite family {1: (1,11)(2,6)(7,9)(8,10)(12,16)(17,19)(18,20), 1160 1166 2: (1,6)(2,12)(3,7)(5,8)(11,16)(13,17)(15,18), 1161 1167 3: (2,7)(3,13)(4,5)(6,9)(12,17)(14,15)(16,19), 1162 1168 4: (3,5)(4,14)(7,8)(9,10)(13,15)(17,18)(19,20)} 1169 sage: W == W.subgroup(W.simple_reflections()) 1170 True 1163 1171 """ 1164 1172 return self.gens()[self._index_set_inverse[i]] 1165 1173 … … class WeylGroup_permutation(UniqueRepresentation, PermutationGroup_generic): 1229 1237 EXAMPLES:: 1230 1238 1231 1239 sage: W = WeylGroup(['G',2], implementation="permutation") 1232 sage: W.roots() 1233 ((1, 0), 1240 sage: sorted(W.roots()) 1241 [(3, 2), 1242 (3, 1), 1243 (2, 1), 1244 (1, 1), 1245 (1, 0), 1246 (0, 1), 1234 1247 (0, 1), 1248 (1, 0), 1235 1249 (1, 1), 1236 (3, 1),1237 1250 (2, 1), 1238 (3, 2), 1239 (1, 0), 1240 (0, 1), 1241 (1, 1), 1242 (3, 1), 1243 (2, 1), 1244 (3, 2)) 1251 (3, 1), 1252 (3, 2)] 1245 1253 """ 1246 1254 Q = self._cartan_type.root_system().root_lattice() 1247 1255 roots = ([x.to_vector() for x in Q.positive_roots()] … … class WeylGroup_permutation(UniqueRepresentation, PermutationGroup_generic): 1257 1265 EXAMPLES:: 1258 1266 1259 1267 sage: W = WeylGroup(['C',3], implementation="permutation") 1260 sage: W.positive_roots() 1268 sage: W.positive_roots() # py2 1261 1269 ((1, 0, 0), 1262 1270 (0, 1, 0), 1263 1271 (0, 0, 1), … … class WeylGroup_permutation(UniqueRepresentation, PermutationGroup_generic): 1267 1275 (2, 2, 1), 1268 1276 (1, 1, 1), 1269 1277 (1, 2, 1)) 1278 sage: W.positive_roots() # py3 1279 ((1, 0, 0), 1280 (0, 1, 0), 1281 (0, 0, 1), 1282 (0, 1, 1), 1283 (0, 2, 1), 1284 (1, 1, 0), 1285 (2, 2, 1), 1286 (1, 1, 1), 1287 (1, 2, 1)) 1270 1288 """ 1271 1289 return self.roots()[:self.number_of_reflections()] 1272 1290
comment:14 followup: ↓ 17 Changed 3 years ago by
However, I am also getting another doctest failure, which leads me to this, which might be a serious problem.
Python 2:
sage: W = WeylGroup(['A',3], implementation="permutation") sage: Permutation('(1,7)(2,5)(4,6)(8,11)(10,12)') in W False
Python 3:
sage: W = WeylGroup(['A',3], implementation="permutation") sage: Permutation('(1,7)(2,5)(4,6)(8,11)(10,12)') in W True
Is this a serious problem? It seems to me that W
should be the same group, regardless of the version of Python.
comment:15 in reply to: ↑ 10 Changed 3 years ago by
Replying to slabbe:
I do not like the idea of having two structures (list + set) to store the same elements. This may make the algorithm use twice as much memory. There must be a way to achieve this using only one.
The following change can improve memory usage, at least if the branching factor is large, say 2 or more. The difference here is that 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 running out of memory.

src/sage/sets/recursively_enumerated_set.pyx
a b cdef class RecursivelyEnumeratedSet_graded(RecursivelyEnumeratedSet_generic): 1166 1166 cdef int depth 1167 1167 if max_depth is None: 1168 1168 max_depth = self._max_depth 1169 1169 current_level = self._seeds 1170 if max_depth >= 0: 1171 for x in current_level: 1172 yield x 1170 1173 depth = 0 1171 while current_level and depth < =max_depth:1174 while current_level and depth < max_depth: 1172 1175 next_level = list() 1173 1176 set_next_level = set() 1174 1177 1175 1178 for x in current_level: 1176 yield x1177 1179 for y in self.successors(x): 1178 1180 if y is None or y in set_next_level: 1179 1181 continue 1182 yield y 1180 1183 next_level.append(y) 1181 1184 set_next_level.add(y) 1182 1185 current_level = next_level 1183 1186 depth += 1
If the branching factor is small, closer to 1, then memory consumption is probably less of a problem. However, also consider that the proposed solution replaces 2 sets by 1 set and 2 lists. Lists have a much smaller memory footprint and iteration is faster.
Aside from that, in most cases, the elements iterated over will add much more to the memory consumption than the additional list.
This solution should also be applied to the generic (nongraded) case. That case does not require an additional list – replacing a set by a list is enough. As far as I can tell, this would also help with #28227.
comment:16 Changed 3 years ago by
What needs to be done to move this ticket along? It is one of the main obstacles to having tests pass with Python 3. (See #28298.)
comment:17 in reply to: ↑ 14 ; followup: ↓ 18 Changed 3 years ago by
Replying to jhpalmieri:
However, I am also getting another doctest failure, which leads me to this, which might be a serious problem.
Python 2:
sage: W = WeylGroup(['A',3], implementation="permutation") sage: Permutation('(1,7)(2,5)(4,6)(8,11)(10,12)') in W FalsePython 3:
sage: W = WeylGroup(['A',3], implementation="permutation") sage: Permutation('(1,7)(2,5)(4,6)(8,11)(10,12)') in W TrueIs this a serious problem? It seems to me that
W
should be the same group, regardless of the version of Python.
W
is a permutation group on the roots W.roots()
, so the concrete representation in terms of permutations depends on the order of these roots, which differs between Python 2 and 3. Hence, this should not be a serious problem.
If this appears in the doctests (?), in order to obtain consistent results between Python versions, this could be solved by writing the permutation as a conjugation with the permutation that sorts the roots. That is, unless RecursivelyEnumeratedSet
itself is changed as suggested in this ticket.
comment:18 in reply to: ↑ 17 Changed 3 years ago by
Replying to ghmwageringel:
If this appears in the doctests (?), in order to obtain consistent results between Python versions, this could be solved by writing the permutation as a conjugation with the permutation that sorts the roots. That is, unless
RecursivelyEnumeratedSet
itself is changed as suggested in this ticket.
It doesn't appear in the doctests: I was experimenting with alternate possible doctests that might work with both Python versions.
comment:19 Changed 3 years ago by
How should we proceed here? I am happy if others take the approach in this ticket, but will that happen soon? If not, I can provide cosmetic doctest patches (as in comment:13) so that tests pass on Python 3, on a separate ticket as a stopgap. Any opinions?
comment:20 Changed 3 years ago by
Regarding the first new doctest failure from the ticket description (W.has_coerce_map_from(W5)
returning True
): with this branch, I get
sage: W = WeylGroup(["B",4], implementation="permutation") sage: W5 = WeylGroup(["C",4], implementation="permutation") sage: W.gens() == W5.gens() True
I'm guessing that's what's going on: the identity map is a coercion map in this case.
The documentation is not consistent with the code. The documentation for _coerce_map_from_
says Return ``True`` if ``P`` is a Weyl group of the same Cartan type and ``False`` otherwise.
The code says
if isinstance(P, WeylGroup_gens) and P.cartan_type() is self.cartan_type(): return True return super(WeylGroup_permutation, self)._coerce_map_from_(P)
So if P
has the same Cartan type, return True
, but otherwise, call something else: don't just automatically return False
as the documentation says. I'm not sure what to do here.
comment:21 Changed 3 years ago by
 Stopgaps set to #28351
I've created #28351 as a stopgap to fix the py3 doctests. If the approach here can be worked out, then it's easy enough to change the doctests again.
comment:22 Changed 3 years ago by
Sorry for not commenting on this sooner. So the problem might stem from the fact that these groups are isomorphic as (Coxeter) groups, but not as Weyl groups. For a Weyl group, it also acts on a set of roots (a set of vectors whose hyperplanes define the reflections and the set is closed under these reflections), which between type B and C are dual (there are two different lengths of the roots, and they are interchanged between the two types).
However, when doing the permutation implementation, we are effectively forgetting about the roots themselves, but instead (as pointed out in comment:17) it just depends on how the roots are permuted around. So when the ordering of the roots changes, the permutation group changes.
Now for the _coerce_map_from_
, that is a trickier thing to handle. I think we should just return False
as per the documentation and not let the base class (i.e., the generic permutation group code) handle it precisely because we define this as a Weyl group.
comment:23 followup: ↓ 25 Changed 3 years ago by
For _coerce_map_from
, I like the idea of changing the code so it is consistent with the documentation.
What about concerns about memory usage, and the other aspects of comment:10? (If we were guaranteed to use Python 3.7 or later, we could use dictionaries, since they are apparently insertion ordered. What's their memory usage like, compared to a list plus a set?)
comment:24 Changed 3 years ago by
 Branch changed from u/vklein/27967 to u/jhpalmieri/27967
comment:25 in reply to: ↑ 23 Changed 3 years ago by
 Commit changed from 0697a2334881b4ccb8aa8cb6da1a0c2a8d602be0 to d7903343951f28ce7875400953ce3f545fc9e2f4
This branch works for me with Python 2 and Python 3, but the issue of memory usage has not been addressed.
New commits:
4a6392b  Trac #27967: In RecursivelyEnumeratedSet_gra...

c5fe69c  Trac #27967: Adapt a root_lattice_realizations ...

c9442b4  Trac #27967: operator "x in list" being O(n) and ...

d790334  trac 27967: Make _coerce_map_from_ consistent with documenation.

comment:26 Changed 3 years ago by
 Commit changed from d7903343951f28ce7875400953ce3f545fc9e2f4 to a352ddc539bb80a1d9b4c15b4573daf4de606b8d
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a352ddc  trac 27967: Make _coerce_map_from_ consistent with documentation.

comment:27 Changed 3 years ago by
 Branch changed from u/jhpalmieri/27967 to u/vklein/27967
comment:28 Changed 3 years ago by
 Branch changed from u/vklein/27967 to u/slabbe/27967
 Commit changed from a352ddc539bb80a1d9b4c15b4573daf4de606b8d to 9c19a387f6f6b1f1394c4834c77a0074a50dfc18
 Status changed from needs_info to needs_review
comment:29 Changed 3 years ago by
Since Python 2.7, there is OrderedDict that we may use. It is written in pure Python, but according to the first answer of this question "Starting with Python 3.5, OrderedDict()
now has a C implementation."
My commit seems to work on Python 2. I did not check on Python 3.
comment:30 Changed 3 years ago by
 Commit changed from 9c19a387f6f6b1f1394c4834c77a0074a50dfc18 to 22c2c91a0f141c48194fcda5ef92ec08bc3f9e0f
Branch pushed to git repo; I updated commit sha1. New commits:
22c2c91  27967: remove py2/py3 tags since output is the same

comment:31 Changed 3 years ago by
comment:32 Changed 3 years ago by
I give positive review to commits 22c2c91
, 9c19a38
and a352ddc
. Another one should validate my owns commits 4a6392b, c5fe69c, c9442b4
and 902e26e
.
Tests passed in py2 and py3 on the whole sage.combinat.root_system
module and on recursively_enumerated_set
.
comment:33 Changed 3 years ago by
It seems there are some failing tests on the patchbot. Will take a look next week.
comment:34 followups: ↓ 35 ↓ 36 Changed 3 years ago by
I disagree with the recent changes. Using OrderedDict
does not address the memory concerns that were brought up, as OrderedDict
will internally store the insertion order in addition to the dictionary. Yet, as explained in comment:15, storing 1 set and 2 lists should usually be more memory efficient than storing 2 ordered dicts. It is faster than using OrderedDict
too, especially in Python 2. So I would prefer to go back to the old branch.
comment:35 in reply to: ↑ 34 Changed 3 years ago by
Replying to slabbe:
It seems there are some failing tests on the patchbot. Will take a look next week.
These don't seem like a big deal, at least as far as I can tell. If we have to fix them (that is, if the failures are due to using OrderedDict
and we decide to keep using it), then please also make this change:

src/sage/categories/coxeter_groups.py
diff git a/src/sage/categories/coxeter_groups.py b/src/sage/categories/coxeter_groups.py index b7beca409b..c6037f6c42 100644
a b class CoxeterGroups(Category_singleton): 1655 1655 sage: W = WeylGroup(["A", 3]) 1656 1656 sage: s = W.simple_reflections() 1657 1657 sage: w0 = s[1] 1658 sage: w1 = s[1]*s[2]*s[3]1659 1658 sage: w0.absolute_covers() 1660 1659 [ 1661 1660 [0 0 1 0] [0 1 0 0] [0 0 0 1] [0 1 0 0] [0 1 0 0]
comment:36 in reply to: ↑ 34 ; followup: ↓ 37 Changed 3 years ago by
Replying to ghmwageringel:
I disagree with the recent changes. Using
OrderedDict
does not address the memory concerns that were brought up, asOrderedDict
will internally store the insertion order in addition to the dictionary. Yet, as explained in comment:15, storing 1 set and 2 lists should usually be more memory efficient than storing 2 ordered dicts. It is faster than usingOrderedDict
too, especially in Python 2. So I would prefer to go back to the old branch.
I don't have strong feelings either way, but I would very much like to get this resolved. Is the old branch good enough? You proposed some other explicit changes in comment:15, along with "This solution should also be applied to the generic (nongraded) case."
By the way, is there a good way to test memory usage, say something analogous to %timeit
?
comment:37 in reply to: ↑ 36 Changed 3 years ago by
Replying to jhpalmieri:
I don't have strong feelings either way, but I would very much like to get this resolved. Is the old branch good enough?
No – to be more precise, my criticism is just about commit 9c19a38
introducing the use of OrderedDict
. All the other changes on the current branch look good to me and I will review them positively. The remaining doctest failures are not caused by OrderedDict
specifically, but by the change in iteration order in general, so should still be fixed:
sage/categories/coxeter_groups.py sage/categories/finite_complex_reflection_groups.py
You proposed some other explicit changes in comment:15, along with "This solution should also be applied to the generic (nongraded) case."
Yes, I still think those changes would be useful, but since this ticket is primarily concerned with making the tests pass with Python 3, let us keep those changes for a followup ticket. Changing the nongraded case would probably entail new doctest failures.
By the way, is there a good way to test memory usage, say something analogous to
%timeit
?
Not that I know of. You can use sys.getsizeof()
to get the (shallow) size in bytes of an object, but it only works for types that implement __sizeof__
(builtin types do so).
comment:38 Changed 3 years ago by
 Commit changed from 22c2c91a0f141c48194fcda5ef92ec08bc3f9e0f to 870441e4e0446fd3c76de929ea368bd918026eca
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
870441e  27967: remove py2/py3 tags since output is the same

comment:39 Changed 3 years ago by
Just forced push my branch after removing commit 9c19a38 but keeping commit 22c2c91 whose hash is now 870441e. Needs review.
comment:40 Changed 3 years ago by
 Branch changed from u/slabbe/27967 to u/jhpalmieri/27967
comment:41 Changed 3 years ago by
 Commit changed from 870441e4e0446fd3c76de929ea368bd918026eca to f2c51a869c60559a47bb51e3592c9b71bb095068
Here are fixes for the doctests in categories
.
New commits:
90762a4  Trac #27967: In RecursivelyEnumeratedSet_gra...

7f8288d  Trac #27967: Adapt a root_lattice_realizations ...

0cc63a9  Trac #27967: operator "x in list" being O(n) and ...

9959e15  trac 27967: Make _coerce_map_from_ consistent with documentation.

1420f35  Trac #27967: Fix doctests to be consistent ...

53a81f0  27967: remove py2/py3 tags since output is the same

f2c51a8  trac 27967: doctest fixes in categories

comment:42 Changed 3 years ago by
 Reviewers set to Vincent Klein, Markus Wageringel
 Status changed from needs_review to positive_review
Thank you all. Everything looks good to me and all the relevant tests pass with both Python 2 and 3 on my end. I am setting this to positive, Vincent, assuming you agree.
I am not sure what the stopgap ticket is about, though, or what needs to be done with it.
comment:43 Changed 3 years ago by
The stopgap can be closed. It was in case this ticket didn't get resolved soon: just fixes to Python 3 doctests with no changes to the code.
comment:44 Changed 3 years ago by
 Branch changed from u/jhpalmieri/27967 to f2c51a869c60559a47bb51e3592c9b71bb095068
 Resolution set to fixed
 Status changed from positive_review to closed
comment:45 Changed 3 years ago by
 Commit f2c51a869c60559a47bb51e3592c9b71bb095068 deleted
Followup ticket: #28674.
Branch pushed to git repo; I updated commit sha1. New commits:
Trac #27967: Adapt a root_lattice_realizations ...