#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: |
Description (last modified by )
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)
Change History (64)
comment:1 Changed 10 years ago by
Description: | modified (diff) |
---|---|
Status: | new → needs_review |
comment:2 follow-up: 3 Changed 10 years ago by
What are the allowed labels/doman elements of the underlying permutation groups? Can they be, say, tuples?
comment:3 Changed 10 years ago by
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
comment:4 Changed 10 years ago by
Dependencies: | → #14291 |
---|
comment:5 Changed 10 years ago by
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:8 Changed 10 years ago by
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
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: 48 Changed 10 years ago by
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: 13 Changed 10 years ago by
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
Description: | modified (diff) |
---|
comment:13 Changed 10 years ago by
Description: | modified (diff) |
---|
I would be in favor of having a
domain
method on the permutation group elements and deprecatelist
.
Done in this new patch ! Thank you for looking at fan_isomorphism
:-)
Nathann
comment:14 Changed 10 years ago by
Dependencies: | #14291 → #14291, #14250 |
---|
Rebased on top of #14250 which is in 5.9.beta1.
Nathann
comment:15 Changed 10 years ago by
Apply trac_14319.patch, trac_14319_fix_fan_isomorphism.patch, trac_14319-from_list_to_domain.patch
Changed 10 years ago by
Attachment: | trac_14319-from_list_to_domain.patch added |
---|
comment:16 Changed 10 years ago by
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}
comment:17 Changed 10 years ago by
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:19 Changed 10 years ago by
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:21 Changed 10 years ago by
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
comment:22 Changed 10 years ago by
What the heeeeeeeeelll ?? I tested this patch one thousand times >_<
Nathann
comment:24 follow-up: 25 Changed 10 years ago by
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 Changed 10 years ago by
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
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
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
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:30 Changed 10 years ago by
Reviewers: | → Volker Braun |
---|---|
Status: | needs_review → positive_review |
Looks good to me
comment:31 Changed 10 years ago by
Yeahhhhhhhhhhhhhhhhhhhhhhhh!! Thank you soooooo much ! I love that patch :-PPP
Nathann
comment:32 Changed 10 years ago by
Milestone: | sage-5.9 → sage-5.10 |
---|
comment:34 Changed 10 years ago by
Dependencies: | #14291, #14250 → #14291, #14250, #14477, #14435 |
---|---|
Status: | positive_review → needs_work |
Work issues: | → rebase |
comment:35 Changed 10 years ago by
Comeeeee ooooooooonnnnnnnnn... This patch is hell to rebase T_T
Sigh... T_T
Will do it... T_T
Nathann
Changed 10 years ago by
Attachment: | trac_14319.patch added |
---|
comment:36 Changed 10 years ago by
Status: | needs_work → positive_review |
---|
Hmmmmmmm... Was not that bad after all :-P
Nathann
comment:37 Changed 10 years ago by
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
Work issues: | rebase |
---|
comment:39 Changed 10 years ago by
Status: | positive_review → 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 10 years ago by
Status: | needs_work → 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 10 years ago by
Status: | positive_review → 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 10 years ago by
Oh. I thought that it would compare types. Okayokay, then !
Nathann
comment:43 Changed 10 years ago by
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
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
Attachment: | trac_14319-empty.patch added |
---|
comment:45 Changed 10 years ago by
Status: | needs_work → positive_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
Merged in: | → sage-5.10.beta2 |
---|
comment:47 Changed 10 years ago by
Resolution: | → fixed |
---|---|
Status: | positive_review → closed |
comment:48 follow-up: 49 Changed 9 years ago by
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 follow-up: 50 Changed 9 years ago by
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 follow-up: 51 Changed 9 years ago by
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 Changed 9 years ago by
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
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:54 Changed 9 years ago by
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
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
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
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
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: 60 Changed 9 years ago by
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.
comment:60 Changed 9 years ago by
I'm confused. What is the problem with renaming the current
p.domain()
top.list()
, and sayingp.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 thatp.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
I hope the patchbot will like this one. I'm pretty sure that it will break 1000 doctests
:-P
Nathann