Opened 9 years ago
Closed 8 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 )
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)
Change History (30)
comment:1 Changed 9 years ago by
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
- Description modified (diff)
comment:3 Changed 9 years ago by
- Description modified (diff)
comment:4 Changed 9 years ago by
- Dependencies set to #10538
- Owner changed from sage-combinat to (none)
comment:5 Changed 9 years ago by
- Dependencies changed from #10538 to #11187
comment:6 Changed 9 years ago by
Apply trac_10817-generalized_associahedra-cs.patch
comment:7 Changed 9 years ago by
- Milestone set to sage-4.7.2
comment:8 Changed 9 years ago by
- 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: ↓ 10 Changed 9 years ago by
- Dependencies set to #11187
well, too bad, it does really depends on #11187
comment:10 in reply to: ↑ 9 Changed 9 years ago by
- Dependencies #11187 deleted
comment:11 Changed 9 years ago by
Apply trac_10817-generalized_associahedra-cs.patch
comment:12 Changed 9 years ago by
- Description modified (diff)
- Milestone changed from sage-4.7.2 to sage-4.7.1
comment:13 Changed 9 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:14 Changed 8 years ago by
- 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: ↓ 16 Changed 8 years ago by
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 8 years ago by
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: ↓ 19 Changed 8 years ago by
- 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 8 years ago by
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 8 years ago by
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: ↓ 21 Changed 8 years ago by
- 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 8 years ago by
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: ↓ 23 Changed 8 years ago by
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: ↓ 24 Changed 8 years ago by
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: ↓ 25 Changed 8 years ago by
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 8 years ago by
comment:25 in reply to: ↑ 24 ; follow-up: ↓ 26 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:26 in reply to: ↑ 25 ; follow-up: ↓ 27 Changed 8 years ago by
- 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: ↓ 28 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
- Merged in set to sage-5.0.beta8
- Resolution set to fixed
- Status changed from positive_review to closed
As many files are touched in #11187, this "depends" on it to apply properly.