Allow automorphism group of a graph to act on the graph's vertex set

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

The current implementation of the automorphism group of a graph always relabels the graph in question to use the vertex set {1,2,...,n+1} and then returns the automorphism group based on this labeling and potentially a translation for the labeling as well.

Needless to say that this is time consuming, confusing and also prone to bugs since if one uses integers as labels (starting at 0 for example) the relabeling might go unnoticed.

As it appears from this sage-devel post it is now possible to use arbitrary domains for permutation groups.

Hence, it would be nice to integrate this change into the automorphism_group function as well.

---

From https://groups.google.com/d/msg/sage-devel/y_TuGhjLYJQ/8YBUmQaNsXUJ

In the long term, I think the right solution is to copy what is done for Galois groups of number fields: depending on a keyword option to automorphism_group(), we should return either the abstract permutation group (as is done now) or a group equipped with an action on the edges and vertices of the graph. David

---

Also what appears to be a 'defect' is that if you have a graph G on say 150 vertices and you want to compute the stabilizer (or some other subgroup..) of Aut(G) and you do

A = G.automorphism_group()
S = A.stabilizer(v)

it happens that you lose the information about the vertices of G. Since S can be a group on a smaller domain and there is no translation from it to the vertices of G

CC: @rbeezer @nathanncohen @dcoudert @benjaminfjones

Component: graph theory

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

[benjaminfjones]

Description changed:

--- 
+++ 
@@ -1,9 +1,15 @@
-The current implementation of the automorphism group of a graph always relabels the graph in question to use the vertex set $1,2,...,$ and then returns the automorphism group based on this labelling and potentially a translation for the labelling as well.
+The current implementation of the automorphism group of a graph always relabels the graph in question to use the vertex set {1,2,...,n+1} and then returns the automorphism group based on this labeling and potentially a translation for the labeling as well.

-Needless to say that this is time consuming, confusing and also prone to bugs since if one uses integers as labels (starting at 0 for example) the relabelling might go unnoticed. 
+Needless to say that this is time consuming, confusing and also prone to bugs since if one uses integers as labels (starting at 0 for example) the relabeling might go unnoticed. 

 As it appears from [this](https://groups.google.com/forum/?fromgroups=#!topic/sage-devel/wLtbNpeYrok) sage-devel post  it is now possible to use arbitrary domains for permutation groups.

 Hence, it would be nice to integrate this change into the automorphism_group function as well.

+---

+From https://groups.google.com/d/msg/sage-devel/y_TuGhjLYJQ/8YBUmQaNsXUJ
+
+> In the long term, I think the right solution is to copy what is done for Galois groups of number fields: depending on a keyword option to automorphism_group(), we should return either the abstract permutation group (as is done now) or a group equipped with an action on the edges and vertices of the graph.
+> David
+

[ca0b67cc-9d10-44c6-be51-5d9e2cdee96a]

Description changed:

--- 
+++ 
@@ -13,3 +13,14 @@
 > In the long term, I think the right solution is to copy what is done for Galois groups of number fields: depending on a keyword option to automorphism_group(), we should return either the abstract permutation group (as is done now) or a group equipped with an action on the edges and vertices of the graph.
 > David

+---
+Also what appears to be a 'defect' is that if you have a graph G on say 150 vertices and you want to compute the stabilizer (or some other subgroup..) of Aut(G) and you do
+
+```
+
+A = G.automorphism_group()
+S = A.stabilizer(v)
+
+```
+
+it happens that you lose the information about the vertices of G. Since S can be a group on a smaller domain and there is no translation from it to the vertices of G

[jasongrout]

comment:4

I posted this to the mailing list, but it's relevant here too:

Until we have proper support for this, you can do:

sage: g=Graph({'a': 'b', 'b': 'c'})
sage: p,q=g.automorphism_group(translation=True)
sage: pp=PermutationGroup(gap_group=p._gap_(), domain=sorted(q, key=q.get))

sage: pp
Permutation Group with generators [('c','a')]

(this also helps you see how to implement it...)

Unfortunately, there is a bug in the stabilizer method when the permutation group has a custom domain, which is now fixed at #13893, which now needs review.

a workaround for the stabilizer bug is:

sage: pp.subgroup(gap_group=gap.Stabilizer(pp, pp._domain_to_gap['b']))
Subgroup of (Permutation Group with generators [('c','a')]) generated by [('c','a')]