Opened 14 months ago
Closed 4 months ago
#30469 closed enhancement (fixed)
Implement `as_combinatorial_polyhedron` for combinatorial faces of polyhedra
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  polyhedral face, face figure, combinatorial polyhedron 
Cc:  yzh, tscrim  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Matthias Koeppe, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  a5a5a2c (Commits, GitHub, GitLab)  Commit:  a5a5a2c4c467c2bb61f35971767709978d2192d8 
Dependencies:  #31821  Stopgaps: 
Description (last modified by )
We implement a method that obtains a combinatorial face or the quotient.
This is much faster than as_polyhedron
from polyhedral face and could be used to obtain a polyhedral face geometrically with precomputed double description.
Change History (35)
comment:1 Changed 14 months ago by
 Commit set to 4c18c3d106fc9d66ab7e4c3959f3e1a03f7812df
comment:2 Changed 14 months ago by
 Status changed from new to needs_review
comment:3 Changed 14 months ago by
 Description modified (diff)
 Status changed from needs_review to needs_work
comment:4 Changed 14 months ago by
 Commit changed from 4c18c3d106fc9d66ab7e4c3959f3e1a03f7812df to 6bc5e6728726530180a1fefa0c73e7f8d59e78a3
Branch pushed to git repo; I updated commit sha1. New commits:
6bc5e67  use correct terminology

comment:5 Changed 14 months ago by
 Status changed from needs_work to needs_review
comment:6 Changed 14 months ago by
 Status changed from needs_review to needs_work
I want to redesign some of the setup before making everything more complicated.
More precisely, creating strucutures face_struct
and faces_list_struct
that take care of the details. Then this overly long argument list of get_next_level
will just reduce to three arguments or so. This would also make future changes easier including the transition to bitsets.pxi
.
comment:7 Changed 12 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:8 Changed 9 months ago by
 Milestone changed from sage9.3 to sage9.4
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:9 Changed 6 months ago by
 Branch changed from u/ghkliem/combinatorial_face_as_polyhedron to public/30469
 Commit changed from 6bc5e6728726530180a1fefa0c73e7f8d59e78a3 to 1d58214e420b6424161098cf0be72ebe451587fb
 Dependencies #30440, #30458 deleted
 Status changed from needs_work to needs_review
comment:10 Changed 6 months ago by
 Cc yzh added
comment:11 Changed 6 months ago by
Shouldn't this method be called as_combinatorial_polyhedron
?
comment:12 Changed 6 months ago by
 Commit changed from 1d58214e420b6424161098cf0be72ebe451587fb to 3896c3224b9b41bac9c78ff1c2f173ec466d8ed9
Branch pushed to git repo; I updated commit sha1. New commits:
3896c32  fix naming and fix a doctest

comment:13 Changed 6 months ago by
 Summary changed from Implement `as_polyhedron` for combinatorial faces of polyhedra to Implement `as_combinatorial_polyhedron` for combinatorial faces of polyhedra
comment:14 Changed 6 months ago by
 Dependencies set to #31821
comment:15 Changed 6 months ago by
I'm getting a merge conflict with (I think) #27366
comment:16 Changed 6 months ago by
Yes, that is because someone introduced trailing spaces and my editor deletes them automatically.
comment:17 Changed 6 months ago by
 Commit changed from 3896c3224b9b41bac9c78ff1c2f173ec466d8ed9 to 82db4082aa4c29a7572bb22981e03f524cabbc36
Branch pushed to git repo; I updated commit sha1. New commits:
82db408  reintroduce spaces to fix merge conflict

