Opened 5 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: 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:

Status badges

Description (last modified by 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.

Change History (22)

comment:1 Changed 5 years ago by moritz

  • Branch set to u/moritz/combinatorial_automorphism_group

comment:2 Changed 5 years ago by moritz

  • Commit set to aa80ed3a21abac2b2d6b0be19c60a3d665f61e63
  • Dependencies set to https://trac.sagemath.org/ticket/22500

New commits:

508bc6binitial version
ca97480pep8 errors fixed
03dbd96better assertins, improved docstrings
5a2307dreference added
0a29d25whitespace
f0ec516little improvements, change 'algo' to 'algorithm'
aa80ed3new version of combinatorial_automorphism_group of polyhedra

comment:3 Changed 5 years ago by moritz

  • 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 jipilab

  • Dependencies changed from https://trac.sagemath.org/ticket/22500 to #22500

comment:5 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_info
  • 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?
Version 0, edited 5 years ago by vdelecroix (next)

comment:6 Changed 5 years ago by moritz

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

comment:7 Changed 5 years ago by git

  • Commit changed from aa80ed3a21abac2b2d6b0be19c60a3d665f61e63 to a56630bd6db8e1a407c8ced18ece71b9ccc8ca47

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

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

comment:8 Changed 5 years ago by moritz

  • Status changed from needs_work to needs_review

comment:9 Changed 5 years ago by jipilab

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

comment:10 Changed 5 years ago by jipilab

  • 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 moritz

  • Description modified (diff)

comment:12 Changed 5 years ago by git

  • Commit changed from a56630bd6db8e1a407c8ced18ece71b9ccc8ca47 to e72d2cb6a2dd4ef12152069baaad3eb134348708

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

9843c05new version of combinatorial_automorphism_group of polyhedra
950f824make method cached and public; better wording for the INPUT docstring
e72d2cbimmprovements in docstring, including SEEALSOs

comment:13 Changed 5 years ago by moritz

  • 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 moritz

  • Status changed from needs_review to needs_work

comment:15 Changed 4 years ago by git

  • Commit changed from e72d2cb6a2dd4ef12152069baaad3eb134348708 to 7fe551fc631fed57c62eeaead5c28a92dd7f87a3

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

e07a18cnew version of combinatorial_automorphism_group of polyhedra
c303ed7make method cached and public; better wording for the INPUT docstring
6b938f8immprovements in docstring, including SEEALSOs
7fe551frebased

comment:16 Changed 4 years ago by moritz

  • Status changed from needs_work to needs_review

comment:17 Changed 4 years ago by jipilab

  • 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 jipilab

  • Reviewers set to Jean-Philippe Labbé

comment:19 Changed 4 years ago by git

  • Commit changed from 7fe551fc631fed57c62eeaead5c28a92dd7f87a3 to 128d28e8b4c59f227b18147866d40aa00ed74f87

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

128d28efixed dependency on order in doctests

comment:20 Changed 4 years ago by moritz

This should fix the problem.

comment:21 Changed 4 years ago by jipilab

  • Status changed from needs_work to positive_review

Looks good to me.

comment:22 Changed 4 years ago by vbraun

  • Branch changed from u/moritz/combinatorial_automorphism_group to 128d28e8b4c59f227b18147866d40aa00ed74f87
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.