Opened 7 months ago
Closed 4 months ago
#31748 closed enhancement (fixed)
PolyhedralComplex
Reported by:  yzh  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  polyhedral complex 
Cc:  mkoeppe, jhpalmieri, jipilab, tscrim  Merged in:  
Authors:  Yuan Zhou  Reviewers:  John Palmieri, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  32d34b7 (Commits, GitHub, GitLab)  Commit:  32d34b71534cea23b6b4cb382ce13064c5b5e928 
Dependencies:  Stopgaps: 
Description (last modified by )
Create (geometric) PolyhedralComplex
, whose cells are Sage Polyhedra.
Change History (60)
comment:1 Changed 7 months ago by
 Branch set to u/yzh/polyhedralcomplex
comment:2 Changed 7 months ago by
 Cc jhpalmieri added
 Commit set to f76287b8ec12aa28e413a9629b36db20b1e92f2f
 Description modified (diff)
comment:3 Changed 7 months ago by
 Commit changed from f76287b8ec12aa28e413a9629b36db20b1e92f2f to 577456a0c3ffddef49d02301c4b59a73a7acd636
Branch pushed to git repo; I updated commit sha1. New commits:
577456a  make tox happy

comment:4 Changed 7 months ago by
 Commit changed from 577456a0c3ffddef49d02301c4b59a73a7acd636 to 38aaf756f91cf3a7e652e9dfdcc0696a1c632afd
Branch pushed to git repo; I updated commit sha1. New commits:
38aaf75  add doc for html build

comment:5 Changed 7 months ago by
 Status changed from new to needs_review
comment:6 Changed 7 months ago by
add author name so that the patchbot runs
comment:7 Changed 7 months ago by
 Commit changed from 38aaf756f91cf3a7e652e9dfdcc0696a1c632afd to 22c902432730cd46535698aa7e8cd2652b6322c4
Branch pushed to git repo; I updated commit sha1. New commits:
22c9024  new methods product, disjoint_union, join

comment:8 Changed 7 months ago by
comment:9 Changed 7 months ago by
 Commit changed from 22c902432730cd46535698aa7e8cd2652b6322c4 to 0bd40423ef06c9c62dc227eb0f756a0d0290e535
comment:10 Changed 7 months ago by
 Commit changed from 0bd40423ef06c9c62dc227eb0f756a0d0290e535 to 18c1a33531445265b88c2b1bcd517165d16463d1
comment:11 Changed 7 months ago by
 Commit changed from 18c1a33531445265b88c2b1bcd517165d16463d1 to 45f080c775da363fa7bb729305a6094b3e32c9d9
Branch pushed to git repo; I updated commit sha1. New commits:
45f080c  implement PolyhedralComplex.remove_cell()

comment:12 followup: ↓ 16 Changed 7 months ago by
Ready for review.
I don't have much experience with abstract complexes. I'd like to know if this is going in the right direction with Sage homology.
I'm also wondering what other methods of PolyhedralComplex
could be interesting. Maybe interactions between PolyhedralComplex
and SimplicialComplex
such as PolyhedralComplex.subdivide()
and SimplicialComplex.geometric_realization()
? And interactions between PolyhedralComplex
and rational polyhedral fan?
Note that the methods wedge
, chain_complex
and alexander_whitney
are currently missing, as I don't know how to implement them.
Any advice or comment is greatly appreciated! Thanks.
comment:13 Changed 7 months ago by
 Cc jipilab tscrim added
comment:14 Changed 7 months ago by
 Commit changed from 45f080c775da363fa7bb729305a6094b3e32c9d9 to dfe5cb8e57280ad49f1c4febf898dbbdceba0c4e
comment:15 Changed 7 months ago by
 Commit changed from dfe5cb8e57280ad49f1c4febf898dbbdceba0c4e to 752011fc6cb7e1ad97b6c4c675e3ba0533df3a91
Branch pushed to git repo; I updated commit sha1. New commits:
752011f  zero is followed by plural countable nouns

