Opened 4 years ago

Closed 4 years ago

Last modified 3 years ago

#14319 closed enhancement (fixed)

Automorphism group with labeled vertices

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: dimpase, nthiery, hivert Merged in: sage-5.10.beta2
Authors: Nathann Cohen Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14291, #14250, #14477, #14435 Stopgaps:

Description (last modified by ncohen)

Permutation groups used to support only 1...n elements, but that is not the case anymore. We can return automorphism groups that do not need to be relabeled, and that is GREAT :-P

Apply

Attachments (4)

trac_14319-from_list_to_domain.patch (7.4 KB) - added by ncohen 4 years ago.
trac_14319_fix_fan_isomorphism.patch (6.6 KB) - added by vbraun 4 years ago.
Updated patch
trac_14319.patch (22.6 KB) - added by ncohen 4 years ago.
trac_14319-empty.patch (10.3 KB) - added by ncohen 4 years ago.

Download all attachments as: .zip

Change History (64)

comment:1 Changed 4 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

I hope the patchbot will like this one. I'm pretty sure that it will break 1000 doctests :-P

Nathann

comment:2 follow-up: Changed 4 years ago by dimpase

What are the allowed labels/doman elements of the underlying permutation groups? Can they be, say, tuples?

comment:3 in reply to: ↑ 2 Changed 4 years ago by ncohen

What are the allowed labels/doman elements of the underlying permutation groups? Can they be, say, tuples?

Well, it lookslike it can be anything that can be hashed. A PermutationGroup contains its own dictionary of "Sage things" <-> "Gap Things" and does the translations, soo... :-)

Nathann

Last edited 4 years ago by ncohen (previous) (diff)

comment:4 Changed 4 years ago by ncohen

  • Dependencies set to #14291

comment:5 Changed 4 years ago by vbraun

Various docstrings need fixing as they explicitly refer to integers, for example list():

Returns list of the images of the integers from 1 to n under this
permutation as a list of Python ints.

comment:6 Changed 4 years ago by ncohen

Where does this docstring come from ?

comment:7 follow-up: Changed 4 years ago by vbraun

Its in sage/groups/perm_gps/permgroup_element.pyx

comment:8 in reply to: ↑ 7 Changed 4 years ago by ncohen

Its in sage/groups/perm_gps/permgroup_element.pyx

Just for the record, #10335 is where this should have been done in the first place >_<

Nathann

comment:9 Changed 4 years ago by ncohen

This being said, I have no idea what to do with this list method. It just has no meaning if the elements are not integers :-/

Nathann

comment:10 follow-up: Changed 4 years ago by ncohen

Patch updated ! I did not touch list(). What do you think we should do with it ? Update its docstring to say "returns the domain" ? Looks like this is all it is used for. And hopefully, because doing otherwise would assume that it is only defined on integers.

Nathann

comment:11 follow-up: Changed 4 years ago by vbraun

I would be in favor of having a domain method on the permutation group elements and deprecate list.

comment:12 Changed 4 years ago by vbraun

  • Description modified (diff)

comment:13 in reply to: ↑ 11 Changed 4 years ago by ncohen

  • Description modified (diff)

I would be in favor of having a domain method on the permutation group elements and deprecate list.

Done in this new patch ! Thank you for looking at fan_isomorphism :-)

Nathann

comment:14 Changed 4 years ago by ncohen

  • Dependencies changed from #14291 to #14291, #14250

Rebased on top of #14250 which is in 5.9.beta1.

Nathann

comment:15 Changed 4 years ago by ncohen

Apply trac_14319.patch, trac_14319_fix_fan_isomorphism.patch, trac_14319-from_list_to_domain.patch

Changed 4 years ago by ncohen

comment:16 Changed 4 years ago by vbraun

You forgot at least one corner case, if the automorphism group is trivial then still need to remember the domain:

sage: Graph({'a':['a'], 'b':[]}).automorphism_group()
Permutation Group with generators [()]
sage: Graph({'a':['a'], 'b':[]}).automorphism_group().domain()
{1}

Changed 4 years ago by vbraun

Updated patch

comment:17 Changed 4 years ago by ncohen

  • Description modified (diff)

