.neighbors() error in polyhedron.representation

[jplab]

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

CC: @LaisRast @kliem

Component: geometry

Keywords: polytopes, stack, representation, neighbors

Author: Jonathan Kliem

Branch/Commit: f4c89fe

Reviewer: Jean-Philippe Labbé

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

[LaisRast]

comment:1

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().

[kliem]

Branch: public/28463

[kliem]

Description changed:

--- 
+++ 
@@ -32,3 +32,7 @@

 IndexError: matrix index out of range

+ +We fix neighbors of polyhedron.representation to only specify inequalities/facets. + +Also, we do some minor changes to stack.

[kliem]

Commit: 8853122

[kliem]

comment:2

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

[kliem]

Changed keywords from polytopes, stack to polytopes, stack, representation, neighbors

[kliem]

Author: Jonathan Kliem

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8853122 to 462db8d

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:4

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.

[LaisRast]

comment:5

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5771568

small changes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 462db8d to 5771568

[kliem]

comment:7

Replying to @jplab:

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.

[jplab]

comment:9

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

[kliem]

comment:11

Replying to @jplab:

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

[jplab]

comment:12

Replying to @kliem:

Replying to @jplab:

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 5771568 to 01c5c19

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

01c5c19

improved docstring

[kliem]

New commits:

01c5c19

improved docstring

---

New commits:

01c5c19

improved docstring

[kliem]

Description changed:

--- 
+++ 
@@ -33,6 +33,9 @@
 IndexError: matrix index out of range

-We fix neighbors of polyhedron.representation to only specify inequalities/facets. +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. +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 interior), +- errors for non-proper faces, +- remove a redundant test (all vertices of a polyhedron satisfy all of its inequalities/equalites).

[kliem]

Description changed:

--- 
+++ 
@@ -36,6 +36,6 @@
 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 interior),
+- 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).

[jplab]

comment:16

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!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

901a37a

minor changes in documentation

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 01c5c19 to 901a37a

[kliem]

comment:18

Replying to @jplab:

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!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 901a37a to f4c89fe

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f4c89fe

fixed pyflakes error in affine hull

[kliem]

comment:21

I guess this is the case now. I'll put in on positive review.

Replying to @jplab:

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!

[vbraun]

Changed branch from public/28463 to f4c89fe