Run test suite for product

[kliem]

We implement a method that tests the construction of the product.

Along the way we fix a bug, where the product of the empty polyhedron and a polyhedron with rays and lines, might be set up with rays and lines (but the empty polyhedron is by convention not set up with rays or lines).

Depends on #30328
Depends on #30330

Component: geometry

Keywords: polyhedra, test suite, product

Author: Jonathan Kliem

Branch/Commit: a4bf2bc

Reviewer: Matthias Koeppe

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

[kliem]

Dependencies: #29899, #29903

[kliem]

comment:2

And another bug discovered:

sage: P = polytopes.regular_polygon(5, exact=True)
sage: P1 = polytopes.regular_polygon(5, exact=False)
sage: P*P1
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9946)()
   1195         try:
-> 1196             action = self._action_maps.get(xp, yp, op)
   1197         except KeyError:

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce_dict.pyx in sage.structure.coerce_dict.TripleDict.get (build/cythonized/sage/structure/coerce_dict.c:7917)()
   1327         if not valid(cursor.key_id1):
-> 1328             raise KeyError((k1, k2, k3))
   1329         value = <object>cursor.value

KeyError: (Polyhedra in AA^2, Polyhedra in RDF^2, <built-in function mul>)

During handling of the above exception, another exception occurred:

ValueError                                Traceback (most recent call last)
<ipython-input-4-69ee963b1fc0> in <module>()
----> 1 P*P1

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12029)()
   1515             return (<Element>left)._mul_(right)
   1516         if BOTH_ARE_ELEMENT(cl):
-> 1517             return coercion_model.bin_op(left, right, mul)
   1518 
   1519         cdef long value

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9996)()
   1196             action = self._action_maps.get(xp, yp, op)
   1197         except KeyError:
-> 1198             action = self.get_action(xp, yp, op, x, y)
   1199         if action is not None:
   1200             if (<Action>action)._is_left:

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:16783)()
   1724         except KeyError:
   1725             pass
-> 1726         action = self.discover_action(R, S, op, r, s)
   1727         action = self.verify_action(action, R, S, op)
   1728         self._action_maps.set(R, S, op, action)

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:18201)()
   1855         """
   1856         if isinstance(R, Parent):
-> 1857             action = (<Parent>R).get_action(S, op, True, r, s)
   1858             if action is not None:
   1859                 return action

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:19745)()
   2457         action = self._get_action_(S, op, self_on_left)
   2458         if action is None:
-> 2459             action = self.discover_action(S, op, self_on_left, self_el, S_el)
   2460 
   2461         if action is not None:

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:20722)()
   2536                 # detect actions defined by _rmul_, _lmul_, _act_on_, and _acted_upon_ methods
   2537                 from .coerce_actions import detect_element_action
-> 2538                 action = detect_element_action(self, S, self_on_left, self_el, S_el)
   2539                 if action is not None:
   2540                     return action

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5360)()
    229     if isinstance(Y, Parent):
    230         try:
--> 231             if x._acted_upon_(y, X_on_left) is not None:
    232                 return ActedUponAction(Y, X, not X_on_left, False)
    233         except CoercionException:

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element._acted_upon_ (build/cythonized/sage/structure/element.c:8604)()
    925         return None
    926 
--> 927     cpdef _acted_upon_(self, x, bint self_on_left):
    928         """
    929         Use this method to implement ``self`` acted on by x.

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in _acted_upon_(self, actor, self_on_left)
   4299         """
   4300         if is_Polyhedron(actor):
-> 4301             return self.product(actor)
   4302         if is_Vector(actor):
   4303             return self.translation(actor)

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in product(self, other)
   3993 
   3994         parent = self.parent().change_ring(new_ring, ambient_dim=self.ambient_dim() + other.ambient_dim())
-> 3995         return parent.element_class(parent, [new_vertices, new_rays, new_lines], None)
   3996 
   3997     _mul_ = product

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in __init__(self, parent, Vrep, Hrep, **kwds)
    459             sage: TestSuite(p).run()
    460         """