Apply trac_14319.patch, trac_14319_fix_fan_isomorphism.patch, trac_14319-from_list_to_domain.patch, trac_14319-empty.patch

comment:18 Changed 4 years ago by ncohen

Updated.

Nathann

comment:19 Changed 4 years ago by vbraun

On sage-5.9.beta5 A number of doctests fail of the sort:

File "devel/sage/sage/combinat/tableau.py", line 1613, in sage.combinat.tableau.Tableau.row_stabilizer
Failed example:
    rs.one().list()
Expected:
    [1, 2, 3]
Got:
    doctest:1: DeprecationWarning: list is deprecated. Please use domain instead.
    See http://trac.sagemath.org/14319 for details.
    [1, 2, 3]

comment:20 Changed 4 years ago by ncohen

Updated.

Nathann

comment:21 Changed 4 years ago by vbraun

Still get DeprecationWarning: list is deprecated failures (sage-5.9.beta5):

sage -t devel/sage/sage/rings/number_field/number_field.py  # 1 doctest failed
sage -t devel/sage/sage/crypto/classical.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/tableau_tuple.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/words/finite_word.py  # 2 doctests failed
sage -t devel/sage/sage/rings/number_field/galois_group.py  # 1 doctest failed
sage -t devel/sage/sage/rings/number_field/number_field_ideal.py  # 1 doctest failed
sage -t devel/sage/sage/coding/linear_code.py  # 1 doctest failed
sage -t devel/sage/doc/en/bordeaux_2008/nf_galois_groups.rst  # 1 doctest failed
sage -t devel/sage/sage/modular/arithgroup/arithgroup_perm.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/permutation.py  # 2 doctests failed
sage -t devel/sage/sage/structure/sage_object.pyx  # 1 doctest failed
sage -t devel/sage/sage/modular/arithgroup/farey_symbol.pyx  # 1 doctest failed
sage -t devel/sage/sage/coding/binary_code.pyx  # 2 doctests failed
sage -t devel/sage/sage/combinat/symmetric_group_representations.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/dyck_word.py  # 1 doctest failed
sage -t devel/sage/sage/modular/arithgroup/congroup_generic.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/symmetric_group_algebra.py  # 1 doctest failed
sage -t devel/sage/sage/categories/finite_permutation_groups.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/species/permutation_species.py  # 1 doctest failed
Last edited 4 years ago by vbraun (previous) (diff)

comment:22 Changed 4 years ago by ncohen

What the heeeeeeeeelll ?? I tested this patch one thousand times >_<

Nathann

comment:23 Changed 4 years ago by ncohen

Updated ! O_O;;;;;

Nathann

comment:24 follow-up: Changed 4 years ago by vbraun

Can you just run a make ptest? There are still lots of places left:

sage -t devel/sage/sage/rings/number_field/number_field.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/words/finite_word.py  # 2 doctests failed
sage -t devel/sage/sage/combinat/tableau_tuple.py  # 1 doctest failed
sage -t devel/sage/sage/coding/binary_code.pyx  # 2 doctests failed
sage -t devel/sage/sage/crypto/classical.py  # 1 doctest failed
sage -t devel/sage/sage/coding/linear_code.py  # 1 doctest failed
sage -t devel/sage/sage/rings/number_field/galois_group.py  # 1 doctest failed
sage -t devel/sage/sage/modular/arithgroup/arithgroup_perm.py  # 1 doctest failed
sage -t devel/sage/sage/rings/number_field/number_field_ideal.py  # 1 doctest failed
sage -t devel/sage/sage/structure/sage_object.pyx  # 1 doctest failed
sage -t devel/sage/doc/en/bordeaux_2008/nf_galois_groups.rst  # 1 doctest failed
sage -t devel/sage/sage/combinat/permutation.py  # 2 doctests failed
sage -t devel/sage/sage/modular/arithgroup/farey_symbol.pyx  # 1 doctest failed
sage -t devel/sage/sage/combinat/symmetric_group_representations.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/dyck_word.py  # 1 doctest failed
sage -t devel/sage/sage/modular/arithgroup/congroup_generic.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/symmetric_group_algebra.py  # 1 doctest failed
sage -t devel/sage/sage/categories/finite_permutation_groups.py  # 1 doctest failed
sage -t devel/sage/sage/combinat/species/permutation_species.py  # 1 doctest failed

