Opened 9 months ago

Closed 8 months ago

#25399 closed defect (fixed)

doctest failures related to automorphism groups of edge-labelled graphs

Reported by: vdelecroix Owned by:
Priority: blocker Milestone: sage-8.3
Component: group theory Keywords:
Cc: jipilab, mkoeppe, moritz, fbissey, stumpc5 Merged in:
Authors: Dima Pasechnik Reviewers: François Bissey
Report Upstream: N/A Work issues:
Branch: a23feee (Commits) Commit: a23feee596c726bab592c9aa83a8a4e054fc1815
Dependencies: Stopgaps:

Description (last modified by dimpase)

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.

Change History (31)

comment:1 Changed 9 months ago by vdelecroix

  • Cc jipilab mkoeppe added

comment:2 Changed 9 months ago by jipilab

  • Cc moritz added

comment:3 Changed 9 months ago by fbissey

  • Cc fbissey added

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.

comment:4 Changed 9 months ago by 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.

Last edited 9 months ago by dimpase (previous) (diff)

comment:5 Changed 9 months ago by fbissey

This appears to be a consequence of this change

  • src/sage/graphs/generic_graph.py

    diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
    index eea21a2d2e..49eadaf162 100644
    a b class GenericGraph(GenericGraph_pyx): 
    2192321923
    2192421924        if (algorithm == 'bliss'           or   # explicit choice from the user; or
    2192521925            (algorithm is None             and  # by default
    21926              not edge_labels               and
    2192721926             have_bliss)):
    21928             if edge_labels:
    21929                 raise ValueError("bliss cannot be used when edge_labels is True")
    2193021927
    2193121928            Bliss().require()

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

comment:6 Changed 9 months ago by 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.

comment:7 Changed 9 months ago by dimpase

  • Authors set to Dima Pasechnik

comment:8 follow-up: Changed 9 months ago by dimpase

  • Branch set to u/dimpase/blissgeom
  • Commit set to 3983db15713478ba596e94604bafa31895f9a714

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


New commits:

3983db1fix all but one doctest on #25399

comment:9 in reply to: ↑ 8 ; follow-up: Changed 9 months ago by 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:

3983db1fix all but one doctest on #25399

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

comment:10 Changed 9 months ago by 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: 

comment:11 Changed 9 months ago by fbissey

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

comment:12 in reply to: ↑ 9 Changed 9 months ago by dimpase

  • Status changed from new to needs_review

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.

comment:13 Changed 9 months ago by dimpase

  • Description modified (diff)
  • Summary changed from doctest failures related to automorphism groups to doctest failures related to automorphism groups of edge-labelled graphs

comment:14 Changed 9 months ago by fbissey

  • Reviewers set to François Bissey
  • Status changed from needs_review to positive_review

LGTM

comment:15 Changed 9 months ago by vbraun

  • Status changed from positive_review to needs_work

polyhedron/base.py fails tests

comment:16 Changed 9 months ago by fbissey

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

comment:17 Changed 9 months ago by 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
**********************************************************************

comment:18 Changed 9 months ago by slabbe

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

comment:19 follow-up: Changed 9 months ago by jdemeyer

So should this be closed as duplicate?

comment:20 in reply to: ↑ 19 Changed 9 months ago by dimpase

Replying to jdemeyer:

So should this be closed as duplicate?

#25475 should be closed, yes.

comment:21 follow-up: Changed 8 months ago by jdemeyer

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

Last edited 8 months ago by jdemeyer (previous) (diff)

comment:22 in reply to: ↑ 21 Changed 8 months ago by 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.

comment:23 Changed 8 months ago by 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.

comment:24 Changed 8 months ago by dimpase

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

comment:25 Changed 8 months ago by git

  • Commit changed from 3983db15713478ba596e94604bafa31895f9a714 to e1a16646e06772d506e49fb4b34d08c723dfe195

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

c7b5404Merge branch 'u/dimpase/blissgeom' of trac.sagemath.org:sage into newbliss
e1a1664properly compare matrix groups for (maths) equality

comment:26 Changed 8 months ago by dimpase

  • Cc stumpc5 added
  • Status changed from needs_work to needs_review

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

comment:27 Changed 8 months ago by jdemeyer

  • Status changed from needs_review to needs_work

This does not guarantee correct ordering:

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

Better use

sorted(fan_isomorphism_generator(fan, fan))

comment:28 Changed 8 months ago by git

  • Commit changed from e1a16646e06772d506e49fb4b34d08c723dfe195 to a23feee596c726bab592c9aa83a8a4e054fc1815

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

a23feeeuse sorted() instead of tuple(set())

comment:29 Changed 8 months ago by dimpase

  • Status changed from needs_work to needs_review

ok, fixed

comment:30 Changed 8 months ago by fbissey

  • Status changed from needs_review to positive_review

Works for me.

comment:31 Changed 8 months ago by vbraun

  • Branch changed from u/dimpase/blissgeom to a23feee596c726bab592c9aa83a8a4e054fc1815
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.