Opened 5 months ago

Closed 4 months ago

#31919 closed enhancement (fixed)

ABC for convex sets

Reported by: mkoeppe Owned by:
Priority: major Milestone: sage-9.4
Component: geometry Keywords:
Cc: gh-kliem, yzh, jipilab, tscrim, novoselt, mjo Merged in:
Authors: Matthias Koeppe Reviewers: Jonathan Kliem
Report Upstream: N/A Work issues:
Branch: 686d0af (Commits, GitHub, GitLab) Commit: 686d0afbeba9f5d33131ecbe20a907c20635faa5
Dependencies: #31916 Stopgaps:

Status badges

Description (last modified by mkoeppe)

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:

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

Change History (50)

comment:1 Changed 5 months ago by mkoeppe

  • Branch set to u/mkoeppe/abc_for_convex_sets

comment:2 Changed 5 months ago by git

  • Commit set to ccc84213906ff6bf34d2e5c6b50d146a2901ec9c

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

e67f753ConvexRationalPolyhedralCone: Add method is_empty and aliases is_full_dimensional, is_universe
770fdcdLatticePolytopeClass, IntegralRayCollection: Make ambient_dim an alias for lattice_dim
b2ac639ConvexSet_base.dim: New
ccc8421ConvexSet_base.is_compact, ConvexSet_compact: New

comment:3 Changed 5 months ago by mkoeppe

  • Authors set to Matthias Koeppe

comment:4 Changed 5 months ago by mkoeppe

  • Dependencies set to #31916

comment:5 Changed 5 months ago by git

  • Commit changed from ccc84213906ff6bf34d2e5c6b50d146a2901ec9c to 4bac2fe2db4519478d6e5633e86b29098d9aa0c4

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

9df2104sage.geometry.relative_interior: Move here from sage.geometry.polyhedron.relint
b8bfe20ConvexRationalPolyhedralCone: Add methods interior, relative_interior
6869673relative_interior: Fix for dimension 0
021d073RelativeInterior: Add documentation, tests, comparison methods, method relative_interior
8f38e04ConvexRationalPolyhedralCone.interior, relative_interior: Add doctests
5f9c852RelativeInterior.interior: New
5c089ecRelativeInterior.__eq__, __ne__: Handle comparisons with objects of other types
86ce301Polyhedron_base.is_relatively_open: New; fix relative_interior for affine subspaces
42adcedMerge #31916
4bac2feRelativeInterior: Subclass ConvexSet_relatively_open, add missing methods

comment:6 Changed 5 months ago by git

  • Commit changed from 4bac2fe2db4519478d6e5633e86b29098d9aa0c4 to 1e8dd0927ac51fd2131b16dbc4073b78f4dc9d8d

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

216cb81ConvexRationalPolyhedralCone.is_relatively_open: New, fix ConvexRationalPolyhedralCone.relative_interior for linear subspaces
1e8dd09Merge #31916

comment:7 Changed 5 months ago by mkoeppe

  • Description modified (diff)

comment:8 Changed 5 months ago by git

  • Commit changed from 1e8dd0927ac51fd2131b16dbc4073b78f4dc9d8d to 3f4acb34d064ec0c721b8a43e898f4d65479d43e

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

44cde1esrc/doc/en/reference/discrete_geometry/index.rst: Add sage/geometry/relative_interior
fa4c2d2Whitespace fixes
3f4acb3Merge #31916

comment:9 Changed 5 months ago by git

  • Commit changed from 3f4acb34d064ec0c721b8a43e898f4d65479d43e to dede9de1a8e01114b289149bccb51c466223d027

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

dede9desrc/doc/en/reference/discrete_geometry/index.rst: Add sage/geometry/convex_set

comment:10 Changed 5 months ago by mkoeppe

  • Status changed from new to needs_review

comment:11 Changed 5 months ago by gh-kliem

  • Status changed from needs_review to needs_work

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

comment:12 Changed 5 months ago by git

  • Commit changed from dede9de1a8e01114b289149bccb51c466223d027 to 007e6fda9fb5dfccf109b06d15f8799f7f03ac5f

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

