Add a new class SnakeGraphs and SnakeGraph in combinat/cluster_algebra_quiver #19160

egunawan · 2015-09-07T21:15:16Z

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 Snake graph perfect matching formula for cluster variables from surfaces #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

The text was updated successfully, but these errors were encountered:

egunawan · 2015-09-07T21:21:14Z

Branch: u/egunawan/19160

egunawan · 2015-09-07T21:21:14Z

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`

egunawan · 2015-09-07T21:21:14Z

Commit: dd7241b

egunawan · 2015-09-07T21:54:29Z

Reviewer: tscrim, mlapointe

tscrim · 2015-09-07T22:18:15Z

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 · 2015-09-07T22:18:15Z

Changed reviewer from tscrim, mlapointe to Travis Scrimshaw, mlapointe

egunawan · 2015-09-07T23:10:04Z

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

egunawan · 2015-09-07T23:11:48Z

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?

sagetrac-git · 2015-09-07T23:15:44Z

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`

sagetrac-git · 2015-09-07T23:15:44Z

Changed commit from dd7241b to e66434e

sagetrac-git · 2015-09-08T02:36:55Z

Changed commit from e66434e to af06bd5

sagetrac-git · 2015-09-08T02:36:55Z

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 · 2015-09-08T13:42:22Z

comment:10

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

sagetrac-git · 2015-09-08T17:51:35Z

Changed commit from af06bd5 to a456b4e

sagetrac-git · 2015-09-08T17:51:35Z

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

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

sagetrac-git · 2015-09-09T19:25:48Z

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.`

sagetrac-git · 2015-09-09T19:25:48Z

Changed commit from a456b4e to a873a60

sagetrac-git · 2015-09-10T09:23:44Z

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

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

sagetrac-git · 2015-09-10T09:23:44Z

Changed commit from a873a60 to 3c7353c

fchapoton · 2015-09-10T17:53:51Z

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

sagetrac-git · 2015-09-11T02:56:56Z

Changed commit from 3c7353c to 52cb82f

sagetrac-git · 2015-09-11T02:56:56Z

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 · 2015-09-11T20:02:56Z

Changed commit from 52cb82f to a44c44c

tscrim · 2015-09-11T20:02:56Z

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

tscrim · 2015-09-11T20:02:56Z

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.`

egunawan · 2015-09-13T09:00:06Z

Changed author from egunawan to Emily Gunawan

fchapoton · 2015-11-09T16:30:06Z

comment:18

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

egunawan · 2015-11-10T09:12:34Z

Changed commit from a44c44c to none

egunawan · 2015-11-10T09:12:34Z

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

egunawan · 2017-01-14T00:15:52Z

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!

egunawan · 2018-07-23T15:12:33Z

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`

egunawan · 2018-07-23T15:12:33Z

Branch: u/egunawan/snake_graphs-19160

egunawan · 2018-07-23T15:12:33Z

Commit: 3728b1a

egunawan mannequin added this to the sage-6.9 milestone Sep 7, 2015

egunawan mannequin added c: combinatorics labels Sep 7, 2015

This comment has been minimized.

Sign in to view

egunawan mannequin added the s: needs review label Sep 7, 2015

tscrim added s: needs work and removed s: needs review labels Sep 7, 2015

egunawan mannequin added s: needs review and removed s: needs work labels Sep 8, 2015

fchapoton added s: needs work and removed s: needs review labels Sep 10, 2015

This comment has been minimized.

Sign in to view

mkoeppe removed this from the sage-6.9 milestone Dec 29, 2022

egunawan mannequin mentioned this issue Jan 29, 2023

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

Open

Add a new class SnakeGraphs and SnakeGraph in combinat/cluster_algebra_quiver #19160

Add a new class SnakeGraphs and SnakeGraph in combinat/cluster_algebra_quiver #19160

Comments

egunawan mannequin commented Sep 7, 2015

This comment has been minimized.

egunawan mannequin commented Sep 7, 2015

egunawan mannequin commented Sep 7, 2015

egunawan mannequin commented Sep 7, 2015

egunawan mannequin commented Sep 7, 2015

tscrim commented Sep 7, 2015

tscrim commented Sep 7, 2015

egunawan mannequin commented Sep 7, 2015

egunawan mannequin commented Sep 7, 2015

sagetrac-git mannequin commented Sep 7, 2015

sagetrac-git mannequin commented Sep 7, 2015

sagetrac-git mannequin commented Sep 8, 2015

sagetrac-git mannequin commented Sep 8, 2015

tscrim commented Sep 8, 2015

sagetrac-git mannequin commented Sep 8, 2015

sagetrac-git mannequin commented Sep 8, 2015

sagetrac-git mannequin commented Sep 9, 2015

sagetrac-git mannequin commented Sep 9, 2015

sagetrac-git mannequin commented Sep 10, 2015

sagetrac-git mannequin commented Sep 10, 2015

fchapoton commented Sep 10, 2015

sagetrac-git mannequin commented Sep 11, 2015

sagetrac-git mannequin commented Sep 11, 2015

tscrim commented Sep 11, 2015

tscrim commented Sep 11, 2015

tscrim commented Sep 11, 2015

egunawan mannequin commented Sep 13, 2015

fchapoton commented Nov 9, 2015

egunawan mannequin commented Nov 10, 2015

egunawan mannequin commented Nov 10, 2015

egunawan mannequin commented Jan 14, 2017

egunawan mannequin commented Jul 23, 2018

egunawan mannequin commented Jul 23, 2018

This comment has been minimized.

egunawan mannequin commented Jul 23, 2018