--> 461         Polyhedron_cdd.__init__(self, parent, Vrep, Hrep, **kwds)

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in __init__(self, parent, Vrep, Hrep, **kwds)
    120             vertices, rays, lines = Vrep
    121             if vertices or rays or lines:
--> 122                 self._init_from_Vrepresentation(vertices, rays, lines, **kwds)
    123             else:
    124                 self._init_empty_polyhedron()

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in _init_from_Vrepresentation(self, vertices, rays, lines, verbose)
     61         from .cdd_file_format import cdd_Vrepresentation
     62         s = cdd_Vrepresentation(self._cdd_type, vertices, rays, lines)
---> 63         s = self._run_cdd(s, '--redcheck', verbose=verbose)
     64         s = self._run_cdd(s, '--repall', verbose=verbose)
     65         self._init_from_cdd_output(s)

/srv/public/shared/sage-9.0/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in _run_cdd(self, cdd_input_string, cmdline_arg, verbose)
    163         if 'Error:' in ans + err:
    164             # cdd reports errors on stdout and misc information on stderr
--> 165             raise ValueError(ans.strip())
    166         return ans
    167 

ValueError: *Input Error: Input format is not correct.
*Format:
 begin
   m   n  NumberType(real, rational or integer)
   b  -A
 end

This is also present with #29568 on the current develop branch.

[kliem]

comment:3

Apparently this introduced when improving products.

Edited: No, I can actually trace it back at least to sage 7.4

[kliem]

comment:4

One more

sage: P1 = polytopes.regular_polygon(5, exact=False)
sage: P2 = Polyhedron()
sage: P1*P2
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9942)()
   1195         try:
-> 1196             action = self._action_maps.get(xp, yp, op)
   1197         except KeyError:

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce_dict.pyx in sage.structure.coerce_dict.TripleDict.get (build/cythonized/sage/structure/coerce_dict.c:7916)()
   1327         if not valid(cursor.key_id1):
-> 1328             raise KeyError((k1, k2, k3))
   1329         value = <object>cursor.value

KeyError: (Polyhedra in RDF^2, Polyhedra in ZZ^0, <built-in function mul>)

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
<ipython-input-10-1f01e20e65dd> in <module>()
----> 1 P1*P2

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12225)()
   1535             return (<Element>left)._mul_(right)
   1536         if BOTH_ARE_ELEMENT(cl):
-> 1537             return coercion_model.bin_op(left, right, mul)
   1538 
   1539         cdef long value

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9992)()
   1196             action = self._action_maps.get(xp, yp, op)
   1197         except KeyError:
-> 1198             action = self.get_action(xp, yp, op, x, y)
   1199         if action is not None:
   1200             if (<Action>action)._is_left:

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:16779)()
   1725         except KeyError:
   1726             pass
-> 1727         action = self.discover_action(R, S, op, r, s)
   1728         action = self.verify_action(action, R, S, op)
   1729         self._action_maps.set(R, S, op, action)

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:18197)()
   1856         """
   1857         if isinstance(R, Parent):
-> 1858             action = (<Parent>R).get_action(S, op, True, r, s)
   1859             if action is not None:
   1860                 return action

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:19900)()
   2475         action = self._get_action_(S, op, self_on_left)
   2476         if action is None:
-> 2477             action = self.discover_action(S, op, self_on_left, self_el, S_el)
   2478 
   2479         if action is not None:

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:20877)()
   2554                 # detect actions defined by _rmul_, _lmul_, _act_on_, and _acted_upon_ methods
   2555                 from .coerce_actions import detect_element_action
-> 2556                 action = detect_element_action(self, S, self_on_left, self_el, S_el)
   2557                 if action is not None:
   2558                     return action

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5358)()
    229     if isinstance(Y, Parent):
    230         try:
--> 231             if x._acted_upon_(y, X_on_left) is not None:
    232                 return ActedUponAction(Y, X, not X_on_left, False)
    233         except CoercionException:

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element._acted_upon_ (build/cythonized/sage/structure/element.c:8800)()
    945         return None
    946 
--> 947     cpdef _acted_upon_(self, x, bint self_on_left):
    948         """
    949         Use this method to implement ``self`` acted on by x.

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in _acted_upon_(self, actor, self_on_left)
   4959         """
   4960         if is_Polyhedron(actor):
-> 4961             return self.product(actor)
   4962         elif is_Vector(actor):
   4963             return self.translation(actor)

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in product(self, other)
   4487         return parent.element_class(parent, [new_vertices, rays, lines],
   4488                                     [ieqs, eqns],
-> 4489                                     Vrep_minimal=True, Hrep_minimal=True, pref_rep=pref_rep)
   4490 
   4491     _mul_ = product

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in __init__(self, parent, Vrep, Hrep, **kwds)
    518             sage: TestSuite(p).run()
    519         """
