Snake graph perfect matching formula for cluster variables from surfaces

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 10 years ago

branch for this ticket: u/egunawan/16310snake (currently at Sage 8.9beta3)

Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a cluster triangulation class T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T that gamma crosses.

The algorithm used is the perfect matching formula from the following papers: "Positivity for cluster algebras from surfaces" http://arxiv.org/abs/0906.0748 (section 4). "Bases for cluster algebras from surfaces" http://arxiv.org/abs/1110.4364 (section 3).

Related snake graph class ticket: See https://github.com/sagemath/sage-prod/issues/19160

CC: @fchapoton @sagetrac-khlee @kelleye @tscrim @sagetrac-gmoose05

Component: combinatorics

Keywords: days64, days64.5, days65, cluster algebras, triangulations, sagedays@icerm

Author: Emily Gunawan, Elizabeth Kelley

Branch/Commit: u/egunawan/16310snake @ a2e8a8c

Reviewer: Gregg Musiker, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/16310

fchapoton commented 10 years ago

comment:1

Hello ! If this just a wish, or do you have code in preparation ?

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a triangulation T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses. 
+(Code in progress) Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a triangulation T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses. 

 The algorithm used is the perfect matching formula from the following papers:
 "Positivity for cluster algebras from surfaces" http://arxiv.org/abs/0906.0748 (section 4).

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 10 years ago

comment:3

Hi, the code is in preparation. -Emily

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Branch: u/egunawan/ticket/16310

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

comment:5

Warning: this version introduces a bug for http://www.sagemath.org/doc/reference/combinat/sage/combinat/cluster_algebra_quiver/cluster_seed.html class when user gives a list of edges as input. To be fixed in later versions.

fchapoton commented 9 years ago

comment:6

Hello,

I just had a quick look. Some remarks:

