Opened 5 months ago
Closed 4 months ago
#31919 closed enhancement (fixed)
ABC for convex sets
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage9.4 
Component:  geometry  Keywords:  
Cc:  ghkliem, 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: 
Description (last modified by )
We create a base class ConvexSet_base
with abstract methods to define an API for convex sets (convex subsets of a finite dimensional topological Rvector space such as R^n
).
We use it to test/unify the API of Polyhedron
, ConvexRationalPolyhedralCone
, LatticePolytope
, RelativeInterior
(#31916)
See also:
Change History (50)
comment:1 Changed 5 months ago by
 Branch set to u/mkoeppe/abc_for_convex_sets
comment:2 Changed 5 months ago by
 Commit set to ccc84213906ff6bf34d2e5c6b50d146a2901ec9c
comment:3 Changed 5 months ago by
comment:4 Changed 5 months ago by
 Dependencies set to #31916
comment:5 Changed 5 months ago by
 Commit changed from ccc84213906ff6bf34d2e5c6b50d146a2901ec9c to 4bac2fe2db4519478d6e5633e86b29098d9aa0c4
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

comment:6 Changed 5 months ago by
 Commit changed from 4bac2fe2db4519478d6e5633e86b29098d9aa0c4 to 1e8dd0927ac51fd2131b16dbc4073b78f4dc9d8d
comment:7 Changed 5 months ago by
 Description modified (diff)
comment:8 Changed 5 months ago by
 Commit changed from 1e8dd0927ac51fd2131b16dbc4073b78f4dc9d8d to 3f4acb34d064ec0c721b8a43e898f4d65479d43e
comment:9 Changed 5 months ago by
 Commit changed from 3f4acb34d064ec0c721b8a43e898f4d65479d43e to dede9de1a8e01114b289149bccb51c466223d027
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

comment:10 Changed 5 months ago by
 Status changed from new to needs_review
comment:11 Changed 5 months ago by
 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
 Commit changed from dede9de1a8e01114b289149bccb51c466223d027 to 007e6fda9fb5dfccf109b06d15f8799f7f03ac5f
Branch pushed to git repo; I updated commit sha1. New commits:
007e6fd  ConvexRationalPolyhedralCone.is_empty: Add doctest

comment:13 Changed 5 months ago by
 Status changed from needs_work to needs_review
I guess it is back on needs review.
comment:14 Changed 5 months ago by
Can you please add doctests for src/sage/geometry/convex_set.py
yet.
comment:15 Changed 5 months ago by
 Commit changed from 007e6fda9fb5dfccf109b06d15f8799f7f03ac5f to 6a0baac5f679d90a1acd3696f3613350af5af9f1
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

comment:16 Changed 5 months ago by
 Status changed from needs_review to needs_work
comment:17 Changed 5 months ago by
 Commit changed from 6a0baac5f679d90a1acd3696f3613350af5af9f1 to 9a7ce3a53d63ace6ed56f4addc92f61b85549b32
comment:18 Changed 5 months ago by
 Status changed from needs_work to needs_review
comment:19 Changed 5 months ago by
 Commit changed from 9a7ce3a53d63ace6ed56f4addc92f61b85549b32 to e2b0ef7390426c7d8f6f7f0a1382b326d5c9bc6e
Branch pushed to git repo; I updated commit sha1. New commits:
e2b0ef7  ConvexSet_base._test_convex_set: Fix doctest output

comment:20 Changed 5 months ago by
 Commit changed from e2b0ef7390426c7d8f6f7f0a1382b326d5c9bc6e to f4bdffda473c608289d6b8c90a3687484d24f3be
comment:21 Changed 5 months ago by
 Description modified (diff)
comment:22 Changed 5 months ago by
 Description modified (diff)
comment:23 Changed 5 months ago by
 Description modified (diff)
comment:24 followup: ↓ 31 Changed 5 months ago by
 Branch changed from u/mkoeppe/abc_for_convex_sets to u/ghkliem/abc_for_convex_sets
 Commit changed from f4bdffda473c608289d6b8c90a3687484d24f3be to c75ba428cd91e71a8b237602a3529b936eb6d965
New commits:
c75ba42  fix coverage

comment:25 followup: ↓ 28 Changed 5 months ago by
 I don't think
ambient_dimension
should return the dimension ofself
.
+ def ambient_dimension(self): + Return the dimension of ``self``. + + This is the same as :meth:`ambient_dim`.
 That
codim
is an alias ofcodimension
should be doctested I think.  Why have you removed the test suite on the relative interior of the empty polyhedron?
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.
 sage: P = Polyhedron() + sage: P = Polyhedron([[1, 2], [3, 4]]) sage: from sage.geometry.relative_interior import RelativeInterior sage: TestSuite(RelativeInterior(P)).run()
 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
 Reviewers set to Jonathan Kliem
comment:27 Changed 5 months ago by
Thanks for these fixes and suggestions!
comment:28 in reply to: ↑ 25 ; followup: ↓ 30 Changed 5 months ago by
Replying to ghkliem:
 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
 Branch changed from u/ghkliem/abc_for_convex_sets to u/mkoeppe/abc_for_convex_sets
comment:30 in reply to: ↑ 28 ; followup: ↓ 36 Changed 5 months ago by
 Commit changed from c75ba428cd91e71a8b237602a3529b936eb6d965 to 30ebaf5a657040cb787bea0f5c2540ca08115284
Replying to mkoeppe:
Replying to ghkliem:
 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:
142fb46  ConvexSet_base.codimension: Add doctest for alias 'codim'

30ebaf5  ConvexSet_base.ambient_dim, ambient_dimension: Fix doc

comment:31 in reply to: ↑ 24 ; followup: ↓ 37 Changed 5 months ago by
Replying to ghkliem:
New commits:
c75ba42 fix coverage
Please fix coverage or cherrypick 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.
comment:32 Changed 5 months ago by
Sorry, forgot to pull in your changes
comment:33 Changed 5 months ago by
 Commit changed from 30ebaf5a657040cb787bea0f5c2540ca08115284 to fcf2a32a768097f9248cda456624784cc9f199c6
Branch pushed to git repo; I updated commit sha1. New commits:
fcf2a32  fix coverage

comment:34 Changed 5 months ago by
 Commit changed from fcf2a32a768097f9248cda456624784cc9f199c6 to 1448835c107b949b9129296a92851d0026bb774a
comment:35 Changed 5 months ago by
 Commit changed from 1448835c107b949b9129296a92851d0026bb774a to 8ff6457938186754c5ef2dcb1559dbfb8c50b248
Branch pushed to git repo; I updated commit sha1. New commits:
8ff6457  Polyhedron_base.interior: Handle the empty polyhedron correctly

comment:36 in reply to: ↑ 30 Changed 5 months ago by
Replying to ghkliem:
Replying to mkoeppe:
Replying to ghkliem:
 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
Replying to ghkliem:
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
 Commit changed from 8ff6457938186754c5ef2dcb1559dbfb8c50b248 to 148016ff92d33c36f29d6ce9c1937a00aba9e17b
Branch pushed to git repo; I updated commit sha1. New commits:
148016f  Polyhedron_base.product: Add doctest for alias 'cartesian_product'

comment:39 Changed 5 months ago by
 Status changed from needs_review to needs_work
sage t long warnlong 111.1 randomseed=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/sitepackages/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/sitepackages/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/sitepackages/sage/geometry/relative_interior.py", line 84, in ambient return self._polyhedron.ambient() File "/home/jonathan/Applications/sage/local/lib/python3.8/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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 warnlong 111.1 randomseed=0 relative_interior.py # 2 doctests failed
comment:40 Changed 5 months ago by
 Commit changed from 148016ff92d33c36f29d6ce9c1937a00aba9e17b to 686d0afbeba9f5d33131ecbe20a907c20635faa5
comment:41 Changed 5 months ago by
 Status changed from needs_work to needs_review
Cherrypicking 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
Patchbot is green modulo the unrelated src/sage/misc/package.py
failure
comment:43 Changed 5 months ago by
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
Fine with me if you want to make this change
comment:45 followup: ↓ 46 Changed 4 months ago by
Actually I think after #31705 this won't matter
comment:46 in reply to: ↑ 45 Changed 4 months ago by
comment:47 Changed 4 months ago by
 Status changed from needs_review to positive_review
One tiny thing about RelativeInterior.interior
: It should return self
, if the relative interior is fulldimensional. 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
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
 Description modified (diff)
comment:50 Changed 4 months ago by
 Branch changed from u/mkoeppe/abc_for_convex_sets to 686d0afbeba9f5d33131ecbe20a907c20635faa5
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
ConvexRationalPolyhedralCone: Add method is_empty and aliases is_full_dimensional, is_universe
LatticePolytopeClass, IntegralRayCollection: Make ambient_dim an alias for lattice_dim
ConvexSet_base.dim: New
ConvexSet_base.is_compact, ConvexSet_compact: New