ABC for convex sets #31919

mkoeppe · 2021-06-06T21:57:32Z

We create a base class ConvexSet_base with abstract methods to define an API for convex sets (convex subsets of a finite dimensional topological R-vector space such as R^n).

We use it to test/unify the API of Polyhedron, ConvexRationalPolyhedralCone, LatticePolytope, RelativeInterior (#31916)

See also:

PolyhedronFace: Make it a subclass of ConvexSet_closed #31959 PolyhedronFace: Make it a subclass of ConvexSet_closed
ConvexSet_base: Add methods an_element, some_elements #31990 ConvexSet_base: Add methods an_element, some_elements
Meta-ticket: Connect Sage sets to sympy sets #31926 Connect Sage sets to sympy sets
Set_base.contains, ConvexSet.contains: Handle symbolic argument #31947 ConvexSet.contains: Handle symbolic argument
ABC for convex sets (follow up) #31955 ABC for convex sets (follow up)

Depends on #31916

CC: @kliem @yuan-zhou @jplab @tscrim @novoselt @orlitzky

Component: geometry

Author: Matthias Koeppe

Branch/Commit: 686d0af

Reviewer: Jonathan Kliem

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

The text was updated successfully, but these errors were encountered:

mkoeppe · 2021-06-06T22:37:21Z

Branch: u/mkoeppe/abc_for_convex_sets

sagetrac-git · 2021-06-07T05:56:29Z

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

`e67f753`	`ConvexRationalPolyhedralCone: Add method is_empty and aliases is_full_dimensional, is_universe`
`770fdcd`	`LatticePolytopeClass, IntegralRayCollection: Make ambient_dim an alias for lattice_dim`
`b2ac639`	`ConvexSet_base.dim: New`
`ccc8421`	`ConvexSet_base.is_compact, ConvexSet_compact: New`

sagetrac-git · 2021-06-07T05:56:29Z

Commit: ccc8421

mkoeppe · 2021-06-07T06:14:54Z

Author: Matthias Koeppe

mkoeppe · 2021-06-07T19:08:54Z

Dependencies: #31916

sagetrac-git · 2021-06-07T19:54:06Z

Changed commit from ccc8421 to 4bac2fe

sagetrac-git · 2021-06-07T19:54:06Z

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`9df2104`	`sage.geometry.relative_interior: Move here from sage.geometry.polyhedron.relint`
`b8bfe20`	`ConvexRationalPolyhedralCone: Add methods interior, relative_interior`
`6869673`	`relative_interior: Fix for dimension 0`
`021d073`	`RelativeInterior: Add documentation, tests, comparison methods, method relative_interior`
`8f38e04`	`ConvexRationalPolyhedralCone.interior, relative_interior: Add doctests`
`5f9c852`	`RelativeInterior.interior: New`
`5c089ec`	`RelativeInterior.__eq__, __ne__: Handle comparisons with objects of other types`
`86ce301`	`Polyhedron_base.is_relatively_open: New; fix relative_interior for affine subspaces`
`42adced`	`Merge #31916`
`4bac2fe`	`RelativeInterior: Subclass ConvexSet_relatively_open, add missing methods`

sagetrac-git · 2021-06-07T20:02:44Z

Changed commit from 4bac2fe to 1e8dd09

sagetrac-git · 2021-06-07T20:02:44Z

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

`216cb81`	`ConvexRationalPolyhedralCone.is_relatively_open: New, fix ConvexRationalPolyhedralCone.relative_interior for linear subspaces`
`1e8dd09`	`Merge #31916`

sagetrac-git · 2021-06-07T23:26:49Z

Changed commit from 1e8dd09 to 3f4acb3

sagetrac-git · 2021-06-07T23:26:49Z

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

`44cde1e`	`src/doc/en/reference/discrete_geometry/index.rst: Add sage/geometry/relative_interior`
`fa4c2d2`	`Whitespace fixes`
`3f4acb3`	`Merge #31916`

sagetrac-git · 2021-06-07T23:47:25Z

Changed commit from 3f4acb3 to dede9de

sagetrac-git · 2021-06-07T23:47:25Z

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

`dede9de`	`src/doc/en/reference/discrete_geometry/index.rst: Add sage/geometry/convex_set`

kliem · 2021-06-08T18:12:40Z

comment:11

Missing doctest.

+    def is_empty(self):
+        """
+        Return whether ``self`` is the empty set.
+
+        Because a cone always contains the origin, this method returns ``False``.
+        """
+        return False

sagetrac-git · 2021-06-08T20:33:58Z

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

`007e6fd`	`ConvexRationalPolyhedralCone.is_empty: Add doctest`

sagetrac-git · 2021-06-08T20:33:58Z

Changed commit from dede9de to 007e6fd

kliem · 2021-06-09T06:11:52Z

comment:13

I guess it is back on needs review.

kliem · 2021-06-09T17:49:25Z

comment:14

Can you please add doctests for src/sage/geometry/convex_set.py yet.

sagetrac-git · 2021-06-10T18:53:59Z

Changed commit from 007e6fd to 6a0baac

sagetrac-git · 2021-06-10T18:53:59Z

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

`73e39ce`	`ConvexRationalPolyhedralCone.is_compact: Define`
`92f0610`	`ConvexSet_open: New`
`03a31ef`	`Polyhedron_base.is_full_dimensional: Merge into ConvexSet_base.is_full_dimensional`
`a71507e`	`ConvexSet_base: Add some doctests`
`3a83182`	`ConvexSet_base.relative_interior: New`
`6a0baac`	`ConvexSet_base._test_convex_set: New`

sagetrac-git · 2021-06-12T16:14:31Z

Changed commit from 30ebaf5 to fcf2a32

sagetrac-git · 2021-06-12T16:21:50Z

Changed commit from fcf2a32 to 1448835

sagetrac-git · 2021-06-12T16:21:50Z

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

`6bef52b`	`ConvexSet_base._test_convex_set: Run the testsuite of relint`
`1448835`	`RelativeInterior.ambient, ambient_vector_space, is_universe: New`

sagetrac-git · 2021-06-12T16:33:50Z

Changed commit from 1448835 to 8ff6457

sagetrac-git · 2021-06-12T16:33:50Z

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

`8ff6457`	`Polyhedron_base.interior: Handle the empty polyhedron correctly`

mkoeppe · 2021-06-12T16:34:24Z

comment:36

Replying to @kliem:

Replying to @mkoeppe:

Replying to @kliem:

Why have you removed the test suite on the relative interior of the empty polyhedron?

The reason for this is the assumption in is_closed

I see. I think it should be fixed then. Either we drop the requirement of being identical in the test suite or we add another clause for Polyhedron_base.relative_interior:
    if not self.is_full_dimensional():
+       if self.is_empty():
+           return self
        return self.parent().element_class(self.parent(), None, None)
    return self.relative_interior()

I have made a similar fix

mkoeppe · 2021-06-12T16:34:57Z

comment:37

Replying to @kliem:

This is one reason why I improved sage --fixdoctests to work for error messages as well.

Yes, this was a great improvement!

sagetrac-git · 2021-06-12T16:40:07Z

Changed commit from 8ff6457 to 148016f

sagetrac-git · 2021-06-12T16:40:07Z

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

`148016f`	`Polyhedron_base.product: Add doctest for alias 'cartesian_product'`

kliem · 2021-06-12T18:16:38Z

comment:39

sage -t --long --warn-long 111.1 --random-seed=0 relative_interior.py
**********************************************************************
File "relative_interior.py", line 82, in sage.geometry.relative_interior.RelativeInterior.ambient
Failed example:
    ri_segment.ambient()
Exception raised:
    Traceback (most recent call last):
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 714, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 1133, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.relative_interior.RelativeInterior.ambient[2]>", line 1, in <module>
        ri_segment.ambient()
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/geometry/relative_interior.py", line 84, in ambient
        return self._polyhedron.ambient()
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/geometry/polyhedron/base_ZZ.py", line 51, in __getattribute__
        return super(Polyhedron_ZZ, self).__getattribute__(name)
      File "sage/structure/element.pyx", line 493, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4708)
        return self.getattr_from_category(name)
      File "sage/structure/element.pyx", line 506, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4820)
        return getattr_from_other_class(self, cls, name)
      File "sage/cpython/getattr.pyx", line 367, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2551)
        raise AttributeError(dummy_error_message)
    AttributeError: 'Polyhedra_ZZ_ppl_with_category.element_class' object has no attribute 'ambient'
