Opened 3 years ago
Closed 2 years ago
#28982 closed enhancement (fixed)
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é, 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 3 years ago by
Branch: | → public/28982 |
---|
comment:2 Changed 3 years ago by
Commit: | → cfb153d6c9f2c110a2468a920a14f4fa3914735a |
---|
comment:3 Changed 3 years ago by
Status: | new → needs_review |
---|
comment:4 Changed 3 years ago by
Commit: | cfb153d6c9f2c110a2468a920a14f4fa3914735a → 41254c28fc83112e7b3b001a1b12c2995613ca8f |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
41254c2 | fixed pyflakes warnings
|
comment:5 Changed 3 years ago by
Branch: | public/28982 → public/28982-reb |
---|---|
Commit: | 41254c28fc83112e7b3b001a1b12c2995613ca8f → 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 3 years 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 3 years ago by
Branch: | public/28982-reb → public/28982-reb2 |
---|---|
Commit: | f249c9db8be362dbd8aa7adac95b672eddd6d3b4 → 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 3 years ago by
Description: | modified (diff) |
---|
comment:9 Changed 3 years ago by
Commit: | f44afa26835ca7a4991864766c1f1c01c9e6f399 → 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 3 years ago by
Milestone: | sage-9.1 → 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 years ago by
Reviewers: | → Jean-Philippe Labbé |
---|---|
Status: | needs_review → 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 years ago by
Branch: | public/28982-reb2 → public/28982-reb3 |
---|---|
Commit: | e9b3201a8b6dd36d5edf0ac54e4d554d9aaff6b4 → 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca |
Status: | needs_work → needs_review |
comment:13 Changed 3 years ago by
Status: | needs_review → 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 years ago by
Commit: | 92842be2496dd8fd327f84f79a3dd3b3cf1dbfca → 708dd7dcf0dbc70c9c53a3c4946624a389b2580e |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
708dd7d | typo
|
comment:17 Changed 3 years ago by
Branch: | public/28982-reb3 → public/28982-reb4 |
---|---|
Commit: | 708dd7dcf0dbc70c9c53a3c4946624a389b2580e → 819d5433d00510a69bc43b8138296713cd9853f5 |
Status: | needs_work → 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 3 years ago by
Status: | needs_review → needs_work |
---|
It doesn't seem to build... See patchbot.
comment:19 Changed 3 years ago by
Branch: | public/28982-reb4 → public/28982-reb5 |
---|---|
Commit: | 819d5433d00510a69bc43b8138296713cd9853f5 → 0e865a04996fe35097ffd04fbdb879b97732e2ce |
Status: | needs_work → 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:21 Changed 3 years ago by
Status: | positive_review → 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 3 years ago by
Dependencies: | → #29583, #28894 |
---|
comment:23 Changed 3 years ago by
Dependencies: | #29583, #28894 → #29583 |
---|
comment:24 Changed 3 years ago by
Branch: | public/28982-reb5 → public/28982-reb6 |
---|---|
Commit: | 0e865a04996fe35097ffd04fbdb879b97732e2ce → 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 3 years ago by
Status: | needs_work → needs_review |
---|
comment:27 Changed 2 years ago by
Branch: | public/28982-reb6 → public/28982-reb7 |
---|---|
Commit: | f4e1deccef14f7aa3dcf1e19241ac042157e4f92 → 22974744b2b580cf94737ca9d04734d89687b73e |
Status: | needs_work → needs_review |
comment:28 Changed 2 years ago by
+ 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
comment:29 Changed 2 years ago by
Status: | needs_review → needs_work |
---|
comment:30 Changed 2 years ago by
Branch: | public/28982-reb7 → public/28982-reb8 |
---|---|
Commit: | 22974744b2b580cf94737ca9d04734d89687b73e → 92487de288ea07cc6f39df2befb5383935285537 |
Status: | needs_work → needs_review |
comment:31 follow-up: 33 Changed 2 years ago by
Reviewers: | Jean-Philippe Labbé → Jean-Philippe 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 non-dual mode, is the resulting order relation still correct?
comment:32 Changed 2 years ago by
Commit: | 92487de288ea07cc6f39df2befb5383935285537 → 6b7b5b6c17a645f55766666295a0424de8efde72 |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
6b7b5b6 | make hash function consistent with dual mode
|
comment:33 Changed 2 years 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 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.
comment:34 Changed 2 years ago by
Status: | needs_review → positive_review |
---|
comment:36 Changed 2 years ago by
Branch: | public/28982-reb8 → 6b7b5b6c17a645f55766666295a0424de8efde72 |
---|---|
Resolution: | → fixed |
Status: | positive_review → 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