Opened 3 years ago

Last modified 3 years ago

#28463 closed defect

.neighbors() error in polyhedron.representation — at Version 2

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:
Report Upstream: N/A Work issues:
Branch: public/28463 (Commits, GitHub, GitLab) Commit: 8853122c90f902a73d8534734563bd6f874a6393
Dependencies: Stopgaps:

Status badges

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.

Also, we do some minor changes to stack.

Change History (2)

comment:1 Changed 3 years 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 3 years 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
Note: See TracTickets for help on using tickets.