Use CombinatorialPolyhedron to obtain faces lattice of polyhedra

[kliem]

We use CombinatorialPolyhedron to compute the face lattice of a polyhedron.

Along the way we implement hasse_diagram for CombinatorialPolyhedron and Polyhedron_base.

Instead of caching face_lattice, we cache hasse_diagram now.

This is much slower, but removes a memory leak. As hasse_diagram is hardly used with #28646, this seems to be reasonable.

Caching the face lattice does create a memory leak:

sage: import gc
sage: P = polytopes.cube()
sage: P.my_face_lattice = P.face_lattice()
sage: n = get_memory_usage()
sage: P = polytopes.cube()
sage: P.my_face_lattice = P.face_lattice()
sage: _ = gc.collect()
sage: n == get_memory_usage()
False

Depends on #29583

CC: @jplab @LaisRast

Component: geometry

Keywords: polyhedron, face lattice

Author: Jonathan Kliem

Branch/Commit: 6b7b5b6

Reviewer: Jean-Philippe Labbé, Matthias Koeppe

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

[kliem]

Branch: public/28982

[sagetrac-git]

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

242f34f	add hasse_diagram to combinatorial polyhedron
af84439	implemented method hasse diagram for polyhedra
cfb153d	use combinatorial polyhedron to obtain face lattice of polyhedron

[sagetrac-git]

Commit: cfb153d

[sagetrac-git]

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

41254c2

fixed pyflakes warnings

[sagetrac-git]

Changed commit from cfb153d to 41254c2

[kliem]

comment:5

I changed to face lattice not to be set up with linear extension anymore.

---

New commits:

261feff	add hasse_diagram to combinatorial polyhedron
721cff6	implemented method hasse diagram for polyhedra
0768b90	use combinatorial polyhedron to obtain face lattice of polyhedron
c82545f	fixed pyflakes warnings
f249c9d	fixed failing doctest; face lattice can compute whether it is eulerian again

[kliem]

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

[kliem]

Changed commit from 41254c2 to f249c9d

[jplab]

comment:6

Few comments:

-        Test that face lattice give no memory leak::
+        Test that computing the face lattice does not lead to a memory leak::

-        Return the hasse diagram of ``self``.
+        Return the hasse diagram of the face lattice of ``self``.

I will go more in depth soon.

Does this mean that we can remove the file hasse_diagram.py?

[kliem]

Changed commit from f249c9d to f44afa2

[kliem]

New commits:

ef69d37	add hasse_diagram to combinatorial polyhedron
919af02	implemented method hasse diagram for polyhedra
f040df6	use combinatorial polyhedron to obtain face lattice of polyhedron
f9f7a42	fixed pyflakes warnings
f306cd0	fixed failing doctest; face lattice can compute whether it is eulerian again
f44afa2	improved documentation

[kliem]

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

[sagetrac-git]

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

e9b3201

improved doctest, gc.collect should be run before the test as well

[sagetrac-git]

Changed commit from f44afa2 to e9b3201

[mkoeppe]

comment:10

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:11

Suggestions:

+        .. NOTE::
-            The face lattice is not cached, as long as this would create a memory leak.
+            The face lattice is not cached, as long as this creates a memory leak, see :trac:`28982`.

Hasse is a lastname, so you can capitalize it within the documentation.

Could the function below have more information? Like which order is meant to be simulated here? Inclusion or lex on indices of vertices, etc? Just one more sentence to specify might be nice?

+    def __lt__(self, other):
+        r"""
+        Compare faces of the same polyhedron.
+
+        EXAMPLES::
+
+            sage: P = polytopes.simplex()
+            sage: C = CombinatorialPolyhedron(P)
+            sage: F1 = C.face_by_face_lattice_index(0)
+            sage: F2 = C.face_by_face_lattice_index(1)
+            sage: F1 < F2
+            True
+        """
+        return hash(self) < hash(other)

Is there a reason why the hasse diagram of the combinatorial polyhedron is not cached?

[kliem]

New commits:

e7093eb	Merge branch 'public/28982-reb2' of git://trac.sagemath.org/sage into public/28982-reb3
b559ca1	cache hasse_diagram of combinatorial polyhedron
2fb6746	improved documentation
92842be	explain __lt__

[kliem]

Changed branch from public/28982-reb2 to public/28982-reb3

[kliem]

Changed commit from e9b3201 to 92842be

[kliem]

comment:26

Needs rebase (build fails).

[kliem]

Changed branch from public/28982-reb6 to public/28982-reb7

[kliem]

New commits:

4596af9	Merge branch 'public/28982-reb6' of git://trac.sagemath.org/sage into public/28982-reb7
2297474	import DiGraph in time

[kliem]

Changed commit from f4e1dec to 2297474

[mkoeppe]

comment:28

+    if polyhedron.dimension() == 0:
+        # In case of the 0-dimensional polyhedron,
+        # there is a facets but no inequality.
+        H_indices = tuple(range(n_equations))
+

The comment needs rewording

[kliem]

Changed commit from 2297474 to 92487de

[kliem]

Changed branch from public/28982-reb7 to public/28982-reb8

[kliem]

New commits:

52b634f	Merge branch 'public/28982-reb7' of git://trac.sagemath.org/sage into public/28982-reb8
92487de	improved comment

[mkoeppe]

comment:31

+    def __lt__(self, other):
+        r"""
+        Compare faces of the same polyhedron.
+
+        This is a helper function.
+        In order to construct a Hasse diagram (a digraph) with combinatorial faces,
+        we must define some order relation that is compatible with the Hasse diagram.
+
+        Any order relation compatible with ordering by dimension is suitable.
+        We us :meth:`__hash__` to define the relation.

I don't fully understand what's happening in that hash function. If one uses the face iterator in non-dual mode, is the resulting order relation still correct?

[mkoeppe]

Changed reviewer from Jean-Philippe Labbé to Jean-Philippe Labbé, Matthias Koeppe

[sagetrac-git]

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

6b7b5b6

make hash function consistent with dual mode

[sagetrac-git]

Changed commit from 92487de to 6b7b5b6

[kliem]

comment:33

Replying to @mkoeppe:

+    def __lt__(self, other):
+        r"""
+        Compare faces of the same polyhedron.
+
+        This is a helper function.
+        In order to construct a Hasse diagram (a digraph) with combinatorial faces,
+        we must define some order relation that is compatible with the Hasse diagram.
+
+        Any order relation compatible with ordering by dimension is suitable.
+        We us :meth:`__hash__` to define the relation.

I don't fully understand what's happening in that hash function. If one uses the face iterator in non-dual mode, is the resulting order relation still correct?

You are right.
I'm surprised it worked that way.
The hash function should be consistent now. And __lt__ returns None if the faces are clearly incompatible.
What's nice about this hash function, if I understand it correctly, is that it allows to store faces in sets etc.

[kliem]

comment:35

Thank you.

[vbraun]

Changed branch from public/28982-reb8 to 6b7b5b6