Use CombinatorialPolyhedron to obtain faces lattice of polyhedra

[gh-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

[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

[git]

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

​41254c2

fixed pyflakes warnings

[gh-kliem]

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

[jipilab]

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?

[gh-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

[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

[mkoeppe]

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.

[jipilab]

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?

[gh-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__

[jipilab]

Great! Thanks for the quick changes. You forgot a capital "H" in the last commit. Apart from that it is good to go!

once you make this last typo change, you can set it to positive review on my behalf.

[git]

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

​708dd7d

typo

[gh-kliem]

Thank you.

[vbraun]

Merge conflict

[gh-kliem]

Last 10 new commits:

​d7bc78d	use combinatorial polyhedron to obtain face lattice of polyhedron
​d6f874e	fixed pyflakes warnings
​7e53757	fixed failing doctest; face lattice can compute whether it is eulerian again
​015232c	improved documentation
​651e621	improved doctest, gc.collect should be run before the test as well
​898feee	cache hasse_diagram of combinatorial polyhedron
​ff18524	improved documentation
​6497d62	explain __lt__
​4e19d6c	typo
​819d543	fix failing doctest

[jipilab]

It doesn't seem to build... See patchbot.

[gh-kliem]

Last 10 new commits:

​5edeaa3	fixed pyflakes warnings
​00f234c	fixed failing doctest; face lattice can compute whether it is eulerian again
​ab0a789	improved documentation
​fefe3b2	improved doctest, gc.collect should be run before the test as well
​4bc4957	cache hasse_diagram of combinatorial polyhedron
​381f7d9	improved documentation
​404efca	explain __lt__
​84746b1	typo
​587738d	fix failing doctest
​0e865a0	missing import

[jipilab]

Looks good to me now.

[vbraun]

sage -t --long --warn-long 36.4 src/sage/geometry/polyhedron/face.py
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 454, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation
Failed example:
    face = p.face_lattice()[5]
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation[1]>", line 1, in <module>
        face = p.face_lattice()[Integer(5)]
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 5873, in face_lattice
        return FiniteLatticePoset(self.hasse_diagram())
      File "sage/misc/cachefunc.pyx", line 2310, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:12712)
        self.cache = f(self._instance)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 5901, in hasse_diagram
        return D.relabel(index_to_polyhedron_face, inplace=False, immutable=True)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 21864, in relabel
        complete_partial_function = complete_partial_function)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 21929, in relabel
        raise NotImplementedError("Non injective relabeling")
    NotImplementedError: Non injective relabeling
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 455, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation
Failed example:
    face
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation[2]>", line 1, in <module>
        face
    NameError: name 'face' is not defined
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 457, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation
Failed example:
    face.ambient_Hrepresentation()
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation[3]>", line 1, in <module>
        face.ambient_Hrepresentation()
    NameError: name 'face' is not defined
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 462, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation
Failed example:
    face.n_ambient_Hrepresentation()
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation[4]>", line 1, in <module>
        face.n_ambient_Hrepresentation()
    NameError: name 'face' is not defined
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 481, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation
Failed example:
    face = p.face_lattice()[5]
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation[1]>", line 1, in <module>
        face = p.face_lattice()[Integer(5)]
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 5873, in face_lattice
        return FiniteLatticePoset(self.hasse_diagram())
      File "sage/misc/cachefunc.pyx", line 2310, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:12712)
        self.cache = f(self._instance)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py", line 5901, in hasse_diagram
        return D.relabel(index_to_polyhedron_face, inplace=False, immutable=True)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 21864, in relabel
        complete_partial_function = complete_partial_function)
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/graphs/generic_graph.py", line 21929, in relabel
        raise NotImplementedError("Non injective relabeling")
    NotImplementedError: Non injective relabeling
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 482, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation
Failed example:
    face
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation[2]>", line 1, in <module>
        face
    NameError: name 'face' is not defined
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 484, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation
Failed example:
    face.ambient_Vrepresentation()
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation[3]>", line 1, in <module>
        face.ambient_Vrepresentation()
    NameError: name 'face' is not defined
**********************************************************************
File "src/sage/geometry/polyhedron/face.py", line 486, in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation
Failed example:
    face.n_ambient_Vrepresentation()
Exception raised:
    Traceback (most recent call last):
      File "/home/release/Sage/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 680, 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 1104, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation[4]>", line 1, in <module>
        face.n_ambient_Vrepresentation()
    NameError: name 'face' is not defined
**********************************************************************
2 items had failures:
   4 of   6 in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Hrepresentation
   4 of   6 in sage.geometry.polyhedron.face.PolyhedronFace.n_ambient_Vrepresentation
    [119 tests, 8 failures, 0.44 s]

[gh-kliem]

I rebased on top of #29583 (as there is some merge conflict).

I also fixed the error in #28894, which caused the doctest failure. Now this ticket works by itself and on top of #28894. At least the following tests pass on my machine with and without #28894:

sage -t --long -p 8 src/doc/en/thematic_tutorials/geometry
sage -t --long -p 8 src/sage/geometry/polyhedron/
sage -t --long -p 8 src/sage/plot/

---

Last 10 new commits:

​cb5e58a	fixed pyflakes warnings
​76a7247	fixed failing doctest; face lattice can compute whether it is eulerian again
​f0c9f6f	improved documentation
​b76f653	improved doctest, gc.collect should be run before the test as well
​a405173	cache hasse_diagram of combinatorial polyhedron
​d2c5332	improved documentation
​e59938a	explain __lt__
​8fbc9c2	typo
​0fbd87d	fix failing doctest
​f4e1dec	missing import

[gh-kliem]

Needs rebase (build fails).

[gh-kliem]

New commits:

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

[mkoeppe]

+    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

[gh-kliem]

New commits:

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

[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?

[git]

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

​6b7b5b6

make hash function consistent with dual mode

[gh-kliem]

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.

[gh-kliem]

Thank you.