Opened 4 years ago

Last modified 9 months 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: sage-6.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_graphs-19160 (Commits) Commit: 3728b1a85222d074f932ffd693ad77742fbd97ca
Dependencies: Stopgaps:

Description (last modified by egunawan)

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

  • Description modified (diff)

comment:2 Changed 4 years ago by egunawan

  • Branch set to u/egunawan/19160
  • Commit set to dd7241b32660b018c8575e80d31e5fbf6d1cf922

New commits:

1731bcconly plain SnakeGraph class works. But we add matchings and weightedsnakegraph class also.
d536815Remove files not related to plain snake graph class.
dd7241badd a blank line

comment:3 Changed 4 years ago by egunawan

  • Cc tscrim added
  • Reviewers set to tscrim, mlapointe
  • Status changed from new to needs_review

comment:4 Changed 4 years ago by tscrim

  • 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 and UP; 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 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.

comment:5 Changed 4 years ago by egunawan

  • Reviewers changed from Travis Scrimshaw, mlapointe to Travis Scrimshaw, Mélodie Lapointe

comment:6 Changed 4 years ago by egunawan

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

  • Commit changed from dd7241b32660b018c8575e80d31e5fbf6d1cf922 to e66434ed786176b691c94a0fc3caeb9379ef0a55

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

ca0681e19160:add doc test for def shape()
e66434e19160: add cluster_snakegraph to __init__.py

comment:8 Changed 4 years ago by git

  • Commit changed from e66434ed786176b691c94a0fc3caeb9379ef0a55 to af06bd5dac91ee883a108ed2ab243c7a3e16139b

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

c4497e119160: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
02c1e3219160: Use ClonableArray (a subclass of Element) because it gives list-like behavior for free. Add __ne__ because otherwise != is wrong
af06bd519160: 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 4 years ago by egunawan

  • Status changed from needs_work to needs_review

comment:10 Changed 4 years ago by tscrim

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

comment:11 Changed 4 years ago by git

  • Commit changed from af06bd5dac91ee883a108ed2ab243c7a3e16139b to a456b4e7d76936664f91c296035198ecc8bf2cfb

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

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

comment:12 Changed 4 years ago by git

  • Commit changed from a456b4e7d76936664f91c296035198ecc8bf2cfb to a873a60c08edef6f9eab5a5a6cce60bd77751a3d

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

5fb2ce419160: Fix a hyperlink reference. Add ascii art for a square tile in doc.
a873a6019160:clean up doc.

comment:13 Changed 4 years ago by git

  • Commit changed from a873a60c08edef6f9eab5a5a6cce60bd77751a3d to 3c7353c2a0a55f681ef2004749c4f32863eb5b37

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

3c7353c19160:fix bug in plot. Add LabeledSnakeGraph class.

comment:14 Changed 4 years ago by chapoton

  • Status changed from needs_review to needs_work

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

comment:15 Changed 4 years ago by git

  • Commit changed from 3c7353c2a0a55f681ef2004749c4f32863eb5b37 to 52cb82faebf1d755d6fec8353ae7d57f8b973758

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

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

comment:16 Changed 4 years ago by tscrim

  • Branch changed from u/egunawan/19160 to u/tscrim/snake_graphs-19160
  • Commit changed from 52cb82faebf1d755d6fec8353ae7d57f8b973758 to a44c44c3c944f35776d9ec4490200b135a946554

WIP for Emily.


New commits:

7afd4a7Merge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs-19160
84ec0a0Making a new non-recursive iterator for composition for speed.
825ecdfMerge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs-19160
69f3547Some more changes; not quite ready.
a44c44cLittle parent classes all in a row.

comment:17 Changed 4 years ago by egunawan

  • Authors changed from egunawan to Emily Gunawan

comment:18 Changed 3 years ago by chapoton

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

comment:19 Changed 3 years ago by egunawan

  • Branch u/tscrim/snake_graphs-19160 deleted
  • Commit a44c44c3c944f35776d9ec4490200b135a946554 deleted

comment:20 Changed 2 years ago by egunawan

  • Cc saliola added

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!

comment:21 Changed 9 months ago by egunawan

  • Branch set to u/egunawan/snake_graphs-19160
  • Cc saliola removed
  • Commit set to 3728b1a85222d074f932ffd693ad77742fbd97ca
  • Description modified (diff)

Last 10 new commits:

84ec0a0Making a new non-recursive iterator for composition for speed.
5fb2ce419160: Fix a hyperlink reference. Add ascii art for a square tile in doc.
a873a6019160:clean up doc.
3c7353c19160:fix bug in plot. Add LabeledSnakeGraph class.
52cb82f19160: Doc builds with no error. Remove references that are not cited in the cluster_snakegraph.py file.
825ecdfMerge branch 'u/egunawan/19160' of git://trac.sagemath.org/sage into u/tscrim/snake_graphs-19160
69f3547Some more changes; not quite ready.
a44c44cLittle parent classes all in a row.
03ee40e19160: merge to 7.5
3728b1aTo Master version 8.2 Merge branch 'u/egunawan/snake_graphs-19160' of git://trac.sagemath.org/sage into 19160
Note: See TracTickets for help on using tickets.