Add a new class SnakeGraphs and SnakeGraph in combinat/cluster_algebra_quiver

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

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 https://github.com/sagemath/sage-prod/issues/16310). However, an abstract snake graph exists outside the context of cluster algebras from surfaces.

CC: @tscrim @sagetrac-mlapointe @sagetrac-gmoose05

Component: combinatorics

Keywords: snake graph, cluster algebra, days69

Author: Emily Gunawan

Branch/Commit: u/egunawan/snake_graphs-19160 @ 3728b1a

Reviewer: Travis Scrimshaw, Mélodie Lapointe

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

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+Note: This branch is currently added on top of Sage version to 6.8
+
 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:

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Branch: u/egunawan/19160

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

New commits:

1731bcc	only plain SnakeGraph class works. But we add matchings and weightedsnakegraph class also.
d536815	Remove files not related to plain snake graph class.
dd7241b	add a blank line

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Commit: dd7241b

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Reviewer: tscrim, mlapointe

[tscrim]

comment:4

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 and UP; just use the python strings (I've never noticed a speed decrease; in fact, python probably keeps string instances in a pool and/or has special compiler behavior for hardcoded strings).
• You might consider using ClonableArray instead of Element since the former gives you list-like behavior for free (and by handling the internal storage in python, will be faster) and is a subclass of Element.
• 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.

[tscrim]

Changed reviewer from tscrim, mlapointe to Travis Scrimshaw, mlapointe

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Changed reviewer from Travis Scrimshaw, mlapointe to Travis Scrimshaw, Mélodie Lapointe

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

comment:6

Thank you Travis. I am trying to figure out why cluster_snakegraph.html does not get created. Do you know what I did wrong?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

ca0681e	19160:add doc test for def shape()
e66434e	19160: add cluster_snakegraph to __init__.py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dd7241b to e66434e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e66434e to af06bd5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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 list-like 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.

[tscrim]

comment:10

You need to add the reference to $SAGE_ROOT/src/doc/en/reference/combinat/module_list.rst.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from af06bd5 to a456b4e

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a456b4e

19160:cluster_snakegraph.html now builds. Fix typos in doc.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a456b4e to a873a60

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3c7353c

19160:fix bug in plot. Add LabeledSnakeGraph class.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a873a60 to 3c7353c

[fchapoton]

comment:14

doc does not build

OSError: [combinat ] /home/dima/sage/sage/local/lib/python2.7/site-packages/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

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c7353c to 52cb82f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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.

[tscrim]

Changed commit from 52cb82f to a44c44c

[tscrim]

Changed branch from u/egunawan/19160 to u/tscrim/snake_graphs-19160

[tscrim]

comment:16

WIP for Emily.

---

New commits:

7afd4a7	Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs-19160
84ec0a0	Making a new non-recursive iterator for composition for speed.
825ecdf	Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs-19160
69f3547	Some more changes; not quite ready.
a44c44c	Little parent classes all in a row.

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Changed author from egunawan to Emily Gunawan

[fchapoton]

comment:18

Could you please add the missing documentation, so that the bot can turn green ?

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Changed commit from a44c44c to none

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Changed branch from u/tscrim/snake_graphs-19160 to none

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

comment:20

See u/egunawan/snake_graphs-19160 (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 one-box; 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 cc-ing Franco in case he may be interested in giving his input on my question. Thank you for reading!

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Last 10 new commits:

84ec0a0	Making a new non-recursive 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_graphs-19160
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_graphs-19160' of git://trac.sagemath.org/sage into 19160

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Branch: u/egunawan/snake_graphs-19160

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-Note: This branch is currently added on top of Sage version to 6.8
+Note: This branch is currently added on top of Sage version 8.2 Master

 Add a new class SnakeGraphs and SnakeGraph. 

[cc6b51a1-a453-4261-a2f3-40d311f6708f]

Commit: 3728b1a