**********************************************************************
File "relative_interior.py", line 96, in sage.geometry.relative_interior.RelativeInterior.ambient_vector_space
Failed example:
    ri_segment.ambient_vector_space()
Exception raised:
    Traceback (most recent call last):
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 714, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/doctest/forker.py", line 1133, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.geometry.relative_interior.RelativeInterior.ambient_vector_space[2]>", line 1, in <module>
        ri_segment.ambient_vector_space()
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/geometry/relative_interior.py", line 98, in ambient_vector_space
        return self._polyhedron.ambient_vector_space(base_field=base_field)
      File "/home/jonathan/Applications/sage/local/lib/python3.8/site-packages/sage/geometry/polyhedron/base_ZZ.py", line 51, in __getattribute__
        return super(Polyhedron_ZZ, self).__getattribute__(name)
      File "sage/structure/element.pyx", line 493, in sage.structure.element.Element.__getattr__ (build/cythonized/sage/structure/element.c:4708)
        return self.getattr_from_category(name)
      File "sage/structure/element.pyx", line 506, in sage.structure.element.Element.getattr_from_category (build/cythonized/sage/structure/element.c:4820)
        return getattr_from_other_class(self, cls, name)
      File "sage/cpython/getattr.pyx", line 367, in sage.cpython.getattr.getattr_from_other_class (build/cythonized/sage/cpython/getattr.c:2551)
        raise AttributeError(dummy_error_message)
    AttributeError: 'Polyhedra_ZZ_ppl_with_category.element_class' object has no attribute 'ambient_vector_space'
