Opened 5 years ago
Closed 5 years ago
#25426 closed defect (fixed)
automorphisms_of_rows_and_columns fails on certain 5x5 matrix if bliss is installed
Reported by:  dimpase  Owned by:  

Priority:  blocker  Milestone:  sage8.3 
Component:  graph theory  Keywords:  
Cc:  stumpc5  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Christian Stump 
Report Upstream:  N/A  Work issues:  
Branch:  db37923 (Commits, GitHub, GitLab)  Commit:  db3792314ac93f966d099c99affb25aac487588c 
Dependencies:  Stopgaps: 
Description
In #24924 bliss was enabled for computing automorphisms of edgecoloured graphs. The latter is used for automorphisms_of_rows_and_columns()
of matrices. For the following matrix j
, with bliss installed, we have failure, found on #25399, see comment 10 there. Namely
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) ...
This is probably due to wrong order of elements in generators produced by the bliss interface:
sage: gj=j.as_bipartite_graph() sage: gj.automorphism_group(edge_labels=True,algorithm="bliss") Permutation Group with generators [(10,2)(1,8)(3,6)(4,9)(5,7), (10,5)(1,6)(2,7)(3,8)(4,9)] sage: gj.automorphism_group(edge_labels=True,algorithm="sage") Permutation Group with generators [(1,3)(2,5)(6,8)(7,10), (1,6)(2,7)(3,8)(4,9)(5,10)]
That (10,2) and (10,5) cycles don't look good...
Change History (16)
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
I have my suspicions that it is not in Permutation
as elements of PermutationGroup
are stored in GAP as lists and converted to cycles for their print representation. So my guess is the creation of the permutation group elements is going wrong somehow.
comment:3 Changed 5 years ago by
well, should Permutation throw an error if it encountered wrong order of elements in a cycle?
specifically, you see that the group is fine, while convering its elements into lists goes nuts...
comment:4 Changed 5 years ago by
I gave the wrong cycles to from_cycles()
and I got the correct output. So I think there is an assumption made about the internal storage of the permutation group element, and these notproperlyordered cycles are saying some (likely undocumenred) internal assumption is violated. I can look into this more tomorrow.
comment:5 Changed 5 years ago by
Okay, so the issue is roughly stemming from the domain being nonstandard from the bliss
group:
sage: cycles = [[(10,2), (1,8), (3,6), (4,9), (5,7)], [(10,5), (1,6), (2,7), (3,8), (4,9)]] sage: PermutationGroup(cycles, domain=[10,1,2,3,4,5,6,7,8,9]) Permutation Group with generators [(10,2)(1,8)(3,6)(4,9)(5,7), (10,5)(1,6)(2,7)(3,8)(4,9)] sage: PermutationGroup(cycles, domain=[1,2,3,4,5,6,7,8,9,10]) Permutation Group with generators [(1,6)(2,7)(3,8)(4,9)(5,10), (1,8)(2,10)(3,6)(4,9)(5,7)]
This generates the outoforder cycles. However, things seem to be generally broken for these permutation group elements:
sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss") sage: G.domain() {10, 1, 2, 3, 4, 5, 6, 7, 8, 9} sage: x = G.gens()[0] sage: x (10,2)(1,8)(3,6)(4,9)(5,7) sage: x._gap_list() [3, 9, 1, 7, 10, 8, 4, 6, 2, 5] sage: x.domain() [2, 8, 10, 6, 9, 7, 3, 5, 1, 4]
So I think there is an implicit assumption that when the domain in [n]
, it should be sorted.
comment:7 followup: 8 Changed 5 years ago by
So in my opinion, Permutation
is doing the correct thing:
sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss") sage: map(Permutation, G) [[10, 1, 2, 3, 4, 5, 6, 7, 8, 9], [5, 6, 7, 8, 9, 10, 1, 2, 3, 4], [2, 8, 10, 6, 9, 7, 3, 5, 1, 4], [7, 3, 5, 1, 4, 2, 8, 10, 6, 9]] sage: list(G) [(), (10,5)(1,6)(2,7)(3,8)(4,9), (10,2)(1,8)(3,6)(4,9)(5,7), (10,7)(1,3)(2,5)(6,8)]
Permutation
rightly has a domain of [1, ..., 10]
, but it is the return trip that is the problem. I think your test in comment:1 is a bit wrong because PermutationGroup
(also rightly) assumes a domain of [1, ..., 10]
. However, there is an issue:
sage: PermutationGroup(map(list, map(Permutation, G)), domain=G.domain()).order() 4 sage: PermutationGroup(map(Permutation, G), domain=G.domain()).order() 1920
in particular PermutationGroup
is ignoring the domain input when given a list of Permutation
's. I am somewhat hesitant to call this a bug given the natural domain of Permutation
(this also is completely broken for nonstandard permutations).
In many ways this is a red herring because automorphisms_of_rows_and_columns
makes the assumption that the domain is [1, ..., nrows]
. I am tempted to have the bliss automorphism_group
method sort the vertices of G
(if able to) before returning the PermutationGroup
.
Thoughts?
comment:8 followup: 9 Changed 5 years ago by
Replying to tscrim:
So in my opinion,
Permutation
is doing the correct thing:sage: G = gj.automorphism_group(edge_labels=True,algorithm="bliss") sage: map(Permutation, G) [[10, 1, 2, 3, 4, 5, 6, 7, 8, 9], [5, 6, 7, 8, 9, 10, 1, 2, 3, 4], [2, 8, 10, 6, 9, 7, 3, 5, 1, 4], [7, 3, 5, 1, 4, 2, 8, 10, 6, 9]]
this makes no sense to me. How come there is no identify permutation in this list?! At best, what we see here is a coset of the Klein 4group...
sage: list(G) [(), (10,5)(1,6)(2,7)(3,8)(4,9), (10,2)(1,8)(3,6)(4,9)(5,7), (10,7)(1,3)(2,5)(6,8)]
Permutation
rightly has a domain of[1, ..., 10]
, but it is the return trip that is the problem. I think your test in comment:1 is a bit wrong becausePermutationGroup
(also rightly) assumes a domain of[1, ..., 10]
. However, there is an issue:sage: PermutationGroup(map(list, map(Permutation, G)), domain=G.domain()).order() 4 sage: PermutationGroup(map(Permutation, G), domain=G.domain()).order() 1920in particular
PermutationGroup
is ignoring the domain input
I don't understand. Domains are, mathematically, sets, not lists.
when given a list of
Permutation
's. I am somewhat hesitant to call this a bug given the natural domain ofPermutation
(this also is completely broken for nonstandard permutations).In many ways this is a red herring because
automorphisms_of_rows_and_columns
makes the assumption that the domain is[1, ..., nrows]
. I am tempted to have the blissautomorphism_group
method sort the vertices ofG
(if able to) before returning thePermutationGroup
.Thoughts?
the background is that to respect edgelabels, the implementation by Christian constucts an auxiliary graph, and then cuts out the relevant subdomain action.
comment:9 Changed 5 years ago by
Replying to dimpase:
Replying to tscrim:
So in my opinion,
Permutation
is doing the correct thing:this makes no sense to me. How come there is no identify permutation in this list?! At best, what we see here is a coset of the Klein 4group...
I don't understand. Domains are, mathematically, sets, not lists.
Perhaps in the strict sense, but here, we need to know what the identity permutation is. So an domain is an ordered set, i.e., a list, and that ordering defines the identity permutation. So in the example above, [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
is the identity.
when given a list of
Permutation
's. I am somewhat hesitant to call this a bug given the natural domain ofPermutation
(this also is completely broken for nonstandard permutations).In many ways this is a red herring because
automorphisms_of_rows_and_columns
makes the assumption that the domain is[1, ..., nrows]
. I am tempted to have the blissautomorphism_group
method sort the vertices ofG
(if able to) before returning thePermutationGroup
.Thoughts?
the background is that to respect edgelabels, the implementation by Christian constucts an auxiliary graph, and then cuts out the relevant subdomain action.
It is that cut out that assumes the domain/identity is [1, ..., nrows]
, which is the source of the problem.
comment:10 Changed 5 years ago by
Branch:  → u/stumpc5/fix_25426 

comment:11 Changed 5 years ago by
Commit:  → db3792314ac93f966d099c99affb25aac487588c 

According to Travis, this fixes the bug (and it indeed does), I haven't really gotten into the hack, though...
New commits:
db37923  fix #25426

comment:12 Changed 5 years ago by
sage: j.automorphisms_of_rows_and_columns() [((), ()), ((1,3)(2,5), (1,3)(2,5))] sage: gj=j.as_bipartite_graph() sage: a = gj.automorphism_group(edge_labels=True,algorithm="bliss") sage: b = gj.automorphism_group(edge_labels=True,algorithm="sage") sage: a == b True
comment:13 Changed 5 years ago by
This gets around the domain issue I noted above. Dima, is this change is okay with you?
comment:14 Changed 5 years ago by
Authors:  → Travis Scrimshaw 

Reviewers:  → Christian Stump 
Status:  new → needs_review 
comment:15 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:16 Changed 5 years ago by
Branch:  u/stumpc5/fix_25426 → db3792314ac93f966d099c99affb25aac487588c 

Resolution:  → fixed 
Status:  positive_review → closed 
In particular, one can see that the order of elements in cycles is important:
whereas having "sage" instead of "bliss" above gives 4 in both outputs. Indeed, it's
Permutation()
that does not like wrongly ordered cycles:Perhaps it should be fixed instead, I don't know (but it's a mess, I recall
ncohen
getting really upset about the quality of the code there...).