Opened 3 years ago
Closed 3 years ago
#27123 closed defect (fixed)
bliss automorphism_group() shouldn't sort vertices
Reported by:  jdemeyer  Owned by:  

Priority:  major  Milestone:  sage8.7 
Component:  graph theory  Keywords:  
Cc:  dimpase, dcoudert, stumpc5  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  bb167c5 (Commits, GitHub, GitLab)  Commit:  bb167c54b98ab2fbe9502c7d9b1e2813abf7fe1c 
Dependencies:  Stopgaps: 
Description (last modified by )
This sorting was introduced in #25426 to fix a problem with automorphisms_of_rows_and_columns
. Since sorting vertices of graphs is not possible in general, that needs to be reverted.
In fact, the problem was not with bliss but with invalid assumptions made in the method automorphisms_of_rows_and_columns
.
So this ticket reverts the fix for #25426 and replaces it by a correct fix.
Change History (16)
comment:1 followup: ↓ 9 Changed 3 years ago by
comment:2 Changed 3 years ago by
 Cc dimpase stumpc5 added
 Description modified (diff)
comment:3 followup: ↓ 7 Changed 3 years ago by
Iirc, I have to relabel the vertices by 0 .. n1 in order to do the computation. To give a bijection, I sort the vertices of the graph.
We need to revert that since vertices of graphs cannot be sorted in general.
In which sense cannot be sorted ? At least these are hashable objects, so these are sortable according to their hashs, aren't they?
comment:4 Changed 3 years ago by
we cannot sort a list of objects of different types with Python3. Of course we can sort by hash, but it's better to avoid sorting whenever possible.
comment:5 Changed 3 years ago by
For fixing #25426, there shouldn't be need to sort the input to PermutationGroup_generic
. I think that something goes wrong in the translation of that groupwithunsorteddomain to an actual concrete automorphism.
comment:6 Changed 3 years ago by
The problem is really in the automorphisms_of_rows_and_columns
method itself. When reverting #25426, the computed graph automorphism is correct. It's just that the conversion of that to an automorphism of the matrix goes wrong.
comment:7 in reply to: ↑ 3 Changed 3 years ago by
Replying to stumpc5:
In which sense cannot be sorted ?
In this sense:
Python 3.6.3 (default, Mar 13 2018, 19:00:30) [GCC 6.4.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> L = [1, "x"] >>> sorted(L) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: '<' not supported between instances of 'str' and 'int'
(image that you have a graph with vertices 1
and "x"
)
comment:8 Changed 3 years ago by
 Branch set to u/jdemeyer/bliss_automorphism_group___shouldn_t_sort_vertices
comment:9 in reply to: ↑ 1 Changed 3 years ago by
 Commit set to bb167c54b98ab2fbe9502c7d9b1e2813abf7fe1c
 Description modified (diff)
 Status changed from new to needs_review
Replying to dcoudert:
According to the documentation, parameter
domain
must be a sorted list of integer
That documentation is just wrong... even the examples in that file have other domains. I decided that remove that piece of documentation: having wrong documentation is worse than no documentation at all.
New commits:
bb167c5  bliss automorphism_group() shouldn't sort vertices

comment:10 Changed 3 years ago by
I hope Python survives this terrible mess created by this "clever" idea of unsortable things (and the whole string/bytes disaster)... Somebody must have been smoking too much homotopic type theory or something...
comment:11 Changed 3 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
Okay, this works as it treats the permutation as a map (instead of in 1line notation), which does also fix the problem. I think it will end up being a little slower automorphisms_of_rows_and_columns
, but I doubt it will practically matter. So I am setting a positive review.
comment:12 followup: ↓ 13 Changed 3 years ago by
 Status changed from positive_review to needs_work
In matrix2 one sees
B = self.as_bipartite_graph() nrows = self.nrows() ncols = self.ncols()  parts = [list(range(1, nrows + 1)),  list(range(nrows + 1, nrows + ncols + 1))]  A = B.automorphism_group(partition=parts, edge_labels=True) + A = B.automorphism_group(edge_labels=True)
I don't understand why this is mathematically correct. With this change, A may end up bigger than before. E.g. imagine B being symmetric and having all entries 1, then the new way will give an extra automorphism flipping row and columns.
comment:13 in reply to: ↑ 12 Changed 3 years ago by
Replying to dimpase:
then the new way will give an extra automorphism flipping row and columns.
No, that's checked in the code after that:
if p(1) <= nrows: # Check that rows are mapped to rows
comment:14 Changed 3 years ago by
 Status changed from needs_work to positive_review
comment:15 Changed 3 years ago by
OK, it did not cross my mind that in the original code there was a condition which was identically true :)
All in all, this function is an example of horribly nonefficient computation  it should return an iterator, or a generating set for the group in question, not a list of permutations.
comment:16 Changed 3 years ago by
 Branch changed from u/jdemeyer/bliss_automorphism_group___shouldn_t_sort_vertices to bb167c54b98ab2fbe9502c7d9b1e2813abf7fe1c
 Resolution set to fixed
 Status changed from positive_review to closed
I had a quick look at
PermutationGroup
(documentation is incomplete) and then atPermutationGroup_generic
... According to the documentation, parameterdomain
must be a sorted list of integer, but in blissautomorphism_group()
we don't ensure that vertices are integers.I agree that we should not sort vertices in bliss, but there is also something to do in
PermutationGroup**
. Why shoulddomain
be sorted ? Why can we callPermutationGroup
with noninteger vertices/domain ?An expert in
PermutationGroup
is certainly needed here.