.neighbors() error in polyhedron.representation

[jipilab]

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)
<ipython-input-3-fae09a40457d> in <module>()
----> 1 sf = s.stack(f)

/home/jplabbe/sage/local/lib/python3.7/site-packages/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/site-packages/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/site-packages/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 non-full-dimensional 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 non-proper faces,
• remove a redundant test (all vertices of a polyhedron satisfy all of its inequalities/equalites).

[gh-LaisRast]

This is actually a serious problem. See

sage: P = polytopes.simplex()
....: F1 = P.Hrepresentation()[1]
....: list(F1.neighbors())
....:
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-11-3a4d81457d82> in <module>()
      1 P = polytopes.simplex()
      2 F = P.Hrepresentation()[Integer(1)]
----> 3 list(F.neighbors())

/usr/lib/python2.7/site-packages/sage/geometry/polyhedron/representation.pyc 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

/usr/lib/python2.7/site-packages/sage/matrix/matrix0.pyx in sage.matrix.matrix0.Matrix.__getitem__ (build/cythonized/sage/matrix/matrix0.c:7281)()
    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

The method neighbors() says that it iterates over the adjacent inequalities and equations. However, its code uses the facet_adjacency_matrix() method which returns the adjacency of just the inequalities. To solve this, I think we should introduce H_adjacency_matrix(), and use it in the code of neighbors().

[gh-kliem]

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

[git]

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)

[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.

• 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?.

[gh-LaisRast]

A small remark. The docstring of neighbors still says inequalities and equations:

    Iterate over the adjacent facets (i.e. inequalities/equations)

[git]

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

​5771568

small changes

[gh-kliem]

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?.

[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.

You forgot to indent the sage blocks.

Have you looked at the other places where .neighbors is used in the polyhedron folder?

[gh-kliem]

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 non-fulldimensional cases due to index shifting. So if anyone has successfully used it, he or she got really lucky. Nevertheless, I can check.

[jipilab]

Replying to gh-kliem:

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.

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 of locus_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_.

[git]

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

​01c5c19

improved docstring

[gh-kliem]

New commits:

​01c5c19

improved docstring

---

New commits:

​01c5c19

improved docstring

[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!

[git]

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

​901a37a

minor changes in documentation

[gh-kliem]

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!

[git]

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

​f4c89fe

fixed pyflakes error in affine hull

[gh-kliem]

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!