Opened 11 years ago
Closed 6 years ago
#10819 closed enhancement (fixed)
implementation of the cluster complex
Reported by:  stumpc5  Owned by:  

Priority:  major  Milestone:  sage7.1 
Component:  combinatorics  Keywords:  cluster complex 
Cc:  tscrim, stumpc5  Merged in:  
Authors:  Christian Stump, Frédéric Chapoton  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  3c7d5ae (Commits, GitHub, GitLab)  Commit:  3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e 
Dependencies:  #20111, #20027  Stopgaps: 
Description (last modified by )
The patch contains an implementation of the cluster complex for finite types.
sage: ClusterComplex(['A',3]) Cluster complex of type ['A', 3] with 9 vertices and 14 facets
The implementation depends on its realization as a subword complex.
Attachments (1)
Change History (57)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
 Dependencies set to 10538,
 Description modified (diff)
 Status changed from new to needs_review
comment:3 Changed 11 years ago by
 Owner changed from sagecombinat to (none)
Apply trac_10819cluster_complexcs.patch
comment:4 Changed 11 years ago by
 Dependencies changed from 10538, to #10538
comment:5 followup: ↓ 6 Changed 11 years ago by
Hi,
1) here also, the header is not correct, you should add ticket number #10819.
2) this seems to be a real error, which appears several times :
AttributeError?: 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse' object has no attribute 'is_skew_symmetrizable'
comment:6 in reply to: ↑ 5 Changed 11 years ago by
Replying to chapoton:
1) here also, the header is not correct, you should add ticket number #10819.
I fixed it  now I think I know what (not why) to do in order to pass the buildbot. Thanks!
2) this seems to be a real error, which appears several times :
There was one dependency missing, see #10298. This is like only knowing one linear extension of the ordering given by the dependencies  so getting the dependencies is really try and error...
comment:7 Changed 11 years ago by
 Milestone set to sage4.7.2
comment:8 followup: ↓ 9 Changed 11 years ago by
 Status changed from needs_review to needs_work
Hello Christian. Here are two things that need to be corrected :
1) type A_n is in n+3 sided polygon
2) formatting of doc is not correct in cartan_type
comment:9 in reply to: ↑ 8 Changed 11 years ago by
Replying to chapoton:
I really appreciate that you do some progress on these patches, thanks!
I think I will reimplement this patch using subword complexes rather than the cluster implementation. This will be much faster, and I don't expect that the cluster package will become part of main sage soon (see the dependency above). On the other hand, the subword complexes depend on my new implementation of finite reflection groups (#11187) which depends on the implementation of the universal cyclotomic field (#8327), so it will also be unlikely that it will get positively reviewed soon (and I see that all of them have rejects in the newest versions, so it will be an even longer way).
1) type A_n is in n+3 sided polygon 2) formatting of doc is not correct in cartan_type
I will update the patch fixing these issues.
Best, Christian
comment:10 Changed 11 years ago by
 Description modified (diff)
 Status changed from needs_work to needs_review
I fixed the two issues suggested by Frederic  what I do not like now is that the vertices are not positive roots anymore, but on the other hand the implementation is now valid for all finite Coxeter groups and also the multicluster complex can be constructed.
comment:11 followup: ↓ 12 Changed 10 years ago by
 Status changed from needs_review to needs_work
Applying this and its dependencies to 5.0.beta11 results in a Sage install that won't start up, and hence fails every doctest in the library  see patchbot logs.
comment:12 in reply to: ↑ 11 Changed 10 years ago by
Replying to davidloeffler:
Applying this and its dependencies to 5.0.beta11 results in a Sage install that won't start up, and hence fails every doctest in the library  see patchbot logs.
Thanks for looking at it  for now, I would prefer if we postpone this patch, since I want to make some further improvements here.
Best, Christian
Changed 9 years ago by
comment:13 Changed 9 years ago by
 Dependencies changed from #10538 to #11010
comment:14 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:15 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:16 Changed 8 years ago by
 Branch set to public/ticket/10189
 Commit set to 7a2d814c6457d49fd67b22b84396215d30321a98
Hello Christian,
I have made a git branch with one part of the patch, not touching the file cluster_seed.py
in order to keep it as independent as possible.
I have also cleaned the code a little bit to make sur it passes the pyflakes and pep8 tests.
New commits:
ffa07b5  #10819 Implementation of the cluster complex

7a2d814  trac #10189 code cleanup (pyflakes, pep8, doc)

comment:17 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:18 Changed 8 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:19 Changed 7 years ago by
 Milestone changed from sage6.4 to sage6.8
comment:20 Changed 7 years ago by
 Branch changed from public/ticket/10189 to public/ticket/10819
 Commit changed from 7a2d814c6457d49fd67b22b84396215d30321a98 to 4f997a995423047e70c6ccf262726183e563be0c
 Milestone changed from sage6.8 to sage6.10
 Work issues set to lacking doc