every line with EXAMPLES:: (or ending with ::) must be followed by an empty line
try no to use comments (with #) in the doc. You can just make sentences.
do not put space after the name of a function: def mything(myarg): and not def mything (myarg):

New commits:

`7d989e6`	`Starting from [Sage Version 6.4, Release Date: 2014-11-14], implement snake graph perfect matching formula to ~/combinat/cluster_algebra_quiver folder:`
`24599a8`	`Implement snake graph perfect matching formula to ~/combinat/cluster_algebra_quiver folder`

fchapoton commented 9 years ago

Commit: 24599a8

fchapoton commented 9 years ago

comment:7

And citations of references such as MSW1 should be written [MSW1]_

fchapoton commented 9 years ago

comment:8

you should not use if something == True and if something != True

but rather just if something and if not something

fchapoton commented 9 years ago

comment:9

Same thing for None. One should use if something is None or if not(something is None) rather than == None and != None

Also please avoid using ; : rather separate the commands on several lines

And last but not least, every single function must be doctested:

sage -coverage src/sage/combinat/cluster_algebra_quiver/surface.py
------------------------------------------------------------------------
SCORE src/sage/combinat/cluster_algebra_quiver/surface.py: 6.7% (3 of 45)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 24599a8 to e835d5e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

e835d5e surface.py: Remove space after functions. Add a blank line after EXAMPLES:: and create doctests for first half of functions.

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

comment:11

(Note: This commit only contains A FEW of the changes requested above)

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

`48e1e40`	`remove the following functions which are no longer used: _edges_from_ideal_triangles`
`214324e`	`Allow draw_lifted_polygon_arc() and draw_lifted_polygon_loop() methods to take user-given labels. Clean up documentation.`
`9a093c1`	`Move the methods arc, loop, snake_graph, band_graph, draw_snake_graph, draw_band_graph, draw_lifted_polygon_arc, draw_lifted_polygon_loop from cluster_seed.py to cluster_triangulation.py, and do the fix that Chapoton asks in regards to None and True/False, and add a few more doc tests in surface.py`
`e88182c`	`Up to function _get_weighted_edges() line 503 in surface.py, finish doctests/examples`
`a8f169b`	`Finish doc and unit tests for functions in surface.py up to line 720 (LaurentExpansionFromSurface())`
`702d0d9`	`Set user_labels=True default option for cluster_triangulation.py, and create a new function GetAllMatchings() to shorten the function LaurentExpansionFromSurface() in surface.py`
`63a1e7f`	`Continue finishing doc and examples in surface.py`
`cf13a06`	`Replace methods .arc with .arc_laurent_expansion, .draw_lifted_polygon_arc with .draw_lifted_arc, .snake_graph with .list_snake_graph (and also their equivalent methods for loops) in cluster_triangulation.py. Replace function _draw_lifted_polygon with _draw_lifted_curve in surface.py. Continue adding to doctest and examples`
`07866a5`	`Fix bug regarding to running ClusterSeed.arc_laurent_expansion with parameter Verbose=False. Finish all examples in surface.py, but sage -docbuild reference/combinat html is currently producing errors`
`0f5e39a`	`Fix documentation`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from e835d5e to 0f5e39a

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-(Code in progress) Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a triangulation T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses. 
+Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a cluster triangulation class T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses. 

 The algorithm used is the perfect matching formula from the following papers:
 "Positivity for cluster algebras from surfaces" http://arxiv.org/abs/0906.0748 (section 4).

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

comment:13

When I run "./sage -docbuild reference/combinat html" I get errors and I have not been able to figure out how to fix them.

When pushing to trac, I did "git push --set-upstream trac HEAD:u/egunawan/ticket/16310". Was this the correct command?

fchapoton commented 9 years ago

comment:14

Ok, I am currently cleaning the doc so that it will build.

The main point is that you did something like that (many times)

EXAMPLES::

    Here is my favorite example::

        sage: 1 + 1 == 3

where it should be instead

EXAMPLES:

Here is my favorite example::

    sage: 1 + 1 == 3

One other important point is that reference should be only given once in all the sage library. You should not duplicate the same reference in distinct files. Sage is able to find them in any place, so you can use citations from references in any other file.

fchapoton commented 9 years ago

Changed commit from 0f5e39a to 0d2b938

fchapoton commented 9 years ago

comment:15

Hello,

I have made a branch public/ticket/16310 based on u/egunawan/ticket/16310 on top of sage 6.5.rc3

If you were working with sage 6.4.1, you should before go to 6.5.rc3 or later. You can then pull this branch using git pull public/ticket/16310

Doc now builds. I have tried not to touch the code, but could not completely stop myself to do that. I should not have broken anything, but please check that it still works.

New commits:

`5b9778e`	`Merge branch 'u/egunawan/ticket/16310' into 6.5.rc3`
`0d2b938`	`trac #16310 lot of documentation clean-up + inclusion of doc`

fchapoton commented 9 years ago

Changed branch from u/egunawan/ticket/16310 to public/ticket/16310

fchapoton commented 9 years ago

comment:16

There are two failing doctests:

File "src/sage/combinat/cluster_algebra_quiver/surface.py", line 1041, in sage.combinat.cluster_algebra_quiver.surface.GetMonomialTerm
Failed example:
    GetMonomialTerm(G,pm_a,boundary_edges=T._boundary_edges_vars)
Expected:
    x3^2*x4^2*x8^3
Got:
    x1^2*x2^2*x6^3
**********************************************************************
File "src/sage/combinat/cluster_algebra_quiver/surface.py", line 1052, in sage.combinat.cluster_algebra_quiver.surface.GetMonomialTerm
Failed example:
    GetMonomialTerm(G,pm_b,boundary_edges=T._boundary_edges_vars)
Expected:
    x3^2*x4*x5*x6*x7*x8*x9
Got:
    x1^2*x2*x3*x4*x5*x6*x7

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

comment:17

Thank you for fixing my code!

Question 1: The two failing doctests above happen in Version 6.5.rc2 but all tests (in cluster_algebra_quiver folder) pass in Version 6.5.rc3.

list.sort() method behaves differently in Version 6.5.rc2 and Version 6.5.rc3. Should I change my doctests so that my doctests do not depend on the behavior of list.sort()?

Sage Version 6.5.rc3 and Version 6.4: sage: li = [1,2,3,'r','ell'] sage: li.sort() sage: li ['ell', 'r', 1, 2, 3]

=============

Sage Version 6.5.rc2: sage: li = [1,2,3,'r','ell'] sage: li.sort() sage: li [1, 2, 3, 'ell', 'r']

Question 2: In the future, when I need to push new commits to the public branch "public/ticket/16310", do I type "git push --set-upstream trac HEAD:public/ticket/16310" or do I need to do something different?

In several months, we would like to enhance this code so that user can work with a surface cluster algebra with principal coefficients. Do we create a new ticket and branch or continue with this ticket?

fchapoton commented 9 years ago

comment:18

Replying to @egunawan:

Thank you for fixing my code!

My pleasure.

Question 1: The two failing doctests above happen in Version 6.5.rc2 but all tests (in cluster_algebra_quiver folder) pass in Version 6.5.rc3.

list.sort() method behaves differently in Version 6.5.rc2 and Version 6.5.rc3. Should I change my doctests so that my doctests do not depend on the behavior of list.sort()?

Sage Version 6.5.rc3 and Version 6.4: sage: li = [1,2,3,'r','ell'] sage: li.sort() sage: li ['ell', 'r', 1, 2, 3]

=============

Sage Version 6.5.rc2: sage: li = [1,2,3,'r','ell'] sage: li.sort() sage: li [1, 2, 3, 'ell', 'r']

Well, all tests must pass in the most recent version.

It seems very strange to use lists that mix integers and letters. Is this really what you use in the code ? Could you try to avoid that ?

Question 2: In the future, when I need to push new commits to the public branch "public/ticket/16310", do I type "git push --set-upstream trac HEAD:public/ticket/16310" or do I need to do something different?

The set-upstream is a convenience, not a necessity. You can just use

"git push trac HEAD:public/ticket/16310"

But in fact, it is not necessary that you work with the public/ticket/16310 branch

Instead I think that you can do that:

1) git checkout "your local name for the branch u/egunawan/ticket/16310" So you are "sitting on your branch" 2) git pull trac public/ticket/16310 So you have included "public/ticket/16310" in your branch 3) then you can just use "git push trac HEAD:u/egunawan/ticket/16310" as before to push into trac under that name 4) you can put back "u/egunawan/ticket/16310" in the branch field of trac

