Opened 19 months ago
Closed 18 months ago
#28463 closed defect (fixed)
.neighbors() error in polyhedron.representation
Reported by:  jipilab  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  geometry  Keywords:  polytopes, stack, representation, neighbors 
Cc:  ghLaisRast, ghkliem  Merged in:  
Authors:  Jonathan Kliem  Reviewers:  JeanPhilippe Labbé 
Report Upstream:  N/A  Work issues:  
Branch:  f4c89fe (Commits, GitHub, GitLab)  Commit:  f4c89fe44a14a833ddc5f153f754d4ab26502f63 
Dependencies:  Stopgaps: 
Description (last modified by )
The following Error happens in Sage8.9.beta8:
sage: s = polytopes.simplex(7) sage: f = s.faces(3)[0] sage: sf = s.stack(f)  IndexError Traceback (most recent call last) <ipythoninput3fae09a40457d> in <module>() > 1 sf = s.stack(f) /home/jplabbe/sage/local/lib/python3.7/sitepackages/sage/geometry/polyhedron/base.py in stack(self, face, position) 4135 neighboring_facets = set() 4136 for facet in face_star: > 4137 for neighbor_facet in facet.neighbors(): 4138 if neighbor_facet not in face_star: 4139 neighboring_facets.add(neighbor_facet) /home/jplabbe/sage/local/lib/python3.7/sitepackages/sage/geometry/polyhedron/representation.py in neighbors(self) 463 adjacency_matrix = self.polyhedron().facet_adjacency_matrix() 464 for x in self.polyhedron().Hrep_generator(): > 465 if adjacency_matrix[self.index(), x.index()] == 1: 466 yield x 467 /home/jplabbe/sage/local/lib/python3.7/sitepackages/sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__getitem__ (build/cythonized/sage/matrix/matrix0.c:7282)() 963 col += ncols 964 if col < 0 or col >= ncols: > 965 raise IndexError("matrix index out of range") 966 single_col = 1 967 IndexError: matrix index out of range
We fix neighbors
of polyhedron.representation
to only specify inequalities/facets. In case of a nonfulldimensional polyhedron, the method had an index shift and did not return anything valuable (if not an error). The method appears to be used only in stack
, so we do not set a deprecation warning (even so the method is now returning an error for equalities).
Also, we do some minor changes to stack
:
 fix a bug: the stacked vertex needs to be in the relative interior of the
locus_polyhedron
(not just contained in),  errors for nonproper faces,
 remove a redundant test (all vertices of a polyhedron satisfy all of its inequalities/equalites).
Change History (24)
comment:1 Changed 19 months ago by
comment:2 Changed 19 months ago by
 Branch set to public/28463
 Commit set to 8853122c90f902a73d8534734563bd6f874a6393
 Description modified (diff)
 Keywords representation neighbors added
 Status changed from new to needs_review
 Summary changed from .stack() or .facet_adjacency_matrix() error in Polyhedron to .neighbors() error in polyhedron.representation
I added a suggested fix.
I changed neighbors
to only include facets
/inequalities
. There is no meaning in checking anything else anyway, is there?
Additionally I changed a few things, which I noticed about stacked
.
As neighbors
did not work for polyhedra with equalities and is not altered for those with without, I don't think a deprecation error is needed.
New commits:
5095c2e  fix neighbors of Hrepresentatives

8853122  small changes to stacking

comment:3 Changed 19 months ago by
 Commit changed from 8853122c90f902a73d8534734563bd6f874a6393 to 462db8d5994837b27badf03b679f13af5a60c40d
Branch pushed to git repo; I updated commit sha1. New commits:
462db8d  stacking is well defined for rationals (and in case of base ring cdd reals as well)

comment:4 followup: ↓ 7 Changed 19 months ago by
 Reviewers set to JeanPhilippe Labbé
 Status changed from needs_review to needs_work
A few comments:
 You should put "Checking that :trac:
28463
is fixed::" in the docstring before the failing test coming from this ticket.
 I would not refer to an internal variable in the TEST block, but try to say it in words.
 It would be good to show the new raised ValueError? at the end of the examples to say that you should do this on proper faces only (but really at the end, so that "working examples" come first...)
 Careful with 1 empty line after
