doctest failures related to automorphism groups of edge-labelled graphs

[vdelecroix]

On 8.3.beta2 with 62 optional packages installed there are failures about automorphism group computations

sage -t --long src/sage/geometry/polyhedron/base.py  # 4 doctests failed
sage -t --long src/sage/geometry/lattice_polytope.py  # 1 doctest failed
sage -t --long src/sage/geometry/triangulation/point_configuration.py  # 1 doctest failed
sage -t --long src/sage/geometry/polyhedron/ppl_lattice_polytope.py  # 5 doctests failed
sage -t --long src/sage/geometry/fan_isomorphism.py  # 1 doctest failed

More precisely

sage -t --long src/sage/geometry/polyhedron/base.py
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 5747, in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
Failed example:
    P.restricted_automorphism_group()
Expected:
    Permutation Group with generators [(3,4), (2,3)(4,5), (2,5), (1,2)(5,6), (1,6)]
Got:
    Permutation Group with generators [(3,4), (2,3)(4,5), (1,2)(5,6)]
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 5749, in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
Failed example:
    P.restricted_automorphism_group(output="permutation")
Expected:
    Permutation Group with generators [(2,3), (1,2)(3,4), (1,4), (0,1)(4,5), (0,5)]
Got:
    Permutation Group with generators [(2,3), (1,2)(3,4), (0,1)(4,5)]
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 5751, in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
Failed example:
    P.restricted_automorphism_group(output="matrix")
Expected:
    Matrix group over Rational Field with 5 generators (
    [ 1  0  0  0]  [1 0 0 0]  [ 1  0  0  0]  [0 1 0 0]  [-1  0  0  0]
    [ 0  1  0  0]  [0 0 1 0]  [ 0 -1  0  0]  [1 0 0 0]  [ 0  1  0  0]
    [ 0  0 -1  0]  [0 1 0 0]  [ 0  0  1  0]  [0 0 1 0]  [ 0  0  1  0]
    [ 0  0  0  1], [0 0 0 1], [ 0  0  0  1], [0 0 0 1], [ 0  0  0  1]
    )
Got:
    Matrix group over Rational Field with 3 generators (
    [ 1  0  0  0]  [1 0 0 0]  [0 1 0 0]
    [ 0  1  0  0]  [0 0 1 0]  [1 0 0 0]
    [ 0  0 -1  0]  [0 1 0 0]  [0 0 1 0]
    [ 0  0  0  1], [0 0 0 1], [0 0 0 1]
    )
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 5763, in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
Failed example:
    PermutationGroup([
        '(1,20,2,24,5,23)(3,18,10,19,4,14)(6,21,11,22,7,15)(8,12,16,17,13,9)',
        '(1,21,8,24,4,17)(2,11,6,15,9,13)(3,20)(5,22)(10,16,12,23,14,19)'
    ]) == AutP24
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   4 of  40 in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
    [1008 tests, 4 failures, 81.42 s]

sage -t --long src/sage/geometry/lattice_polytope.py
**********************************************************************
File "src/sage/geometry/lattice_polytope.py", line 3067, in sage.geometry.lattice_polytope.Latt
icePolytopeClass._palp_PM_max
Failed example:
    all(len(i) == len(j.automorphisms_of_rows_and_columns())
        for j, i in PMs) # long time
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   1 of  12 in sage.geometry.lattice_polytope.LatticePolytopeClass._palp_PM_max
    [638 tests, 1 failure, 52.58 s]

sage -t --long src/sage/geometry/triangulation/point_configuration.py
**********************************************************************
File "src/sage/geometry/triangulation/point_configuration.py", line 1155, in sage.geometry.triangulation.point_configuration.PointConfiguration.restricted_automorphism_group
Failed example:
    pyramid.restricted_automorphism_group()
Expected:
    Permutation Group with generators [(3,5), (2,3)(4,5), (2,4)]
Got:
    Permutation Group with generators [(3,5), (2,3)(4,5)]
