Opened 20 months ago
Closed 18 months ago
#28646 closed enhancement (fixed)
Use CombinatorialPolyhedron to obtain faces of polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.1 
Component:  geometry  Keywords:  polytopes, combinatorial polyhedron 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  13f0214 (Commits, GitHub, GitLab)  Commit:  13f0214ab2f9f42755bf757a3325143ab423f982 
Dependencies:  Stopgaps: 
Description (last modified by )
We use CombinatorialPolyhedron
to obtain the faces of fixed dimensions of a polyhedron.
We add a method face_generator
, which iterates over all faces (possibly of fixed dimension).
With this ticket we can obtain the faces much faster and without generating the entire face lattice. The iterator is a true iterator in the sense that it has almost constant memory usage and does and no point store a list of all faces.
This ticket changes the order of the output of faces
.
Change History (19)
comment:1 Changed 20 months ago by
 Branch set to public/28646
 Commit set to ca5405111f0733513f8a1010b4237d4a4c644280
 Dependencies set to #28625
 Status changed from new to needs_review
comment:2 Changed 20 months ago by
 Commit changed from ca5405111f0733513f8a1010b4237d4a4c644280 to 6828a751122c3f9f779f21a914788b79110dfeda
Branch pushed to git repo; I updated commit sha1. New commits:
6828a75  avoid import of PolyhedronFace; use existing method

comment:3 followup: ↓ 5 Changed 20 months ago by
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to needs_work
I would vote to change face_dimension
to simply dimension
.
The INPUT of combinatorial_face_to_polyhedral_face
is too verbose to me.
A Polyhedron
, the polyhedron containing the face
A CombinatorialFace
OUTPUT:
A PolyhedronFace
is sufficient. If you insist to have the links on the documentation ok... But I would not be too verbose here.
comment:4 Changed 20 months ago by
 Commit changed from 6828a751122c3f9f779f21a914788b79110dfeda to d85f05534c216adedb07174a5f155e63007c0986
Branch pushed to git repo; I updated commit sha1. New commits:
d85f055  simplified input/output

comment:5 in reply to: ↑ 3 Changed 20 months ago by
Replying to jipilab:
I would vote to change
face_dimension
to simplydimension
.
This is to be consistent with the method faces
`.
comment:6 Changed 20 months ago by
 Status changed from needs_work to needs_review
comment:7 Changed 20 months ago by
 Dependencies changed from #28625 to #28625, #17215
There will be a conflict with #17215.
comment:8 Changed 20 months ago by
 Branch changed from public/28646 to public/28646reb
 Commit changed from d85f05534c216adedb07174a5f155e63007c0986 to d9cb64930ee3473eea787cf91136a71d04488163
 Dependencies changed from #28625, #17215 to #17215
Rebased
New commits:
d9cb649  polyhedron uses CombinatorialPolyhedron for :meth:`faces`; added :meth:`face_generator`

comment:9 Changed 20 months ago by
 Commit changed from d9cb64930ee3473eea787cf91136a71d04488163 to 849e09a9e95523b3e742f4c6f2e4fd48f65bdd3d
Branch pushed to git repo; I updated commit sha1. New commits:
849e09a  fixed a new failing test

comment:10 Changed 20 months ago by
 Commit changed from 849e09a9e95523b3e742f4c6f2e4fd48f65bdd3d to 4d53c14735f3435fe91d876d336a1af104997015
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
a4c3025  polyhedron uses CombinatorialPolyhedron for :meth:`faces`; added :meth:`face_generator`

5f284dd  avoid import of PolyhedronFace; use existing method

d15170d  simplified input/output

4d53c14  fixed a new failing test

comment:11 Changed 19 months ago by
 Description modified (diff)
comment:12 Changed 19 months ago by
 Status changed from needs_review to positive_review
The tests all pass on my end. face_generator runs for every type of polytope it should run on, and combinatorial_face_to_polyhedral_face runs as it should. The change in order experienced by the various face functions only affected the lists, not the correctness.
comment:13 Changed 19 months ago by
 Dependencies #17215 deleted
 Description modified (diff)
Removing the dependency.
#17215 will need small changes in the doctests, once it's done.
comment:14 Changed 19 months ago by
 Status changed from positive_review to needs_work
sage t long warnlong 34.6 src/sage/geometry/polyhedron/base.py # 9 doctests failed sage t long warnlong 34.6 src/sage/geometry/polyhedron/face.py # 4 doctests failed
e.g.
File "src/sage/geometry/polyhedron/face.py", line 10, in sage.geometry.polyhedron.face Failed example: P.faces(3) Exception raised: Traceback (most recent call last): File "/home/release/Sage/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 681, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/sage/doctest/forker.py", line 1123, in compile_and_execute exec(compiled, globs) File "<doctest sage.geometry.polyhedron.face[1]>", line 1, in <module> P.faces(Integer(3)) File "/home/release/Sage/local/lib/python3.7/sitepackages/sage/geometry/polyhedron/base.py", line 5577, in faces return tuple(self.face_generator(face_dimension)) File "/home/release/Sage/local/lib/python3.7/sitepackages/sage/geometry/polyhedron/base.py", line 5480, in face_generator yield self._make_polyhedron_face(range(self.n_Vrepresentation()), []) File "/home/release/Sage/local/lib/python3.7/sitepackages/sage/geometry/polyhedron/base_ZZ.py", line 53, in __getattribute__ return super(Polyhedron_ZZ, self).__getattribute__(name) File "sage/structure/element.pyx", line 487, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4608) return self.getattr_from_category(name) File "sage/structure/element.pyx", line 500, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4717) return getattr_from_other_class(self, cls, name) File "sage/cpython/getattr.pyx", line 389, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2547) raise AttributeError(dummy_error_message) AttributeError: 'Polyhedra_ZZ_ppl_with_category.element_class' object has no attribute '_make_polyhedron_face'
comment:15 Changed 19 months ago by
 Branch changed from public/28646reb to public/28646reb2
 Commit changed from 4d53c14735f3435fe91d876d336a1af104997015 to 13f0214ab2f9f42755bf757a3325143ab423f982
 Status changed from needs_work to needs_review
comment:16 Changed 18 months ago by
ping
comment:17 Changed 18 months ago by
 Reviewers changed from JeanPhilippe Labbé to JeanPhilippe Labbé, Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM.
comment:19 Changed 18 months ago by
 Branch changed from public/28646reb2 to 13f0214ab2f9f42755bf757a3325143ab423f982
 Resolution set to fixed
 Status changed from positive_review to closed
I accidentally pulled #28625 instead of #28621. As #28625 is closed, I don't feel like fixing the branch.
New commits:
added combinatorial polyhedron as an attribute for polyhedra
Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621
used CombinatorialPolyhedron to compute f_vector
give an error message for polytopes in some cases; removed incorrect example
now we get a precice error message for inexact truncated dodecahedron
subsequent calls for f_vector fail if first attempt fails
Merge branch 'public/28625' of git://trac.sagemath.org/sage into face_iter
polyhedron uses CombinatorialPolyhedron for :meth:`faces`; added :meth:`face_generator`