::
and indentation of code blocks, otherwise documentation won't build.
 You introduced two useless empty lines it seems.
 Please reread what you changed in
representation
it seems contradictory "Does not work for inequalities::" and "AssertionError?: must be inequality" is at best very confusing.
 I don't know what you are talking about with a deprecation: you are changing the behavior of the function, not changing a name or an option. In principle, this change is not wished. That is: we may break a lot of code doing so. That said, the code was broken, so fair enough. But the question remains: is there internal code that breaks due to a weird use of
neighbor()
? Could you check that? Then, I would say it should be a TypeError? and not an AssertionError?.
comment:5 Changed 19 months ago by
A small remark. The docstring of neighbors
still says inequalities and equations:
Iterate over the adjacent facets (i.e. inequalities/equations)
comment:6 Changed 19 months ago by
 Commit changed from 462db8d5994837b27badf03b679f13af5a60c40d to 5771568fdcd64567a9b2771a9a3abf27f75b46ea
Branch pushed to git repo; I updated commit sha1. New commits:
5771568  small changes

comment:7 in reply to: ↑ 4 Changed 19 months ago by
Replying to jipilab:
A few comments:
 You should put "Checking that :trac:
28463
is fixed::" in the docstring before the failing test coming from this ticket.
 I would not refer to an internal variable in the TEST block, but try to say it in words.
 It would be good to show the new raised ValueError? at the end of the examples to say that you should do this on proper faces only (but really at the end, so that "working examples" come first...)
 Careful with 1 empty line after
::
and indentation of code blocks, otherwise documentation won't build.
 You introduced two useless empty lines it seems.
My editor deletes trailing white spaces by default.
 Please reread what you changed in
representation
it seems contradictory "Does not work for inequalities::" and "AssertionError?: must be inequality" is at best very confusing.
 I don't know what you are talking about with a deprecation: you are changing the behavior of the function, not changing a name or an option. In principle, this change is not wished. That is: we may break a lot of code doing so. That said, the code was broken, so fair enough. But the question remains: is there internal code that breaks due to a weird use of
neighbor()
? Could you check that? Then, I would say it should be a TypeError? and not an AssertionError?.
comment:8 Changed 19 months ago by
 Status changed from needs_work to needs_review
comment:9 followup: ↓ 11 Changed 19 months ago by
 Checking that stacked point needs to be in the interior of  ``locus_polyhedron``:: + The stacked vertex may not satisfy any inequality + defining the original polyhedron::
This is making it less precise. Why not say:
+ Taking the stacking vertex too far with the parameter `XXX` may result in a failure to produce the desired (combinatorial type of) polytope.
You forgot to indent the sage blocks.
Have you looked at the other places where .neighbors
is used in the polyhedron folder?
comment:10 Changed 19 months ago by
 Status changed from needs_review to needs_work
comment:11 in reply to: ↑ 9 ; followup: ↓ 12 Changed 19 months ago by
Replying to jipilab:
 Checking that stacked point needs to be in the interior of  ``locus_polyhedron``:: + The stacked vertex may not satisfy any inequality + defining the original polyhedron::This is making it less precise. Why not say:
+ Taking the stacking vertex too far with the parameter `XXX` may result in a failure to produce the desired (combinatorial type of) polytope.
Actually, I did fix a bug in stacked as well. The set of permittable points should be the relative interior of locus_polyhedron
. This is not the way it was before. Maybe I should really set up another ticket for the fixes in stack
and describe this in the ticket.
position=4
is in the boundary of locus_polyhedron
and before my fix it returned a wrong combinatorial type.
You forgot to indent the sage blocks.
Have you looked at the other places where
.neighbors
is used in the polyhedron folder?
Not yet. The tests passed and so I figured it's fine. Also neighbors
returned complete nonsense for nonfulldimensional cases due to index shifting. So if anyone has successfully used it, he or she got really lucky. Nevertheless, I can check.
comment:12 in reply to: ↑ 11 Changed 19 months ago by
Replying to ghkliem:
Replying to jipilab:
 Checking that stacked point needs to be in the interior of  ``locus_polyhedron``:: + The stacked vertex may not satisfy any inequality + defining the original polyhedron::This is making it less precise. Why not say:
