Opened 6 months ago

Last modified 7 weeks ago

#28982 needs_review enhancement

Use CombinatorialPolyhedron to obtain faces lattice of polyhedra

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.2
Component: geometry Keywords: polyhedron, face lattice
Cc: jipilab, gh-LaisRast Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: public/28982-reb6 (Commits) Commit: f4e1deccef14f7aa3dcf1e19241ac042157e4f92
Dependencies: #29583 Stopgaps:

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

Change History (25)

comment:1 Changed 6 months ago by gh-kliem

  • Branch set to public/28982

comment:2 Changed 6 months ago by git

  • Commit set to cfb153d6c9f2c110a2468a920a14f4fa3914735a

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

242f34fadd hasse_diagram to combinatorial polyhedron
af84439implemented method hasse diagram for polyhedra
cfb153duse combinatorial polyhedron to obtain face lattice of polyhedron

comment:3 Changed 6 months ago by gh-kliem

  • Status changed from new to needs_review

comment:4 Changed 6 months ago by git

  • Commit changed from cfb153d6c9f2c110a2468a920a14f4fa3914735a to 41254c28fc83112e7b3b001a1b12c2995613ca8f

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

41254c2fixed pyflakes warnings

comment:5 Changed 5 months ago by gh-kliem

  • Branch changed from public/28982 to public/28982-reb
  • Commit changed from 41254c28fc83112e7b3b001a1b12c2995613ca8f to f249c9db8be362dbd8aa7adac95b672eddd6d3b4

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


New commits:

261feffadd hasse_diagram to combinatorial polyhedron
721cff6implemented method hasse diagram for polyhedra
0768b90use combinatorial polyhedron to obtain face lattice of polyhedron
c82545ffixed pyflakes warnings
f249c9dfixed failing doctest; face lattice can compute whether it is eulerian again

comment:6 Changed 5 months ago by 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?

comment:7 Changed 5 months ago by gh-kliem

  • Branch changed from public/28982-reb to public/28982-reb2
  • Commit changed from f249c9db8be362dbd8aa7adac95b672eddd6d3b4 to f44afa26835ca7a4991864766c1f1c01c9e6f399

New commits:

ef69d37add hasse_diagram to combinatorial polyhedron
919af02implemented method hasse diagram for polyhedra
f040df6use combinatorial polyhedron to obtain face lattice of polyhedron
f9f7a42fixed pyflakes warnings
f306cd0fixed failing doctest; face lattice can compute whether it is eulerian again
f44afa2improved documentation

comment:8 Changed 5 months ago by gh-kliem

  • Description modified (diff)

comment:9 Changed 5 months ago by git

  • Commit changed from f44afa26835ca7a4991864766c1f1c01c9e6f399 to e9b3201a8b6dd36d5edf0ac54e4d554d9aaff6b4

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

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

comment:10 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.1 to sage-9.2

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.

comment:11 Changed 3 months ago by jipilab

  • Reviewers set to Jean-Philippe Labbé
  • Status changed from needs_review to needs_work

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?

comment:12 Changed 3 months ago by gh-kliem

  • Branch changed from public/28982-reb2 to public/28982-reb3
  • Commit changed from e9b3201a8b6dd36d5edf0ac54e4d554d9aaff6b4 to 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca
  • Status changed from needs_work to needs_review

New commits:

e7093ebMerge branch 'public/28982-reb2' of git://trac.sagemath.org/sage into public/28982-reb3
b559ca1cache hasse_diagram of combinatorial polyhedron
2fb6746improved documentation
92842beexplain __lt__

comment:13 Changed 3 months ago by jipilab

  • Status changed from needs_review to needs_work

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.

comment:14 Changed 3 months ago by git

  • Commit changed from 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca to 708dd7dcf0dbc70c9c53a3c4946624a389b2580e

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

708dd7dtypo

comment:15 Changed 3 months ago by gh-kliem

  • Status changed from needs_work to positive_review

Thank you.

comment:16 Changed 3 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:17 Changed 3 months ago by gh-kliem

  • Branch changed from public/28982-reb3 to public/28982-reb4
  • Commit changed from 708dd7dcf0dbc70c9c53a3c4946624a389b2580e to 819d5433d00510a69bc43b8138296713cd9853f5
  • Status changed from needs_work to needs_review

Last 10 new commits:

d7bc78duse combinatorial polyhedron to obtain face lattice of polyhedron
d6f874efixed pyflakes warnings
7e53757fixed failing doctest; face lattice can compute whether it is eulerian again
015232cimproved documentation
651e621improved doctest, gc.collect should be run before the test as well
898feeecache hasse_diagram of combinatorial polyhedron
ff18524improved documentation
6497d62explain __lt__
4e19d6ctypo
819d543fix failing doctest

comment:18 Changed 3 months ago by jipilab

  • Status changed from needs_review to needs_work

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

comment:19 Changed 3 months ago by gh-kliem

  • Branch changed from public/28982-reb4 to public/28982-reb5
  • Commit changed from 819d5433d00510a69bc43b8138296713cd9853f5 to 0e865a04996fe35097ffd04fbdb879b97732e2ce
  • Status changed from needs_work to needs_review

Last 10 new commits:

5edeaa3fixed pyflakes warnings
00f234cfixed failing doctest; face lattice can compute whether it is eulerian again
ab0a789improved documentation
fefe3b2improved doctest, gc.collect should be run before the test as well
4bc4957cache hasse_diagram of combinatorial polyhedron
381f7d9improved documentation
404efcaexplain __lt__
84746b1typo
587738dfix failing doctest
0e865a0missing import

comment:20 Changed 2 months ago by jipilab

  • Status changed from needs_review to positive_review

Looks good to me now.

comment:21 Changed 8 weeks ago by vbraun

  • Status changed from positive_review to needs_work
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]

comment:22 Changed 7 weeks ago by gh-kliem

  • Dependencies set to #29583, #28894

comment:23 Changed 7 weeks ago by gh-kliem

  • Dependencies changed from #29583, #28894 to #29583

comment:24 Changed 7 weeks ago by gh-kliem

  • Branch changed from public/28982-reb5 to public/28982-reb6
  • Commit changed from 0e865a04996fe35097ffd04fbdb879b97732e2ce to f4e1deccef14f7aa3dcf1e19241ac042157e4f92

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:

cb5e58afixed pyflakes warnings
76a7247fixed failing doctest; face lattice can compute whether it is eulerian again
f0c9f6fimproved documentation
b76f653improved doctest, gc.collect should be run before the test as well
a405173cache hasse_diagram of combinatorial polyhedron
d2c5332improved documentation
e59938aexplain __lt__
8fbc9c2typo
0fbd87dfix failing doctest
f4e1decmissing import

comment:25 Changed 7 weeks ago by gh-kliem

  • Status changed from needs_work to needs_review
Note: See TracTickets for help on using tickets.