comment:25 in reply to: ↑ 24 Changed 4 years ago by ncohen

Can you just run a make ptest? There are still lots of places left:

I did, and all these tests pass.

Nathann

comment:26 Changed 4 years ago by vbraun

Do you have any other patches applied?

trac_14291-v2.patch
trac_14291_reviewer.patch
trac_14319.patch
trac_14319-from_list_to_domain.patch
trac_14319_fix_fan_isomorphism.patch
trac_14319-empty.patch

None of these patches touches sage/combinat/tableau_tuple.py, for example.

comment:27 Changed 4 years ago by vbraun

Or you might have an old version of trac_14319-from_list_to_domain.patch, since this patch introduced the deprecation warning.

comment:28 Changed 4 years ago by ncohen

tableau_tuple is modified by the version of trac_14319-empty.patch I uploaded earlier. You can check it on the html version of the patch : http://trac.sagemath.org/sage_trac/attachment/ticket/14319/trac_14319-empty.patch

In case it may be related : the patchbot sees down. I do not know how you download the patch files, but I had to do it manually because my scripts rely on the patchbot for that... But really, the HTML version of the patch you get when you click on it, on this trac ticket, does modify tableau_tuple.

Nathann

comment:29 Changed 4 years ago by vbraun

Ok, seems like I tripped yet again over #11813

comment:30 Changed 4 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

Looks good to me

comment:31 Changed 4 years ago by ncohen

Yeahhhhhhhhhhhhhhhhhhhhhhhh!! Thank you soooooo much ! I love that patch :-PPP

Nathann

comment:32 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.9 to sage-5.10

comment:33 Changed 4 years ago by ncohen

NOoooooooooooooooooooooooooooooooooooooo :-PPPPPP

Nathann

comment:34 Changed 4 years ago by jdemeyer

  • Dependencies changed from #14291, #14250 to #14291, #14250, #14477, #14435
  • Status changed from positive_review to needs_work
  • Work issues set to rebase

Please rebase to #14477 + #14435.

comment:35 Changed 4 years ago by ncohen

Comeeeee ooooooooonnnnnnnnn... This patch is hell to rebase T_T

Sigh... T_T

Will do it... T_T

Nathann

Changed 4 years ago by ncohen

comment:36 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

Hmmmmmmm... Was not that bad after all :-P

Nathann

comment:37 Changed 4 years ago by ncohen

Apply trac_14319.patch, trac_14319_fix_fan_isomorphism.patch, trac_14319-from_list_to_domain.patch, trac_14319-empty.patch

comment:38 Changed 4 years ago by jdemeyer

  • Work issues rebase deleted

comment:39 Changed 4 years ago by jdemeyer

  • Status changed from positive_review to needs_work

On various systems:

sage -t --long devel/sage/sage/homology/simplicial_complex.py
**********************************************************************
File "devel/sage/sage/homology/simplicial_complex.py", line 3149, in sage.homology.simplicial_complex.SimplicialComplex.automorphism_group
Failed example:
    group.domain()
Expected:
    {1, 2, 3, 'a'}
Got:
    {'a', 1, 2, 3}
**********************************************************************

comment:40 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

If it works with a Graph's vertices, it should work there too... :-P

They're now sorted in the doctest !

Nathann

P.S. : And just to make it clear, it passed all tests on my two machines... :-/

comment:41 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Nonono they are already sorted in the set output. The problem is that python compares int and string by address, which depends on memory layout. The best fix for the doctest would be to have string labels for the whole domain.

comment:42 Changed 4 years ago by ncohen

Oh. I thought that it would compare types. Okayokay, then !

Nathann

comment:43 Changed 4 years ago by ncohen

Fixed again !

sage: set(group.domain()) == set(Z.vertices())
True

Is that ok Volker ? I don't want Jeroen to yell at me again. Nor to send to sage-devel (without naming me) all my past mistakes... :-P

Nathann

comment:44 Changed 4 years ago by vbraun

Thats works but is fugly.. how about changing the simplicial complex to