**********************************************************************
1 item had failures:
   1 of   7 in sage.geometry.triangulation.point_configuration.PointConfiguration.restricted_automorphism_group
    [247 tests, 1 failure, 38.46 s]

sage -t --long src/sage/geometry/polyhedron/ppl_lattice_polytope.py
**********************************************************************
File "src/sage/geometry/polyhedron/ppl_lattice_polytope.py", line 985, in sage.geometry.polyhed
ron.ppl_lattice_polytope.LatticePolytope_PPL_class.restricted_automorphism_group
Failed example:
    Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4))
Expected:
    Permutation Group with generators [(2,3), (1,2)(3,4), (1,4)]
Got:
    Permutation Group with generators [(2,3), (1,2)(3,4)]
**********************************************************************
File "src/sage/geometry/polyhedron/ppl_lattice_polytope.py", line 987, in sage.geometry.polyhed
ron.ppl_lattice_polytope.LatticePolytope_PPL_class.restricted_automorphism_group
Failed example:
    G = Z3square.restricted_automorphism_group(); G
Expected:
    Permutation Group with generators [((1,2),(2,1)),
    ((0,0),(1,2))((2,1),(3,3)), ((0,0),(3,3))]
Got:
    Permutation Group with generators [((0,0),(3,3)), ((1,2),(0,0))((3,3),(2,1))]
**********************************************************************
File "src/sage/geometry/polyhedron/ppl_lattice_polytope.py", line 990, in sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class.restricted_automorphism_group
Failed example:
    tuple(G.domain()) == Z3square.vertices()
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/geometry/polyhedron/ppl_lattice_polytope.py", line 992, in sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class.restricted_automorphism_group
Failed example:
    G.orbit(Z3square.vertices()[0])
Expected:
    ((0, 0), (1, 2), (3, 3), (2, 1))
Got:
    ((0, 0), (3, 3), (1, 2), (2, 1))
**********************************************************************
File "src/sage/geometry/polyhedron/ppl_lattice_polytope.py", line 1063, in sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class.lattice_automorphism_group
Failed example:
    G2 = Z3square.restricted_automorphism_group(vertex_labels=(1,2,3,4)); G2
Expected:
    Permutation Group with generators [(2,3), (1,2)(3,4), (1,4)]
Got:
    Permutation Group with generators [(2,3), (1,2)(3,4)]
**********************************************************************
2 items had failures:
   1 of  13 in sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class.lattice_automorphism_group
   4 of   9 in sage.geometry.polyhedron.ppl_lattice_polytope.LatticePolytope_PPL_class.restricted_automorphism_group
    [173 tests, 5 failures, 27.58 s]

sage -t --long src/sage/geometry/fan_isomorphism.py
**********************************************************************
File "src/sage/geometry/fan_isomorphism.py", line 84, in sage.geometry.fan_isomorphism.fan_isom
orphism_generator
Failed example:
    tuple( fan_isomorphism_generator(fan, fan) )
Expected:
    (
    [1 0]  [0 1]  [ 1  0]  [ 0  1]  [-1 -1]  [-1 -1]
    [0 1], [1 0], [-1 -1], [-1 -1], [ 1  0], [ 0  1]
    )
Got:
    (
    [1 0]  [0 1]  [-1 -1]  [-1 -1]  [ 0  1]  [ 1  0]
    [0 1], [1 0], [ 0  1], [ 1  0], [-1 -1], [-1 -1]
    )
**********************************************************************
1 item had failures:
   1 of  21 in sage.geometry.fan_isomorphism.fan_isomorphism_generator
    [65 tests, 1 failure, 2.56 s]

apart from geometry/lattice_polytope.py, it's merely different backend producing different, but equivalent, data; the former however uncovers a bug, cf #25426, coming from the work done on #24924.

[fbissey]

My own testing seems to point to bliss's presence being the only cause. I think the feature ticket may have changed a default behavior with bliss.