comment:18 Changed 6 months ago by
Merges fine now.
comment:19 Changed 6 months ago by
Thanks
comment:20 Changed 6 months ago by
Perhaps rephrase the docstring of as_combinatorial_polyhedron
so it is clearer what quotient is formed (what is "the" polyhedron).
Also perhaps a doctest could show how the Vrep/Hrep? of a quotient is labeled.
(This is relevant for #31803 when we introduce more specific parents, and morphisms)
comment:21 Changed 6 months ago by
 Commit changed from 82db4082aa4c29a7572bb22981e03f524cabbc36 to f460b23a68b891ba6baad0f221d2956f7d61ee35
Branch pushed to git repo; I updated commit sha1. New commits:
f460b23  improve documentation

comment:22 Changed 6 months ago by
Maybe change the variables names for the faces and quotients in these examples for consistency?
comment:23 Changed 6 months ago by
 Commit changed from f460b23a68b891ba6baad0f221d2956f7d61ee35 to 479f743f27fd76a062a0247d1b8d7bb4c9f451f3
Branch pushed to git repo; I updated commit sha1. New commits:
479f743  better variable names for documentation

comment:24 Changed 6 months ago by
src/sage/geometry/polyhedron/base.py L6944: facet.dim() == 0
seems to be v.dim() == 0
. It might be good to include the case isinstance(v, PolyhedronFace)
in the doctest "The input is flexible..."
comment:25 Changed 6 months ago by
:meth:~sage.geometry.polyhedron.base.Polyhedron_base.meet_of_facets
 largest face contained specified facets` > contained in the specified facetsPolyhedron_base.join_of_Vrep(self, *Vrepresentatives): ... in case of...
> "in the case of" * 2FaceIterator_base(SageObject).join_of_Vrep(self, *indices): .. NOTE:: ... may not te well defined.
> "be" Why is it
meet_of_facets
, but notmeet_of_Hrep
? If rays/lines are allowed on the primal side, why doesn't it make sense to consider equations on the dual side?
comment:26 Changed 6 months ago by
Sorry, the comments 24 & 25 are supposed to be on #29683
comment:27 Changed 6 months ago by
 Cc tscrim added
This seems to work well but it would be good if a reviewer who knows Cython better than I do could take a look
comment:28 Changed 6 months ago by
 Reviewers set to Matthias Koeppe, Travis Scrimshaw
Not a Cython comment, but in as_combinatorial_polyhedron
, the REFERENCES
should not be indented.
Since __copy__
is a special Python method, I am slightly worried about making it into a cpdef
method. I think you are better off implementing a cdef _copy
method and calling that from __copy__
.
Looks good other than those two things.
comment:29 Changed 6 months ago by
I have to say I don't fully understand the design of CombinatorialPolyhedron
regarding the labels that are used for the Vrep. When I get the CombinatorialPolyhedron
from a polyhedron, its Vrep consists of geometric VRepresentation objects; and there seems to be no method that returns an abstract CombinatorialPolyhedron
instead (in which the Vrep consists of indices only). Then, why does as_combinatorial_polyhedron
(with quotient=False
) forget the geometric VRepresentation objects and return a CombinatorialPolyhedron
whose Vrep uses indices?
I think this can be made clearer via #31803, which introduces parents.
comment:30 Changed 6 months ago by
You are right. The method in list_of_faces.pyx
might as well return the relabeling map as well, so that the labels can be used.
Vrepresentation
/vertices is clear. But I also keep the labels of the facets, taking the label of the first representative of each facet, if that makes any sense.
I even know all the equations, but that is a hard one for CombinatorialPolyhedron
.
I could even introduce a tiny class InducedRepresentation
that just wrappes around the original Hrepresentation object. I don't know what is best.
comment:31 Changed 5 months ago by
 Status changed from needs_review to positive_review
I think we can work on the refinements regarding the labeling discussed above in #31803.
comment:32 Changed 5 months ago by
Thank you.
comment:33 Changed 4 months ago by
 Commit changed from 479f743f27fd76a062a0247d1b8d7bb4c9f451f3 to a5a5a2c4c467c2bb61f35971767709978d2192d8
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
a5a5a2c  Merge tag '9.4.beta2' into t/30469/public/30469

comment:34 Changed 4 months ago by
 Status changed from needs_review to positive_review
comment:35 Changed 4 months ago by
 Branch changed from public/30469 to a5a5a2c4c467c2bb61f35971767709978d2192d8
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
document pyramid method in `ListOfFaces`
temporary commit
outsource inclusion maximal
removed redundant function
Merge branch 'u/ghkliem/outsource_inclusion_maximal' of git://trac.sagemath.org/sage into u/ghkliem/combinatorial_face_as_polyhedron
temporary commit
add test for trailing bits
remove unused things
documentation
safe some time by random only some of the tests