+ Taking the stacking vertex too far with the parameter `XXX` may result in a failure to produce the desired (combinatorial type of) polytope.
Actually, I did fix a bug in stacked as well. The set of permittable points should be the relative interior of
locus_polyhedron
. This is not the way it was before. Maybe I should really set up another ticket for the fixes instack
and describe this in the ticket.
No, I believe it is fine. This ticket is about the fact that stacking was not working (originally). So I would say that one can fix the bug and adapt the description of the ticket accordingly.
position=4
is in the boundary oflocus_polyhedron
and before my fix it returned a wrong combinatorial type.
One more reason to mention this in the documentation before this test (how should I know that this is what is tested???).
You forgot to indent the sage blocks.
Have you looked at the other places where
.neighbors
is used in the polyhedron folder?Not yet. The tests passed and so I figured it's fine.
Exactly, that's my point: just checking the tests is not enough. One should do a grep to see where this function is used _internally_.
comment:13 Changed 19 months ago by
 Commit changed from 5771568fdcd64567a9b2771a9a3abf27f75b46ea to 01c5c190ff7ae068fd201c479df6ba8d5a0b3110
Branch pushed to git repo; I updated commit sha1. New commits:
01c5c19  improved docstring

comment:14 Changed 19 months ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
comment:15 Changed 19 months ago by
 Description modified (diff)
comment:16 followups: ↓ 18 ↓ 21 Changed 18 months ago by
 Status changed from needs_review to needs_work
Two minor things:
permittable > possible, permitted, allowed
position
> position
Once you fix these and the pyflakes error at line 8112, you can set it to positive review on my behalf.
P.S. Welcome back to work!
comment:17 Changed 18 months ago by
 Commit changed from 01c5c190ff7ae068fd201c479df6ba8d5a0b3110 to 901a37ada4795138726d6ebcd22562e6ec580167
Branch pushed to git repo; I updated commit sha1. New commits:
901a37a  minor changes in documentation

comment:18 in reply to: ↑ 16 Changed 18 months ago by
Replying to jipilab:
Two minor things:
permittable > possible, permitted, allowed
position
>position
Once you fix these and the pyflakes error at line 8112, you can set it to positive review on my behalf.
I can't even locate that error. I don't know in which line this appears (I don't find a version, where line 8112 could have resulted in this error.)
P.S. Welcome back to work!
comment:19 Changed 18 months ago by
 Status changed from needs_work to needs_review
comment:20 Changed 18 months ago by
 Commit changed from 901a37ada4795138726d6ebcd22562e6ec580167 to f4c89fe44a14a833ddc5f153f754d4ab26502f63
Branch pushed to git repo; I updated commit sha1. New commits:
f4c89fe  fixed pyflakes error in affine hull

comment:21 in reply to: ↑ 16 Changed 18 months ago by
I guess this is the case now. I'll put in on positive review.
Replying to jipilab:
Two minor things:
permittable > possible, permitted, allowed
position
>position
Once you fix these and the pyflakes error at line 8112, you can set it to positive review on my behalf.
P.S. Welcome back to work!
comment:22 Changed 18 months ago by
 Status changed from needs_review to positive_review
comment:23 Changed 18 months ago by
 Milestone changed from sage8.9 to sage9.0
comment:24 Changed 18 months ago by
 Branch changed from public/28463 to f4c89fe44a14a833ddc5f153f754d4ab26502f63
 Resolution set to fixed
 Status changed from positive_review to closed
This is actually a serious problem. See
The method
neighbors()
says that it iterates over the adjacent inequalities and equations. However, its code uses thefacet_adjacency_matrix()
method which returns the adjacency of just the inequalities. To solve this, I think we should introduceH_adjacency_matrix()
, and use it in the code ofneighbors()
.