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: sage-8.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 dcoudert)

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 is list(G), but setting partition=[G.vertices()] will change that order
    sage: 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 always list(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 in automorphism_group and canonical_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 dcoudert

  • Branch set to public/graphs/27571_automorphism_group
  • Commit set to 45630b83893e2242dd9585778d326c4ca33d7d90
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

45630b8trac #27571: fix a doctest in families.py

comment:2 Changed 7 weeks ago by dcoudert

  • 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:

88bde07trac #27571: fix a doctest in MathonPseudocyclicStronglyRegularGraph

comment:3 Changed 7 weeks ago by git

  • Commit changed from 88bde074188d451a70022cdaa6f592199e42d387 to cedcb226dee96aa3959eb134242b98cd4bb65120

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

cedcb22trac #27571: clean bliss, canonical_form, and automorphism_group

comment:4 Changed 7 weeks ago by dcoudert

  • 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 git

  • Commit changed from cedcb226dee96aa3959eb134242b98cd4bb65120 to 9006edba8dcff2c3642bbbc67d2cb8205ad0d531

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

9006edbtrac #27571: remove not tested tag in petersen_family

comment:6 Changed 7 weeks ago by dcoudert

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 dcoudert

  • Cc tscrim dimpase added

comment:8 Changed 7 weeks ago by git

  • Commit changed from 9006edba8dcff2c3642bbbc67d2cb8205ad0d531 to 8fcd5842211b9a469d3a631cb7f28cdc1a944be1

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

7598b52trac #27571: Merged with 8.8.beta0
8fcd584trac #27571: mark a doctest printing a dictionary py2 py3

comment:9 Changed 7 weeks ago by dcoudert

  • Description modified (diff)

comment:10 Changed 4 weeks ago by dcoudert

  • 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...

Note: See TracTickets for help on using tickets.