comment:16 in reply to: ↑ 12 ; followups: ↓ 20 ↓ 21 Changed 6 months ago by
Replying to yzh:
Ready for review.
I don't have much experience with abstract complexes. I'd like to know if this is going in the right direction with Sage homology.
It looks good to me so far, thank you for all of the work you've done.
Note that the methods
wedge
,chain_complex
andalexander_whitney
are currently missing, as I don't know how to implement them.
I don't know anything about polyhedral complexes. The wedge is the onepoint union, and to construct this, you're going to have to translate the two complexes so that they share a point. Is that acceptable? I could imagine taking a complex which has a point (x_1, x_2) and another complex which has a point (y_1, y_2), and forming the join by embedding both in a larger ambient space so that (x_1, x_2) > (x_1, x_2, y_1, y_2) < (y_1, y_2) — the first complex lies in the first coordinates, the second in the last coordinates. I don't know if that's a sensible construction from the point of view of people who actually work with these objects.
chain_complex
— is there a standard way to produce a chain complex from a polyhedral complex? I would hope so, and I would hope that it's written down somewhere. We shouldn't invent something from scratch. Can we have a method that triangulates the complex and produces a simplicial complex? How hard would that be? I found this: https://sites.millersville.edu/rumble/slides/SevilleFeb2018.pdf. Is it helpful?
alexander_whitney
— I don't know how to handle this (although maybe the Umble slides describe it), and in any case, it's tied to a map of chain complexes, so there is no need to worry about it until the chain complex situation is resolved.
comment:17 Changed 6 months ago by
By the way, is it possible to have a class of abstract polyhedral complexes, in addition to these more concrete complexes? Maybe it would be nice to view the product of two simplicial complexes as an "abstract" polyhedral complex without having to choose embeddings of the simplicial complexes.
comment:18 Changed 6 months ago by
That would be #31842  CombinatorialPolyhedralComplex
comment:19 followup: ↓ 23 Changed 6 months ago by
I am also wondering where delta complexes fit in this story. Is every abstract polyhedral complex a delta complex?
comment:20 in reply to: ↑ 16 ; followup: ↓ 22 Changed 6 months ago by
Replying to jhpalmieri:
chain_complex
— is there a standard way to produce a chain complex from a polyhedral complex? I would hope so, and I would hope that it's written down somewhere. We shouldn't invent something from scratch. Can we have a method that triangulates the complex and produces a simplicial complex? How hard would that be? I found this: https://sites.millersville.edu/rumble/slides/SevilleFeb2018.pdf. Is it helpful?
My quick thought for the case of a *polytope* complex this is you could take any simplicial complex equivalent to the topdimensional polytopes to get an equivalent simplicial complex. Then the generalized Stokes theorem would allow you to compute a differential via that simplicial decomposition. Moreover, we should be able to do this with a combinatorial description (i.e., just using the vertices of the polytope complex).
For a polyhedral complex, then we have issues with noncompactness to address. Although in the notes John linked to, they define a polyhedral complex to be with polytope faces. So I think we should be slightly careful about naming to distinguish which objects we allow.
There's a wikipedia stub page about this as well: https://en.wikipedia.org/wiki/Polyhedral_complex The ability to plot tropical varieties would be great to have. (Reminder to myself, I still need to implement tropical polynomials...) It might be good to also link this to special cases such as fans.
comment:21 in reply to: ↑ 16 Changed 6 months ago by
@tscrim @jhpalmieri Thank you very much for the feedback! I have yet to study those references.
Replying to jhpalmieri:
Can we have a method that triangulates the complex and produces a simplicial complex?
Do you mean the method PolyhedralComplex.subdivide(make_simplicial=True)
? It produces a geometric simplicial complex.
Then, #31842  CombinatorialPolyhedralComplex
will take care of making it abstract.
comment:22 in reply to: ↑ 20 Changed 6 months ago by
Replying to tscrim:
It might be good to also link this to special cases such as fans.
I considered to link between PolyhedralComplex
and RationalPolyhedralFan
. However, I really didn't want to restrict to the rational case only.
comment:23 in reply to: ↑ 19 Changed 6 months ago by
Replying to mkoeppe:
I am also wondering where delta complexes fit in this story. Is every abstract polyhedral complex a delta complex?
The cells in a Deltacomplex are all simplices, but maybe any triangulation of an abstract polyhedral complex will always be a Deltacomplex. The boundary of a simplex in a Deltacomplex is not determined by its vertices: you can make a Deltacomplex model of a 2sphere out of two triangles with a common boundary. Is that allowed in an abstract polyhedral complex?
comment:24 Changed 6 months ago by
In my opinion, we can merge this and then refine later. What do others think?
comment:25 followup: ↓ 26 Changed 6 months ago by
No objection here. It looks great to me!
Minor comment: Shouldn't disjoint_union
raise an error if the input is not disjoint?
Typos: interoir>interior, complexe>complex
comment:26 in reply to: ↑ 25 Changed 6 months ago by
Minor comment: Shouldn't
disjoint_union
raise an error if the input is not disjoint?
It does.
sage: pc = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 2)])]) sage: pc2 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (0, 1)])]) sage: pc.disjoint_union(pc2) ValueError: The given cells are not facetoface
comment:27 followup: ↓ 29 Changed 6 months ago by
But
sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)])]) sage: pc2.disjoint_union(pc3) Polyhedral complex with 2 maximal cells
comment:28 Changed 6 months ago by
 Commit changed from 752011fc6cb7e1ad97b6c4c675e3ba0533df3a91 to 27af45ad95dda448babc665b58181717dca6fa47
