bliss automorphism_group() shouldn't sort vertices

[jdemeyer]

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.

[dcoudert]

I had a quick look at PermutationGroup (documentation is incomplete) and then at PermutationGroup_generic... According to the documentation, parameter domain must be a sorted list of integer, but in bliss automorphism_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 should domain be sorted ? Why can we call PermutationGroup with non-integer vertices/domain ?

An expert in PermutationGroup is certainly needed here.

[stumpc5]

Iirc, I have to relabel the vertices by 0 .. n-1 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?

[dcoudert]

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.

[jdemeyer]

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 group-with-unsorted-domain to an actual concrete automorphism.

[jdemeyer]

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.

[jdemeyer]

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")

[jdemeyer]

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

[dimpase]

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

[tscrim]

Okay, this works as it treats the permutation as a map (instead of in 1-line 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.

[dimpase]

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.

[jdemeyer]

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

[dimpase]

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 non-efficient computation - it should return an iterator, or a generating set for the group in question, not a list of permutations.