Opened 3 years ago
Closed 3 years ago
#25399 closed defect (fixed)
doctest failures related to automorphism groups of edgelabelled graphs
Reported by:  vdelecroix  Owned by:  

Priority:  blocker  Milestone:  sage8.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, GitHub, GitLab)  Commit:  a23feee596c726bab592c9aa83a8a4e054fc1815 
Dependencies:  Stopgaps: 
Description (last modified by )
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 3 years ago by
 Cc jipilab mkoeppe added
comment:2 Changed 3 years ago by
 Cc moritz added
comment:3 Changed 3 years ago by
 Cc fbissey added
comment:4 Changed 3 years ago by
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 obviousdifferent generator sets lead to different ordering of elements in orbits, so they should be compared as sets.
comment:5 Changed 3 years ago by
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): 21923 21923 21924 21924 if (algorithm == 'bliss' or # explicit choice from the user; or 21925 21925 (algorithm is None and # by default 21926 not edge_labels and21927 21926 have_bliss)): 21928 if edge_labels:21929 raise ValueError("bliss cannot be used when edge_labels is True")21930 21927 21931 21928 Bliss().require()
from #24924. Reverting it fixes all the failing doctests.
comment:6 Changed 3 years ago by
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 3 years ago by
comment:8 followup: ↓ 9 Changed 3 years ago by
 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:
3983db1  fix all but one doctest on #25399

comment:9 in reply to: ↑ 8 ; followup: ↓ 12 Changed 3 years ago by
comment:10 Changed 3 years ago by
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) <ipythoninput1016e33f1efc3a2> in <module>() > 1 j.automorphisms_of_rows_and_columns() /home/dima/Sage/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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/sagedev/local/lib/python2.7/sitepackages/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 3 years ago by
OK, the branch fixes those 4 doctests for me. So I am OK with that part.
comment:12 in reply to: ↑ 9 Changed 3 years ago by
 Status changed from new to needs_review
comment:13 Changed 3 years ago by
 Description modified (diff)
 Summary changed from doctest failures related to automorphism groups to doctest failures related to automorphism groups of edgelabelled graphs
comment:14 Changed 3 years ago by
 Reviewers set to François Bissey
 Status changed from needs_review to positive_review
LGTM
comment:15 Changed 3 years ago by
 Status changed from positive_review to needs_work
polyhedron/base.py fails tests
comment:16 Changed 3 years ago by
I am guessing we overlooked testing without bliss
installed. I cannot look at it before tomorrow in my time zone.
comment:17 Changed 3 years ago by
OK so without bliss
this branch leads to the following failure
File "/usr/lib64/python2.7/sitepackages/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 3 years ago by
Note: I created yesterday #25475 which turned out to be a duplicate of this one.
comment:19 followup: ↓ 20 Changed 3 years ago by
So should this be closed as duplicate?
comment:20 in reply to: ↑ 19 Changed 3 years ago by
comment:21 followup: ↓ 22 Changed 3 years ago by
If this is not fixed soon, we should just revert #24924.
comment:22 in reply to: ↑ 21 Changed 3 years ago by
comment:23 Changed 3 years ago by
Note my condition:
If this is not fixed soon, we should just revert #24924.
The statusquo is not acceptable since this is causing doctest failures.
comment:24 Changed 3 years ago by
I know how to fix it (a bit ugly, but mathematically correct). I'll post a branch.
comment:25 Changed 3 years ago by
 Commit changed from 3983db15713478ba596e94604bafa31895f9a714 to e1a16646e06772d506e49fb4b34d08c723dfe195
comment:26 Changed 3 years ago by
 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 3 years ago by
 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 3 years ago by
 Commit changed from e1a16646e06772d506e49fb4b34d08c723dfe195 to a23feee596c726bab592c9aa83a8a4e054fc1815
Branch pushed to git repo; I updated commit sha1. New commits:
a23feee  use sorted() instead of tuple(set())

comment:31 Changed 3 years ago by
 Branch changed from u/dimpase/blissgeom to a23feee596c726bab592c9aa83a8a4e054fc1815
 Resolution set to fixed
 Status changed from positive_review to closed
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.