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: gh-kliem Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords: polyhedron, faces, meet, join
Cc: jipilab, gh-LaisRast, ​vdelecroix Merged in:
Authors: Jonathan Kliem Reviewers:
Report Upstream: N/A Work issues:
Branch: public/29683-reb2 (Commits, GitHub, GitLab) Commit: 69740e73fa5df58a5ee4a69937cae6aeb58a7271
Dependencies: Stopgaps:

Status badges

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 Vrepresentatives
  • join_of_facets -- the largest face contained specified facets

This allows an easy answer for ​https://ask.sagemath.org/question/34485/what-is-the-most-efficient-way-to-look-up-a-face-in-the-face-lattice-of-a-polyhedron/#50965

Change History (11)

comment:1 Changed 11 months ago by gh-kliem

  • Branch set to pubic/29683
  • Status changed from new to needs_review

comment:2 Changed 11 months ago by gh-kliem

  • Branch changed from pubic/29683 to public/29683
  • Commit set to 521f9e0352a52e85f647dc2e2c9e6a784c563489

Last 10 new commits:

295039adocumentation
d36da4acoverage and small improvement
2d0f0d9method `reset` for the face iterator
6d99a4ctypo
5711f6bmethod `ignore_subsets`
f6633bdmethod current and fix for reset
e8c17c3join_of_Vrep and meet_of_facets for face iterator
b371a73expose in combinatorial_polyhedron
954b5c8raise index error for index error
521f9e0expose in Polyhedron_base

comment:3 Changed 10 months ago by gh-kliem

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

  • Milestone changed from sage-9.2 to sage-9.3

comment:5 Changed 7 months ago by gh-kliem

  • Branch changed from public/29683 to public/29683-reb
  • Commit changed from 521f9e0352a52e85f647dc2e2c9e6a784c563489 to a6f53afd730cae0b29c666c3767636346d583de2
  • Status changed from needs_work to needs_review

New commits:

19d2742join_of_Vrep and meet_of_facets for face iterator
c5c17ffaccount for changes in the newest develop
7a4b950expose in combinatorial_polyhedron
f108b06raise index error for index error; fix doctests
a69ba9fexpose in Polyhedron_base
a6f53affix doctests

comment:6 Changed 7 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 3 months ago by gh-kliem

  • Branch changed from public/29683-reb to public/29683-reb2
  • Commit changed from a6f53afd730cae0b29c666c3767636346d583de2 to 7e0a25e2196de51fe6c4b57b8ba446f69b374136
  • Dependencies #29681 deleted
  • Status changed from needs_work to needs_review

New commits:

2a14433join_of_Vrep and meet_of_facets for face iterator
530d85cexpose in combinatorial_polyhedron
73a8be1raise index error for index error; fix doctests
c7ce411expose in Polyhedron_base
7e0a25efix doctests

comment:8 Changed 3 months ago by mkoeppe

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

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 git

  • Commit changed from 7e0a25e2196de51fe6c4b57b8ba446f69b374136 to 69740e73fa5df58a5ee4a69937cae6aeb58a7271

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

69740e7improved documentation

comment:11 Changed 4 weeks 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.

Note: See TracTickets for help on using tickets.