Opened 21 months ago
Closed 19 months ago
#31819 closed enhancement (fixed)
Only subfaces/supfaces for polyhedral face iterator
Reported by:  ghkliem  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  face iterator, polyhedron 
Cc:  mkoeppe, yzh  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  Yuan Zhou, Matthias Koeppe 
Report Upstream:  N/A  Work issues:  
Branch:  7f7e630 (Commits, GitHub, GitLab)  Commit:  7f7e6301eb49ed48fd646beae85772344ba52338 
Dependencies:  #29683, #31245  Stopgaps: 
Description
We allow for the face iterator to only visit subsets of the current face.
Change History (36)
comment:1 Changed 21 months ago by
Dependencies:  → #29683 

Status:  new → needs_review 
comment:2 Changed 21 months ago by
Commit:  a95f8d7c5fa17c1dd0076e0c8cb7398e82182d2e → 1cb1b7864dade6b479238c7db4dd9e66424382f1 

comment:3 Changed 21 months ago by
Commit:  1cb1b7864dade6b479238c7db4dd9e66424382f1 → 2dc14f5f761f967f654434bd027d797566dfc9da 

Branch pushed to git repo; I updated commit sha1. New commits:
2dc14f5  fix the order of the coatoms when resetting the face iterator

comment:4 Changed 21 months ago by
Cc:  yzh added 

comment:5 Changed 21 months ago by
Commit:  2dc14f5f761f967f654434bd027d797566dfc9da → 2e41ed7294ae4a1a7517b1de051074c162217cb6 

Branch pushed to git repo; I updated commit sha1. New commits:
2e41ed7  fix a variable name and add a doctest

comment:6 Changed 21 months ago by
Commit:  2e41ed7294ae4a1a7517b1de051074c162217cb6 → 6ddf2284a5ae25d4680e78615e881df6ef5bf0d9 

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

comment:7 Changed 21 months ago by
(Edited)
You probably need to rebase this ticket on the #29683, or put face.ambient_H_indices(add_equations=False)
everywhere.
comment:8 followup: 16 Changed 21 months ago by
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
comment:9 followup: 15 Changed 21 months ago by
Does self.structure.dimension
in cdef int find_face(self, face_t face) except 1
need changing?
comment:10 Changed 21 months ago by
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
comment:11 followup: 14 Changed 21 months ago by
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
comment:12 followup: 17 Changed 21 months ago by
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
?
comment:13 Changed 21 months ago by
Commit:  6ddf2284a5ae25d4680e78615e881df6ef5bf0d9 → 40d56400d156210c2c7c7b9751ac88b84b399acd 

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

comment:14 Changed 21 months ago by
Replying to yzh:
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.
comment:15 Changed 21 months ago by
Replying to yzh:
Does
self.structure.dimension
incdef 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.
comment:16 followup: 19 Changed 21 months ago by
Replying to yzh:
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.
comment:17 Changed 21 months ago by
Replying to yzh:
cdef int only_subsets(self) except 1: self.structure.highest_dimension = self.structure.current_dimension  1Why 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 nonzero, 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
.
comment:18 Changed 21 months ago by
Work issues:  → Merge conflict with #31245. One of them needs to be rebased. 

