Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#11763 closed enhancement (fixed)

Parents for polyhedra

Reported by: vbraun Owned by: mhampton
Priority: major Milestone: sage-5.6
Component: geometry Keywords:
Cc: robertwb Merged in: sage-5.6.beta1
Authors: Volker Braun Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #11634, #13109, #11310 Stopgaps:

Description (last modified by jdemeyer)

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:

Attachments (13)

trac_11763_ZZ_polyhedron.patch (14.2 KB) - added by vbraun 8 years ago.
Initial patch
trac_11763_parents_for_polyhedron.py (174.0 KB) - added by vbraun 8 years ago.
Initial patch
trac_11763_parents_for_polyhedron.patch (174.0 KB) - added by vbraun 8 years ago.
Updated patch
trac_11763_ZZ_polyhedron-rebase.patch (14.1 KB) - added by davidloeffler 8 years ago.
Rebased for new patch at 11634
trac_11763_parents-rebase.patch (173.6 KB) - added by davidloeffler 8 years ago.
Rebased for new patch at #11634
trac_11763-polyhedra_coercion_folded.patch (177.6 KB) - added by davidloeffler 8 years ago.
Apply only this patch. Patch against 5.0.beta7
trac_11763_relax_typechecks.patch (2.2 KB) - added by vbraun 8 years ago.
Updated patch
trac_11763-polyhedra_coercion_folded.2.2.patch (177.7 KB) - added by vbraun 7 years ago.
Updated patch
trac_11763_remove_trailing_whitespace.patch (54.7 KB) - added by vbraun 7 years ago.
Updated patch
trac_11763_fix_associahedron.patch (10.0 KB) - added by vbraun 7 years ago.
Updated patch
trac_11763_lazy_import.patch (1.4 KB) - added by vbraun 7 years ago.
Improved patch
trac_11763-polyhedra_coercion_folded.2.patch (247.1 KB) - added by vbraun 7 years ago.
Updated patch
trac_11763-polyhedra_coercion_folded.3.patch (247.0 KB) - added by jdemeyer 7 years ago.

Download all attachments as: .zip

Change History (75)

comment:1 Changed 8 years ago by novoselt

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

comment:2 Changed 8 years ago by vbraun

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

Changed 8 years ago by vbraun

Initial patch

Changed 8 years ago by vbraun

Initial patch

comment:3 Changed 8 years ago by vbraun

  • Authors set to Volker Braun
  • Description modified (diff)
  • Status changed from new to needs_review

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

comment:4 Changed 8 years ago by vbraun

  • Description modified (diff)

comment:5 Changed 8 years ago by vbraun

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.

Changed 8 years ago by vbraun

Updated patch

Changed 8 years ago by davidloeffler

Rebased for new patch at 11634

Changed 8 years ago by davidloeffler

Rebased for new patch at #11634

comment:6 Changed 8 years ago by davidloeffler

  • Description modified (diff)

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

comment:7 Changed 8 years ago by davidloeffler

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

(bloody patchbot!)

comment:8 Changed 8 years ago by davidloeffler

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!

comment:9 Changed 8 years ago by davidloeffler

  • Description modified (diff)

Changed 8 years ago by davidloeffler

Apply only this patch. Patch against 5.0.beta7

comment:10 Changed 8 years ago by davidloeffler

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

comment:11 Changed 8 years ago by mhampton

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.

comment:12 Changed 8 years ago by vbraun

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.

comment:13 Changed 8 years ago by mhampton

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".

comment:14 Changed 8 years ago by novoselt

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...

comment:15 Changed 8 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to doctest failure

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

comment:16 Changed 8 years ago by vbraun

  • Description modified (diff)
  • Status changed from needs_work to needs_review

The associahedron needed to be translated to the parent/element framework as well. I've fixed this. Also, I rediffed trac_11763-polyhedra_coercion_folded.2.patch because it only applied with some fuzz on sage-5.0.beta11

Changed 8 years ago by vbraun

Updated patch

comment:17 Changed 8 years ago by vbraun

  • Description modified (diff)

The final patch fixes the point() command to not make dumb type checks.

comment:18 Changed 8 years ago by vbraun

I noted a problem in the documentatation build, the updated patch fixes just that.

comment:19 Changed 8 years ago by davidloeffler

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