[dimpase]

It's probably <s>isomorphic</s> equal groups (need to check for all the cases, but certainly true here):

Expected:
    Permutation Group with generators [(2,3), (1,2)(3,4), (1,4)]
Got:
    Permutation Group with generators [(2,3), (1,2)(3,4)]

robust tests should check that these groups are the same; isomorphism might be too slow, probably quicker to that that the generators of the 1st (resp 2nd) are in the 2nd (resp in the 1st).

With orbits, it's even more obvious---different generator sets lead to different ordering of elements in orbits, so they should be compared as sets.

[fbissey]

This appears to be a consequence of this change

src/sage/graphs/generic_graph.py

@@ -21923 +21923 @@
 
         if (algorithm == 'bliss'           or   # explicit choice from the user; or
             (algorithm is None             and  # by default
-             not edge_labels               and
              have_bliss)):
-            if edge_labels:
-                raise ValueError("bliss cannot be used when edge_labels is True")
 
             Bliss().require()

from #24924. Reverting it fixes all the failing doctests.

[dimpase]

this change is correct, it introduces functionality that allows bliss to be used on graphs with edge labels. The doctests should be fixed, obviously.

why we did not see these test failures while working on #24924, I don't know. Perhaps an oversight on our side.

[dimpase]

this fixes all but sage/geometry/lattice_polytope.py doctest. The latter actually is a real bug, sort of...

---

New commits:

​3983db1

fix all but one doctest on #25399

[fbissey]

Replying to dimpase:

this fixes all but sage/geometry/lattice_polytope.py doctest. The latter actually is a real bug, sort of...

---

New commits:

​3983db1

fix all but one doctest on #25399

Do you want to deal with it as a separate ticket?

[dimpase]

namely, it boils down to bliss failing on

sage: j = matrix([(3, 2, 1, 0, 0),
....:  (2, 2, 0, 1, 0),
....:  (1, 0, 3, 0, 2),
....:  (0, 1, 0, 2, 1),
....:  (0, 0, 2, 1, 2)])
sage: j.automorphisms_of_rows_and_columns()
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-101-6e33f1efc3a2> in <module>()
----> 1 j.automorphisms_of_rows_and_columns()

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.automorphisms_of_rows_and_columns (build/cythonized/sage/matrix/matrix2.c:56065)()
   7137             if p[0] <= nrows:
   7138                 permutations.append(
-> 7139                     (PermutationGroupElement(p[:nrows]),
   7140                      PermutationGroupElement([elt - nrows for elt in p[nrows:]])
   7141                     ))

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_element.pyx in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__init__ (build/cythonized/sage/groups/perm_gps/permgroup_element.c:5204)()
    444         convert_dict = parent._domain_to_gap if parent is not None else None
    445         try:
--> 446             v = standardize_generator(g, convert_dict)
    447         except KeyError:
    448             raise ValueError("Invalid permutation vector: %s" % g)

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/groups/perm_gps/permgroup_element.pyx in sage.groups.perm_gps.permgroup_element.standardize_generator (build/cythonized/sage/groups/perm_gps/permgroup_element.c:4685)()
    253         if convert_dict is not None and needs_conversion:
    254             g = [convert_dict[x] for x in g]