comment:21 Changed 6 years ago by
 Commit changed from 4f997a995423047e70c6ccf262726183e563be0c to 615b67fbcad7fc66484fd9d14fce4ae7564993a2
comment:22 Changed 6 years ago by
 Milestone changed from sage6.10 to sage7.1
 Status changed from needs_work to needs_review
 Work issues lacking doc deleted
comment:23 Changed 6 years ago by
 Dependencies #11010 deleted
comment:24 Changed 6 years ago by
 Cc tscrim stumpc5 added
This should be almost ready. Anybody available to have a look ?
comment:25 Changed 6 years ago by
Will do that.
comment:26 Changed 6 years ago by
By almost ready, do you mean you will be making changes or that it just needs someone else to look it over?
comment:27 Changed 6 years ago by
second thing: "it just needs someone else to look it over"
comment:28 Changed 6 years ago by
Hey Christian and Frédéric, here are my comments:
 We should use the standard copyright template from http://doc.sagemath.org/html/en/developer/coding_basics.html#headingsofsagelibrarycodefiles for all new files.
 The file should be added to the documentation.
 You should run the
TestSuite
on the cluster complex (often this is done in the__init__
tests).  Error messages are typically not considered as sentences, so they should start with a lower case and not end with a period.
 Your
__call__
does not appear to be idempotent, i.e.,C(C((0,1)))
should equal (or even better, be identical to)C((0,1))
.  You aren't properly using the category framework by not having
ClusterComplexFacet
as theElement
attribute ofClusterComplex
, and subsequently, you should useself.element_class
inClusterComplex
.  The methods of
ClusterComplexFacet
should at least have a oneline description of what the method does.
Some of these comments extend to the SubwordComplex
, which might require a separate ticket to work on.
comment:29 Changed 6 years ago by
 Commit changed from 615b67fbcad7fc66484fd9d14fce4ae7564993a2 to b8b9e820573be4b0e217af7dfa0c54bedc13a4d5
comment:30 Changed 6 years ago by
 Commit changed from b8b9e820573be4b0e217af7dfa0c54bedc13a4d5 to 279a3da0fd5b6c24fd410fd5d6111dc246f31aa5
Branch pushed to git repo; I updated commit sha1. New commits:
279a3da  removed one line in cluster seed that doesn't have anything to do with this ticket

comment:31 Changed 6 years ago by
 Commit changed from 279a3da0fd5b6c24fd410fd5d6111dc246f31aa5 to 6d984c83175130d18313be1d14549f59b5e5a7de
Branch pushed to git repo; I updated commit sha1. New commits:
6d984c8  moved the file into the main combinat folder since the implementation does not have anything to do with cluster algebras anymore

comment:32 Changed 6 years ago by
 Dependencies set to #20111
comment:33 Changed 6 years ago by
 Commit changed from 6d984c83175130d18313be1d14549f59b5e5a7de to c8e990cf5a951d7f13fb5af894aa0076b36de308
comment:34 Changed 6 years ago by
 Status changed from needs_review to needs_info
Once the issues raised by Travis are solved in #20111, I will start looking at the actual content of this ticket...
comment:35 Changed 6 years ago by
 Commit changed from c8e990cf5a951d7f13fb5af894aa0076b36de308 to 102bba164ec83205209387f33de34894bb6a44e5
comment:36 Changed 6 years ago by
So, technically I think the ticket is ready. But the documentation is still lousy. I will work on this a bit, but it would also be good if someone else takes a look!
New commits:
8b74225  fixed the parent type problem for subwordcomplexfacet

471fb5d  Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

102bba1  finished the moving of the file, fixed all issues raised by Travis

comment:37 Changed 6 years ago by
 Commit changed from 102bba164ec83205209387f33de34894bb6a44e5 to 51d99ce28e0973828bb79c35afc1b0272cc02690
Branch pushed to git repo; I updated commit sha1. New commits:
a34e61c  Merge branch 'develop' into u/stumpc5/10819

81171d7  added doctest for classcall, removed __eq__ for subword complexes

190e8d2  Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code20111

e8ad2a9  Fixing doctest errors and some cython tweaks.

51d99ce  Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

comment:38 Changed 6 years ago by
A few methods here depend on the notyetavailable implementation of reflection groups. Is it appropriate to put them into comments for now?
New commits:
a34e61c  Merge branch 'develop' into u/stumpc5/10819

81171d7  added doctest for classcall, removed __eq__ for subword complexes

190e8d2  Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code20111

e8ad2a9  Fixing doctest errors and some cython tweaks.

51d99ce  Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

comment:39 Changed 6 years ago by
 Commit changed from 51d99ce28e0973828bb79c35afc1b0272cc02690 to 8878fdc1db44264cc8fb68abd1ea3ecbecced88b
Branch pushed to git repo; I updated commit sha1. New commits:
8878fdc  added a few tests and docs, commented 2 methods that depend on #11187