(for patchbot)

comment:20 Changed 8 years ago by novoselt

I thought the point of having "Apply" section in the description was to make the patchbot happy, why does it need to be duplicated?..

comment:21 Changed 8 years ago by davidloeffler

It was previously applying the patches in an order other than that listed on the ticket description (with coercion_folded.2.patch last rather than first). I didn't think to check whether the patches were applying happily anyway; as it happens they were. Sorry for the noise!

comment:22 Changed 8 years ago by novoselt

Oh, I don't complain about your post - I complain about patchbot not figuring out what is the correct order despite a clear description ;-)

comment:23 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work
  • Work issues changed from doctest failure to remove trailing whitespaces

comment:24 Changed 7 years ago by vbraun

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Work issues remove trailing whitespaces deleted

We don't have a policy on trailing white space, so its completely useless bikeshedding to require it one way or another. But since this ticket is the special case where we create a new subdirectory layout, I used a simple sed script to remove trailing whitespace.

comment:25 Changed 7 years ago by vbraun

  • Description modified (diff)

comment:26 Changed 7 years ago by chapoton

  • Status changed from needs_review to needs_work
  • There is now an error to be corrected, see bot report for 5.0rc0. This comes from a strange comparison with 'anything', which looks weird.
  • Maybe fold all the patches into one ?
  • In the part about associahedra, you replaced the sentence "Returns the Cartan type of self." by the sentence "Returns the Cartan type". This seems to be less informative.

Changed 7 years ago by vbraun

Updated patch

comment:27 Changed 7 years ago by vbraun

I've changed the cmp() doctest to use abs(cmp()) to avoid dependence on arbitrary memory positions.

Folding patches is considered harmful since it destroys history without any benefit.

A method always returns information about self, you could add "... of self" to every docstring.

comment:28 Changed 7 years ago by vbraun

  • Status changed from needs_work to needs_review

comment:29 Changed 7 years ago by vbraun

Rediffed for sage-5.0.beta3 because #12340 introduced a newline in one of the docstrings. No actual code changed.

comment:30 Changed 7 years ago by vbraun

  • Description modified (diff)

comment:31 Changed 7 years ago by vbraun

  • Description modified (diff)

Apply trac_11763-polyhedra_coercion_folded.2.patch, trac_11763_fix_associahedron.patch, trac_11763_relax_typechecks.patch, trac_11763_remove_trailing_whitespace.patch

comment:32 Changed 7 years ago by vbraun

  • Dependencies changed from #11634 to #11634, #13109

comment:33 Changed 7 years ago by vbraun

  • Dependencies changed from #11634, #13109 to #11634, #13109, #11310

#11310 fixes all the catch-all except: clauses, breaking this patch.

comment:34 Changed 7 years ago by novoselt

I'm getting one error when testing:

File "/home/novoselt/sage-5.2.rc1/devel/sage-main/sage/libs/ppl.pyx", line 119:
    sage: Polyhedron(vertices=gs, backend='cddr')  # long time (3s on sage.math, 2011)
Exception raised:
    Traceback (most recent call last):
      File "/home/novoselt/sage-5.2.rc1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.rc1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.rc1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[37]>", line 1, in <module>
        Polyhedron(vertices=gs, backend='cddr')  # long time (3s on sage.math, 2011)###line 119:
    sage: Polyhedron(vertices=gs, backend='cddr')  # long time (3s on sage.math, 2011)
      File "/home/novoselt/sage-5.2.rc1/local/lib/python/site-packages/sage/misc/decorators.py", line 691, in wrapper
        return func(*args, **kwds)
      File "/home/novoselt/sage-5.2.rc1/local/lib/python/site-packages/sage/geometry/polyhedron/constructor.py", line 325, in Polyhedron
        parent = Polyhedra(base_ring, ambient_dim, backend=backend)
      File "/home/novoselt/sage-5.2.rc1/local/lib/python/site-packages/sage/geometry/polyhedron/parent.py", line 56, in Polyhedra
        ') implemented for given basering (='+str(base_ring)+').')
    ValueError: No such backend (=cddr) implemented for given basering (=Integer Ring).

comment:35 Changed 7 years ago by vbraun

I fixed the doctest (its backend=cdd not cddr) and added documentation to the sage.geometry.polyhedron.parent.Polyhedra constructor function.

