Opened 14 months ago

Closed 4 months ago

#30469 closed enhancement (fixed)

Implement `as_combinatorial_polyhedron` for combinatorial faces of polyhedra

Reported by: gh-kliem Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by gh-kliem)

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 git

  • Commit set to 4c18c3d106fc9d66ab7e4c3959f3e1a03f7812df

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

b35a670document pyramid method in `ListOfFaces`
afb046ctemporary commit
20a39b6outsource inclusion maximal
b672fcaremoved redundant function
a7b4f0aMerge branch 'u/gh-kliem/outsource_inclusion_maximal' of git://trac.sagemath.org/sage into u/gh-kliem/combinatorial_face_as_polyhedron
1f558dbtemporary commit
e12e0c5add test for trailing bits
57ad251remove unused things
281450edocumentation
4c18c3dsafe some time by random only some of the tests

comment:2 Changed 14 months ago by gh-kliem

  • Status changed from new to needs_review

comment:3 Changed 14 months ago by gh-kliem

  • Description modified (diff)
  • Status changed from needs_review to needs_work

comment:4 Changed 14 months ago by git

  • Commit changed from 4c18c3d106fc9d66ab7e4c3959f3e1a03f7812df to 6bc5e6728726530180a1fefa0c73e7f8d59e78a3

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

6bc5e67use correct terminology

comment:5 Changed 14 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:6 Changed 14 months ago by gh-kliem

  • 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 mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3

comment:8 Changed 9 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:9 Changed 6 months ago by gh-kliem

  • Branch changed from u/gh-kliem/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

New commits:

5912839implement combinatorial face as polyhedron
1d58214update documentation

comment:10 Changed 6 months ago by mkoeppe

  • Cc yzh added

comment:11 Changed 6 months ago by mkoeppe

Shouldn't this method be called as_combinatorial_polyhedron?

comment:12 Changed 6 months ago by git

  • Commit changed from 1d58214e420b6424161098cf0be72ebe451587fb to 3896c3224b9b41bac9c78ff1c2f173ec466d8ed9

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

3896c32fix naming and fix a doctest

comment:13 Changed 6 months ago by gh-kliem

  • 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 gh-kliem

  • Dependencies set to #31821

Adding #31821 as a dependency.

It merges cleanly and tests run successful. Which is important, because the testsuite of combinatorial polyhedron is not run without #31821.

comment:15 Changed 6 months ago by mkoeppe

I'm getting a merge conflict with (I think) #27366

comment:16 Changed 6 months ago by gh-kliem

Yes, that is because someone introduced trailing spaces and my editor deletes them automatically.

comment:17 Changed 6 months ago by git

  • Commit changed from 3896c3224b9b41bac9c78ff1c2f173ec466d8ed9 to 82db4082aa4c29a7572bb22981e03f524cabbc36

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

82db408reintroduce spaces to fix merge conflict

comment:18 Changed 6 months ago by gh-kliem

Merges fine now.

comment:19 Changed 6 months ago by mkoeppe

Thanks

comment:20 Changed 6 months ago by mkoeppe

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 git

  • Commit changed from 82db4082aa4c29a7572bb22981e03f524cabbc36 to f460b23a68b891ba6baad0f221d2956f7d61ee35

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

f460b23improve documentation

comment:22 Changed 6 months ago by mkoeppe

Maybe change the variables names for the faces and quotients in these examples for consistency?

comment:23 Changed 6 months ago by git

  • Commit changed from f460b23a68b891ba6baad0f221d2956f7d61ee35 to 479f743f27fd76a062a0247d1b8d7bb4c9f451f3

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

479f743better variable names for documentation

comment:24 Changed 6 months ago by yzh

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 yzh

  • :meth:~sage.geometry.polyhedron.base.Polyhedron_base.meet_of_facets | largest face contained specified facets` --> contained in the specified facets
  • Polyhedron_base.join_of_Vrep(self, *Vrepresentatives): ... in case of... --> "in the case of" * 2
  • FaceIterator_base(SageObject).join_of_Vrep(self, *indices): .. NOTE:: ... may not te well defined. --> "be"
  • Why is it meet_of_facets, but not meet_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 yzh

Sorry, the comments 24 & 25 are supposed to be on #29683

comment:27 Changed 6 months ago by mkoeppe

  • 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 tscrim

  • 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 mkoeppe

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 gh-kliem

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 mkoeppe

  • 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 gh-kliem

Thank you.

comment:33 Changed 4 months ago by git

  • 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:

a5a5a2cMerge tag '9.4.beta2' into t/30469/public/30469

comment:34 Changed 4 months ago by mkoeppe

  • Status changed from needs_review to positive_review

comment:35 Changed 4 months ago by vbraun

  • Branch changed from public/30469 to a5a5a2c4c467c2bb61f35971767709978d2192d8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.