Opened 4 years ago
Closed 4 years ago
#22546 closed enhancement (fixed)
Improve combinatorial_automorphism_group in polyhedra class
Reported by:  moritz  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  polyhedron, days84 
Cc:  jipilab  Merged in:  
Authors:  Moritz Firsching  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  128d28e (Commits, GitHub, GitLab)  Commit:  128d28e8b4c59f227b18147866d40aa00ed74f87 
Dependencies:  #22500  Stopgaps: 
Description (last modified by )
Currently, the combinatorial_automorphism_group
method in the polyhedron class returns a group isomorphic to the automorphism group of the vertexedge 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 vertexedge graph, but also of the vertexfacet graph.
The second improvement has the advantage that the automorphism group of the vertexfacet graph is the same as the automorphism of the face lattice.
Since the vertexfacet 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.
Change History (22)
comment:1 Changed 4 years ago by
 Branch set to u/moritz/combinatorial_automorphism_group
comment:2 Changed 4 years ago by
 Commit set to aa80ed3a21abac2b2d6b0be19c60a3d665f61e63
 Dependencies set to https://trac.sagemath.org/ticket/22500
comment:3 Changed 4 years ago by
 Status changed from new to needs_review
This addition does everything I propose to do and illustrate the differences with examples.
comment:4 Changed 4 years ago by
 Dependencies changed from https://trac.sagemath.org/ticket/22500 to #22500
comment:5 Changed 4 years ago by
 Status changed from needs_review to needs_info
 Aren't the vertices actually numbered from
0
up ton1
?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?
comment:6 Changed 4 years ago by
 Description modified (diff)
 Status changed from needs_info to needs_work
Thanks for the comments, Vincent!
 about the numbering: yes the vertices have their labeling from
0
ton1
, and also the facets of dimensionP.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. iflabels=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 optionslabels=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).
comment:7 Changed 4 years ago by
 Commit changed from aa80ed3a21abac2b2d6b0be19c60a3d665f61e63 to a56630bd6db8e1a407c8ced18ece71b9ccc8ca47
Branch pushed to git repo; I updated commit sha1. New commits:
a56630b  make method cached and public; better wording for the INPUT docstring

comment:8 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:9 Changed 4 years ago by
Is the description of the ticket missing a sentence at the end?
comment:10 Changed 4 years ago by
 Status changed from needs_review to needs_work
 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
comment:11 Changed 4 years ago by
 Description modified (diff)
comment:12 Changed 4 years ago by
 Commit changed from a56630bd6db8e1a407c8ced18ece71b9ccc8ca47 to e72d2cb6a2dd4ef12152069baaad3eb134348708
comment:13 Changed 4 years ago by
 Status changed from needs_work to needs_review
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.
comment:14 Changed 4 years ago by
 Status changed from needs_review to needs_work
comment:15 Changed 4 years ago by
 Commit changed from e72d2cb6a2dd4ef12152069baaad3eb134348708 to 7fe551fc631fed57c62eeaead5c28a92dd7f87a3
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

comment:16 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:17 Changed 4 years ago by
 Status changed from needs_review to needs_work
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)] **********************************************************************
comment:18 Changed 4 years ago by
 Reviewers set to JeanPhilippe Labbé
comment:19 Changed 4 years ago by
 Commit changed from 7fe551fc631fed57c62eeaead5c28a92dd7f87a3 to 128d28e8b4c59f227b18147866d40aa00ed74f87
Branch pushed to git repo; I updated commit sha1. New commits:
128d28e  fixed dependency on order in doctests

comment:20 Changed 4 years ago by
This should fix the problem.
comment:21 Changed 4 years ago by
 Status changed from needs_work to positive_review
Looks good to me.
comment:22 Changed 4 years ago by
 Branch changed from u/moritz/combinatorial_automorphism_group to 128d28e8b4c59f227b18147866d40aa00ed74f87
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
initial version
pep8 errors fixed
better assertins, improved docstrings
reference added
whitespace
little improvements, change 'algo' to 'algorithm'
new version of combinatorial_automorphism_group of polyhedra