comment:36 Changed 7 years ago by vbraun

Updated patch fixes one important issue. The inherited comparison for PolyhedronFace_base was too lax, which resulted in identical (and not just isomorphic) face lattices in some cases. Fixed now.

comment:37 Changed 7 years ago by vbraun

  • Dependencies changed from #11634, #13109, #11310 to #11634, #13109, #11310, #13638

Rebased for #13638

Changed 7 years ago by vbraun

Updated patch

Changed 7 years ago by vbraun

Updated patch

comment:38 Changed 7 years ago by vbraun

  • Description modified (diff)

I've changed the PolyhedronFace class to just derive from SageObject this should be clearer. Also, the more trivial patches are folded into the first.

It would be great if this ticket could be reviewed before the heat death of the universe.

comment:39 Changed 7 years ago by vbraun

Rebased for changes in #13638

comment:40 Changed 7 years ago by chapoton

Apply only trac_11763-polyhedra_coercion_folded.2.patch trac_11763_fix_associahedron.patch

comment:41 Changed 7 years ago by chapoton

Ok, let us forget about trailing whitespaces.

But what about the startup plugin which is complaining here ?

comment:42 Changed 7 years ago by vbraun

I agree that using lazy imports would be good. I'll give it a whirl.

comment:43 Changed 7 years ago by vbraun

  • Description modified (diff)

Patch loads Polyhedron lazily, so we don't import anything on startup.

comment:44 Changed 7 years ago by vbraun

Also lazily import the parent PolyhedralSets, plus one typo fix.

comment:45 Changed 7 years ago by chapoton

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

Changed 7 years ago by vbraun

Improved patch

comment:46 Changed 7 years ago by vbraun

  • Dependencies changed from #11634, #13109, #11310, #13638 to #11634, #13109, #11310

I switched the order this patch and #13638.

comment:47 Changed 7 years ago by dimpase

  • Status changed from needs_review to positive_review

comment:48 follow-up: Changed 7 years ago by dimpase

The patchbot seems to follow the patch order in the Attachments list, rather than in the ticket description Apply list.

comment:49 in reply to: ↑ 48 Changed 7 years ago by dimpase

  • Cc robertwb added

Replying to dimpase:

The patchbot seems to follow the patch order in the Attachments list, rather than in the ticket description Apply list.

If I am reading the right patchbot source, it seems that it looks for apply in the whole rss feed...

comment:50 Changed 7 years ago by vbraun

For the patchbot:

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

comment:51 Changed 7 years ago by vbraun

  • Reviewers set to Dmitrii Pasechnik

comment:52 Changed 7 years ago by jdemeyer

On some systems, such as OS X 10.8 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
**********************************************************************
Version 0, edited 7 years ago by jdemeyer (next)

comment:53 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Changed 7 years ago by vbraun

Updated patch

comment:54 Changed 7 years ago by vbraun

  • Status changed from needs_work to positive_review

I've added the trivial fix.

comment:55 Changed 7 years ago by vbraun

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

comment:56 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.6.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

Changed 7 years ago by jdemeyer

comment:57 Changed 7 years ago by jdemeyer

  • Description modified (diff)

Rebased to sage-5.6.beta0.

comment:58 Changed 7 years ago by novoselt

Hey Volker,

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

  • sage/geometry/cone.py

    diff --git a/sage/geometry/cone.py b/sage/geometry/cone.py
    
    a b  
    568568        V = lattice.base_extend(QQ)
    569569        for n, ray in enumerate(rays):
    570570            try:
    571                 ray = V(ray)
     571                if isinstance(ray, (list, tuple, V._element_class)):
     572                    ray = V(ray)
     573                else:
     574                    ray = V(list(ray))
    572575            except TypeError:
    573576                raise TypeError("cannot convert %s to %s!" % (ray, V))
    574577            if ray.is_zero():

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

comment:59 Changed 7 years ago by vbraun

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.

comment:60 follow-up: Changed 7 years ago by novoselt

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

comment:61 in reply to: ↑ 60 ; follow-up: Changed 7 years ago by vbraun

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?

comment:62 in reply to: ↑ 61 Changed 7 years ago by novoselt

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.

Note: See TracTickets for help on using tickets.