**********************************************************************
2 items had failures:
   1 of   4 in sage.geometry.relative_interior.RelativeInterior.ambient
   1 of   4 in sage.geometry.relative_interior.RelativeInterior.ambient_vector_space
    [59 tests, 2 failures, 0.13 s]
----------------------------------------------------------------------
sage -t --long --warn-long 111.1 --random-seed=0 relative_interior.py  # 2 doctests failed

sagetrac-git · 2021-06-12T19:46:17Z

Changed commit from 148016f to 686d0af

sagetrac-git · 2021-06-12T19:46:17Z

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`6ab5677`	`RelativeInterior.is_universe: New`
`c085d30`	`Polyhedron_base.interior: Handle the empty polyhedron correctly`
`686d0af`	`Polyhedron_base.product: Add doctest for alias 'cartesian_product'`

mkoeppe · 2021-06-12T19:47:58Z

comment:41

Cherry-picking 1448835 from #31959 was a mistake, thanks for catching this.
Let's see what the patchbot thinks now

mkoeppe · 2021-06-13T02:48:03Z

comment:42

Patchbot is green modulo the unrelated src/sage/misc/package.py failure

kliem · 2021-06-13T06:15:21Z

comment:43

We could replace the imports in lattice_polytope.py and cone.py by lazy imports:

========== startup_modules ==========

--- 9.4.beta1

+++ 9.4.beta1 + #31919


-Total count: 1762
+Total count: 1764
+New:
+sage.geometry.convex_set
+    sage.geometry.relative_interior
+====================

+sage.geometry.convex_set

+sage.geometry.relative_interior

-startup_modules Passed
+startup_modules Failed

mkoeppe · 2021-06-13T06:17:09Z

comment:44

Fine with me if you want to make this change

mkoeppe · 2021-06-13T14:21:43Z

comment:45

Actually I think after #31705 this won't matter

kliem · 2021-06-14T06:24:18Z

comment:46

Replying to @mkoeppe:

Actually I think after #31705 this won't matter

Yes, that's right.

kliem · 2021-06-14T07:01:54Z

comment:47

One tiny thing about RelativeInterior.interior: It should return self, if the relative interior is full-dimensional. This is currently the case, because the method relative_interior is cached for polyhedra and cones. Maybe it is cleaner to immediately catch the case. But it is not really needed.

Either way, LGTM.

mkoeppe · 2021-06-14T07:07:43Z

comment:48

Thank you!

We can make refinements to RelativeInterior in a later ticket. For now I prefer the version as is.

vbraun · 2021-06-29T17:40:23Z

Changed branch from u/mkoeppe/abc_for_convex_sets to 686d0af

mkoeppe added this to the sage-9.4 milestone Jun 6, 2021

mkoeppe added c: geometry labels Jun 6, 2021

This comment has been minimized.

Sign in to view

mkoeppe added the s: needs review label Jun 7, 2021

kliem added s: needs work and removed s: needs review labels Jun 8, 2021

kliem added s: needs review and removed s: needs work labels Jun 9, 2021

kliem added s: needs work and removed s: needs review labels Jun 12, 2021

mkoeppe added s: needs review and removed s: needs work labels Jun 12, 2021

kliem added s: positive review and removed s: needs review labels Jun 14, 2021

This comment has been minimized.

Sign in to view

vbraun removed the s: positive review label Jun 29, 2021

vbraun closed this as completed in 17c8565 Jun 29, 2021

ABC for convex sets #31919

ABC for convex sets #31919

Comments

mkoeppe commented Jun 6, 2021

mkoeppe commented Jun 6, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

mkoeppe commented Jun 7, 2021

mkoeppe commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

This comment has been minimized.

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

sagetrac-git mannequin commented Jun 7, 2021

kliem commented Jun 8, 2021

sagetrac-git mannequin commented Jun 8, 2021

sagetrac-git mannequin commented Jun 8, 2021

kliem commented Jun 9, 2021

kliem commented Jun 9, 2021

sagetrac-git mannequin commented Jun 10, 2021

sagetrac-git mannequin commented Jun 10, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

mkoeppe commented Jun 12, 2021

mkoeppe commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

kliem commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

sagetrac-git mannequin commented Jun 12, 2021

mkoeppe commented Jun 12, 2021

mkoeppe commented Jun 13, 2021

kliem commented Jun 13, 2021

mkoeppe commented Jun 13, 2021

mkoeppe commented Jun 13, 2021

kliem commented Jun 14, 2021

kliem commented Jun 14, 2021

mkoeppe commented Jun 14, 2021

This comment has been minimized.

vbraun commented Jun 29, 2021