sage: Z = SimplicialComplex([['1', '2'],['2', '3', 'a']])

Changed 4 years ago by ncohen

comment:45 Changed 4 years ago by ncohen

  • Status changed from needs_work to positive_review

Feels like it's cheating. Plus it's nice to test weird inputs too. But done.

Nathann

comment:46 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2

comment:47 Changed 4 years ago by jdemeyer

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:48 in reply to: ↑ 10 ; follow-up: Changed 4 years ago by nthiery

Replying to ncohen:

Patch updated ! I did not touch list(). What do you think we should do with it ? Update its docstring to say "returns the domain" ? Looks like this is all it is used for. And hopefully, because doing otherwise would assume that it is only defined on integers.

Damned, I missed this. The list method is important! It gives the permutation in list notation, and I am using it in my class tomorrow! Ok, the meaning is a bit dubious when the domain is any set, but I guess the following semantic would make sense:

  • domain(): returns self.parent().domain() (if at all needed)
  • list(): returns [self(i) for i in self.parent().domain()]
  • tuple(): returns tuple(self.list())

If you agree with the above, I'll create a new ticket. And ignore the warning in class tomorrow ...

comment:49 in reply to: ↑ 48 ; follow-up: Changed 4 years ago by ncohen

Yoooooooooo !!

Damned, I missed this.

Looks like I added you to the Cc when I created the ticket, though. And Florent, too.

The list method is important! It gives the permutation in list notation, and I am using it in my class tomorrow!

Yeah well, you may need it and everything but it isn't even defined properly.

Ok, the meaning is a bit dubious when the domain is any set

DUBIOUS ? Come on, it has no meaning whatsoever. Other than what "domain" returns.

but I guess the following semantic would make sense:

  • domain(): returns self.parent().domain() (if at all needed)
  • list(): returns [self(i) for i in self.parent().domain()]
  • tuple(): returns tuple(self.list())

If you agree with the above, I'll create a new ticket. And ignore the warning in class tomorrow ...

Why don't you just add some lines to the constructor of Permutation ? You could just write p = Permutation(your_permutation_group_element). That would have a meaning.

What would a .list() function do in PermutationGroupElement otherwise ? Hell, what does .tuple() do there too ? It's not like tuple(a.domain()) is so long that it needs a function of its own O_o

Nathann

comment:50 in reply to: ↑ 49 ; follow-up: Changed 4 years ago by nthiery

Replying to ncohen:

Looks like I added you to the Cc when I created the ticket, though. And Florent, too.

Sure, I take the blame for not spotting this and suggesting something different back then.

DUBIOUS ? Come on, it has no meaning whatsoever. Other than what "domain" returns.

Yes it does! When the domain is 1...n it gives you the permutation in the usual list notation, which is a basic feature! And otherwise it still shows how the elements of the domain are permuted which is a worthwhile information; it does not seem ridiculous to me to do:

sage: for sigma in SymmetricGroup(['a','b','c']): print sigma.list()
['a', 'b', 'c']
['a', 'c', 'b']
['b', 'a', 'c']
['b', 'c', 'a']
['c', 'a', 'b']
['c', 'b', 'a']

If there is something to be contested it's that self.domain() returns the domain with its elements permuted; I would just return the domain of the parent (like other functions do in Sage).

comment:51 in reply to: ↑ 50 Changed 4 years ago by ncohen

Yoooooo !

Yes it does! When the domain is 1...n it gives you the permutation in the usual list notation, which is a basic feature!

I understand that this information is useful in this case, the scope of PermutationGroupElement is much larger than that.

And otherwise it still shows how the elements of the domain are permuted which is a worthwhile information;

Isn't that machine-dependent when domain is a set ?

If there is something to be contested it's that self.domain() returns the domain with its elements permuted; I would just return the domain of the parent (like other functions do in Sage).

No objection to that.

What would be the problem of a .to_permutation method (the findstat guys would love that) which would output the permutation of 1...n corresponding to the element ? When the domain is not 1...n they could be relabeled "in any way" (i.e. the ordering of .domain()) to return a permutation of 1...n, and when the domain IS 1...n then it could return the list that you expect ?

Or you could also implement something in the constructor of Permutation which would do the same, what do you think ?

