Opened 22 months ago
Closed 14 months ago
#28982 closed enhancement (fixed)
Use CombinatorialPolyhedron to obtain faces lattice of polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  geometry  Keywords:  polyhedron, face lattice 
Cc:  jipilab, ghLaisRast  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé, Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  6b7b5b6 (Commits, GitHub, GitLab)  Commit:  6b7b5b6c17a645f55766666295a0424de8efde72 
Dependencies:  #29583  Stopgaps: 
Description (last modified by )
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 (36)
comment:1 Changed 22 months ago by
 Branch set to public/28982
comment:2 Changed 22 months ago by
 Commit set to cfb153d6c9f2c110a2468a920a14f4fa3914735a
comment:3 Changed 22 months ago by
 Status changed from new to needs_review
comment:4 Changed 22 months ago by
 Commit changed from cfb153d6c9f2c110a2468a920a14f4fa3914735a to 41254c28fc83112e7b3b001a1b12c2995613ca8f
Branch pushed to git repo; I updated commit sha1. New commits:
41254c2  fixed pyflakes warnings

comment:5 Changed 21 months ago by
 Branch changed from public/28982 to public/28982reb
 Commit changed from 41254c28fc83112e7b3b001a1b12c2995613ca8f to f249c9db8be362dbd8aa7adac95b672eddd6d3b4
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

comment:6 Changed 20 months ago by
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 20 months ago by
 Branch changed from public/28982reb to public/28982reb2
 Commit changed from f249c9db8be362dbd8aa7adac95b672eddd6d3b4 to f44afa26835ca7a4991864766c1f1c01c9e6f399
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

comment:8 Changed 20 months ago by
 Description modified (diff)
comment:9 Changed 20 months ago by
 Commit changed from f44afa26835ca7a4991864766c1f1c01c9e6f399 to e9b3201a8b6dd36d5edf0ac54e4d554d9aaff6b4
Branch pushed to git repo; I updated commit sha1. New commits:
e9b3201  improved doctest, gc.collect should be run before the test as well

comment:10 Changed 18 months ago by
 Milestone changed from sage9.1 to sage9.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 18 months ago by
 Reviewers set to JeanPhilippe 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 18 months ago by
 Branch changed from public/28982reb2 to public/28982reb3
 Commit changed from e9b3201a8b6dd36d5edf0ac54e4d554d9aaff6b4 to 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca
 Status changed from needs_work to needs_review
comment:13 Changed 18 months ago by
 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 18 months ago by
 Commit changed from 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca to 708dd7dcf0dbc70c9c53a3c4946624a389b2580e
Branch pushed to git repo; I updated commit sha1. New commits:
708dd7d  typo

comment:16 Changed 18 months ago by
 Status changed from positive_review to needs_work
Merge conflict
comment:17 Changed 18 months ago by
 Branch changed from public/28982reb3 to public/28982reb4
 Commit changed from 708dd7dcf0dbc70c9c53a3c4946624a389b2580e to 819d5433d00510a69bc43b8138296713cd9853f5
 Status changed from needs_work to needs_review
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

comment:18 Changed 18 months ago by
 Status changed from needs_review to needs_work
It doesn't seem to build... See patchbot.
comment:19 Changed 18 months ago by
 Branch changed from public/28982reb4 to public/28982reb5
 Commit changed from 819d5433d00510a69bc43b8138296713cd9853f5 to 0e865a04996fe35097ffd04fbdb879b97732e2ce
 Status changed from needs_work to needs_review
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

comment:20 Changed 18 months ago by
 Status changed from needs_review to positive_review
Looks good to me now.
comment:21 Changed 17 months ago by
 Status changed from positive_review to needs_work
sage t long warnlong 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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/sage/graphs/generic_graph.py", line 21864, in relabel complete_partial_function = complete_partial_function) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/sage/graphs/generic_graph.py", line 21864, in relabel complete_partial_function = complete_partial_function) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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/sitepackages/sage/doctest/forker.py", line 680, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/release/Sage/local/lib/python3.7/sitepackages/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 17 months ago by
 Dependencies set to #29583, #28894
comment:23 Changed 17 months ago by
 Dependencies changed from #29583, #28894 to #29583
comment:24 Changed 17 months ago by
 Branch changed from public/28982reb5 to public/28982reb6
 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:
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

comment:25 Changed 17 months ago by
 Status changed from needs_work to needs_review
comment:26 Changed 14 months ago by
 Status changed from needs_review to needs_work
Needs rebase (build fails).
comment:27 Changed 14 months ago by
 Branch changed from public/28982reb6 to public/28982reb7
 Commit changed from f4e1deccef14f7aa3dcf1e19241ac042157e4f92 to 22974744b2b580cf94737ca9d04734d89687b73e
 Status changed from needs_work to needs_review
comment:28 Changed 14 months ago by
+ if polyhedron.dimension() == 0: + # In case of the 0dimensional polyhedron, + # there is a facets but no inequality. + H_indices = tuple(range(n_equations)) +
The comment needs rewording
comment:29 Changed 14 months ago by
 Status changed from needs_review to needs_work
comment:30 Changed 14 months ago by
 Branch changed from public/28982reb7 to public/28982reb8
 Commit changed from 22974744b2b580cf94737ca9d04734d89687b73e to 92487de288ea07cc6f39df2befb5383935285537
 Status changed from needs_work to needs_review
comment:31 followup: ↓ 33 Changed 14 months ago by
 Reviewers changed from JeanPhilippe Labbé to JeanPhilippe Labbé, Matthias Koeppe
+ 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 nondual mode, is the resulting order relation still correct?
comment:32 Changed 14 months ago by
 Commit changed from 92487de288ea07cc6f39df2befb5383935285537 to 6b7b5b6c17a645f55766666295a0424de8efde72
Branch pushed to git repo; I updated commit sha1. New commits:
6b7b5b6  make hash function consistent with dual mode

comment:33 in reply to: ↑ 31 Changed 14 months ago by
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 nondual 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.
comment:34 Changed 14 months ago by
 Status changed from needs_review to positive_review
comment:35 Changed 14 months ago by
Thank you.
comment:36 Changed 14 months ago by
 Branch changed from public/28982reb8 to 6b7b5b6c17a645f55766666295a0424de8efde72
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
add hasse_diagram to combinatorial polyhedron
implemented method hasse diagram for polyhedra
use combinatorial polyhedron to obtain face lattice of polyhedron