Opened 10 years ago

Closed 10 years ago

Last modified 9 years ago

#14319 closed enhancement (fixed)

Automorphism group with labeled vertices

Reported by: Nathann Cohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: Dima Pasechnik, Nicolas M. Thiéry, Florent 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:

Status badges

Description (last modified by Nathann Cohen)

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 Nathann Cohen 10 years ago.
trac_14319_fix_fan_isomorphism.patch (6.6 KB) - added by Volker Braun 10 years ago.
Updated patch
trac_14319.patch (22.6 KB) - added by Nathann Cohen 10 years ago.
trac_14319-empty.patch (10.3 KB) - added by Nathann Cohen 10 years ago.

Download all attachments as: .zip

Change History (64)

comment:1 Changed 10 years ago by Nathann Cohen

Description: modified (diff)
Status: newneeds_review

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

Nathann

comment:2 Changed 10 years ago by Dima Pasechnik

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

comment:3 in reply to:  2 Changed 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen (previous) (diff)

comment:4 Changed 10 years ago by Nathann Cohen

Dependencies: #14291

comment:5 Changed 10 years ago by Volker Braun

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 10 years ago by Nathann Cohen

Where does this docstring come from ?

comment:7 Changed 10 years ago by Volker Braun

Its in sage/groups/perm_gps/permgroup_element.pyx

comment:8 in reply to:  7 Changed 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen

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 Changed 10 years ago by Nathann Cohen

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 Changed 10 years ago by Volker Braun

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

comment:12 Changed 10 years ago by Volker Braun

Description: modified (diff)

comment:13 in reply to:  11 Changed 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen

Dependencies: #14291#14291, #14250

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

Nathann

comment:15 Changed 10 years ago by Nathann Cohen

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

Changed 10 years ago by Nathann Cohen

comment:16 Changed 10 years ago by Volker Braun

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 10 years ago by Volker Braun

Updated patch

comment:17 Changed 10 years ago by Nathann Cohen

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 10 years ago by Nathann Cohen

Updated.

Nathann

comment:19 Changed 10 years ago by Volker Braun

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 10 years ago by Nathann Cohen

Updated.

Nathann

comment:21 Changed 10 years ago by Volker Braun

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 10 years ago by Volker Braun (previous) (diff)

comment:22 Changed 10 years ago by Nathann Cohen

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

Nathann

comment:23 Changed 10 years ago by Nathann Cohen

Updated ! O_O;;;;;

Nathann

comment:24 Changed 10 years ago by Volker Braun

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 10 years ago by Nathann Cohen

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 10 years ago by Volker Braun

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 10 years ago by Volker Braun

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 10 years ago by Nathann Cohen

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 10 years ago by Volker Braun

Ok, seems like I tripped yet again over #11813

comment:30 Changed 10 years ago by Volker Braun

Reviewers: Volker Braun
Status: needs_reviewpositive_review

Looks good to me

comment:31 Changed 10 years ago by Nathann Cohen

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

Nathann

comment:32 Changed 10 years ago by Jeroen Demeyer

Milestone: sage-5.9sage-5.10

comment:33 Changed 10 years ago by Nathann Cohen

NOoooooooooooooooooooooooooooooooooooooo :-PPPPPP

Nathann

comment:34 Changed 10 years ago by Jeroen Demeyer

Dependencies: #14291, #14250#14291, #14250, #14477, #14435
Status: positive_reviewneeds_work
Work issues: rebase

Please rebase to #14477 + #14435.

comment:35 Changed 10 years ago by Nathann Cohen

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

Sigh... T_T

Will do it... T_T

Nathann

Changed 10 years ago by Nathann Cohen

Attachment: trac_14319.patch added

comment:36 Changed 10 years ago by Nathann Cohen

Status: needs_workpositive_review

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

Nathann

comment:37 Changed 10 years ago by Nathann Cohen

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

comment:38 Changed 10 years ago by Jeroen Demeyer

Work issues: rebase

comment:39 Changed 10 years ago by Jeroen Demeyer

Status: positive_reviewneeds_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 10 years ago by Nathann Cohen

Status: needs_workpositive_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 10 years ago by Volker Braun

Status: positive_reviewneeds_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 10 years ago by Nathann Cohen

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

Nathann

comment:43 Changed 10 years ago by Nathann Cohen

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 10 years ago by Volker Braun

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

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

Changed 10 years ago by Nathann Cohen

Attachment: trac_14319-empty.patch added

comment:45 Changed 10 years ago by Nathann Cohen

Status: needs_workpositive_review

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

Nathann

comment:46 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.10.beta2

comment:47 Changed 10 years ago by Jeroen Demeyer

Resolution: fixed
Status: positive_reviewclosed

comment:48 in reply to:  10 ; Changed 9 years ago by Nicolas M. Thiéry

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 ; Changed 9 years ago by Nathann Cohen

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 ; Changed 9 years ago by Nicolas M. Thiéry

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 9 years ago by Nathann Cohen

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 9 years ago by Jason Grout

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 9 years ago by Nathann Cohen

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

Nathann

comment:54 Changed 9 years ago by Nathann Cohen

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 9 years ago by Jason Grout

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 9 years ago by Jason Grout

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

comment:57 Changed 9 years ago by Jason Grout

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

comment:58 Changed 9 years ago by Nathann Cohen

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 Changed 9 years ago by Jason Grout

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 9 years ago by Jason Grout (previous) (diff)

comment:60 in reply to:  59 Changed 9 years ago by Nathann Cohen

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.