Only subfaces/supfaces for polyhedral face iterator

[kliem]

We allow for the face iterator to only visit subsets of the current face.

Depends on #29683
Depends on #31245

CC: @mkoeppe @yuan-zhou

Component: geometry

Keywords: face iterator, polyhedron

Author: Jonathan Kliem

Branch/Commit: 7f7e630

Reviewer: Yuan Zhou, Matthias Koeppe

Issue created by migration from https://trac.sagemath.org/ticket/31819

[kliem]

Dependencies: #29683

[sagetrac-git]

Changed commit from a95f8d7 to 1cb1b78

[sagetrac-git]

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

69fcd71	fix bug revealed by a_maximal_chain
1cb1b78	fix error message in doctest

[sagetrac-git]

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

2dc14f5

fix the order of the coatoms when resetting the face iterator

[sagetrac-git]

Changed commit from 1cb1b78 to 2dc14f5

[sagetrac-git]

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

2e41ed7

fix a variable name and add a doctest

[sagetrac-git]

Changed commit from 2dc14f5 to 2e41ed7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

2a5a782	expose in combinatorial_polyhedron
6cecfd7	raise index error for index error; fix doctests
9a66e32	expose in Polyhedron_base
977c088	fix doctests
15e2c58	improved documentation
deca8e0	fix a variable name and add a doctest
be121ad	implement only subfaces/supfaces for face iterator
ee42e98	fix bug revealed by a_maximal_chain
05ec5b2	fix error message in doctest
6ddf228	fix the order of the coatoms when resetting the face iterator

[sagetrac-git]

Changed commit from 2e41ed7 to 6ddf228

[yuan-zhou]

comment:7

(Edited)
You probably need to rebase this ticket on the #29683, or put face.ambient_H_indices(add_equations=False) everywhere.

[yuan-zhou]

comment:8

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

[yuan-zhou]

comment:9

Does self.structure.dimension in cdef int find_face(self, face_t face) except -1 need changing?

[yuan-zhou]

comment:10

In face_iterator.pxd: New value 3 to be added to the comment

int face_status            # 0 not initialized, 1 initialized, 2 added to visited_all

[yuan-zhou]

comment:11

raise ValueError("cannot only visit subsets after ignoring a face")
raise ValueError("cannot ignore a face after setting iterator to only visit subsets")

I understood the first, but not the second. Why is it an error, rather than say that the iterator is consumed?
I apologize if this is a silly question

[yuan-zhou]

comment:12

cdef int only_subsets(self) except -1:
    self.structure.highest_dimension = self.structure.current_dimension - 1

Why doesn't it prevent visiting the (sub) faces of dimension >= self.structure.current_dimension?

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

c3f028b	check with a nice error for negative indices
110228e	better check for the far face containment
ec79d1e	implement only subfaces/supfaces for face iterator
35c50d7	fix bug revealed by a_maximal_chain
8609ee2	fix error message in doctest
1f508a8	fix the order of the coatoms when resetting the face iterator
b6e097d	do not display equations for doctests illustrating how the iterator works
ff87201	update face status
a1b4c12	consume the iterator if running ignore_subsets after only_subsets
40d5640	specify for `find_face` that we assume the iterator to be clean

[sagetrac-git]

Changed commit from 6ddf228 to 40d5640

[kliem]

comment:14

Replying to @yuan-zhou:

raise ValueError("cannot only visit subsets after ignoring a face")
raise ValueError("cannot ignore a face after setting iterator to only visit subsets")

I understood the first, but not the second. Why is it an error, rather than say that the iterator is consumed?
I apologize if this is a silly question

It's not a silly question and even if it where: You are reviewing the ticket and I'm very thankful for this. You have every right to ask silly questions.

Fixed.

[kliem]

comment:15

Replying to @yuan-zhou:

Does self.structure.dimension in cdef int find_face(self, face_t face) except -1 need changing?

I specified what I expect in find_face. It's a hidden cython method. So I think it is fine to assume things without checking.

It's not a terrible fail, if self.structure.highest_dimension was set. This would just be ignored in this case.

[kliem]

comment:16

Replying to @yuan-zhou:

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

This just prevents segmentation fault. It's never supposed to happen anyway. In fact I can't even change this. Because when I set highest_dimension it will be equal to current_dimension. Only after running this, is current_dimension lower, if there are faces left.

[kliem]

comment:17

Replying to @yuan-zhou:

cdef int only_subsets(self) except -1:
    self.structure.highest_dimension = self.structure.current_dimension - 1

Why doesn't it prevent visiting the (sub) faces of dimension >= self.structure.current_dimension?

I don't understand the question.

next_dimension first calls next_face_loop. only_subsets makes sure that next_face_loop actually gets to the point of calling get_next_level (unless our face is the the only face left, than there are no new subfaces). If new_faces_counter is non-zero, the current dimension is lowered and it holds that current_dimension < highest_dimension.

If new_faces_counter is zero and there are no new subfaces, then next_face_loop returns 0 and next_dimension terminates as current_dimension = highest_dimension.