--> 255         return Permutation(g).cycle_tuples()
    256     else:
    257         if convert_dict is not None and needs_conversion:

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1639)()
    327         """
    328         if cls.classcall is not None:
--> 329             return cls.classcall(cls, *args, **kwds)
    330         else:
    331             # Fast version of type.__call__(cls, *args, **kwds)

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in __classcall_private__(cls, l, check_input)
    479 
    480         # otherwise, it gets processed by CombinatorialElement's __init__.
--> 481         return Permutations()(l, check_input=check_input)
    482 
    483     def __init__(self, parent, l, check_input=True):

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9761)()
    920                 return mor._call_(x)
    921             else:
--> 922                 return mor._call_with_args(x, args, kwds)
    923 
    924         raise TypeError("No conversion defined from %s to %s"%(R, self))

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:5093)()
    162                 print(type(C), C)
    163                 print(type(C._element_constructor), C._element_constructor)
--> 164             raise
    165 
    166 

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/structure/coerce_maps.pyx in sage.structure.coerce_maps.DefaultConvertMap_unique._call_with_args (build/cythonized/sage/structure/coerce_maps.c:4883)()
    152                     return C._element_constructor(x)
    153                 else:
--> 154                     return C._element_constructor(x, **kwds)
    155             else:
    156                 if len(kwds) == 0:

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/categories/sets_cat.pyc in _element_constructor_from_element_class(self, *args, **keywords)
    993                 <class 'sage.categories.examples.sets_cat.PrimeNumbers_Inherits_with_category.element_class'>
    994             """
--> 995             return self.element_class(self, *args, **keywords)
    996 
    997         def is_parent_of(self, element):

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.pyx in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1664)()
    330         else:
    331             # Fast version of type.__call__(cls, *args, **kwds)
--> 332             return (<PyTypeObject*>type).tp_call(cls, args, kwds)
    333 
    334     def __get__(cls, instance, owner):

/home/dima/Sage/sage-dev/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in __init__(self, parent, l, check_input)
    540                                  str(int(lst[-1]))+". Some element "+
    541                                  "may be repeated, or an element is missing"+
--> 542                                  ", but there is something wrong with its length.")
    543 
    544             # Do the elements appear only once ?

ValueError: The permutation has length 5 but its maximal element is 9. Some element may be repeated, or an element is missing, but there is something wrong with its length.
sage: 

[fbissey]

OK, the branch fixes those 4 doctests for me. So I am OK with that part.

[dimpase]

Replying to fbissey:

Do you want to deal with it as a separate ticket?

I just opened #25426 to deal with the remaining error; it certainly points to the work done on #24924. Meanwhile, let's merge the branch I posted here.

[fbissey]

LGTM

[vbraun]

polyhedron/base.py fails tests

[fbissey]

I am guessing we overlooked testing without bliss installed. I cannot look at it before tomorrow in my time zone.

[fbissey]

OK so without bliss this branch leads to the following failure

File "/usr/lib64/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 5752, in sage.geometry.polyhedron.base.Polyhedron_base.restricted_automorphism_group
Failed example:
    P.restricted_automorphism_group(output="matrix") == MatrixGroup(map(lambda t: matrix(QQ,t), mgens))
Expected:
    True
Got:
    False
**********************************************************************

[slabbe]

Note: I created yesterday #25475 which turned out to be a duplicate of this one.

[jdemeyer]

So should this be closed as duplicate?

[dimpase]

Replying to jdemeyer:

So should this be closed as duplicate?

#25475 should be closed, yes.

[jdemeyer]

If this is not fixed soon, we should just revert #24924.

[dimpase]

Replying to jdemeyer:

Is this is not fixed soon, we should just revert #24924.

no, we should not. Someone should do some work, understand where this weird doctest error comes from.

[jdemeyer]

Note my condition:

If this is not fixed soon, we should just revert #24924.

The status-quo is not acceptable since this is causing doctest failures.

[dimpase]

I know how to fix it (a bit ugly, but mathematically correct). I'll post a branch.

[git]

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

​c7b5404	Merge branch 'u/dimpase/blissgeom' of trac.sagemath.org:sage into newbliss
​e1a1664	properly compare matrix groups for (maths) equality

[dimpase]

now this works for me both with and without bliss installed.

[jdemeyer]

This does not guarantee correct ordering:

tuple(set(fan_isomorphism_generator(fan, fan)))

Better use

sorted(fan_isomorphism_generator(fan, fan))

[git]

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

​a23feee

use sorted() instead of tuple(set())

[dimpase]

ok, fixed

[fbissey]

Works for me.