Use CombinatorialPolyhedron to obtain faces of polyhedra

[kliem]

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.

CC: @jplab @LaisRast

Component: geometry

Keywords: polytopes, combinatorial polyhedron

Author: Jonathan Kliem

Branch/Commit: 13f0214

Reviewer: Jean-Philippe Labbé, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/28646

[kliem]

Commit: ca54051

[kliem]

Dependencies: #28625

[kliem]

comment:1

I accidentally pulled #28625 instead of #28621. As #28625 is closed, I don't feel like fixing the branch.

---

New commits:

b89610e	added combinatorial polyhedron as an attribute for polyhedra
dfbe2ad	Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621
ed5518b	used CombinatorialPolyhedron to compute f_vector
9bdd005	give an error message for polytopes in some cases; removed incorrect example
acd671d	now we get a precice error message for inexact truncated dodecahedron
bf85a62	subsequent calls for f_vector fail if first attempt fails
36ac386	Merge branch 'public/28625' of git://trac.sagemath.org/sage into face_iter
ca54051	polyhedron uses CombinatorialPolyhedron for :meth:`faces`; added :meth:`face_generator`

[kliem]

Branch: public/28646

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

6828a75

avoid import of PolyhedronFace; use existing method

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ca54051 to 6828a75

[jplab]

comment:3

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.

[jplab]

Reviewer: Jean-Philippe Labbé

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d85f055

simplified input/output

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6828a75 to d85f055

[kliem]

comment:5

Replying to @jplab:

I would vote to change face_dimension to simply dimension.

This is to be consistent with the method `faces``.

[kliem]

comment:7

There will be a conflict with #17215.

[kliem]

Changed dependencies from #28625 to #28625, #17215

[kliem]

comment:8

Rebased

---

New commits:

d9cb649

polyhedron uses CombinatorialPolyhedron for :meth:`faces`; added :meth:`face_generator`

[kliem]

Changed branch from public/28646 to public/28646-reb

[kliem]

Changed commit from d85f055 to d9cb649

[kliem]

Changed dependencies from #28625, #17215 to #17215

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d9cb649 to 849e09a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

849e09a

fixed a new failing test

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 849e09a to 4d53c14

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

[kliem]

Description changed:

--- 
+++ 
@@ -5,3 +5,5 @@
 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`.
+
+There is a conflict with #17215, as it assumes the faces in the old order. However, if this here looks good, #17215 can also be marked dependent on #28646.

[e5d7a320-2f16-45df-b1ae-dad94ad63f33]

comment:12

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.

[kliem]

comment:13

Removing the dependency.

17215 will need small changes in the doctests, once it's done.

[kliem]

Description changed:

--- 
+++ 
@@ -5,5 +5,3 @@
 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`.
-
-There is a conflict with #17215, as it assumes the faces in the old order. However, if this here looks good, #17215 can also be marked dependent on #28646.

[kliem]

Changed dependencies from #17215 to none

[vbraun]

comment:14

sage -t --long --warn-long 34.6 src/sage/geometry/polyhedron/base.py  # 9 doctests failed
sage -t --long --warn-long 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/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/release/Sage/local/lib/python3.7/site-packages/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/site-packages/sage/geometry/polyhedron/base.py", line 5577, in faces
        return tuple(self.face_generator(face_dimension))
      File "/home/release/Sage/local/lib/python3.7/site-packages/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/site-packages/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'

[kliem]

comment:15

Should work now.

---

New commits:

fa296e6	Merge branch 'public/28646-reb' of git://trac.sagemath.org/sage into public/28646-reb2
13f0214	fix some errors due to merging

[kliem]

Changed branch from public/28646-reb to public/28646-reb2

[kliem]

Changed commit from 4d53c14 to 13f0214

[kliem]

comment:16

ping

[tscrim]

comment:17

LGTM.

[tscrim]

Changed reviewer from Jean-Philippe Labbé to Jean-Philippe Labbé, Travis Scrimshaw

[fchapoton]

comment:18

9.0 is out

[vbraun]

Changed branch from public/28646-reb2 to 13f0214