Opened 6 years ago
Last modified 3 years ago
#19160 needs_work enhancement
Add a new class SnakeGraphs and SnakeGraph in combinat/cluster_algebra_quiver
Reported by:  egunawan  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  combinatorics  Keywords:  snake graph, cluster algebra, days69 
Cc:  tscrim, mlapointe, gmoose05  Merged in:  
Authors:  Emily Gunawan  Reviewers:  Travis Scrimshaw, Mélodie Lapointe 
Report Upstream:  N/A  Work issues:  
Branch:  u/egunawan/snake_graphs19160 (Commits, GitHub, GitLab)  Commit:  3728b1a85222d074f932ffd693ad77742fbd97ca 
Dependencies:  Stopgaps: 
Description (last modified by )
Note: This branch is currently added on top of Sage version 8.2 Master
Add a new class SnakeGraphs? and SnakeGraph?.
A snake graph is a connected sequence of square tiles which goes north and east. For example of where snake graphs come up in mathematics, see the following articles:
 :arxiv:
0906.0748
 :arxiv:
abs/1209.4617
Note:
 A SnakeGraph? class only has the attribute of shape (list of sizes of each row of the snake graph). For example, the edges do not have weights attached to them. For the purpose of doing computation with cluster algebra objects, we will create another class ClusterWeightedSnakeGraph?(SnakeGraph?) later.
 Our motivation for creating this snake graph class is to compute cluster variables for cluster algebras from surfaces (see http://trac.sagemath.org/ticket/16310). However, an abstract snake graph exists outside the context of cluster algebras from surfaces.
Change History (21)
comment:1 Changed 6 years ago by
 Description modified (diff)
comment:2 Changed 6 years ago by
 Branch set to u/egunawan/19160
 Commit set to dd7241b32660b018c8575e80d31e5fbf6d1cf922
comment:3 Changed 6 years ago by
 Cc tscrim added
 Reviewers set to tscrim, mlapointe
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
 Reviewers changed from tscrim, mlapointe to Travis Scrimshaw, mlapointe
 Status changed from needs_review to needs_work
Thank you for your work on this.
Some things that need to be addressed from a quick glance:
 Full doctest coverage (
shape
). print 'print an error message here TODO'
in_element_constructor_
needs to raise an actual error.The snake graphs
>Snake graphs
. You should include more information in the
SnakeGraphs
's class level docstring.  Remove the module variables
RIGHT
andUP
; just use the python strings (I've never noticed a speed decrease; <technobabble>in fact, python probably keeps string instances in a pool and/or has special compiler behavior for hardcoded strings</technobabble>).  You might consider using
ClonableArray
instead ofElement
since the former gives you listlike behavior for free (and by handling the internal storage in python, will be faster) and is a subclass ofElement
.  You should explain the association between your internal data structure and the behavior of the snake graph (i.e., what integer makes the graph go in which direction?). This can be in python comments, not necessarily in the docstrings.
Looks pretty, and I like the ascii art.
For the ticket on trac, you should use real names for author and reviewer.
comment:5 Changed 6 years ago by
 Reviewers changed from Travis Scrimshaw, mlapointe to Travis Scrimshaw, Mélodie Lapointe
comment:6 Changed 6 years ago by
Thank you Travis. I am trying to figure out why cluster_snakegraph.html does not get created. Do you know what I did wrong?
comment:7 Changed 6 years ago by
 Commit changed from dd7241b32660b018c8575e80d31e5fbf6d1cf922 to e66434ed786176b691c94a0fc3caeb9379ef0a55
comment:8 Changed 6 years ago by
 Commit changed from e66434ed786176b691c94a0fc3caeb9379ef0a55 to af06bd5dac91ee883a108ed2ab243c7a3e16139b
Branch pushed to git repo; I updated commit sha1. New commits:
c4497e1  19160:Remove the module variables RIGHT and UP. Raise error in _element_constructor_ if SnakeGraph of different size is input, or if sum(x) is not equal the number of tiles, or if x is not a SnakeGraph nor a list/tuple/set. Replace The snake graphs with Snake graphs

02c1e32  19160: Use ClonableArray (a subclass of Element) because it gives listlike behavior for free. Add __ne__ because otherwise != is wrong

af06bd5  19160: Add info in docstring for SnakeGraphs. Improve doc for SnakeGraph. Explain the association between your internal data structure and the behavior of the snake graph.

comment:9 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:10 Changed 6 years ago by
You need to add the reference to $SAGE_ROOT/src/doc/en/reference/combinat/module_list.rst
.
comment:11 Changed 6 years ago by
 Commit changed from af06bd5dac91ee883a108ed2ab243c7a3e16139b to a456b4e7d76936664f91c296035198ecc8bf2cfb
Branch pushed to git repo; I updated commit sha1. New commits:
a456b4e  19160:cluster_snakegraph.html now builds. Fix typos in doc.

comment:12 Changed 6 years ago by
 Commit changed from a456b4e7d76936664f91c296035198ecc8bf2cfb to a873a60c08edef6f9eab5a5a6cce60bd77751a3d
comment:13 Changed 6 years ago by
 Commit changed from a873a60c08edef6f9eab5a5a6cce60bd77751a3d to 3c7353c2a0a55f681ef2004749c4f32863eb5b37
Branch pushed to git repo; I updated commit sha1. New commits:
3c7353c  19160:fix bug in plot. Add LabeledSnakeGraph class.

comment:14 Changed 6 years ago by
 Status changed from needs_review to needs_work
doc does not build
OSError: [combinat ] /home/dima/sage/sage/local/lib/python2.7/sitepackages/sage/combinat/cluster_algebra_quiver/cluster_snakegraph.py:docstring of sage.combinat.cluster_algebra_quiver.cluster_snakegraph.LabeledSnakeGraph:28: WARNING: Bullet list ends without a blank line; unexpected unindent
comment:15 Changed 6 years ago by
 Commit changed from 3c7353c2a0a55f681ef2004749c4f32863eb5b37 to 52cb82faebf1d755d6fec8353ae7d57f8b973758
Branch pushed to git repo; I updated commit sha1. New commits:
52cb82f  19160: Doc builds with no error. Remove references that are not cited in the cluster_snakegraph.py file.

comment:16 Changed 6 years ago by
 Branch changed from u/egunawan/19160 to u/tscrim/snake_graphs19160
 Commit changed from 52cb82faebf1d755d6fec8353ae7d57f8b973758 to a44c44c3c944f35776d9ec4490200b135a946554
WIP for Emily.
New commits:
7afd4a7  Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs19160

84ec0a0  Making a new nonrecursive iterator for composition for speed.

825ecdf  Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs19160

69f3547  Some more changes; not quite ready.

a44c44c  Little parent classes all in a row.

comment:17 Changed 6 years ago by
comment:18 Changed 6 years ago by
Could you please add the missing documentation, so that the bot can turn green ?
comment:19 Changed 6 years ago by
 Branch u/tscrim/snake_graphs19160 deleted
 Commit a44c44c3c944f35776d9ec4490200b135a946554 deleted
comment:20 Changed 4 years ago by
 Cc saliola added
See u/egunawan/snake_graphs19160 (on top of Sage 7.5) for the most current work. I have questions about using Words
on Sage.
Currently the parent SnakeGraphs
takes one parameter (the number of boxes), but for what I'd like to do mathematically, it would make sense to let SnakeGraphs
be the set of all snake graphs (of any number of boxes).
Instead of enumerating them with compositions, we can also enumerate them by binary numbers, i.e. words on two alphabets 0 and 1 where the first alphabet must be 1 (except the the number 0). For example, the binary number 1 corresponds to the onebox; the word 10 corresponds to the shape (1,1) snake graph; the word 11 corresponds to the shape (2) snake graph; the word 100 corresponds to the shape (1,2) shape snake graph; the word 101 corresponds to the shape (1,1,1) snake graph; etc.
Words
are already implemented in Sage, so maybe I can use that and append the alphabet 1 to the beginning of every word (in order to get the correct words for my need). What do you think? I am ccing Franco in case he may be interested in giving his input on my question. Thank you for reading!
comment:21 Changed 3 years ago by
 Branch set to u/egunawan/snake_graphs19160
 Cc saliola removed
 Commit set to 3728b1a85222d074f932ffd693ad77742fbd97ca
 Description modified (diff)
Last 10 new commits:
84ec0a0  Making a new nonrecursive iterator for composition for speed.

5fb2ce4  19160: Fix a hyperlink reference. Add ascii art for a square tile in doc.

a873a60  19160:clean up doc.

3c7353c  19160:fix bug in plot. Add LabeledSnakeGraph class.

52cb82f  19160: Doc builds with no error. Remove references that are not cited in the cluster_snakegraph.py file.

825ecdf  Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs19160

69f3547  Some more changes; not quite ready.

a44c44c  Little parent classes all in a row.

03ee40e  19160: merge to 7.5

3728b1a  To Master version 8.2 Merge branch 'u/egunawan/snake_graphs19160' of git://trac.sagemath.org/sage into 19160

New commits:
only plain SnakeGraph class works. But we add matchings and weightedsnakegraph class also.
Remove files not related to plain snake graph class.
add a blank line