comment:29 in reply to: ↑ 27 Changed 6 months ago by
Replying to mkoeppe:
But
sage: pc3 = PolyhedralComplex([Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)])]) sage: pc2.disjoint_union(pc3) Polyhedral complex with 2 maximal cells
That looks correct to me.
comment:30 Changed 6 months ago by
Ah, do you mean that pc2.disjoint_union(pc2)
should raise an error?
comment:31 followup: ↓ 33 Changed 6 months ago by
pc2 and pc3 are not disjoint, so this should be an error
comment:32 Changed 6 months ago by
sage: pc0 = PolyhedralComplex() sage: pc0.ambient_dimension() 1 sage: pc0.add_cell(Polyhedron(vertices=[(1, 1), (0, 0), (1, 0)])) ValueError: The given cell is not a polyhedron in the same ambient space.
I think it would be better to add a keyword argument ambient_dim
to __init__
so that one can set up an empty complex in the intended ambient space
comment:33 in reply to: ↑ 31 Changed 6 months ago by
Good point! What I implemented in disjoint_union
is actually the union, but not the disjoint union.
Replying to mkoeppe:
pc2 and pc3 are not disjoint, so this should be an error
comment:34 Changed 6 months ago by
 Commit changed from 27af45ad95dda448babc665b58181717dca6fa47 to 372a10767ed2eb77b40a6ba0da6a77a576631b2d
comment:35 Changed 6 months ago by
My comments have all been addressed, thanks!
comment:36 Changed 6 months ago by
I agree that we can merge this without implementing the homology stuff. I have a few comments that should be addressed first:
 It feels like there is a lot of overlap with the
SimplicialComplex
code. Do we want to refactor things to common base classes and/or use inheritance?  The bullet points for
backend
inPolyhedralComplex
's doc are overindented (back them up 2 spaces).  Not every method has a doctest, even if all they currently do is raise a
NotImplementedError
.  It would be good to include a message when you raise an error (see, e.g., the
ValueError
inPolyhedralComplex.__init__
).  Error messages should start with a lowercase and not end with a period/fullstop. This is a Python convention we generally try to follow
 Be consistent with how you do your documentation. I would not use the
:param
format personally.  I think the
_an_element_
should raise anEmptySetError
if it has no elements.
comment:37 Changed 6 months ago by
 Commit changed from 372a10767ed2eb77b40a6ba0da6a77a576631b2d to 0a40f1f841b07be7862f2a97c4cb501ccca451c2
Branch pushed to git repo; I updated commit sha1. New commits:
0a40f1f  improve documentation and error messages

