Py3: Fix RecursivelyEnumeratedSet BFS for python3.

[vklein]

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 2019-06-11-11-15-20-edaa5a63.
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.

[git]

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

​6743437

Trac #27967: Adapt a root_lattice_realizations ...

[chapoton]

Not clear to me that you can just replace set by list.. There could be repetitions..

[vklein]

I think repetitions are filtered:

if y is None or y in next_level:
    continue
next_level.append(y)

[embray]

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).

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​fee09c6	Trac #27967: In RecursivelyEnumeratedSet_gra...
​8757dd0	Trac #27967: Adapt a root_lattice_realizations ...
​0697a23	Trac #27967: operator "x in list" being O(n) and ...

[slabbe]

-        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 most 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.

[vklein]

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.

[vklein]

Fixes for root_lattice_realizations are now in #28167.

[jhpalmieri]

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

@@ -355 +355 @@
         EXAMPLES::
 
             sage: W = WeylGroup("B2", prefix="s")
-            sage: refdict = W.reflections(); refdict
+            sage: refdict = W.reflections()
+            sage: refdict # random
             Finite family {(1, -1): s1, (0, 1): s2, (1, 1): s2*s1*s2, (1, 0): s1*s2*s1}
+            sage: [(a, refdict[a]) for a in sorted(dict(refdict))]
+            [((1, 0), s1*s2*s1), ((1, -1), s1), ((1, 1), s2*s1*s2), ((0, 1), s2)]
             sage: [r+refdict[r].action(r) for r in refdict.keys()]
             [(0, 0), (0, 0), (0, 0), (0, 0)]
 
@@ -1153 +1156 @@
         EXAMPLES::
 
             sage: W = WeylGroup(['A',4], implementation="permutation")
-            sage: W.simple_reflection(1)
+            sage: a = W.simple_reflection(1)
+            sage: a # random
             (1,11)(2,6)(7,9)(8,10)(12,16)(17,19)(18,20)
-            sage: W.simple_reflections()
+            sage: a.is_reflection()
+            True
+            sage: W.simple_reflections() # random
             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)}
+            sage: W == W.subgroup(W.simple_reflections())
+            True
         """
         return self.gens()[self._index_set_inverse[i]]
 
@@ -1229 +1237 @@
         EXAMPLES::
 
             sage: W = WeylGroup(['G',2], implementation="permutation")
-            sage: W.roots()
-            ((1, 0),
+            sage: sorted(W.roots())
+            [(-3, -2),
+             (-3, -1),
+             (-2, -1),
+             (-1, -1),
+             (-1, 0),
+             (0, -1),
              (0, 1),
+             (1, 0),
              (1, 1),
-             (3, 1),
              (2, 1),
-             (3, 2),
-             (-1, 0),
-             (0, -1),
-             (-1, -1),
-             (-3, -1),
-             (-2, -1),
-             (-3, -2))
+             (3, 1),
+             (3, 2)]
         """
         Q = self._cartan_type.root_system().root_lattice()
         roots = ([x.to_vector() for x in Q.positive_roots()]
@@ -1257 +1265 @@
         EXAMPLES::
 
             sage: W = WeylGroup(['C',3], implementation="permutation")
-            sage: W.positive_roots()
+            sage: W.positive_roots() # py2
             ((1, 0, 0),
              (0, 1, 0),
              (0, 0, 1),
@@ -1267 +1275 @@
              (2, 2, 1),
              (1, 1, 1),
              (1, 2, 1))
+            sage: W.positive_roots() # py3
+            ((1, 0, 0),
+             (0, 1, 0),
+             (0, 0, 1),
+             (0, 1, 1),
+             (0, 2, 1),
+             (1, 1, 0),
+             (2, 2, 1),
+             (1, 1, 1),
+             (1, 2, 1))
         """
         return self.roots()[:self.number_of_reflections()]
 

[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
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.

[gh-mwageringel]

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

@@ -1166 +1166 @@
         cdef int depth
         if max_depth is None:
             max_depth = self._max_depth
         current_level = self._seeds
+        if max_depth >= 0:
+            for x in current_level:
+                yield x
         depth = 0
-        while current_level and depth <= max_depth:
+        while current_level and depth < max_depth:
             next_level = list()
             set_next_level = set()
 
             for x in current_level:
-                yield x
                 for y in self.successors(x):
                     if y is None or y in set_next_level:
                         continue
+                    yield y
                     next_level.append(y)
                     set_next_level.add(y)
             current_level = next_level
             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 (non-graded) 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.

[jhpalmieri]

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.)

[gh-mwageringel]

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
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.

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.

[jhpalmieri]

Replying to gh-mwageringel:

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.

[jhpalmieri]

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?

[jhpalmieri]

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.

[jhpalmieri]

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.

[tscrim]

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.

[jhpalmieri]

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?)

[jhpalmieri]

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.

[git]

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.

[slabbe]

New commits:

​902e26e	Trac #27967: Fix doctests to be consistent ...
​9c19a38	27967: using OrderedDict to preserve the order of insertion

[slabbe]

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.

[git]

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

​22c2c91

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

[vklein]

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.

[slabbe]

It seems there are some failing tests on the patchbot. Will take a look next week.

[gh-mwageringel]

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.

[jhpalmieri]

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

@@ -1655 +1655 @@
                 sage: W = WeylGroup(["A", 3])
                 sage: s = W.simple_reflections()
                 sage: w0 = s[1]
-                sage: w1 = s[1]*s[2]*s[3]
                 sage: w0.absolute_covers()
                 [
                 [0 0 1 0]  [0 1 0 0]  [0 0 0 1]  [0 1 0 0]  [0 1 0 0]

[jhpalmieri]

Replying to gh-mwageringel:

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.

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 (non-graded) case."

By the way, is there a good way to test memory usage, say something analogous to %timeit?

[gh-mwageringel]

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 (non-graded) 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 follow-up ticket. Changing the non-graded 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__ (built-in types do so).

[git]

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

[slabbe]

Just forced push my branch after removing commit ​9c19a38 but keeping ​commit 22c2c91 whose hash is now ​870441e. Needs review.

[jhpalmieri]

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

[gh-mwageringel]

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.

[jhpalmieri]

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.

[gh-mwageringel]

Follow-up ticket: #28674.