007e6fdConvexRationalPolyhedralCone.is_empty: Add doctest

comment:13 Changed 5 months ago by gh-kliem

  • Status changed from needs_work to needs_review

I guess it is back on needs review.

comment:14 Changed 5 months ago by gh-kliem

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

comment:15 Changed 5 months ago by git

  • Commit changed from 007e6fda9fb5dfccf109b06d15f8799f7f03ac5f to 6a0baac5f679d90a1acd3696f3613350af5af9f1

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

73e39ceConvexRationalPolyhedralCone.is_compact: Define
92f0610ConvexSet_open: New
03a31efPolyhedron_base.is_full_dimensional: Merge into ConvexSet_base.is_full_dimensional
a71507eConvexSet_base: Add some doctests
3a83182ConvexSet_base.relative_interior: New
6a0baacConvexSet_base._test_convex_set: New

comment:16 Changed 5 months ago by mkoeppe

  • Status changed from needs_review to needs_work

comment:17 Changed 5 months ago by git

  • Commit changed from 6a0baac5f679d90a1acd3696f3613350af5af9f1 to 9a7ce3a53d63ace6ed56f4addc92f61b85549b32

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

0495bb0RelativeInterior: Fix up doctest
9a7ce3asrc/sage/geometry/convex_set.py: More examples and tests

comment:18 Changed 5 months ago by mkoeppe

  • Status changed from needs_work to needs_review

comment:19 Changed 5 months ago by git

  • Commit changed from 9a7ce3a53d63ace6ed56f4addc92f61b85549b32 to e2b0ef7390426c7d8f6f7f0a1382b326d5c9bc6e

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

e2b0ef7ConvexSet_base._test_convex_set: Fix doctest output

comment:20 Changed 5 months ago by git

  • Commit changed from e2b0ef7390426c7d8f6f7f0a1382b326d5c9bc6e to f4bdffda473c608289d6b8c90a3687484d24f3be

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

45c840aConvexSet_base.codim, codimension: New
17467c4ConvexSet_base: Make dimension, ambient_dimension aliases for dim, ambient_dim
fa5dc6eConvexSet_base.cartesian_product: New
f4bdffdConvexSet_base.contains, intersection: New

comment:21 Changed 5 months ago by mkoeppe

  • Description modified (diff)

comment:22 Changed 5 months ago by mkoeppe

  • Description modified (diff)

comment:23 Changed 5 months ago by mkoeppe

  • Description modified (diff)

comment:24 follow-up: Changed 5 months ago by gh-kliem

  • Branch changed from u/mkoeppe/abc_for_convex_sets to u/gh-kliem/abc_for_convex_sets
  • Commit changed from f4bdffda473c608289d6b8c90a3687484d24f3be to c75ba428cd91e71a8b237602a3529b936eb6d965

New commits:

c75ba42fix coverage

comment:25 follow-up: Changed 5 months ago by gh-kliem

  • I don't think ambient_dimension should return the dimension of self.
    +    def ambient_dimension(self):
    +        Return the dimension of ``self``.
    +
    +        This is the same as :meth:`ambient_dim`.
    
  • That codim is an alias of codimension should be doctested I think.
  • Why have you removed the test suite on the relative interior of the empty polyhedron?
    -            sage: P = Polyhedron()
    +            sage: P = Polyhedron([[1, 2], [3, 4]])
                 sage: from sage.geometry.relative_interior import RelativeInterior
                 sage: TestSuite(RelativeInterior(P)).run()
    
    Would it make sense to run the test suite on relative interior of polyhedra as part of the standard polyhedron test suite? Just like in #31821.
  • Cartesian product is now a new alias of product. This should be doctested with a tiny doctest I think.

comment:26 Changed 5 months ago by gh-kliem

  • Reviewers set to Jonathan Kliem

comment:27 Changed 5 months ago by mkoeppe

Thanks for these fixes and suggestions!

comment:28 in reply to: ↑ 25 ; follow-up: Changed 5 months ago by mkoeppe

Replying to gh-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