Whenever next_face_loop raises the dimension, it will return 0. This way next_dimension will in fact check, that we still have current_dimension <= highest_dimension.

[kliem]

Work Issues: Merge conflict with #31245. One of them needs to be rebased.

[yuan-zhou]

comment:19

Replying to @kliem:

Replying to @yuan-zhou:

Does this need to be changed to structure.highest_dimension? Or maybe I'm looking at a wrong version of the code.

cdef inline int next_face_loop(iter_t structure) nogil except -1:
    r"""
    See :meth:`FaceIterator.next_face_loop`.
    """
    if unlikely(structure.current_dimension == structure.dimension):
        # The function is not supposed to be called,
        # just prevent it from crashing.
        raise StopIteration

This just prevents segmentation fault. It's never supposed to happen anyway. In fact I can't even change this. Because when I set highest_dimension it will be equal to current_dimension. Only after running this, is current_dimension lower, if there are faces left.

I meant to change to if unlikely(self.structure.current_dimension > self.structure.highest_dimension): like all other checkings.

Sure, if it never happens, then the current version is fine.

[yuan-zhou]

comment:20

    if n_faces <= 1:
        # There will be no more faces from intersections.
        structure.current_dimension += 1
        return 0

What do you mean by "no more faces from intersections"? Why is it n_faces <= 1, not n_faces == 0, nor n_faces == 1?

[yuan-zhou]

comment:21

All other things on this ticket look good to me. Thanks for the explanations!

[kliem]

comment:26

Thank you.

However, I will set this on "needs work" due to merge conflict with #31245. Depending on whether #31245 gets in or not, I will either rebase here or rebase #31245 and then put it back on "positive review".

[mkoeppe]

comment:27

Ready to merge #31245?

[kliem]

comment:28

I don't know, if #31245 will be rejected again. But it looks like it's done now. It just triggered an unrelated bug.

What is the best way to proceed from here? I could just create a branch for this ticket here on top of #31245 and can always go back to the old branch if that fails.

[mkoeppe]

comment:29

Sure, it's easy to just back out the merge if necessary

[kliem]

Changed commit from 40d5640 to d073ca5

[kliem]

Last 10 new commits:

70a8791	Merge branch 'u/gh-kliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/gh-kliem/first_parallel_version_of_face_iterator_reb2
fdbe95f	use cython.parallel.threadid instead of omp_get_thread_num
4ae6966	Merge tag '9.4.beta0' into t/31245/first_parallel_version_of_face_iterator_reb2
bfb4efb	Merge branch 'u/mkoeppe/first_parallel_version_of_face_iterator_reb2' of git://trac.sagemath.org/sage into u/mkoeppe/first_parallel_version_of_face_iterator_reb3
4c0a4ae	initialize do_f_vector
9119d8e	merge in #31245
5dc2c8c	merge in public/31834
f1270b0	Merge branch 'public/31834-reb' of git://trac.sagemath.org/sage into public/31834-reb2
297792a	equalities -> equations for #31821 as well
d073ca5	Merge branch 'public/31834-reb2' of git://trac.sagemath.org/sage into u/gh-kliem/only_subsets_reb

[kliem]

Changed branch from u/gh-kliem/only_subsets to u/gh-kliem/only_subsets_reb

[kliem]

comment:31

Rebased on #31245 and new version of #29683.

Needed to fix max_dim in next_dimension because of #31245.

[kliem]

Changed work issues from Merge conflict with #31245. One of them needs to be rebased. to none

[kliem]

Changed dependencies from #29683 to #29683, #31245

[kliem]

comment:32

Actually rebasing on new version of #29683 and then pulling in #31245.

---

Last 10 new commits:

99ddc2f	better check for the far face containment
0f78d2a	implement only subfaces/supfaces for face iterator
6c88068	fix bug revealed by a_maximal_chain
b72578b	fix error message in doctest
ad75abb	fix the order of the coatoms when resetting the face iterator
3d158ad	do not display equations for doctests illustrating how the iterator works
353313c	update face status
842fb8e	consume the iterator if running ignore_subsets after only_subsets
250f0e4	specify for `find_face` that we assume the iterator to be clean
542baee	merge in #31245

[kliem]

Changed commit from d073ca5 to 542baee

[kliem]

Changed branch from u/gh-kliem/only_subsets_reb to u/gh-kliem/only_subsets_reb2

[mkoeppe]

Changed branch from u/gh-kliem/only_subsets_reb2 to u/mkoeppe/only_subsets_reb2

[mkoeppe]

Changed commit from 542baee to 7f7e630

[mkoeppe]

Changed reviewer from Yuan Zhou to Yuan Zhou, Matthias Koeppe

[mkoeppe]

comment:34

Back to positive review. LGTM

---

New commits:

3e0229f	Merge tag '9.4.beta3' into t/31834/public/31834-reb2
8190917	Merge #31834
7f7e630	Merge #29683

[kliem]

comment:35

Thank you.

[vbraun]

Changed branch from u/mkoeppe/only_subsets_reb2 to 7f7e630