Opened 7 weeks ago
Last modified 4 weeks ago
#27571 needs_review enhancement
py3: automorphism_group, canonical_label, canonical_form and doctest in MathonPseudocyclicStronglyRegularGraph
Reported by:  dcoudert  Owned by:  

Priority:  major  Milestone:  sage8.8 
Component:  graph theory  Keywords:  py3, graph 
Cc:  tscrim, dimpase  Merged in:  
Authors:  David Coudert  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/graphs/27571_automorphism (Commits)  Commit:  8fcd5842211b9a469d3a631cb7f28cdc1a944be1 
Dependencies:  Stopgaps: 
Description (last modified by )
This ticket fix this py3 failing doctest in graphs.MathonPseudocyclicStronglyRegularGraph
Failed example: L = sum(i*(r[a]r[b]) for i,(a,b) in zip(range(1,len(ff)+1), ff)); L Expected: [ 0 1 1 3 2 4 3 4 2] [1 0 1 4 3 2 2 3 4] [ 1 1 0 2 4 3 4 2 3] [ 3 4 2 0 1 1 3 2 4] [ 2 3 4 1 0 1 4 3 2] [ 4 2 3 1 1 0 2 4 3] [3 2 4 3 4 2 0 1 1] [4 3 2 2 3 4 1 0 1] [2 4 3 4 2 3 1 1 0] Got: [ 0 1 4 2 3 1 4 2 3] [1 0 3 4 4 1 2 3 2] [4 3 0 1 2 2 4 3 1] [2 4 1 0 4 3 3 2 1] [ 3 4 2 4 0 2 1 1 3] [ 1 1 2 3 2 0 3 4 4] [ 4 2 4 3 1 3 0 1 2] [ 2 3 3 2 1 4 1 0 4] [3 2 1 1 3 4 2 4 0]
This is an ordering issue related to method automorphism_group
. The way the automorphism group is computed depends on a ordering of the vertices. Currently:
 for the
'sage'
algorithm, the default order islist(G)
, but settingpartition=[G.vertices()]
will change that ordersage: G = graphs.PaleyGraph(9) sage: G.automorphism_group(algorithm='sage') Permutation Group with generators [(1,2)(a,a + 2)(2*a,2*a + 1), (1,2*a + 2)(2,a + 1)(a + 2,2*a + 1), (0,1)(a + 1,a + 2)(2*a,2*a + 2)] sage: G.automorphism_group(algorithm='sage', partition=[list(G)]) Permutation Group with generators [(1,2)(a,a + 2)(2*a,2*a + 1), (1,2*a + 2)(2,a + 1)(a + 2,2*a + 1), (0,1)(a + 1,a + 2)(2*a,2*a + 2)] sage: G.automorphism_group(algorithm='sage', partition=[list(G)[::1]]) Permutation Group with generators [(2*a + 1,2*a)(a + 2,a)(2,1), (2*a + 1,0)(2*a,a + 1)(a,1), (2*a + 2,2*a + 1)(a + 1,a)(2,0)]
 for
'bliss'
, the order is alwayslist(G)
and the order list(G)
is not always the same in py2 and py3...
So, in this ticket, we do
 ensure that the ordering with
'sage'
and'bliss'
is the same inautomorphism_group
andcanonical_label
/canonical_form
 clean bliss to avoid for instance indexing a dictionary with a possibly not hashable key. The new solution is slower but safe.
 specify the partition in the doctest of
MathonPseudocyclicStronglyRegularGraph
to make the doctest stable with py2 and py3
Other doctests are still failing with py3 and bliss and could be fixed in another ticket.
Change History (10)
comment:1 Changed 7 weeks ago by
 Branch set to public/graphs/27571_automorphism_group
 Commit set to 45630b83893e2242dd9585778d326c4ca33d7d90
 Description modified (diff)
 Status changed from new to needs_review
comment:2 Changed 7 weeks ago by
 Branch changed from public/graphs/27571_automorphism_group to public/graphs/27571_automorphism
 Commit changed from 45630b83893e2242dd9585778d326c4ca33d7d90 to 88bde074188d451a70022cdaa6f592199e42d387
previous branch was not correct (direct modification of develop. oups..)
New commits:
88bde07  trac #27571: fix a doctest in MathonPseudocyclicStronglyRegularGraph

comment:3 Changed 7 weeks ago by
 Commit changed from 88bde074188d451a70022cdaa6f592199e42d387 to cedcb226dee96aa3959eb134242b98cd4bb65120
Branch pushed to git repo; I updated commit sha1. New commits:
cedcb22  trac #27571: clean bliss, canonical_form, and automorphism_group

comment:4 Changed 7 weeks ago by
 Description modified (diff)
 Summary changed from py3: automorphism_group and doctest in MathonPseudocyclicStronglyRegularGraph to py3: automorphism_group, canonical_label, canonical_form and doctest in MathonPseudocyclicStronglyRegularGraph
comment:5 Changed 7 weeks ago by
 Commit changed from cedcb226dee96aa3959eb134242b98cd4bb65120 to 9006edba8dcff2c3642bbbc67d2cb8205ad0d531
Branch pushed to git repo; I updated commit sha1. New commits:
9006edb  trac #27571: remove not tested tag in petersen_family

comment:6 Changed 7 weeks ago by
With py3 I regularly tag has not tested the doctest of pertersen_family
. This is a bug reported in #26800...
comment:7 Changed 7 weeks ago by
 Cc tscrim dimpase added
comment:8 Changed 7 weeks ago by
 Commit changed from 9006edba8dcff2c3642bbbc67d2cb8205ad0d531 to 8fcd5842211b9a469d3a631cb7f28cdc1a944be1
comment:9 Changed 7 weeks ago by
 Description modified (diff)
comment:10 Changed 4 weeks ago by
 Description modified (diff)
I tried to investigate further on the possible cause of the issues with automorphism_group
and the Python3 failing doctests in src/sage/graphs/generators/families.py
.
The good news is that we have the same result with 'bliss'
and 'sage'
sage: G = graphs.PaleyGraph(9) sage: a = G.automorphism_group(partition=[sorted(G)]) sage: it = (x for x in a.normal_subgroups() if x.order() == 9) sage: subg = next(iter(it)) sage: r = [matrix(libgap.PermutationMat(libgap(z), 9).sage()) ....: for z in subg] sage: ff = list(map(lambda y: (y[0]1,y[1]1), ....: Permutation(map(lambda x: 1+r.index(x^1), r)).cycle_tuples()[1:])) sage: L = sum(i*(r[a]r[b]) for i,(a,b) in zip(range(1,len(ff)+1), ff)); L [ 0 1 1 3 2 4 3 4 2] [1 0 1 4 3 2 2 3 4] [ 1 1 0 2 4 3 4 2 3] [ 3 4 2 0 1 1 3 2 4] [ 2 3 4 1 0 1 4 3 2] [ 4 2 3 1 1 0 2 4 3] [3 2 4 3 4 2 0 1 1] [4 3 2 2 3 4 1 0 1] [2 4 3 4 2 3 1 1 0] sage: G.relabel() sage: G3x3=graphs.MathonPseudocyclicStronglyRegularGraph(2,G=G,L=L) sage: G3x3.is_strongly_regular(parameters=True) (441, 220, 109, 110) sage: G3x3.automorphism_group(algorithm="bliss").order() # optional  bliss 3 # < expect 27 in Python 2 sage: G3x3.automorphism_group(algorithm="sage").order() # long time 3 # < expect 27 in Python 2
The issue may come from PermutationGroup
that is used in both case...
New commits:
trac #27571: fix a doctest in families.py