search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 453 forks source link

ABC for convex sets #31919

Closed mkoeppe closed 3 years ago

mkoeppe commented 3 years ago

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:

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

mkoeppe commented 3 years ago

Branch: u/mkoeppe/abc_for_convex_sets

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Commit: ccc8421

mkoeppe commented 3 years ago

Author: Matthias Koeppe

mkoeppe commented 3 years ago

Dependencies: #31916

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from ccc8421 to 4bac2fe

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 4bac2fe to 1e8dd09

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

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

-
+See also: #31926 Connect Sage sets to sympy sets
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 1e8dd09 to 3f4acb3

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 3f4acb3 to dede9de

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

dede9desrc/doc/en/reference/discrete_geometry/index.rst: Add sage/geometry/convex_set
kliem commented 3 years ago
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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

007e6fdConvexRationalPolyhedralCone.is_empty: Add doctest
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from dede9de to 007e6fd

kliem commented 3 years ago
comment:13

I guess it is back on needs review.

kliem commented 3 years ago
comment:14

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 007e6fd to 6a0baac

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 6a0baac to 9a7ce3a

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

e2b0ef7ConvexSet_base._test_convex_set: Fix doctest output
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 9a7ce3a to e2b0ef7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from e2b0ef7 to f4bdffd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,7 @@

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

-See also: #31926 Connect Sage sets to sympy sets
+See also: 
+- #31926 Connect Sage sets to sympy sets
+- #31955 ABC for convex sets (follow up)
+
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -4,5 +4,6 @@

 See also: 
 - #31926 Connect Sage sets to sympy sets
+- #31947 `ConvexSet.contains`: Handle symbolic argument
 - #31955 ABC for convex sets (follow up)
mkoeppe commented 3 years ago

Description changed:

--- 
+++ 
@@ -3,6 +3,7 @@
 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`
 - #31926 Connect Sage sets to sympy sets
 - #31947 `ConvexSet.contains`: Handle symbolic argument
 - #31955 ABC for convex sets (follow up)
kliem commented 3 years ago

Changed commit from f4bdffd to c75ba42

kliem commented 3 years ago

New commits:

c75ba42fix coverage
kliem commented 3 years ago

Changed branch from u/mkoeppe/abc_for_convex_sets to u/gh-kliem/abc_for_convex_sets

kliem commented 3 years ago
comment:25
+    def ambient_dimension(self):
+        Return the dimension of ``self``.
+
+        This is the same as :meth:`ambient_dim`.
-            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.

kliem commented 3 years ago

Reviewer: Jonathan Kliem

mkoeppe commented 3 years ago
comment:27

Thanks for these fixes and suggestions!

mkoeppe commented 3 years ago
comment:28

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

mkoeppe commented 3 years ago

Changed branch from u/gh-kliem/abc_for_convex_sets to u/mkoeppe/abc_for_convex_sets

kliem commented 3 years ago
comment:30

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()

New commits:

142fb46ConvexSet_base.codimension: Add doctest for alias 'codim'
30ebaf5ConvexSet_base.ambient_dim, ambient_dimension: Fix doc
kliem commented 3 years ago

Changed commit from c75ba42 to 30ebaf5

kliem commented 3 years ago
comment:31

Replying to @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.

mkoeppe commented 3 years ago
comment:32

Sorry, forgot to pull in your changes

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

fcf2a32fix coverage
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 30ebaf5 to fcf2a32

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from fcf2a32 to 1448835

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

Changed commit from 1448835 to 8ff6457

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 3 years ago

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

8ff6457Polyhedron_base.interior: Handle the empty polyhedron correctly
mkoeppe commented 3 years ago
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 commented 3 years ago
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!