#27123 closed defect (fixed)

bliss automorphism_group() shouldn't sort vertices

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-8.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) Commit: bb167c54b98ab2fbe9502c7d9b1e2813abf7fe1c
Dependencies: Stopgaps:

Description (last modified by 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.

Change History (16)

comment:1 follow-up: Changed 11 months ago by 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.

comment:2 Changed 11 months ago by jdemeyer

  • Cc dimpase stumpc5 added
  • Description modified (diff)

comment:3 follow-up: Changed 11 months ago by 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?

comment:4 Changed 11 months ago by 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.

comment:5 Changed 11 months ago by 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.

comment:6 Changed 11 months ago by 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.

comment:7 in reply to: ↑ 3 Changed 11 months ago by 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")

comment:8 Changed 11 months ago by jdemeyer

  • Branch set to u/jdemeyer/bliss_automorphism_group___shouldn_t_sort_vertices

comment:9 in reply to: ↑ 1 Changed 11 months ago by jdemeyer

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

bb167c5bliss automorphism_group() shouldn't sort vertices

comment:10 Changed 11 months ago by 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...

comment:11 Changed 11 months ago by tscrim

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

comment:12 follow-up: Changed 11 months ago by dimpase

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

Last edited 11 months ago by dimpase (previous) (diff)

comment:13 in reply to: ↑ 12 Changed 11 months ago by 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

comment:14 Changed 11 months ago by jdemeyer

  • Status changed from needs_work to positive_review

comment:15 Changed 11 months ago by 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.

comment:16 Changed 11 months ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.