Opened 7 years ago

Closed 6 years ago

#10817 closed enhancement (fixed)

implementation of the generalized associahedron as a polyhedral complex

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-5.0
Component: combinatorics Keywords: associahedra
Cc: Merged in: sage-5.0.beta8
Authors: Christian Stump Reviewers: Frédéric Chapoton, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by stumpc5)

The patch contains the implementation of the generalized associahedron, as constructed in [CFZ] Chapoton, Fomin, Zelevinsky - Polytopal realizations of the generalized associahedra, http://arxiv.org/abs/math/0202004.

sage: Associahedron(['A',3])
Generalized associahedron of type ['A', 3] with 14 vertices

The class inherits from Polyhedra, and uses several new methods for root spaces:

  • RootLatticeRealization.index_bipartition, returns the bipartition of the indices of the Dynkin diagram vertices, if it is bipartite
  • RootLatticeRealization.almost_positive_roots, returns the sorted list of positive and simple negative roots
  • RootLatticeRealization.tau_plus_minus, returns two piecewise linear operators on the root space which are used to define the "tropical Coxeter element" in [CFZ]
  • RootLatticeRealization.almost_positive_root_decomposition, returns the orbit decomposition of the almost positive roots under the dihedral group action of < tau_plus, tau_minus > as defined above

Attachments (1)

trac_10817-generalized_associahedra-cs.patch (17.6 KB) - added by stumpc5 6 years ago.

Download all attachments as: .zip

Change History (30)

comment:1 Changed 7 years ago by stumpc5

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by stumpc5

  • Description modified (diff)

comment:3 Changed 7 years ago by stumpc5

  • Description modified (diff)

comment:4 Changed 7 years ago by stumpc5

  • Dependencies set to #10538
  • Owner changed from sage-combinat to (none)

comment:5 Changed 7 years ago by stumpc5

  • Dependencies changed from #10538 to #11187

As many files are touched in #11187, this "depends" on it to apply properly.

comment:6 Changed 7 years ago by chapoton

Apply trac_10817-generalized_associahedra-cs.patch

comment:7 Changed 7 years ago by stumpc5

  • Milestone set to sage-4.7.2

comment:8 Changed 7 years ago by chapoton

  • Dependencies #11187 deleted

Let us try without the dependency, which is not obviously needed.

Apply trac_10817-generalized_associahedra-cs.patch

comment:9 follow-up: Changed 7 years ago by chapoton

  • Dependencies set to #11187

well, too bad, it does really depends on #11187

comment:10 in reply to: ↑ 9 Changed 7 years ago by stumpc5

  • Dependencies #11187 deleted

Replying to chapoton:

well, too bad, it does really depends on #11187

I removed the dependencies so we can get it done without waiting for the other patch - Thanks for looking at it!

comment:11 Changed 7 years ago by chapoton

Apply trac_10817-generalized_associahedra-cs.patch

comment:12 Changed 7 years ago by stumpc5

  • Description modified (diff)
  • Milestone changed from sage-4.7.2 to sage-4.7.1

comment:13 Changed 7 years ago by stumpc5

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:14 Changed 6 years ago by chapoton

  • Reviewers set to Frédéric Chapoton, Nicolas M. Thiéry

A review has been done, and a reviewer patch follows soon.

comment:15 follow-up: Changed 6 years ago by nthiery

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Cheers,

Nicolas

comment:16 in reply to: ↑ 15 Changed 6 years ago by nthiery

Replying to nthiery:

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Ok, I finally could do it. The patch is on the queue. If you are happy with it, you may fold the two patches, upload them here, and set a positive review on my behalf.

comment:17 follow-up: Changed 6 years ago by stumpc5

  • Status changed from needs_review to positive_review

Thanks for the review -- you should add yourself as an author actually... .

I set a positive review on Nicolas' behalf.

Best, Christian

comment:18 Changed 6 years ago by nthiery

For the record: all tests pass on 5.0 beta4, with the following patches applied:

trac_11003-folded.patch
trac_10998-categories-posets-nt.patch
trac_11118-finite_enumset_list_cache-fh.patch
trac_11250-action_coerce_doc-fh.patch
trac_11257_avoid_coercion_power_zero-nb.patch
trac_12483-family-workaround_12482-nt.patch
trac_12464-free_module_classcall-fh.patch
trac_12490-trac_role-fh.patch
trac_10670_integral_mobius_matrix_for_posets-fh.patch
trac_11382-subposet_to_vertex_speedup-fh.patch
trac_12484-free_module-monomials_cmp-nt.patch
trac_12489-freemod_eq-nt.patch
trac_10347_is_skew_symmetrizable-cs.patch
trac_12476-lattice_join_matrix_speedup-fh.patch
trac_9469-category-membership_without_arguments-nt.patch
trac_10603-union_enumset_elconstr_fix-fh.patch
trac_12528_free_module-optimize-nt.patch
trac_10817-generalized_associahedra-cs.patch
trac_10817-generalized_associahedra-review-nt.patch

Most of the above patches are either orthogonal or already merged in beta5, so I assume the test pass without them too.

comment:19 in reply to: ↑ 17 Changed 6 years ago by nthiery

Replying to stumpc5:

Thanks for the review -- you should add yourself as an author actually... .

Bah, just my reviewer's job. You drove this patch through!

comment:20 follow-up: Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

There is a doctest failure on hawk (OpenSolaris? 06.2009-32):

**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0]
**********************************************************************

comment:21 in reply to: ↑ 20 Changed 6 years ago by stumpc5

Replying to jdemeyer:

There is a doctest failure on hawk (OpenSolaris? 06.2009-32):

    sage: sorted(Asso.Hrepresentation())

The buildbot doesn't find the failure, and the list has actually the same content. So the problem must be something with the cmp of inequalities.

I wouldn't know how to fix that in this patch actually.

Best, Christian

comment:22 follow-up: Changed 6 years ago by jdemeyer

On Cicero (Linux i386):

**********************************************************************
File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]
**********************************************************************

comment:23 in reply to: ↑ 22 ; follow-up: Changed 6 years ago by stumpc5

Replying to jdemeyer:

I updated the patch with this order in the sorted list of inequalities.

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

comment:24 in reply to: ↑ 23 ; follow-up: Changed 6 years ago by nthiery

Replying to stumpc5:

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

What about:

    sage: sorted(Asso.Hrepresentation(), key=repr)
    [An inequality (-1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]

Then the result should be sorted according to their string representation, and string comparison should be platform independent.

Changed 6 years ago by stumpc5

comment:25 in reply to: ↑ 24 ; follow-up: Changed 6 years ago by stumpc5

  • Status changed from needs_work to needs_review

Replying to nthiery:

Replying to stumpc5: Then the result should be sorted according to their string representation, and string comparison should be platform independent.

Done - how can I know that string representations should be platform independent and some others aren't?

Thanks! Christian

comment:26 in reply to: ↑ 25 ; follow-up: Changed 6 years ago by nthiery

  • Status changed from needs_review to positive_review

Replying to stumpc5:

Replying to nthiery:

Replying to stumpc5: Then the result should be sorted according to their string representation, and string comparison should be platform independent.

Done

Thanks! Positive review, assuming the tests pass.

how can I know that string representations should be platform independent and some others aren't?

Because:

  • I am amost certain that Python compares strings lexicographically (it does for e.g. tuples; see http://docs.python.org/library/stdtypes.html; it's certainly specified somewhere for strings too)
  • The Inequality class implements _repr_ independently of the platform
  • On the other hand, this class does not implement cmp, so its behavior is unspecified. And likely to be platform dependent.

comment:27 in reply to: ↑ 26 ; follow-up: Changed 6 years ago by stumpc5

Replying to nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test

for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)

I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Best, Christian

comment:28 in reply to: ↑ 27 Changed 6 years ago by nthiery

Replying to stumpc5:

Replying to nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test

for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)

I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Indeed.

Python has been upgraded to 2.7 in Sage 5.0. I guess this syntax for format was not yet supported in Python 2.6. Let's just wait for the buildbot to run on 5.0.

comment:29 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.0.beta8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.