Parents for polyhedra

[vbraun]

The Polyhedron class is, so far, free-standing with some sort of coercion for the base ring tacked manually. This ticket strives to add parents for polyhedra and make the base ring coercion work more naturally.

There will be 3 supported base rings:

• ZZ (meaning that the polyhedron is a lattice polytope, that is, both H- and V-representation are defined over ZZ)
• QQ
• RDF

Apply:

• attachment: trac_11763-polyhedra_coercion_folded.3.patch
• attachment: trac_11763_fix_associahedron.patch
• attachment: trac_11763_lazy_import.patch

Depends on #11634
Depends on #13109
Depends on #11310

CC: @robertwb

Component: geometry

Author: Volker Braun

Reviewer: Dmitrii Pasechnik

Merged: sage-5.6.beta1

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

[novoselt]

comment:1

Would there be any benefit in supporting real fields of arbitrary precision?

[vbraun]

comment:2

We don't have an implementation of the double description algorithm for other base rings, so we wouldn't be able to compute anything.

[vbraun]

Attachment: trac_11763_ZZ_polyhedron.patch.gz

Initial patch

[vbraun]

Initial patch

[vbraun]

comment:3

Attachment: trac_11763_parents_for_polyhedron.py.gz

This is now ready for inclusion. Marshall, are you interested in reviewing this patch and its dependency? ;-)

[vbraun]

Author: Volker Braun

[vbraun]

comment:5

Fix comparison of H/V-representation objects:

sage: triangle = Polyhedron([(0,0), (1,0), (0,1)])
sage: ieq = triangle.inequality_generator().next()
sage: ieq == copy(ieq)
False

Now returns True, as it should.

[vbraun]

Updated patch

[loefflerd]

Attachment: trac_11763_parents_for_polyhedron.patch.gz

Attachment: trac_11763_ZZ_polyhedron-rebase.patch.gz

Rebased for new patch at 11634

[loefflerd]

Attachment: trac_11763_parents-rebase.patch.gz

Rebased for new patch at #11634

[loefflerd]

comment:6

The new patch I posted at #11634 broke these, so I rebased them.

Apply trac_11763_ZZ_polyhedron-rebase.patch, trac_11763_parents-rebase.patch

[loefflerd]

comment:7

Apply trac_11763_zz_polyhedron-rebase.patch, trac_11763_parents-rebase.patch

(bloody patchbot!)

[loefflerd]

comment:8

No matter what I do, the patchbot won't pick up the two patches above, so I've done a single qfolded patch. Hopefully this will now work!

[loefflerd]

Apply only this patch. Patch against 5.0.beta7

[loefflerd]

comment:10

Attachment: trac_11763-polyhedra_coercion_folded.patch.gz

Sorry, I made a hash of rebasing the patch, so here's a new version.

[sagetrac-mhampton]

comment:11

This changes the behavior of the .vertices() method, returning "sage.geometry.polyhedron.representation.Vertex" objects instead of simple lists of coordinates. This breaks some code of mine, so I think there should be a deprecation warning before introducing this. I don't really like the behavior, but I see that .vertices_list() does return a list of lists of coordinates.

This patch also seems to slow things down a bit, but I haven't carefully tested that aspect.

[vbraun]

comment:12

The Vertex object implements the list interface, so any code that doesn't just test isinstance(-,list) should work fine. Plus, you can't really deprecate something unless you want to remove it later. I added the 'vertices_list` method so people can keep their broken code with minimal patching if they want.

[sagetrac-mhampton]

comment:13

Well, no, there is quite a bit of my code that does not work fine, and I am not talking about artificial test cases. Here is a shortened example of something this patch breaks:

c = polytopes.n_cube(3)
v = c.vertices()[0]
point(v)

This now gives a "TypeError: 'sage.rings.integer.Integer' object does not support indexing".

[novoselt]

comment:14

For the record: #12541 and #12544 have a similar situation. I replaced tuples with tuple-like containers and some stuff got broken. As it turned out, it was not too difficult to fix it by eliminating some "hard typechecks", although they are still waiting for an approval. If this is the case here, perhaps it is also not too difficult to fix.

As I understand it, direct typechecking is not welcomed in either Python or Sage, so if the new class implements list interface, it should be OK to use in place of the old one. If it does break some code, it is a bug and it should be fixed before merging, but not a reason for avoiding the change entirely or inventing elaborate deprecation scheme...

[loefflerd]

comment:15

There is a doctest failing on 5.0.beta10, according to the patchbot (something to do with the new associahedron class from #10817)

[vbraun]

comment:50

For the patchbot:

Apply trac_11763-polyhedra_coercion_folded.2.patch, trac_11763_fix_associahedron.patch, trac_11763_lazy_import.patch

[vbraun]

Reviewer: Dmitrii Pasechnik

[jdemeyer]

comment:52

On some systems, such as OS X >= 10.6 and Itanium:

sage -t  --long -force_lib devel/sage/sage/geometry/polyhedron/base.py
**********************************************************************
File "/Users/dehayebuildbot/build/sage/dehaye/dehaye_full/build/sage-5.6.beta0/devel/sage-main/sage/geometry/polyhedron/base.py", line 385:
    sage: cmp(P, 'string')
Expected:
    -1
Got:
    1
**********************************************************************

[vbraun]

Attachment: trac_11763-polyhedra_coercion_folded.2.patch.gz

Updated patch

[vbraun]

comment:54

I've added the trivial fix.

[vbraun]

comment:55

And now I noticed that this was already fixed in #12193.

[jdemeyer]

Merged: sage-5.6.beta1

[jdemeyer]

Attachment: trac_11763-polyhedra_coercion_folded.3.patch.gz

[jdemeyer]

comment:57

Rebased to sage-5.6.beta0.

[novoselt]

comment:58

Hey Volker,

Do you remember what was the reason for this change in normalize_rays?

diff --git a/sage/geometry/cone.py b/sage/geometry/cone.py

Index: sage/geometry/cone.py
===================================================================
--- a/sage/geometry/cone.py
+++ b/sage/geometry/cone.py
@@ -568,7 +568,10 @@
         V = lattice.base_extend(QQ)
         for n, ray in enumerate(rays):
             try:
-                ray = V(ray)
+                if isinstance(ray, (list, tuple, V._element_class)):
+                    ray = V(ray)
+                else:
+                    ray = V(list(ray))
             except TypeError:
                 raise TypeError("cannot convert %s to %s!" % (ray, V))
             if ray.is_zero():

It seems that if V does not want to take a ray, we should not force it.

[vbraun]

comment:59

I think the idea is to allow arbitrary iterables in normalize_rays. Why not? Its an auxiliary function, and the more general it is the better.

[novoselt]

comment:60

I just was wondering what was the particular use case - found this bit because of the fuzz with another patch. I don't mind it, although changing what V.__call__ accepts seems a more pleasant solution ;-)

[vbraun]

comment:61

Replying to @novoselt:

I don't mind it, although changing what V.__call__ accepts seems a more pleasant solution ;-)

Wasn't that one of our design decisions, that the ToricLattice should forbid conversion between the lattice and its dual?

[novoselt]

comment:62

Replying to @vbraun:

Wasn't that one of our design decisions, that the ToricLattice should forbid conversion between the lattice and its dual?

We prohibit coercion, conversion is certainly possible, and here V is the spanned vector space anyway. But I've also hit many times a situation when a standard constructor in Sage would not take generators as input, which is probably what has happened here.