Opened 6 years ago

Closed 16 months ago

#10819 closed enhancement (fixed)

implementation of the cluster complex

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-7.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) Commit: 3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e
Dependencies: #20111, #20027 Stopgaps:

Description (last modified by stumpc5)

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)

trac_10819-cluster_complex-cs.patch (12.1 KB) - added by stumpc5 4 years ago.

Download all attachments as: .zip

Change History (57)

comment:1 Changed 6 years ago by chapoton

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.

comment:2 Changed 6 years ago by stumpc5

  • Dependencies set to 10538,
  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 6 years ago by chapoton

  • Owner changed from sage-combinat to (none)

Apply trac_10819-cluster_complex-cs.patch

comment:4 Changed 6 years ago by chapoton

  • Dependencies changed from 10538, to #10538

comment:5 follow-up: Changed 6 years ago by chapoton

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 6 years ago by stumpc5

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 6 years ago by stumpc5

  • Milestone set to sage-4.7.2

comment:8 follow-up: Changed 6 years ago by chapoton

  • 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 6 years ago by stumpc5

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 6 years ago by stumpc5

  • 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 multi-cluster complex can be constructed.

comment:11 follow-up: Changed 5 years ago by davidloeffler

  • 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 5 years ago by stumpc5

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 4 years ago by stumpc5

comment:13 Changed 4 years ago by stumpc5

  • Dependencies changed from #10538 to #11010

comment:14 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:15 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:16 Changed 3 years ago by chapoton

  • 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
7a2d814trac #10189 code clean-up (pyflakes, pep8, doc)

comment:17 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:18 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:19 Changed 2 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.8

comment:20 Changed 20 months ago by chapoton

  • Branch changed from public/ticket/10189 to public/ticket/10819
  • Commit changed from 7a2d814c6457d49fd67b22b84396215d30321a98 to 4f997a995423047e70c6ccf262726183e563be0c
  • Milestone changed from sage-6.8 to sage-6.10
  • Work issues set to lacking doc

New commits:

fbd3246Merge branch 'public/ticket/10189' into 6.10.beta2
4f997a9trac #10819 minor doc and code details

comment:21 Changed 17 months ago by git

  • Commit changed from 4f997a995423047e70c6ccf262726183e563be0c to 615b67fbcad7fc66484fd9d14fce4ae7564993a2

Branch pushed to git repo; I updated commit sha1. New commits:

3762d3eMerge branch 'public/ticket/10819' into 7.1.b0
615b67ftrac #10819 make it work by small changes

comment:22 Changed 17 months ago by chapoton

  • Milestone changed from sage-6.10 to sage-7.1
  • Status changed from needs_work to needs_review
  • Work issues lacking doc deleted

comment:23 Changed 17 months ago by chapoton

  • Dependencies #11010 deleted

comment:24 Changed 16 months ago by chapoton

  • Cc tscrim stumpc5 added

This should be almost ready. Anybody available to have a look ?

comment:25 Changed 16 months ago by stumpc5

Will do that.

comment:26 Changed 16 months ago by tscrim

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 16 months ago by chapoton

second thing: "it just needs someone else to look it over"

comment:28 Changed 16 months ago by tscrim

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#headings-of-sage-library-code-files 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 the Element attribute of ClusterComplex, and subsequently, you should use self.element_class in ClusterComplex.
  • The methods of ClusterComplexFacet should at least have a one-line 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 16 months ago by git

  • Commit changed from 615b67fbcad7fc66484fd9d14fce4ae7564993a2 to b8b9e820573be4b0e217af7dfa0c54bedc13a4d5

Branch pushed to git repo; I updated commit sha1. New commits:

ab38a11Merge branch 'public/ticket/10819' of git://trac.sagemath.org/sage into u/stumpc5/10819
b8b9e82working on cleaning. Almost done with first round

comment:30 Changed 16 months ago by git

  • Commit changed from b8b9e820573be4b0e217af7dfa0c54bedc13a4d5 to 279a3da0fd5b6c24fd410fd5d6111dc246f31aa5

Branch pushed to git repo; I updated commit sha1. New commits:

279a3daremoved one line in cluster seed that doesn't have anything to do with this ticket

comment:31 Changed 16 months ago by git

  • Commit changed from 279a3da0fd5b6c24fd410fd5d6111dc246f31aa5 to 6d984c83175130d18313be1d14549f59b5e5a7de

Branch pushed to git repo; I updated commit sha1. New commits:

6d984c8moved the file into the main combinat folder since the implementation does not have anything to do with cluster algebras anymore

comment:32 Changed 16 months ago by stumpc5

  • Dependencies set to #20111

comment:33 Changed 16 months ago by git

  • Commit changed from 6d984c83175130d18313be1d14549f59b5e5a7de to c8e990cf5a951d7f13fb5af894aa0076b36de308

Branch pushed to git repo; I updated commit sha1. New commits:

924a4d9cleaning of the subword complex code
c8e990cMerge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

comment:34 Changed 16 months ago by stumpc5

  • 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 16 months ago by git

  • Commit changed from c8e990cf5a951d7f13fb5af894aa0076b36de308 to 102bba164ec83205209387f33de34894bb6a44e5