Why the hell do we have both Permutation and PermutationGroupElement by the way ?

Nathann

comment:52 Changed 3 years ago by jason

I just ran into the .list() deprecation warning as well, and was a bit confused by p.domain() permuting the domain. nthiery: were you planning on opening a new ticket to have p.domain() just give back the parent's domain, and restoring the p.list()? I'm deciding whether to ignore the deprecation or to update my code.

comment:53 Changed 3 years ago by ncohen

Ohhhhhhhh... An unanswered question from 3 months ago :-P

Nathann

comment:54 Changed 3 years ago by ncohen

Jason : what would you want .list() to return except what .domain() returns ? What it returns at the moment only has a meaning for specific sets of vertices, and this class is meant to handle everything !

comment:55 Changed 3 years ago by jason

My confusion is just about the naming of .domain(). At first, it sounded like if p was a permutation group element, then p.domain() would just give me back the original domain of the permutation group, and p.list() would do what it has done in the past---a list representation of the permutation (exactly what nthiery describes). Even after reading the patch, I had to double-check that domain actually did permute the domain, because it sounds like it shouldn't to me.

comment:56 Changed 3 years ago by jason

Sorry---a more direct answer: it makes more sense to me if .domain() and .list() do exactly what nthiery proposes above.

comment:57 Changed 3 years ago by jason

Put another way: to me, it's confusing that p.parent().domain() and p.domain() return different lists.

comment:58 Changed 3 years ago by ncohen

Oh. I see. Well, p.parent().domain() probably makes more sense indeed. Then I would vote for removing .domain() too. My point is that you cannot give a meaning to .list() unless for "the subset of groups that are of personal interest to you" (i.e. those that act on integers) and for this reason I do not think this function should exist. I mean, of course you can define "list" but you cannot define what is of interest to you, i.e. that the output of .list() defines the permutation itself. This only works when all elements are integers, and there already is a class for that, i.e. permutations.

How are p.parent().domain() and p.domain() different ? If it is only the order, there is nothing wrong in that. Those things are morally "sets", and only returned as tuples/lists for efficiency reasons I guess.

Nathann

comment:59 follow-up: Changed 3 years ago by jason

I'm confused. What is the problem with renaming the current p.domain() to p.list(), and saying p.list() is going to return the list representation of the permutation (in terms of the domain)? That's how it always was---but before, the domain was always [1...n]. In other words, if you aren't using the domain argument of the permutation group, p.list() does what it always has done. If you are using the domain argument, it makes sense that p.list() will speak in terms of the domain.

Last edited 3 years ago by jason (previous) (diff)

comment:60 in reply to: ↑ 59 Changed 3 years ago by ncohen

I'm confused. What is the problem with renaming the current p.domain() to p.list(), and saying p.list() is going to return the list representation of the permutation (in terms of the domain)? That's how it always was---but before, the domain was always [1...n]. In other words, if you aren't using the domain argument of the permutation group, p.list() does what it always has done. If you are using the domain argument, it makes sense that p.list() will speak in terms of the domain.

I am only worried of what I saw in the code of Permutations : that there are assumptions made by some developpers which are not known by others, and that code will end up being broken because the assumptions are never checked. .list() does not *mean* that "the output represents the permutations when the elements are integers". Having a .to_permutation() function which would return a Permutation object (i.e. that only handle integers) and a dictionary associating the elements of the PermutationGroupElement to integers is okay.

I just want to be sure that the code stays correct. Right now the list that is returned by .list() is a private attribute, and with a name like that there is absolutely no reason to believe that a code which creates this private attribute should ensure the property that you expect.

Exactly like the labeling of a poset's vertices with integers is a linear extension : that is assumed nearly everywhere in poset code, and you will sweat for a while before finding it out. If this variable was named "linear_extension" there would be no problem, though.

And changing the code of list to ensure that the list it returns satisfies the property that you expect would ensure that the code is good, but .list() really isn't right name for such a function. If you need "the integer permutation represented by a PermutationGroupElement, it looks like what you want is a way to create a Permutation object from a PermutationGroupElement.

Well. What do you think ?

Nathann

Note: See TracTickets for help on using tickets.