#28463 closed defect (fixed)

.neighbors() error in polyhedron.representation

Reported by: jipilab Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords: polytopes, stack, representation, neighbors
Cc: gh-LaisRast, gh-kliem Merged in:
Authors: Jonathan Kliem Reviewers: Jean-Philippe Labbé
Report Upstream: N/A Work issues:
Branch: f4c89fe (Commits) Commit: f4c89fe44a14a833ddc5f153f754d4ab26502f63
Dependencies: Stopgaps:

Description (last modified by gh-kliem)

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

Change History (24)

comment:1 Changed 11 months ago by 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().

comment:2 Changed 11 months ago by gh-kliem

  • Authors set to Jonathan Kliem
  • 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:

5095c2efix neighbors of Hrepresentatives
8853122small changes to stacking

comment:3 Changed 11 months ago by git

  • Commit changed from 8853122c90f902a73d8534734563bd6f874a6393 to 462db8d5994837b27badf03b679f13af5a60c40d

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

462db8dstacking is well defined for rationals (and in case of base ring cdd reals as well)

comment:4 follow-up: Changed 11 months ago by jipilab

  • Reviewers set to Jean-Philippe 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 11 months ago by gh-LaisRast

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

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

comment:6 Changed 11 months ago by git

  • Commit changed from 462db8d5994837b27badf03b679f13af5a60c40d to 5771568fdcd64567a9b2771a9a3abf27f75b46ea

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

5771568small changes

comment:7 in reply to: ↑ 4 Changed 11 months ago by 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?.

comment:8 Changed 11 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:9 follow-up: Changed 11 months ago by 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?

comment:10 Changed 11 months ago by jipilab

  • Status changed from needs_review to needs_work

comment:11 in reply to: ↑ 9 ; follow-up: Changed 11 months ago by 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.

comment:12 in reply to: ↑ 11 Changed 11 months ago by 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_.

comment:13 Changed 11 months ago by git

  • Commit changed from 5771568fdcd64567a9b2771a9a3abf27f75b46ea to 01c5c190ff7ae068fd201c479df6ba8d5a0b3110

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

01c5c19improved docstring

comment:14 Changed 11 months ago by gh-kliem

  • Description modified (diff)
  • Status changed from needs_work to needs_review

New commits:

01c5c19improved docstring

New commits:

01c5c19improved docstring

comment:15 Changed 11 months ago by gh-kliem

  • Description modified (diff)

comment:16 follow-ups: Changed 10 months ago by jipilab

  • 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 10 months ago by git

  • Commit changed from 01c5c190ff7ae068fd201c479df6ba8d5a0b3110 to 901a37ada4795138726d6ebcd22562e6ec580167

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

901a37aminor changes in documentation

comment:18 in reply to: ↑ 16 Changed 10 months ago by 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!

comment:19 Changed 10 months ago by gh-kliem

  • Status changed from needs_work to needs_review

comment:20 Changed 10 months ago by git

  • Commit changed from 901a37ada4795138726d6ebcd22562e6ec580167 to f4c89fe44a14a833ddc5f153f754d4ab26502f63

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

f4c89fefixed pyflakes error in affine hull

comment:21 in reply to: ↑ 16 Changed 10 months ago by 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!

comment:22 Changed 10 months ago by gh-kliem

  • Status changed from needs_review to positive_review

comment:23 Changed 10 months ago by chapoton

  • Milestone changed from sage-8.9 to sage-9.0

comment:24 Changed 10 months ago by vbraun

  • Branch changed from public/28463 to f4c89fe44a14a833ddc5f153f754d4ab26502f63
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.