But I am not a git wizard, so be careful..

I suggest you click on the "commits" links at right of the Branch field (above here) to see what happens to the various branches : they coexist. Currently yours is behind public, but it can very well go back to leading position, if you do what I suggest.

In several months, we would like to enhance this code so that user can work with a surface cluster algebra with principal coefficients. Do we create a new ticket and branch or continue with this ticket?

Well, it depends on your priorities. In my opinion, there is still some work to be done here before this can enter SageMath. Adding another layer of complexity can only make things take longer. So I would suggest to make another ticket, depending on this one.

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed branch from public/ticket/16310 to u/egunawan/ticket/16310

fchapoton commented 9 years ago

comment:21

There seem to be still a duplicate citation:

OSError: [combinat ] /home/patchbot/sage-patchbot/local/lib/python2.7/site-packages/sage/combinat/cluster_algebra_quiver/cluster_triangulation.py:
docstring of sage.combinat.cluster_algebra_quiver.cluster_triangulation:15:
WARNING: duplicate citation MSW_Positivity,
other instance in /home/patchbot/sage-patchbot/src/doc/en/reference/combinat/sage/combinat/cluster_algebra_quiver/cluster_seed.rst

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed branch from u/egunawan/ticket/16310 to public/ticket/16310

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed commit from 0d2b938 to 97cde19

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`87a3669`	`Merge branch 'public/ticket/16310' into 6.6.beta3`
`770c98e`	`trac #16310 make sure that doc builds`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 97cde19 to 770c98e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

75b482e trac #16310 trying again to make sure that doc builds

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 770c98e to 75b482e

