Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

doctest failures related to automorphism groups of edge-labelled graphs #25399

Closed
videlec opened this issue May 19, 2018 · 34 comments
Closed

doctest failures related to automorphism groups of edge-labelled graphs #25399

videlec opened this issue May 19, 2018 · 34 comments

Comments

@videlec
Copy link
Contributor

videlec commented May 19, 2018

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.

CC: @jplab @mkoeppe @mo271 @kiwifb @stumpc5

Component: group theory

Author: Dima Pasechnik

Branch/Commit: a23feee

Reviewer: François Bissey

Issue created by migration from https://trac.sagemath.org/ticket/25399

@videlec videlec added this to the sage-8.3 milestone May 19, 2018
@kiwifb
Copy link
Member

kiwifb commented May 21, 2018

comment:3

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
Copy link
Member

dimpase commented May 21, 2018

comment:4

It's probably isomorphic 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.

@kiwifb
Copy link
Member

kiwifb commented May 22, 2018

comment:5

This appears to be a consequence of this change

diff --git a/src/sage/graphs/generic_graph.py b/src/sage/graphs/generic_graph.py
index eea21a2d2e..49eadaf162 100644
--- a/src/sage/graphs/generic_graph.py
+++ b/src/sage/graphs/generic_graph.py
@@ -21923,7 +21923,10 @@ class GenericGraph(GenericGraph_pyx):
 
         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
Copy link
Member

dimpase commented May 22, 2018

comment:6

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
Copy link
Member

dimpase commented May 22, 2018

Author: Dima Pasechnik

@dimpase
Copy link
Member

dimpase commented May 22, 2018

Branch: u/dimpase/blissgeom

@dimpase
Copy link
Member

dimpase commented May 22, 2018

Commit: 3983db1

@dimpase
Copy link
Member

dimpase commented May 22, 2018

comment:8

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

@kiwifb
Copy link
Member

kiwifb commented May 22, 2018

comment:9

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?

@dimpase
Copy link
Member

dimpase commented May 22, 2018

comment:10

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: 

@kiwifb
Copy link
Member

kiwifb commented May 22, 2018

comment:11

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

@dimpase
Copy link
Member

dimpase commented May 23, 2018

comment:12

Replying to @kiwifb:

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.

@dimpase

This comment has been minimized.

@dimpase dimpase changed the title doctest failures related to automorphism groups doctest failures related to automorphism groups of edge-labelled graphs May 23, 2018
@kiwifb
Copy link
Member

kiwifb commented May 23, 2018

Reviewer: François Bissey

@kiwifb
Copy link
Member

kiwifb commented May 23, 2018

comment:14

LGTM

@vbraun
Copy link
Member

vbraun commented May 28, 2018

comment:15

polyhedron/base.py fails tests

@kiwifb
Copy link
Member

kiwifb commented May 28, 2018

comment:16

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

@kiwifb
Copy link
Member

kiwifb commented May 29, 2018

comment:17

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

@seblabbe
Copy link
Contributor

comment:18

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

@jdemeyer
Copy link

jdemeyer commented Jun 7, 2018

comment:19

So should this be closed as duplicate?

@dimpase
Copy link
Member

dimpase commented Jun 7, 2018

comment:20

Replying to @jdemeyer:

So should this be closed as duplicate?

#25475 should be closed, yes.

@jdemeyer
Copy link

comment:21

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

@dimpase
Copy link
Member

dimpase commented Jun 19, 2018

comment:22

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
Copy link

comment:23

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
Copy link
Member

dimpase commented Jun 19, 2018

comment:24

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 19, 2018

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

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 19, 2018

Changed commit from 3983db1 to e1a1664

@dimpase
Copy link
Member

dimpase commented Jun 19, 2018

comment:26

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

@jdemeyer
Copy link

comment:27

This does not guarantee correct ordering:

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

Better use

sorted(fan_isomorphism_generator(fan, fan))

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 19, 2018

Changed commit from e1a1664 to a23feee

@sagetrac-git
Copy link
Mannequin

sagetrac-git mannequin commented Jun 19, 2018

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

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

@dimpase
Copy link
Member

dimpase commented Jun 19, 2018

comment:29

ok, fixed

@kiwifb
Copy link
Member

kiwifb commented Jun 20, 2018

comment:30

Works for me.

@vbraun
Copy link
Member

vbraun commented Jun 21, 2018

Changed branch from u/dimpase/blissgeom to a23feee

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

6 participants