Opened 5 years ago
Closed 5 years ago
#22546 closed enhancement (fixed)
Improve combinatorial_automorphism_group in polyhedra class
Reported by: | moritz | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.6 |
Component: | geometry | Keywords: | polyhedron, days84 |
Cc: | jipilab | Merged in: | |
Authors: | Moritz Firsching | Reviewers: | Jean-Philippe 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 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.
Change History (22)
comment:1 Changed 5 years ago by
- Branch set to u/moritz/combinatorial_automorphism_group
comment:2 Changed 5 years ago by
- Commit set to aa80ed3a21abac2b2d6b0be19c60a3d665f61e63
- Dependencies set to https://trac.sagemath.org/ticket/22500
comment:3 Changed 5 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 5 years ago by
- Dependencies changed from https://trac.sagemath.org/ticket/22500 to #22500
comment:5 Changed 5 years ago by
- Status changed from needs_review to needs_info
- Aren't the vertices actually numbered from
0
up ton-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?
comment:6 Changed 5 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
ton-1
, 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 5 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 5 years ago by
- Status changed from needs_work to needs_review
comment:9 Changed 5 years ago by
Is the description of the ticket missing a sentence at the end?
comment:10 Changed 5 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 5 years ago by
- Description modified (diff)
comment:12 Changed 5 years ago by
- Commit changed from a56630bd6db8e1a407c8ced18ece71b9ccc8ca47 to e72d2cb6a2dd4ef12152069baaad3eb134348708
comment:13 Changed 5 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 5 years ago by
- Status changed from needs_review to needs_work
comment:15 Changed 5 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 5 years ago by
- Status changed from needs_work to needs_review
comment:17 Changed 5 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 5 years ago by
- Reviewers set to Jean-Philippe Labbé
comment:19 Changed 5 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 5 years ago by
This should fix the problem.
comment:21 Changed 5 years ago by
- Status changed from needs_work to positive_review
Looks good to me.
comment:22 Changed 5 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