6bfcfeed-779b-4b16-82e6-63808dde0af0 commented 9 years ago

comment:25

Uh... That ticket was set to needs_review four weeks ago, but there have been changes eight days ago to fix doc building... so is it ready or not ?

Also notice that Volker doesn't like needs_review tickets without "Authors:" :-P

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Author: egunawan

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

comment:27

Thanks for the comment. I changed the status to needs_work because we will do a mathematical review first before it's ready for review.

Whenever there is a new beta in the develop branch (for example, currently 6.6 beta 5) should I merge this ticket branch into the latest beta, and how? If someone pulls this ticket branch on top of the latest sage (6.6 beta 5), will it work OK?

6bfcfeed-779b-4b16-82e6-63808dde0af0 commented 9 years ago

comment:28

You should probably rebase before you ask for a review ; it's explained in the sage developer's guide.

That will show you if your code conflicts with what is now in sage, and allow you to fix the discrepancies.

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed keywords from cluster algebras from surfaces to days64, cluster algebras, triangulations

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

1f1c3db Merge branch 'develop' into t/16310/public/ticket/16310

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 75b482e to 1f1c3db

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed commit from 1f1c3db to none

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Changed branch from public/ticket/16310 to none

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,6 @@
+Most recent stable version is available at branch: u/egunawan/snakegraph
+(Sage 6.6.beta5)
+
 Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a cluster triangulation class T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses. 

 The algorithm used is the perfect matching formula from the following papers:

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Branch: u/egunawan/snakegraph

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Commit: 048b942

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Last 10 new commits:

`5b1ee64`	`Musiker comment 1: Explain the difference between __edge_list_to_matrix and _surface_edge_list_to_matrix.`
`8b60a04`	`Musiker comment 3: triangulation_dictionary is now a dictionary instead of a list.`
`c1c1957`	`Gregg Musiker comment #5 and #8: ClusterTriangulation = class(ClusterSeed) instead of class(SageObject). Also allow ClusterTriangulation.mutate method to mutate a self-folded triangle's radius r. This mutation method is not quite an involution because it you mutate r twice you will end up with the same (unlabeled) triangulation but the label of r and the loop are switched.`
`ba018c1`	`Fix bug in ClusterTriangulation.mutate method and bug in ClusterTriangulation.get_edge_position method by introducing self._edges and self._arcs and self._boundary_edges (previously two lists to handle all the edges)`
`d33626f`	`Introduce new function _is_arc_mutable to check for more illegal triangulatons. For example, a noose (ell-loop) has to be mutable, i.e. inside an ideal quadrilateral.`
`c380e75`	`ticket 16310: Fix bug in ClusterTriangulation.mutate. Add more examples for that method.`
`fd2c1df`	`Tiket 16310:`
`329c484`	`Ticket 16310:`
`0871a57`	`Ticket 16310: description 'A cluster algebra' -> 'A seed for a cluster algebra'`
`048b942`	`Ticket 16310: Change the names of the four methods in ClusterTriangulation to map_label_to_variable, _get_map_label_to_variable, map_variable_to_label, and _get_map_variable_to_label. Fix incorrect error messages. Add more tests for cases when ClusterTriangulation has been mutated`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 048b942 to f9dbe0e

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

f9dbe0e Ticket 16310:

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

e6d196d Merge branch 'u/egunawan/snakegraph' of trac.sagemath.org:sage into Master version 6.7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from f9dbe0e to e6d196d

cc6b51a1-a453-4261-a2f3-40d311f6708f commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
-Most recent stable version is available at branch: u/egunawan/snakegraph
-(Sage 6.6.beta5)
+my branch for this ticket: u/egunawan/snakegraph
+(fetch or pull this branch from Sage 6.7 master branch)

 Enhancement to the cluster_algebra_quiver package: User can define a cluster algebra seed by entering a cluster triangulation class T of a surface. User can then compute the T-expansion of an arc or loop gamma by entering the arcs of T  that gamma crosses.

sagemath / sage

Snake graph perfect matching formula for cluster variables from surfaces #16310