Branch pushed to git repo; I updated commit sha1. New commits:

8b74225fixed the parent type problem for subwordcomplexfacet
471fb5dMerge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819
102bba1finished the moving of the file, fixed all issues raised by Travis

comment:36 Changed 16 months ago by stumpc5

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:

8b74225fixed the parent type problem for subwordcomplexfacet
471fb5dMerge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819
102bba1finished the moving of the file, fixed all issues raised by Travis

comment:37 Changed 16 months ago by git

  • Commit changed from 102bba164ec83205209387f33de34894bb6a44e5 to 51d99ce28e0973828bb79c35afc1b0272cc02690

Branch pushed to git repo; I updated commit sha1. New commits:

a34e61cMerge branch 'develop' into u/stumpc5/10819
81171d7added doctest for classcall, removed __eq__ for subword complexes
190e8d2Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code-20111
e8ad2a9Fixing doctest errors and some cython tweaks.
51d99ceMerge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

comment:38 Changed 16 months ago by stumpc5

A few methods here depend on the not-yet-available implementation of reflection groups. Is it appropriate to put them into comments for now?


New commits:

a34e61cMerge branch 'develop' into u/stumpc5/10819
81171d7added doctest for classcall, removed __eq__ for subword complexes
190e8d2Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code-20111
e8ad2a9Fixing doctest errors and some cython tweaks.
51d99ceMerge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

comment:39 Changed 16 months ago by git

  • Commit changed from 51d99ce28e0973828bb79c35afc1b0272cc02690 to 8878fdc1db44264cc8fb68abd1ea3ecbecced88b

Branch pushed to git repo; I updated commit sha1. New commits:

8878fdcadded a few tests and docs, commented 2 methods that depend on #11187

comment:40 Changed 16 months ago by tscrim

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 16 months ago by stumpc5

I already pushed that change, so have a look and tell me what you think concretely there...

comment:42 Changed 16 months ago by stumpc5

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 16 months ago by git

  • Commit changed from 8878fdc1db44264cc8fb68abd1ea3ecbecced88b to 9f6fe10c2c998385a5d21830deea3c62c99e24e4

Branch pushed to git repo; I updated commit sha1. New commits:

9f6fe10added naive implementations of upper cluster and its product

comment:44 Changed 16 months ago by stumpc5

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:

9f6fe10added naive implementations of upper cluster and its product

comment:45 Changed 16 months ago by tscrim

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 16 months ago by tscrim

However, that's not to say we should not implement a method root_to_reflection for (finite) Coxeter groups.

comment:47 Changed 16 months ago by git

  • Commit changed from 9f6fe10c2c998385a5d21830deea3c62c99e24e4 to e1f49c3f4d4397906a45c937860c7e51435536e8

Branch pushed to git repo; I updated commit sha1. New commits:

e1f49c3added product of upper cluster

comment:48 Changed 16 months ago by stumpc5

  • Dependencies changed from #20111 to #20111, #20027

New commits:

e1f49c3added product of upper cluster

comment:49 Changed 16 months ago by git

  • Commit changed from e1f49c3f4d4397906a45c937860c7e51435536e8 to f1d1dff343c53b9ec2bc99ceb31575f9405cc5ed

Branch pushed to git repo; I updated commit sha1. New commits:

90b278aReversing the family for reflections.
8c9b809Making CoxeterGroup.reflections return a Family and some touchups.
2595826Removing caching of CoxeterGroup.positive_roots().
7ed4c2aMerge 7.1.beta6.
3c32075Fixing doctest failures in the thematic tutorials.
35eb71cFixing some documentation and adding note to WeylGroup.reflections.
46565ecMissed (hopefully the last) one instance of the flipped keys/values.
a93c402Merge branch 'u/stumpc5/20027' into u/stumpc5/10819
e72d0a3removed product of upper cluster for now
f1d1dffproduct is back again, though not clear why

comment:50 Changed 16 months ago by stumpc5

(hey travis, are you in korea at the moment?)

comment:51 Changed 16 months ago by stumpc5

  • Status changed from needs_info to needs_review

comment:52 Changed 16 months ago by git

  • Commit changed from f1d1dff343c53b9ec2bc99ceb31575f9405cc5ed to 28ebb5b1df079ff0ee287c3db55403328a9e5f7e

Branch pushed to git repo; I updated commit sha1. New commits:

28ebb5bSome reviewer changes.

comment:53 Changed 16 months ago by git

  • Commit changed from 28ebb5b1df079ff0ee287c3db55403328a9e5f7e to 3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e

Branch pushed to git repo; I updated commit sha1. New commits:

3c7d5aeMissed a trailing whitespace.

comment:54 Changed 16 months ago by tscrim

  • Authors changed from Christian Stump to Christian Stump, Frédéric Chapoton
  • Reviewers set to Travis Scrimshaw

Indeed, greetings from Korea.

I pushed some changes:

  • I moved the description of the cluster complex to the class-level doc (instead of the module-level 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 16 months ago by stumpc5

  • Status changed from needs_review to positive_review

comment:56 Changed 16 months ago by vbraun

  • Branch changed from public/ticket/10819 to 3c7d5ae34b0baf70f5486ebe15dbf77f477f0e2e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.