Sage: Ticket #17339: Polyhedron class mistreats empty inputs
https://trac.sagemath.org/ticket/17339
<pre class="wiki">sage: Polyhedron(ambient_dim=0, ieqs=[], eqns=[], base_ring=QQ)
The empty polyhedron in QQ^0
</pre><p>
This should be a one-point polyhedron.
</p>
<pre class="wiki">sage: Polyhedron(ambient_dim=2, ieqs=[], eqns=[], base_ring=QQ)
The empty polyhedron in QQ^2
</pre><p>
This should be the whole QQ<sup>2.
</sup></p>
<pre class="wiki">sage: Polyhedron(ambient_dim=2, vertices=[], rays=[], lines=[], base_ring=QQ)
The empty polyhedron in QQ^2
</pre><p>
This is correct, but only because the code misunderstands the empty V-representation as no V-representation given at all.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/17339
Trac 1.1.6vbraunThu, 13 Nov 2014 20:54:11 GMT
https://trac.sagemath.org/ticket/17339#comment:1
https://trac.sagemath.org/ticket/17339#comment:1
<p>
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.
</p>
TicketdarijThu, 13 Nov 2014 20:59:58 GMT
https://trac.sagemath.org/ticket/17339#comment:2
https://trac.sagemath.org/ticket/17339#comment:2
<p>
There is a difference between <code>vertices=[]</code> and <code>vertices=None</code>. 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 <code>[]</code> and <code>None</code> at one of its first steps (the <code>_make_listlist</code> call); this is what I think needs to be fixed.
</p>
TicketvbraunThu, 13 Nov 2014 22:56:30 GMT
https://trac.sagemath.org/ticket/17339#comment:3
https://trac.sagemath.org/ticket/17339#comment:3
<p>
I don't really like to make a distinction between <code>None</code> and <code>[]</code>, Python generally treats them as similar. Both are <code>not __nonzero__</code>. Its a bad UI to assign meaning to one over the other.
</p>
TicketdarijThu, 13 Nov 2014 23:29:06 GMT
https://trac.sagemath.org/ticket/17339#comment:4
https://trac.sagemath.org/ticket/17339#comment:4
<p>
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?
</p>
TicketvbraunThu, 13 Nov 2014 23:45:34 GMT
https://trac.sagemath.org/ticket/17339#comment:5
https://trac.sagemath.org/ticket/17339#comment:5
<p>
The design choice is: nothing specified = empty polyhedron.
</p>
<p>
This is fine with your example, empty vertex list = empty polygon. Unless you mean a non-compact 2-d polyhedron.
</p>
<p>
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.
</p>
<p>
How about separate <code>Polyhedron.from_Vrep(vertices, rays, lines)</code> and similarly <code>from_Hrep</code> with positional arguments and strict rules?
</p>
TicketdarijThu, 13 Nov 2014 23:47:47 GMT
https://trac.sagemath.org/ticket/17339#comment:6
https://trac.sagemath.org/ticket/17339#comment:6
<p>
Very good idea about the <code>from_Vrep</code> and <code>from_Hrep</code> methods. Should the usual <code>__init__</code> then dispatch to them?
</p>
TicketvbraunFri, 14 Nov 2014 11:30:20 GMT
https://trac.sagemath.org/ticket/17339#comment:7
https://trac.sagemath.org/ticket/17339#comment:7
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/17339#comment:6" title="Comment 6">darij</a>:
</p>
<blockquote class="citation">
<p>
Should the usual <code>__init__</code> then dispatch to them?
</p>
</blockquote>
<p>
Haven't really thought about it, whatever is convenient for the implementation.
</p>
TicketmkoeppeWed, 23 Nov 2016 05:23:37 GMTcc changed
https://trac.sagemath.org/ticket/17339#comment:8
https://trac.sagemath.org/ticket/17339#comment:8
<ul>
<li><strong>cc</strong>
<em>mkoeppe</em> added
</li>
</ul>
TicketmkoeppeWed, 23 Nov 2016 05:53:12 GMT
https://trac.sagemath.org/ticket/17339#comment:9
https://trac.sagemath.org/ticket/17339#comment:9
<p>
Even if it's not good style to distinguish between <code>None</code> and <code>[]</code>, I think it is fine to distinguish between a provided keyword argument and a not-provided keyword argument.
</p>
<p>
So perhaps we should just change the default value of eqns from <code>None</code> to some unique value such as <code>"not_given"</code>.
</p>
<p>
Then users who want to explicitly pass an empty list of eqns could either pass <code>eqns=None</code> or <code>eqns=[]</code>.
</p>
TicketmkoeppeFri, 21 Sep 2018 19:14:44 GMTcc, milestone changed
https://trac.sagemath.org/ticket/17339#comment:10
https://trac.sagemath.org/ticket/17339#comment:10
<ul>
<li><strong>cc</strong>
<em>tscrim</em> added
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-8.4</em>
</li>
</ul>
TickettscrimFri, 21 Sep 2018 22:34:44 GMT
https://trac.sagemath.org/ticket/17339#comment:11
https://trac.sagemath.org/ticket/17339#comment:11
<p>
I think Python quite often distinguishes between <code>[]</code> and <code>None</code>:
</p>
<pre class="wiki">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
</pre><p>
They are completely different objects in Python. Other languages behave in the same way for their list-like objects and equivalent of <code>NULL</code>.
</p>
<p>
I agree that it can be useful to have <code>[]</code> and <code>None</code> behave the same way, but it is not good practice to say we should not distinguish between the two. <code>None</code> is also faster, easier, and safer to work with than some other (essentially equally) generic input.
</p>
Ticketgh-kliemWed, 11 Dec 2019 13:00:03 GMTcommit, branch changed; author set
https://trac.sagemath.org/ticket/17339#comment:12
https://trac.sagemath.org/ticket/17339#comment:12
<ul>
<li><strong>commit</strong>
changed from <em>f7642d6e2d2502e3df95c76ef2ffa7e9319a99aa</em> to <em>f3c0bfbba740e2c001aa0ad15a47e956c8181c0d</em>
</li>
<li><strong>branch</strong>
changed from <em>public/polytopes/0</em> to <em>public/17339</em>
</li>
<li><strong>author</strong>
set to <em>Darij Grinberg, Jonathan Kliem</em>
</li>
</ul>
<p>
I took the half-backed fix and did some changes that seem to make it work.
</p>
<p>
It seems that fixing this ticket implies a fixing <a class="closed ticket" href="https://trac.sagemath.org/ticket/28654" title="defect: A Bug in the backend `field` (closed: fixed)">#28654</a>. The verification of the double description for backend <code>field</code> relied on mistreatment of empty input (or fixing <a class="closed ticket" href="https://trac.sagemath.org/ticket/28654" title="defect: A Bug in the backend `field` (closed: fixed)">#28654</a>).
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f3c0bfbba740e2c001aa0ad15a47e956c8181c0d"><span class="icon"></span>f3c0bfb</a></td><td><code>fix empty input for Polyhedron class</code>
</td></tr></table>
Ticketgh-kliemWed, 11 Dec 2019 13:01:05 GMTstatus changed
https://trac.sagemath.org/ticket/17339#comment:13
https://trac.sagemath.org/ticket/17339#comment:13
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketgitWed, 11 Dec 2019 14:56:17 GMTcommit changed
https://trac.sagemath.org/ticket/17339#comment:14
https://trac.sagemath.org/ticket/17339#comment:14
<ul>
<li><strong>commit</strong>
changed from <em>f3c0bfbba740e2c001aa0ad15a47e956c8181c0d</em> to <em>c5bf04100b1b1bbd32e7c85e0096f69934948811</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=c5bf04100b1b1bbd32e7c85e0096f69934948811"><span class="icon"></span>c5bf041</a></td><td><code>added a doctest, some simplification</code>
</td></tr></table>
Ticketgh-kliemWed, 11 Dec 2019 15:02:15 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/17339#comment:15
https://trac.sagemath.org/ticket/17339#comment:15
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/17339?action=diff&version=15">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-8.4</em> to <em>sage-9.0</em>
</li>
</ul>
<p>
I propose leaving the following as it is:
</p>
<pre class="wiki">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
</pre>
TickettscrimThu, 12 Dec 2019 05:04:12 GMT
https://trac.sagemath.org/ticket/17339#comment:16
https://trac.sagemath.org/ticket/17339#comment:16
<p>
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?
</p>
Ticketgh-kliemThu, 12 Dec 2019 08:43:46 GMT
https://trac.sagemath.org/ticket/17339#comment:17
https://trac.sagemath.org/ticket/17339#comment:17
<p>
I think if vertices is <code>None</code> then it makes sense to add a vertex.
</p>
<p>
However, if vertices is <code>[]</code> 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.
</p>
TickettscrimThu, 12 Dec 2019 12:40:05 GMT
https://trac.sagemath.org/ticket/17339#comment:18
https://trac.sagemath.org/ticket/17339#comment:18
<p>
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?
</p>
Ticketgh-kliemFri, 13 Dec 2019 12:52:34 GMT
https://trac.sagemath.org/ticket/17339#comment:19
https://trac.sagemath.org/ticket/17339#comment:19
<p>
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.
</p>
<p>
I don't understand what part is computationally hard.
</p>
TickettscrimFri, 13 Dec 2019 21:45:26 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/17339#comment:20
https://trac.sagemath.org/ticket/17339#comment:20
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Travis Scrimshaw</em>
</li>
</ul>
<p>
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.
</p>
TicketvbraunTue, 17 Dec 2019 23:42:53 GMTauthor changed
https://trac.sagemath.org/ticket/17339#comment:21
https://trac.sagemath.org/ticket/17339#comment:21
<ul>
<li><strong>author</strong>
changed from <em>Darij Grinberg, Jonathan Kliem</em> to <em>Darij Grinberg, Jonathan Kliem</em>
</li>
</ul>
<p>
fixed zero width space in the author name
</p>
TicketvbraunFri, 20 Dec 2019 22:45:49 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/17339#comment:22
https://trac.sagemath.org/ticket/17339#comment:22
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/17339</em> to <em>c5bf04100b1b1bbd32e7c85e0096f69934948811</em>
</li>
</ul>
Ticket