--> 520         Polyhedron_cdd.__init__(self, parent, Vrep, Hrep, **kwds)
    521 
    522     def _init_from_Vrepresentation_and_Hrepresentation(self, Vrep, Hrep, verbose=False):

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/base.py in __init__(self, parent, Vrep, Hrep, Vrep_minimal, Hrep_minimal, pref_rep, **kwds)
    206                                  " and Vrep_minimal and Hrep_minimal must both be True")
    207             if hasattr(self, "_init_from_Vrepresentation_and_Hrepresentation"):
--> 208                 self._init_from_Vrepresentation_and_Hrepresentation(Vrep, Hrep)
    209                 return
    210             else:

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in _init_from_Vrepresentation_and_Hrepresentation(self, Vrep, Hrep, verbose)
    632             simplefilter("error")
    633             try:
--> 634                 try_init(prim)
    635             except UserWarning:
    636                 simplefilter("once")  # Only print the first warning.

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/backend_cdd.py in try_init(rep)
    603             if rep == "Vrep":
    604                 from .cdd_file_format import cdd_Vrepresentation
--> 605                 s = cdd_Vrepresentation(self._cdd_type, vertices, rays, lines)
    606             else:
    607                 # We have to add a trivial inequality, in case the polyhedron is the universe.

/home/jonathan/Applications/sage/local/lib/python3.7/site-packages/sage/geometry/polyhedron/cdd_file_format.py in cdd_Vrepresentation(cdd_type, vertices, rays, lines, file_output)
     60     # cdd implicitly assumes that the origin is a vertex if none is given
     61     if vertices is None:
---> 62         vertices = [[0]*ambient_dim]
     63         num += 1
     64 

TypeError: can't multiply sequence by non-int of type 'NoneType'

[kliem]

Last 10 new commits:

5d79b2b	some more testsuites
6eaf649	test some basic properties
6a467b4	implement _test_product
e41d698	fix universe from Hrep for cdd
e055bc7	correctly detect the empty polyhedron
7eba64d	trivial inequality
067fb16	also fix it for initialization from Hrep and Vrep
e94f71c	add doctests
6f2b544	Merge branch 'public/29899' of git://trac.sagemath.org/sage into public/29934
f73e4f1	small improvements

[kliem]

Branch: public/29934

[kliem]

Commit: f73e4f1

[kliem]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 We implement a method that tests the construction of the product.
+
+Along the way we fix a bug, where the product of the empty polyhedron and a polyhedron with rays and lines, might be set up with rays and lines (but the empty polyhedron is by convention not set up with rays or lines).

[kliem]

New commits:

1f00faa	fix lawrence extension with base extension; add test method for lawrence construction
8e8158c	fix missing conversion to RDF
319c172	check lawrence construction with new vertex in RDF
96adb63	python 3.8 compatible
2052dd8	merge public/29934
c3896a2	fix initialization of impty RDF polyhedron from double descpription
98e456f	Merge branch 'public/30330' of git://trac.sagemath.org/sage into public/29934-reb
d98e2db	small fixes to make the test method for the product work

[kliem]

Changed branch from public/29934 to public/29934-reb

[kliem]

Changed commit from f73e4f1 to d98e2db