Improve combinatorial_automorphism_group in polyhedra class

[moritz]

Currently, the combinatorial_automorphism_group method in the polyhedron class returns a group isomorphic to the automorphism group of the vertex-edge graph of the polyhedron. I propose to changes two the method:

(1) don't return a permutation group on the number 1, 2,.. self.n_vertices(), but rather a permutation group on the actual objects (vertices of the polyhedron)

(2) wide the functionality to not only return the automorphism group of the vertex-edge graph, but also of the vertex-facet graph.

The second improvement has the advantage that the automorphism group of the vertex-facet graph is the same as the automorphism of the face lattice.

Since the vertex-facet graph is also used in the related .is_combinatorially_isomorphic method (see #22500) and it might be useful on its own, it is now a seperate function.

[moritz]

New commits:

​508bc6b	initial version
​ca97480	pep8 errors fixed
​03dbd96	better assertins, improved docstrings
​5a2307d	reference added
​0a29d25	whitespace
​f0ec516	little improvements, change 'algo' to 'algorithm'
​aa80ed3	new version of combinatorial_automorphism_group of polyhedra

[moritz]

This addition does everything I propose to do and illustrate the differences with examples.

[vdelecroix]

• Aren't the vertices actually numbered from 0 up to n-1?

  sage: p = polytopes.associahedron(['A',2])
  sage: p.faces(0)
  (<0>, <1>, <2>, <3>, <4>)
  

• typo in the ticket description returns the a group isomorphic

• in the docstring, I am not sure that whether to the graph is proper english

• Why _vertex_facet_graph starts with a underscore?

[moritz]

Thanks for the comments, Vincent!

• about the numbering: yes the vertices have their labeling from 0 to n-1, and also the facets of dimension P.dim()-1 have their labeling. From this it is not quite clear to me, what the best labeling for the nodes in the vertex_facet_graph would be. if labels=True, we get consistent result with the .graph method:

  sage: p = polytopes.associahedron(['A',2])
  sage: p.graph().vertices()
  
  [A vertex at (-1, 0),
   A vertex at (-1, 1),
   A vertex at (0, -1),
   A vertex at (1, -1),
   A vertex at (1, 1)]
  sage: p.vertex_facet_graph().vertices()
  
  [An inequality (-1, 0) x + 1 >= 0,
   An inequality (0, -1) x + 1 >= 0,
   An inequality (0, 1) x + 1 >= 0,
   An inequality (1, 0) x + 1 >= 0,
   An inequality (1, 1) x + 1 >= 0,
   A vertex at (-1, 0),
   A vertex at (-1, 1),
   A vertex at (0, -1),
   A vertex at (1, -1),
   A vertex at (1, 1)]
  

  The reason to have the options labels=False is basically only for internal use by the .is_combinatorially_isomorphic method.

• typo in the description fixed
• changed the sentence to "decide how the nodes of the graph are labelled. Either with the original vertices/facets of the Polyhedron or with integers."
• I have no strong opinion if this method should be public or start with an underscore, I guess there are reasons for both. (Now I removed the underscore).

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a56630b

make method cached and public; better wording for the INPUT docstring

[jipilab]

Is the description of the ticket missing a sentence at the end?

[jipilab]

• There is a space missing here:

sage: O=polytopes.octahedron(); O

• There is an indentation too much it seems in the OUTPUT field of combinatorial_automorphism_group

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​9843c05	new version of combinatorial_automorphism_group of polyhedra
​950f824	make method cached and public; better wording for the INPUT docstring
​e72d2cb	immprovements in docstring, including SEEALSOs

[moritz]

Thanks for looking at the ticket, JP! I fixed up the things you mentioned and added some little improvements in the docstring. Also I rebased on the current rc0.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​e07a18c	new version of combinatorial_automorphism_group of polyhedra
​c303ed7	make method cached and public; better wording for the INPUT docstring
​6b938f8	immprovements in docstring, including SEEALSOs
​7fe551f	rebased

[jipilab]

There are failed doctests. See the bot shortlog,

**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 498, in sage.geometry.polyhedron.base.Polyhedron_base.vertex_facet_graph
Failed example:
    G.vertices()
Expected:
    [An inequality (-1, 0, 0) x + 1 >= 0,
     An inequality (0, -1, 0) x + 1 >= 0,
     An inequality (0, 0, -1) x + 1 >= 0,
     An inequality (0, 0, 1) x + 1 >= 0,
     An inequality (0, 1, 0) x + 1 >= 0,
     An inequality (1, 0, 0) x + 1 >= 0,
     A vertex at (-1, -1, -1),
     A vertex at (-1, -1, 1),
     A vertex at (-1, 1, -1),
     A vertex at (-1, 1, 1),
     A vertex at (1, -1, -1),
     A vertex at (1, -1, 1),
     A vertex at (1, 1, -1),
     A vertex at (1, 1, 1)]
Got:
    [A vertex at (-1, -1, -1),
     A vertex at (-1, -1, 1),
     A vertex at (-1, 1, -1),
     A vertex at (-1, 1, 1),
     A vertex at (1, -1, -1),
     A vertex at (1, -1, 1),
     A vertex at (1, 1, -1),
     A vertex at (1, 1, 1),
     An inequality (-1, 0, 0) x + 1 >= 0,
     An inequality (0, -1, 0) x + 1 >= 0,
     An inequality (0, 0, -1) x + 1 >= 0,
     An inequality (0, 0, 1) x + 1 >= 0,
     An inequality (0, 1, 0) x + 1 >= 0,
     An inequality (1, 0, 0) x + 1 >= 0]
**********************************************************************
File "src/sage/geometry/polyhedron/base.py", line 4909, in sage.geometry.polyhedron.base.Polyhedron_base.combinatorial_automorphism_group
Failed example:
    quadrangle.combinatorial_automorphism_group()
Expected:
    Permutation Group with generators [(An inequality (0,1) x + 0 >= 0,An inequality (1,0) x + 0 >= 0)(An inequality (1,-1) x + 1 >= 0,An inequality (-3,1) x + 3 >= 0)(A vertex at (0,1),A vertex at (1,0)), (An inequality (0,1) x + 0 >= 0,An inequality (1,-1) x + 1 >= 0)(A vertex at (0,0),A vertex at (0,1))(A vertex at (1,0),A vertex at (2,3))]
Got:
    Permutation Group with generators [(A vertex at (0,1),A vertex at (1,0))(An inequality (0,1) x + 0 >= 0,An inequality (1,0) x + 0 >= 0)(An inequality (1,-1) x + 1 >= 0,An inequality (-3,1) x + 3 >= 0), (A vertex at (0,0),A vertex at (0,1))(A vertex at (1,0),A vertex at (2,3))(An inequality (0,1) x + 0 >= 0,An inequality (1,-1) x + 1 >= 0)]
**********************************************************************

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​128d28e

fixed dependency on order in doctests

[moritz]

This should fix the problem.

[jipilab]

Looks good to me.