comment:29 Changed 5 months ago by mkoeppe

  • Branch changed from u/gh-kliem/abc_for_convex_sets to u/mkoeppe/abc_for_convex_sets

comment:30 in reply to: ↑ 28 ; follow-up: Changed 5 months ago by gh-kliem

  • Commit changed from c75ba428cd91e71a8b237602a3529b936eb6d965 to 30ebaf5a657040cb787bea0f5c2540ca08115284

Replying to mkoeppe:

Replying to gh-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()

New commits:

142fb46ConvexSet_base.codimension: Add doctest for alias 'codim'
30ebaf5ConvexSet_base.ambient_dim, ambient_dimension: Fix doc

comment:31 in reply to: ↑ 24 ; follow-up: Changed 5 months ago by gh-kliem

Replying to gh-kliem:

New commits:

c75ba42fix coverage

Please fix coverage or cherry-pick the above commit.

It's trivial, I see no need to add me as an author. Of course this case is trivial. But if we allow people to not test trivial things, where do we draw the line?

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

Last edited 5 months ago by gh-kliem (previous) (diff)

comment:32 Changed 5 months ago by mkoeppe

Sorry, forgot to pull in your changes

comment:33 Changed 5 months ago by git

  • Commit changed from 30ebaf5a657040cb787bea0f5c2540ca08115284 to fcf2a32a768097f9248cda456624784cc9f199c6

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

fcf2a32fix coverage

comment:34 Changed 5 months ago by git

  • Commit changed from fcf2a32a768097f9248cda456624784cc9f199c6 to 1448835c107b949b9129296a92851d0026bb774a

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

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

comment:35 Changed 5 months ago by git

  • Commit changed from 1448835c107b949b9129296a92851d0026bb774a to 8ff6457938186754c5ef2dcb1559dbfb8c50b248

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

8ff6457Polyhedron_base.interior: Handle the empty polyhedron correctly

comment:36 in reply to: ↑ 30 Changed 5 months ago by mkoeppe

Replying to gh-kliem:

Replying to mkoeppe:

Replying to gh-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

comment:37 in reply to: ↑ 31 Changed 5 months ago by mkoeppe

Replying to gh-kliem:

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

Yes, this was a great improvement!

comment:38 Changed 5 months ago by git

  • Commit changed from 8ff6457938186754c5ef2dcb1559dbfb8c50b248 to 148016ff92d33c36f29d6ce9c1937a00aba9e17b

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

148016fPolyhedron_base.product: Add doctest for alias 'cartesian_product'

comment:39 Changed 5 months ago by gh-kliem

  • Status changed from needs_review to needs_work
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

comment:40 Changed 5 months ago by git

  • Commit changed from 148016ff92d33c36f29d6ce9c1937a00aba9e17b to 686d0afbeba9f5d33131ecbe20a907c20635faa5

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

6ab5677RelativeInterior.is_universe: New
c085d30Polyhedron_base.interior: Handle the empty polyhedron correctly
686d0afPolyhedron_base.product: Add doctest for alias 'cartesian_product'

comment:41 Changed 5 months ago by mkoeppe

  • Status changed from needs_work to needs_review

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

comment:42 Changed 5 months ago by mkoeppe

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

comment:43 Changed 5 months ago by gh-kliem

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

comment:44 Changed 5 months ago by mkoeppe

Fine with me if you want to make this change

comment:45 follow-up: Changed 4 months ago by mkoeppe

Actually I think after #31705 this won't matter

comment:46 in reply to: ↑ 45 Changed 4 months ago by gh-kliem

Replying to mkoeppe:

Actually I think after #31705 this won't matter

Yes, that's right.

comment:47 Changed 4 months ago by gh-kliem

  • Status changed from needs_review to positive_review

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.

comment:48 Changed 4 months ago by mkoeppe

Thank you!

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

comment:49 Changed 4 months ago by mkoeppe

  • Description modified (diff)

comment:50 Changed 4 months ago by vbraun

  • Branch changed from u/mkoeppe/abc_for_convex_sets to 686d0afbeba9f5d33131ecbe20a907c20635faa5
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.