Automorphism group with labeled vertices

[nathanncohen]

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

• attachment: trac_14319.patch
• attachment: trac_14319_fix_fan_isomorphism.patch
• attachment: trac_14319-from_list_to_domain.patch
• attachment: trac_14319-empty.patch

Depends on #14291
Depends on #14250
Depends on #14477
Depends on #14435

CC: @dimpase @nthiery @hivert

Component: graph theory

Author: Nathann Cohen

Reviewer: Volker Braun

Merged: sage-5.10.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14319

[nathanncohen]

comment:1

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

Nathann

[dimpase]

comment:2

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

[nathanncohen]

comment:3

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

[nathanncohen]

Dependencies: #14291

[vbraun]

comment:5

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.

[nathanncohen]

comment:6

Where does this docstring come from ?

[vbraun]

comment:7

Its in sage/groups/perm_gps/permgroup_element.pyx

[nathanncohen]

comment:8

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

[nathanncohen]

comment:9

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

[nathanncohen]

comment:10

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

[vbraun]

comment:11

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

[nathanncohen]

comment:13

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

[nathanncohen]

comment:14

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

Nathann

[nathanncohen]

Changed dependencies from #14291 to #14291, #14250

[nathanncohen]

comment:15

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

[nathanncohen]

Attachment: trac_14319-from_list_to_domain.patch.gz

[vbraun]

comment:16

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}

[vbraun]

Updated patch

[nathanncohen]

comment:17

Attachment: trac_14319_fix_fan_isomorphism.patch.gz

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

[vbraun]

comment:41

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.

[nathanncohen]

comment:42

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

Nathann

[nathanncohen]

comment:43

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

[vbraun]

comment:44

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

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

[nathanncohen]

Attachment: trac_14319-empty.patch.gz

[nathanncohen]

comment:45

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

Nathann

[jdemeyer]

Merged: sage-5.10.beta2

[nthiery]

comment:48

Replying to @nathanncohen:

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

[nathanncohen]

comment:49

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

[nthiery]

comment:50

Replying to @nathanncohen:

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

[nathanncohen]

comment:51

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

[jasongrout]

comment:52

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.

[nathanncohen]

comment:53

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

Nathann

[nathanncohen]

comment:54

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 !

[jasongrout]

comment:55

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.

[jasongrout]

comment:56

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

[jasongrout]

comment:57

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

[nathanncohen]

comment:58

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

[jasongrout]

comment:59

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.

[nathanncohen]

comment:60

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