comment:38 Changed 6 months ago by
Thanks, Travis! I revised the code according to your comments (expect for 1).
I agree that PolyhedralComplex
and SimplicialComplex
have many overlapping methods. As you may have noticed, these are methods required by the parent class GenericCellComplex
. However, as one is geometric and the other is abstract, and due to the different ways that cells are stored inside the two complexes, I don't see how one can easily factor out a common base class etc.
comment:39 followup: ↓ 40 Changed 6 months ago by
Typo: "poyhedron" on about line 8.
I might change has_maximal_cell
to is_maximal_cell
. What do you think?
As far as refactoring goes, I see similar code but not identical code, so it would some work to reorganize things. That can be done on another ticket, in my opinion.
comment:40 in reply to: ↑ 39 ; followup: ↓ 42 Changed 6 months ago by
Replying to jhpalmieri:
Typo: "poyhedron" on about line 8.
Thanks for catching that!
I might change
has_maximal_cell
tois_maximal_cell
. What do you think?
I once heard that self.is_xxx(other)
means that "self
is xxx of other
". Therefore, in this case, I would think that cell.is_maximal_cell(polyhedralcomplex)
and polyhedralcomplex.has_maximal_cell(cell)
. If this is not the convention in sage/homology
, I'm happy to change the name to is_maximal_cell
.
As far as refactoring goes, I see similar code but not identical code, so it would some work to reorganize things. That can be done on another ticket, in my opinion.
:)
comment:41 Changed 6 months ago by
 Commit changed from 0a40f1f841b07be7862f2a97c4cb501ccca451c2 to f5be3fa7f178d9ab0390374781f8f16ca1b86b39
Branch pushed to git repo; I updated commit sha1. New commits:
f5be3fa  fix typo

comment:42 in reply to: ↑ 40 Changed 6 months ago by
Replying to yzh:
Replying to jhpalmieri:
I might change
has_maximal_cell
tois_maximal_cell
. What do you think?I once heard that
self.is_xxx(other)
means that "self
is xxx ofother
". Therefore, in this case, I would think thatcell.is_maximal_cell(polyhedralcomplex)
andpolyhedralcomplex.has_maximal_cell(cell)
. If this is not the convention insage/homology
, I'm happy to change the name tois_maximal_cell
.
In simplicial_complex.py
, the methods is_face
and is_shelling_order
use is...
the way I'm suggesting. It's common for is_xxx(self)
to be used the way you say, but not universal, and absolutely not universal for is_xxx(self, x, y, z)
, with more arguments.
comment:43 Changed 6 months ago by
A few things to do before I would set a positive review:
 Add doctests for the
NotImplementedError
raising methods.  Change
has_maximal_cell
tois_maximal_cell
because that is what the docstring is saying. If this washas_maximal_cell
, I would expect it not to take any other arguments.  You can test plotting:
sage: poset.plot(element_labels=d) # not tested
 Change:
TESTS on nonbounded polyhedral complex:: +For a nonbounded polyhedral complex::
 Add a
TestSuite(foo).run()
to the__init__
doctests. (Not really necessary, but I like to see such a test there.)
comment:44 Changed 6 months ago by
comment:45 Changed 5 months ago by
 Status changed from needs_review to needs_work
In light of #31925 I would actually suggest to move PolyhedralComplex
to sage.geometry.polyhedral_complex
 where already similar modules exist: fan
, triangulation
, voronoi_diagram
, hyperplane_arrangement
.
comment:46 Changed 5 months ago by
 Commit changed from f5be3fa7f178d9ab0390374781f8f16ca1b86b39 to 9e7e1fd7e2dec550f016a228c14e5c11a67bff20
comment:47 Changed 5 months ago by
 Commit changed from 9e7e1fd7e2dec550f016a228c14e5c11a67bff20 to 3188e747c31d7a5f933290f1c663510893087cfc
Branch pushed to git repo; I updated commit sha1. New commits:
3188e74  revise according to ticket 31748 comment 43

comment:48 Changed 5 months ago by
 Status changed from needs_work to needs_review
comment:49 Changed 5 months ago by
 Branch changed from u/yzh/polyhedralcomplex to public/geometry/polyhedral_complex31748
 Commit changed from 3188e747c31d7a5f933290f1c663510893087cfc to ee3f294832c4febf69b6ca2b11f501e4e263f37c
 Reviewers set to John Palmieri, Travis Scrimshaw
I made some reviewer changes to the documentation to standardize it a bit. If my changes are good, then I think we can set a positive review.
New commits:
ee3f294  Some reviewer changes to documentation.