comment:19 followup: 22 Changed 21 months ago by
Replying to ghkliem:
Replying to yzh:
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 StopIterationThis 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 tocurrent_dimension
. Only after running this, iscurrent_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.
comment:20 followup: 23 Changed 21 months ago by
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
?
comment:21 Changed 21 months ago by
All other things on this ticket look good to me. Thanks for the explanations!
comment:22 followup: 24 Changed 21 months ago by
Replying to yzh:
Replying to ghkliem:
Replying to yzh:
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 StopIterationThis 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 tocurrent_dimension
. Only after running this, iscurrent_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.
That's what I figure you meant. But it does not work. E.g. when you want to only visit the elements below the first facet, the highest dimension will be set to d2
. But current dimension is d1
. Only after next_face_loop
is called has the dimension changed to d2
. This is different from the start. At the start the facets are already known and hence the dimension starts at d1
. But when you want to visit everything below something, the elements below have not been computed yet.
I could set this up differently, if you find it confusing and make only_subsets
call next_face_loop
once.
comment:23 followup: 25 Changed 21 months ago by
Replying to yzh:
if n_faces <= 1: # There will be no more faces from intersections. structure.current_dimension += 1 return 0What do you mean by "no more faces from intersections"? Why is it
n_faces <= 1
, notn_faces == 0
, norn_faces == 1
?
The intersections are obtained by intersecting the last face with each previous ones. If there is only one face, we can stop and don't need get_next_level
to tell us that there are no intersections.
I don't think n_faces == 0
can happen, but it is better to be safe than sorry. Because get_next_level
will intersect the last face with all previous ones. If there is zero faces we have an overflow and the face 2^641
is intersected with all previous once, which will result in an segmentation fault.
But maybe it is better to handle this check as a first thing in get_next_level
. This is probably where it belongs anyway. What do you think?
comment:24 Changed 21 months ago by
Replying to ghkliem:
That's what I figure you meant. But it does not work. E.g. when you want to only visit the elements below the first facet, the highest dimension will be set to
d2
. But current dimension isd1
. Only afternext_face_loop
is called has the dimension changed tod2
. This is different from the start. At the start the facets are already known and hence the dimension starts atd1
. But when you want to visit everything below something, the elements below have not been computed yet.I could set this up differently, if you find it confusing and make
only_subsets
callnext_face_loop
once.
Thank you for the patient answer! It makes sense to me now.
comment:25 Changed 21 months ago by
Reviewers:  → Yuan Zhou 

Status:  needs_review → positive_review 
Replying to ghkliem:
The intersections are obtained by intersecting the last face with each previous ones. If there is only one face, we can stop and don't need
get_next_level
to tell us that there are no intersections.I don't think
n_faces == 0
can happen, but it is better to be safe than sorry. Becauseget_next_level
will intersect the last face with all previous ones. If there is zero faces we have an overflow and the face2^641
is intersected with all previous once, which will result in an segmentation fault.But maybe it is better to handle this check as a first thing in
get_next_level
. This is probably where it belongs anyway. What do you think?
I thought that n_faces == 0
couldn't happen too; that's why I asked, in case I missed/misunderstood something. I was also wondering about the order of the if
checks in next_face_loop
, but I figured out that it doesn't really matter. Besides, next_face_loop
and get_next_level
are not objects of this ticket. The current implementation works well, so I don't think more changes are needed.
comment:26 Changed 21 months ago by
Status:  positive_review → needs_work 

comment:28 Changed 20 months ago by
comment:30 Changed 20 months ago by
Branch:  u/ghkliem/only_subsets → u/ghkliem/only_subsets_reb 

Commit:  40d56400d156210c2c7c7b9751ac88b84b399acd → d073ca56b926a795c5a22490aa9644accb7f9a1c 
Status:  needs_work → needs_review 
Last 10 new commits:
70a8791  Merge branch 'u/ghkliem/check_openmp_at_configuration' of git://trac.sagemath.org/sage into u/ghkliem/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/31834reb' of git://trac.sagemath.org/sage into public/31834reb2

297792a  equalities > equations for #31821 as well

d073ca5  Merge branch 'public/31834reb2' of git://trac.sagemath.org/sage into u/ghkliem/only_subsets_reb

comment:31 Changed 20 months ago by
Dependencies:  #29683 → #29683, #31245 

Work issues:  Merge conflict with #31245. One of them needs to be rebased. 
comment:32 Changed 20 months ago by
Branch:  u/ghkliem/only_subsets_reb → u/ghkliem/only_subsets_reb2 

Commit:  d073ca56b926a795c5a22490aa9644accb7f9a1c → 542baee396e8db57d59020cc1fd905e1b045eaa7 
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

comment:33 Changed 20 months ago by
Branch:  u/ghkliem/only_subsets_reb2 → u/mkoeppe/only_subsets_reb2 

comment:34 Changed 20 months ago by
Commit:  542baee396e8db57d59020cc1fd905e1b045eaa7 → 7f7e6301eb49ed48fd646beae85772344ba52338 

Reviewers:  Yuan Zhou → Yuan Zhou, Matthias Koeppe 
Status:  needs_review → positive_review 
comment:36 Changed 19 months ago by
Branch:  u/mkoeppe/only_subsets_reb2 → 7f7e6301eb49ed48fd646beae85772344ba52338 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
fix bug revealed by a_maximal_chain
fix error message in doctest