Opened 6 years ago

Closed 16 months ago

#17339 closed defect (fixed)

Polyhedron class mistreats empty inputs

Reported by: darij Owned by:
Priority: major Milestone: sage-9.0
Component: geometry Keywords:
Cc: vbraun, mkoeppe, tscrim Merged in:
Authors: Darij Grinberg, Jonathan Kliem Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: c5bf041 (Commits, GitHub, GitLab) Commit: c5bf04100b1b1bbd32e7c85e0096f69934948811
Dependencies: Stopgaps:

Status badges

Description (last modified by gh-kliem)

sage: Polyhedron(ambient_dim=0, ieqs=[], eqns=[], base_ring=QQ)
The empty polyhedron in QQ^0

This should be a one-point polyhedron.

sage: Polyhedron(ambient_dim=2, ieqs=[], eqns=[], base_ring=QQ)
The empty polyhedron in QQ^2

This should be the whole QQ2.

sage: Polyhedron(ambient_dim=2, vertices=[], rays=[], lines=[], base_ring=QQ)
The empty polyhedron in QQ^2

This is correct, but only because the code misunderstands the empty V-representation as no V-representation given at all.

Change History (22)

comment:1 Changed 6 years ago by vbraun

For the case with rays but no vertex we follow cdd in implicitly adding the origin as vertex. This is also spelled out in the docs.

comment:2 Changed 6 years ago by darij

There is a difference between vertices=[] and vertices=None. In the latter case, we should follow the cdd convention. In the former, we should not; this kind of exception conflicts with regular usage and forces writers of methods to special-case empty vertex sets. Currently the constructor loses the difference between [] and None at one of its first steps (the _make_listlist call); this is what I think needs to be fixed.

Last edited 6 years ago by darij (previous) (diff)

comment:3 Changed 6 years ago by vbraun

I don't really like to make a distinction between None and [], Python generally treats them as similar. Both are not __nonzero__. Its a bad UI to assign meaning to one over the other.

comment:4 Changed 6 years ago by darij

What we have right now is way worse. Say I write some code which constructs a ton of polytopes from their Vreps (e.g., I have a polygon and I construct all subpolygons from some of its vertices). A few of them have empty vertices lists. Why should they be understood differently from the rest?

comment:5 Changed 6 years ago by vbraun

The design choice is: nothing specified = empty polyhedron.

This is fine with your example, empty vertex list = empty polygon. Unless you mean a non-compact 2-d polyhedron.

I agree that there is perhaps too much DWIM but its also very convenient for interactive use. If you just specify a bunch of rays then in 99% of the cases you want a cone, not some rule thumping about missing a vertex.

How about separate Polyhedron.from_Vrep(vertices, rays, lines) and similarly from_Hrep with positional arguments and strict rules?

comment:6 follow-up: Changed 6 years ago by darij

Very good idea about the from_Vrep and from_Hrep methods. Should the usual __init__ then dispatch to them?

comment:7 in reply to: ↑ 6 Changed 6 years ago by vbraun

Replying to darij:

Should the usual __init__ then dispatch to them?

Haven't really thought about it, whatever is convenient for the implementation.

comment:8 Changed 4 years ago by mkoeppe

  • Cc mkoeppe added

comment:9 Changed 4 years ago by mkoeppe

Even if it's not good style to distinguish between None and [], I think it is fine to distinguish between a provided keyword argument and a not-provided keyword argument.

So perhaps we should just change the default value of eqns from None to some unique value such as "not_given".

Then users who want to explicitly pass an empty list of eqns could either pass eqns=None or eqns=[].

comment:10 Changed 3 years ago by mkoeppe

  • Cc tscrim added
  • Milestone changed from sage-6.4 to sage-8.4

comment:11 Changed 3 years ago by tscrim

I think Python quite often distinguishes between [] and None:

sage: list([])
sage: list(None)
TypeError                                 Traceback (most recent call last)
<ipython-input-1-f23beda2b661> in <module>()
----> 1 list(None)

TypeError: 'NoneType' object is not iterable

sage: for x in []:
....:     print("hi")
sage: for x in None:
....:     print("hi")
TypeError                                 Traceback (most recent call last)
<ipython-input-5-b89ce2509dd6> in <module>()
----> 1 for x in None:
      2     print("hi")

TypeError: 'NoneType' object is not iterable

They are completely different objects in Python. Other languages behave in the same way for their list-like objects and equivalent of NULL.

I agree that it can be useful to have [] and None behave the same way, but it is not good practice to say we should not distinguish between the two. None is also faster, easier, and safer to work with than some other (essentially equally) generic input.

comment:12 Changed 16 months ago by gh-kliem

  • Authors set to ​Darij Grinberg, Jonathan Kliem
  • Branch changed from public/polytopes/0 to public/17339
  • Commit changed from f7642d6e2d2502e3df95c76ef2ffa7e9319a99aa to f3c0bfbba740e2c001aa0ad15a47e956c8181c0d

I took the half-backed fix and did some changes that seem to make it work.

It seems that fixing this ticket implies a fixing #28654. The verification of the double description for backend field relied on mistreatment of empty input (or fixing #28654).

New commits:

f3c0bfbfix empty input for Polyhedron class
Last edited 16 months ago by gh-kliem (previous) (diff)

comment:13 Changed 16 months ago by gh-kliem

  • Status changed from new to needs_review

comment:14 Changed 16 months ago by git

  • Commit changed from f3c0bfbba740e2c001aa0ad15a47e956c8181c0d to c5bf04100b1b1bbd32e7c85e0096f69934948811

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

c5bf041added a doctest, some simplification

comment:15 Changed 16 months ago by gh-kliem

  • Description modified (diff)
  • Milestone changed from sage-8.4 to sage-9.0

I propose leaving the following as it is:

sage: Polyhedron(ambient_dim=2, vertices=[], rays=[(2,2)], lines=[], base_ring=QQ)
A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 vertex and 1 ray

comment:16 Changed 16 months ago by tscrim

Should we consider that as valid input? Given a single ray, I don't think there is enough information to determine a polyhedron. However, since that is the current behavior, I cannot strictly object to it. I am only with accepting the ticket as-is since it does improve things, but perhaps we can take a quick second look at the current corner case behaviors?

comment:17 Changed 16 months ago by gh-kliem

I think if vertices is None then it makes sense to add a vertex.

However, if vertices is [] and there are Rays or Lines, maybe it makes sense to throw an error. The user specifically stated that there are no vertices, so the input doesn't make any sense.

comment:18 Changed 16 months ago by tscrim

But you cannot infer what the vertices should be from a single ray (or even line). This should be true more generally for any non-full-dimensional polyhedron that cannot specify at least one point inside it. However, as I write that, it seems like a (computationally) hard problem to me to verify this information. Although maybe this is already implicit in how the polyhedron is constructed?

comment:19 Changed 16 months ago by gh-kliem

I guess it is just convention, to add a vertex, when rays and lines are given, but no vertex. I don't really care about that convention one way or the other. I just left it the way it is.

I don't understand what part is computationally hard.

comment:20 Changed 16 months ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

I was thinking given enough rays, but now I realize that no matter how much affine data you have, you need to specify a vertex. However, what about a mixture of lines and rays. Although I guess it is documented that the origin is added if no vertices are specified, so it is enshrined as the behavior. Thus this point is moot.

comment:21 Changed 16 months ago by vbraun

  • Authors changed from ​Darij Grinberg, Jonathan Kliem to Darij Grinberg, Jonathan Kliem

fixed zero width space in the author name

comment:22 Changed 16 months ago by vbraun

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