comment:50 followup: ↓ 51 Changed 5 months ago by
there is a red patchbot plugin (pyflakes)
comment:51 in reply to: ↑ 50 Changed 5 months ago by
Replying to chapoton:
there is a red patchbot plugin (pyflakes)
In particular:
src/sage/geometry/polyhedral_complex.py:117:1 'sage.structure.sage_object.SageObject' imported but unused src/sage/geometry/polyhedral_complex.py:119:1 'sage.rings.rational_field.QQ' imported but unused src/sage/geometry/polyhedral_complex.py:326:13 local variable 'cells' is assigned to but never used src/sage/geometry/polyhedral_complex.py:967:13 local variable 'cells' is assigned to but never used
comment:52 Changed 5 months ago by
These changes should fix those problems. Should I push a branch? What do you think of just calling self.cells()
instead of cells = self.cells()
?

src/sage/geometry/polyhedral_complex.py
diff git a/src/sage/geometry/polyhedral_complex.py b/src/sage/geometry/polyhedral_complex.py index 351bfe65b3..06dc60380c 100644
a b from sage.topology.cell_complex import GenericCellComplex 114 114 from sage.geometry.polyhedron.constructor import Polyhedron 115 115 from sage.geometry.polyhedron.base import is_Polyhedron 116 116 from sage.modules.free_module_element import vector 117 from sage.structure.sage_object import SageObject118 117 from sage.rings.integer_ring import ZZ 119 from sage.rings.rational_field import QQ120 118 from sage.graphs.graph import Graph 121 119 from sage.combinat.posets.posets import Poset 122 120 from sage.misc.misc import powerset … … class PolyhedralComplex(GenericCellComplex): 323 321 self._face_poset = None 324 322 325 323 if maximality_check: 326 cells =self.cells() # compute self._cells and self._face_poset324 self.cells() # compute self._cells and self._face_poset 327 325 self._maximal_cells = cells_list_to_cells_dict( 328 326 self._face_poset.maximal_elements()) 329 327 if face_to_face_check: … … class PolyhedralComplex(GenericCellComplex): 964 962 Finite poset containing 9 elements 965 963 """ 966 964 if self._face_poset is None: 967 cells =self.cells() # poset is obtained and cached in cells()965 self.cells() # poset is obtained and cached in cells() 968 966 return self._face_poset 969 967 970 968 def is_subcomplex(self, other):
comment:53 Changed 5 months ago by
Thanks for the fixes! Calling self.cells()
looks good to me.
comment:54 Changed 5 months ago by
 Commit changed from ee3f294832c4febf69b6ca2b11f501e4e263f37c to 2f77bbcbf68fb4ef5400dabd912a34f88d5d01c3
Branch pushed to git repo; I updated commit sha1. New commits:
2f77bbc  solve the red patchbot plugin (pyflakes)

comment:55 Changed 5 months ago by
I'm happy. Positive review from everyone else?
comment:57 Changed 4 months ago by
 Status changed from positive_review to needs_work
On 32bit:
********************************************************************** File "src/sage/geometry/polyhedral_complex.py", line 1407, in sage.geometry.polyhedral_complex.PolyhedralComplex.relative_boundary_cells Failed example: [p.vertices() for p in pc_lower_dim.relative_boundary_cells()] Expected: [(A vertex at (0, 2),), (A vertex at (1, 2),)] Got: [(A vertex at (1, 2),), (A vertex at (0, 2),)] ********************************************************************** 1 item had failures: 1 of 17 in sage.geometry.polyhedral_complex.PolyhedralComplex.relative_boundary_cells [451 tests, 1 failure, 14.88 s]  sage t long randomseed=0 src/sage/geometry/polyhedral_complex.py # 1 doctest failed 
comment:58 Changed 4 months ago by
 Commit changed from 2f77bbcbf68fb4ef5400dabd912a34f88d5d01c3 to 32d34b71534cea23b6b4cb382ce13064c5b5e928
comment:59 Changed 4 months ago by
 Status changed from needs_work to positive_review
Trivial fix of added sorted
to doctest.
comment:60 Changed 4 months ago by
 Branch changed from public/geometry/polyhedral_complex31748 to 32d34b71534cea23b6b4cb382ce13064c5b5e928
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
initial implementation of polyhedral_complex.py