comment:40 Changed 6 years ago by
In a perfect world, I would just put it directly in a branch which depends on the branch which implements the reflection groups. However, I know that can be a hassle. So if it is just few lines, then I would say yes it is okay, but make sure to state clearly which ticket will change those lines. If they are entire methods, I'm more reluctant, but again, I'm not strictly opposed to it...
comment:41 Changed 6 years ago by
I already pushed that change, so have a look and tell me what you think concretely there...
comment:42 Changed 6 years ago by
It is the two methods
+ # the following methods only make sense for the implementation using #11187: + + #def upper_cluster(self): + #def product_of_upper_cluster(self):
I might actually implement them in a much slower way now, so I guess that might be the way to go... (and then commenting out the possible speed improvement with #11187)
comment:43 Changed 6 years ago by
 Commit changed from 8878fdc1db44264cc8fb68abd1ea3ecbecced88b to 9f6fe10c2c998385a5d21830deea3c62c99e24e4
Branch pushed to git repo; I updated commit sha1. New commits:
9f6fe10  added naive implementations of upper cluster and its product

comment:44 Changed 6 years ago by
Okay, I now use a naive implementation. But I am missing
AttributeError: 'CoxeterMatrixGroup_with_category' object has no attribute 'root_to_reflection'
Is there chance to get this method ? Otherwise, I will just delete that method needing this for now. I can then get it back later, if desired.
New commits:
9f6fe10  added naive implementations of upper cluster and its product

comment:45 Changed 6 years ago by
I think this is the best way to do things (at least because their implementation was simple).
Coxeter groups don't necessarily have all of the methods that Weyl groups have (since they are not tied to a particular root lattice). You should be able to use W.reflections()[beta]
from #20027, and it should work as well for Weyl groups now that the behavior is consistent.
comment:46 Changed 6 years ago by
However, that's not to say we should not implement a method root_to_reflection
for (finite) Coxeter groups.
comment:47 Changed 6 years ago by
 Commit changed from 9f6fe10c2c998385a5d21830deea3c62c99e24e4 to e1f49c3f4d4397906a45c937860c7e51435536e8
Branch pushed to git repo; I updated commit sha1. New commits:
e1f49c3  added product of upper cluster

comment:48 Changed 6 years ago by
 Dependencies changed from #20111 to #20111, #20027
New commits:
e1f49c3  added product of upper cluster

comment:49 Changed 6 years ago by
 Commit changed from e1f49c3f4d4397906a45c937860c7e51435536e8 to f1d1dff343c53b9ec2bc99ceb31575f9405cc5ed
Branch pushed to git repo; I updated commit sha1. New commits:
90b278a  Reversing the family for reflections.

8c9b809  Making CoxeterGroup.reflections return a Family and some touchups.

2595826  Removing caching of CoxeterGroup.positive_roots().

7ed4c2a  Merge 7.1.beta6.

3c32075  Fixing doctest failures in the thematic tutorials.

35eb71c  Fixing some documentation and adding note to WeylGroup.reflections.

46565ec  Missed (hopefully the last) one instance of the flipped keys/values.

a93c402  Merge branch 'u/stumpc5/20027' into u/stumpc5/10819

e72d0a3  removed product of upper cluster for now

f1d1dff  product is back again, though not clear why

comment:50 Changed 6 years ago by
(hey travis, are you in korea at the moment?)
comment:51 Changed 6 years ago by
 Status changed from needs_info to needs_review
comment:52 Changed 6 years ago by
 Commit changed from f1d1dff343c53b9ec2bc99ceb31575f9405cc5ed to 28ebb5b1df079ff0ee287c3db55403328a9e5f7e
Branch pushed to git repo; I updated commit sha1. New commits:
28ebb5b  Some reviewer changes.

comment:53 Changed 6 years ago by
 Commit changed from 28ebb5b1df079ff0ee287c3db55403328a9e5f7e to 3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e
Branch pushed to git repo; I updated commit sha1. New commits:
3c7d5ae  Missed a trailing whitespace.

comment:54 Changed 6 years ago by
 Reviewers set to Travis Scrimshaw
Indeed, greetings from Korea.
I pushed some changes:
 I moved the description of the cluster complex to the classlevel doc (instead of the modulelevel doc) so it can be visible from
ClusterComplex?
.  I updated the reference bibliographic info.
 I added more tests to
__classcall__
to make sure it covers all of the code paths/input formats.  I removed the verbose output from
TestSuite
as these can change as tests get added and it's annoying to make these trivial changes all over Sage (not that it happens that often).  Other misc tweaks.
If you agree with my changes, then you can set a positive review.
comment:55 Changed 6 years ago by
 Status changed from needs_review to positive_review
comment:56 Changed 6 years ago by
 Branch changed from public/ticket/10819 to 3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e
 Resolution set to fixed
 Status changed from positive_review to closed
some comments :
there is a typo in "facet" at the beginning.
The examples are wrong, because they call "associahedron" which has nothing to do with the simplicial complex.
There is a "tba" in the examples section, that should be removed or replaced by a true example
You should include serious tests, like the computation of the homology of an example.