Opened 21 months ago
Closed 19 months ago
#31819 closed enhancement (fixed)
Only subfaces/supfaces for polyhedral face iterator
Reported by: | gh-kliem | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-9.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 follow-up: 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 follow-up: 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 follow-up: 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 follow-up: 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 follow-up: 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 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
.
comment:18 Changed 21 months ago by
Work issues: | → Merge conflict with #31245. One of them needs to be rebased. |
---|
comment:19 follow-up: 22 Changed 21 months ago by
Replying to gh-kliem:
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 follow-up: 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 follow-up: 24 Changed 21 months ago by
Replying to yzh:
Replying to gh-kliem:
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 d-2
. But current dimension is d-1
. Only after next_face_loop
is called has the dimension changed to d-2
. This is different from the start. At the start the facets are already known and hence the dimension starts at d-1
. 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 follow-up: 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^64-1
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 gh-kliem:
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
d-2
. But current dimension isd-1
. Only afternext_face_loop
is called has the dimension changed tod-2
. This is different from the start. At the start the facets are already known and hence the dimension starts atd-1
. 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 gh-kliem:
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^64-1
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/gh-kliem/only_subsets → u/gh-kliem/only_subsets_reb |
---|---|
Commit: | 40d56400d156210c2c7c7b9751ac88b84b399acd → d073ca56b926a795c5a22490aa9644accb7f9a1c |
Status: | needs_work → needs_review |
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
|
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/gh-kliem/only_subsets_reb → u/gh-kliem/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/gh-kliem/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