#22578 closed enhancement (fixed)
Polyhedron.bounding_box: New keyword argument integral_hull, use it in .integral_points
Reported by:  mkoeppe  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  geometry  Keywords:  days84, days85 
Cc:  vdelecroix, jipilab, tscrim  Merged in:  
Authors:  Matthias Koeppe  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  18e7a74 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
An amazing insight is that if one wants to know to bounding box of the integer points, rather than of all points, then one can round down upper bounds and round up lower bounds.
This can make a huge difference for integer points enumeration.
Change History (20)
comment:1 Changed 4 years ago by
 Branch set to u/mkoeppe/polyhedron_bounding_box__new_keyword_argument_integral_hull__use_it_it__integral_points
comment:2 Changed 4 years ago by
 Cc vdelecroix jipilab added
 Commit set to b82ac33abb8e7db2340db42af4e9047834d3132f
 Keywords days84 added
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Summary changed from Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points to Polyhedron.bounding_box: New keyword argument integral_hull, use it in .integral_points
comment:4 Changed 4 years ago by
 Cc tscrim added
comment:5 Changed 4 years ago by
 Status changed from needs_review to needs_work
This causes doctest failures in sandpiles. My guess is something is now returning a None
that is fed to a zip
.
comment:6 Changed 4 years ago by
Thanks for catching this. I'm preparing a fix.
comment:7 Changed 4 years ago by
 Commit changed from b82ac33abb8e7db2340db42af4e9047834d3132f to 486204f7e7a5ac5f14573e006f3d6464584ef6bd
comment:8 Changed 4 years ago by
Fixed the failures that resulted from empty bounding boxes;
but there remain failures that result from different sorting orders of integral_points
.
Should I change all these doctests so that they become independent of the sorting order?
comment:9 Changed 4 years ago by
 Keywords days85 added
 Reviewers set to Travis Scrimshaw
If the output of integral_points
is not subject to location in memory, then you don't have to. I'm prepared to set a positive review once addressed.
comment:10 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:11 Changed 4 years ago by
It looks like the order of some doctests in sandpiles have either changes or does depend on the machine/memory location (which is the case if they pass on your machine). I do agree that they are all trivial failures and can be easily fixed, but I just need an answer to which of the above cases we are in.
comment:12 Changed 4 years ago by
I think the order has changed because a different enumeration strategy is selected. I don't think it's machine or address specific.
In my opinion, doctests should not rely on the order of lists whose ordering is unspecified by documentation; they should be rewritten using sort
or set
.
comment:13 Changed 4 years ago by
If you want to change the tests so that the order is sorted, go ahead. I would avoid using set
since (unfortunately) the output may not be in a specific order. However, we can just change the output for now too. I can also make these changes if you want me to.
comment:14 Changed 4 years ago by
I would strongly suggest to adjust the tests to use sort
then; because it is very likely that future changes to the lattice point enumeration code (such as automatic selection of the normaliz backend if it is available) will change the order again. If you'd like to go ahead with this change, that would be great...
comment:15 Changed 4 years ago by
I will do so now.
comment:16 Changed 4 years ago by
 Branch changed from u/mkoeppe/polyhedron_bounding_box__new_keyword_argument_integral_hull__use_it_it__integral_points to public/geometry/polyhedron_bounding_box_integer_hull22578
 Commit changed from 486204f7e7a5ac5f14573e006f3d6464584ef6bd to 18e7a748198e1c3abc175b703a24d1010b8ee8cf
All tests now pass, and they are now checked by sorting the output. If my changes look good to you, then you can set a positive review.
New commits:
18e7a74  Fixing doctests and doing it so the order doesn't change in the future.

comment:17 Changed 4 years ago by
 Status changed from needs_review to positive_review
Looks good. Thanks very much!
comment:18 Changed 4 years ago by
 Branch changed from public/geometry/polyhedron_bounding_box_integer_hull22578 to 18e7a748198e1c3abc175b703a24d1010b8ee8cf
 Resolution set to fixed
 Status changed from positive_review to closed
comment:19 Changed 4 years ago by
 Branch changed from 18e7a748198e1c3abc175b703a24d1010b8ee8cf to u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf
comment:20 Changed 4 years ago by
 Branch changed from u/jmantysalo/18e7a748198e1c3abc175b703a24d1010b8ee8cf to 18e7a748198e1c3abc175b703a24d1010b8ee8cf
 Commit 18e7a748198e1c3abc175b703a24d1010b8ee8cf deleted
Sorry, my typo in a ticket number.
New commits:
22578: Polyhedron.bounding_box: New keyword argument integral_hull, use it it .integral_points