Opened 11 months ago
Last modified 4 weeks ago
#29683 needs_review enhancement
"look up" a face in the face lattice of a polyhedron
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  polyhedron, faces, meet, join 
Cc:  jipilab, ghLaisRast, vdelecroix  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  public/29683reb2 (Commits, GitHub, GitLab)  Commit:  69740e73fa5df58a5ee4a69937cae6aeb58a7271 
Dependencies:  Stopgaps: 
Description
We implement two methods that look up a face in the face lattice of a polyhedron:
meet_of_Vrep
 the smallest face containing specified Vrepresentativesjoin_of_facets
 the largest face contained specified facets
This allows an easy answer for https://ask.sagemath.org/question/34485/whatisthemostefficientwaytolookupafaceinthefacelatticeofapolyhedron/#50965
Change History (11)
comment:1 Changed 11 months ago by
 Branch set to pubic/29683
 Status changed from new to needs_review
comment:2 Changed 11 months ago by
 Branch changed from pubic/29683 to public/29683
 Commit set to 521f9e0352a52e85f647dc2e2c9e6a784c563489
comment:3 Changed 10 months ago by
 Status changed from needs_review to needs_work
There are failing tests. I would wait until the dependices are taken care of to make things work again.
comment:4 Changed 7 months ago by
 Milestone changed from sage9.2 to sage9.3
comment:5 Changed 7 months ago by
 Branch changed from public/29683 to public/29683reb
 Commit changed from 521f9e0352a52e85f647dc2e2c9e6a784c563489 to a6f53afd730cae0b29c666c3767636346d583de2
 Status changed from needs_work to needs_review
comment:6 Changed 7 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 3 months ago by
 Branch changed from public/29683reb to public/29683reb2
 Commit changed from a6f53afd730cae0b29c666c3767636346d583de2 to 7e0a25e2196de51fe6c4b57b8ba446f69b374136
 Dependencies #29681 deleted
 Status changed from needs_work to needs_review
comment:8 Changed 3 months ago by
Some quick comments:
 "The offset is taken correctly"  what's that?
 Change "reseted" to "reset"
 "In case of an unbounded polyhedron" > "In the case ..."
comment:9 Changed 3 months ago by
I discovered a bug by accident:
sage: P = polytopes.permutahedron(3, backend='cdd') sage: [x.ambient_Hrepresentation() for x in P.facets()] [(An inequality (1, 1, 0) x  3 >= 0, An inequality (1, 0, 1) x  3 >= 0), (An inequality (1, 1, 0) x  3 >= 0, An inequality (1, 0, 0) x  1 >= 0), (An inequality (1, 1, 0) x  3 >= 0, An inequality (0, 1, 1) x  3 >= 0), (An inequality (1, 1, 0) x  3 >= 0, An inequality (0, 1, 0) x  1 >= 0), (An inequality (1, 1, 0) x  3 >= 0, An inequality (0, 0, 1) x  1 >= 0), (An inequality (1, 1, 0) x  3 >= 0, An equation (1, 1, 1) x  6 == 0)]
The problem is that the backend cdd
doesn't put equations in a stable place, which my code assumed. It depends whether you initialize from Vrep or from Hrep I guess.
comment:10 Changed 3 months ago by
 Commit changed from 7e0a25e2196de51fe6c4b57b8ba446f69b374136 to 69740e73fa5df58a5ee4a69937cae6aeb58a7271
Branch pushed to git repo; I updated commit sha1. New commits:
69740e7  improved documentation

comment:11 Changed 4 weeks 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.
Last 10 new commits:
documentation
coverage and small improvement
method `reset` for the face iterator
typo
method `ignore_subsets`
method current and fix for reset
join_of_Vrep and meet_of_facets for face iterator
expose in combinatorial_polyhedron
raise index error for index error
expose in Polyhedron_base