Thematic Tutorial on Sandpiles

[bc92013b-9220-40da-a45f-06c52942e68d]

I would like to add a thematic tutorial on the abelian sandpile model.

---

Apply only attachment: trac_11682_sandpile_doc.v6.patch to the Sage library.

Note: To fully make use of it, the optional 4ti2 spkg is required; see comments below.

CC: @sagetrac-mhampton @rbeezer

Component: documentation

Keywords: sandpile

Author: David Perkinson

Reviewer: Rob Beezer, John Palmieri

Merged: sage-4.7.2.alpha3

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

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:1

While you're at it, there are some typos(?) in sandpile.py's docstring (just the modification dates), and GLPK is meanwhile a standard Sage package.

[bc92013b-9220-40da-a45f-06c52942e68d]

Attachment: trac_11682_sandpile_doc.patch.gz

thematic tutorial on the abelian sandpile model

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:2

I am new at this. So although I did my best to follow the online documentation for submitting a change, I apologize in advance for any mistakes I may have made. My intention was to add three changes to the thematic_tutorials directory:

1. Add the file sandpile.rst.
2. Change index.rst to include a reference to sandpile.rst.
3. Add a directory, sandpile, containing png image files for sandpile.rst.

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:3

Replying to @nexttime:

While you're at it, there are some typos(?) in sandpile.py's docstring (just the modification dates), and GLPK is meanwhile a standard Sage package.

Will do. Thanks.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:4

Hi David,

This will be a nice contribution!

One suggestion after a quick look. Really long output in code blocks can be broken at any white-space character without breaking doctests (and you can add whitespace to existing whitespace).

So sometimes you can break, and line-up output to be a bit more readable, rather than spilling over the margin in PDF versions, or having to use a very long horizontal scrollbar in HTML versions. Experiment with one instance before doing a lot of tedious editing, to see what works and how.

Rob

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:5

Replying to @sagetrac-dperkinson:

I am new at this. So although I did my best to follow the online documentation for submitting a change, I apologize in advance for any mistakes I may have made.

Nothing to apologize for.

Although they'll meanwhile be added in case they're missing when a ticket gets merged into a release, commit messages should IMHO still contain the trac ticket number, i.e. start with e.g. either "#11682 ..." or "Trac 11682: ...", or at least reference the ticket on the first line ("brief one-line description (#11682)").

I think the indices to collections of rather unrelated documents (like Thematic Tutorials) are kept in alphabetical order, so sandpile should unfortunately be the last. ;-)

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:6

Although they'll meanwhile be added in case they're missing when a ticket gets merged into a release, commit messages should IMHO still contain the trac ticket number, i.e. start with e.g. either "#11682 ..." or "Trac 11682: ...", or at least reference the ticket on the first line ("brief one-line description (#11682)").

Yes. I accidentally left that out, and then could not figure out how to change the commit message after-the-fact. How does one do that? Can it be changed now?

I think the indices to collections of rather unrelated documents (like Thematic Tutorials) are kept in alphabetical order, so sandpile should unfortunately be the last. ;-)

I realize the topics should be in alphatical order. The issue here is that the file is called "sandpile.rst" and the title of the resulting html page is "Abelian sandpile model". So if you do a html docbuild, the topics actually will be in alphabetical order.

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:7

Replying to @sagetrac-dperkinson:

commit messages should IMHO still contain the trac ticket number

Yes. I accidentally left that out, and then could not figure out how to change the commit message after-the-fact. How does one do that? Can it be changed now?

Not an issue if you update your patch anyway. (You can check Replace existing file of the same name or whatever it is called when you re-attach a new version of the patch.)

You can also just edit the patch you exported with Mercurial (since it is a plain text file) with any editor and re-upload it (with the same filename, see above).

Nobody will mind if you decide to attach a new version of your patch with a different filename, e.g. trac_11682_sandpile_doc.v2.patch, but the previous, obsolete one doesn't contain the ticket number in its commit message.

If there are different [versions of] patches or other files (to not be applied) attached to the ticket, the ticket's description should state which files have to actually be applied, and if necessary, in which order. (You could also attach a second patch to be applied on top of your previous one, in which case you should change the commit message of the first as mentioned above.)

The issue here is that the file is called "sandpile.rst" and the title of the resulting html page is "Abelian sandpile model".

Ah sorry, did not notice.

[bc92013b-9220-40da-a45f-06c52942e68d]

Attachment: trac_11682_sandpile_doc.v2.patch.gz

replaces trac_11682_sandpile_doc.patch

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:8

I just posted trac_11682_sandpile_doc.v2.patch. It replaces trac_11682_sandpile_doc.patch. So trac_11682_sandpile_doc.v2.patch should not be applied after applying trac_11682_sandpile_doc.patch.

In trac_11682_sandpile_doc.v2.patch, I have fixed the long lines as suggested by Rob Beezer (thanks, Rob!). I have included the trac number in the commit message this time around.

For me, all tests passed with the command

sudo sage -t -verbose -long --optional /doc/en/thematic_tutorials/sandpile.rst

[bc92013b-9220-40da-a45f-06c52942e68d]

replaces first two versions

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:9

Attachment: trac_11682_sandpile_doc.v3.patch.gz

The third version of the patch, trac_11682_sandpile_doc.v3.patch does the following:

1. Adds the file sandpile.rst,
2. Changes index.rst to include a reference to sandpile.rst. (Note that in index.rst, 'sandpile' does not appear in alphabetical order, but in the actual index.html that is produced, the corresponding title is 'Abelian sandpile model', which is in alphabetical order.)
3. Adds a subdirectory, media/sandpile, containing png image files for sandpile.rst.

To test the patch, I created a fresh clone of sage-main, applied the patch

trac_11682_sandpile_doc.v3.patch

and ran 'sage -docbuild thematic_tutorials html' and 'sage -docbuild thematic_tutorials pdf'. The resulting html and pdf files and the index for the thematic tutorials were all as expected. I reran

sage -t -verbose -long --optional <PATH_TO_SAGE_BRANCH>/doc/en/thematic_tutorials/sandpile.rst 

and again the tests all passed.

[The problem with v2 of the patch was that mercurial was not allowing me to add png files. (I needed to add appropriate lines to my .hgrc).]

[dimpase]

comment:10

Replying to @sagetrac-dperkinson:

The third version of the patch, trac_11682_sandpile_doc.v3.patch does the following:

At http://localhost:8000/doc/live/thematic_tutorials/sandpile.html#zeros I see

The zero set for the sandpile ideal  is

      Extra close brace

(the latter is in a red frame) instead of a rendering of the (correctly looking) TeX formula. Is it just me (MacOSX 10.6, Sage 4.7.apha5)?

PS. I looked at it in hope of finding code to supply the addition operation on the spanning trees, but to no avail :-)

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:11

Hmm... I am not having that problem (Ubuntu 10.10, Sage Version 4.7, Release Date: 2011-05-23).

About spanning trees: are you thinking of adding them, using a bijection between them and elements of the sandpile group?

Replying to @dimpase:

Replying to @sagetrac-dperkinson:

The third version of the patch, trac_11682_sandpile_doc.v3.patch does the following:

At http://localhost:8000/doc/live/thematic_tutorials/sandpile.html#zeros I see

The zero set for the sandpile ideal  is

      Extra close brace

(the latter is in a red frame) instead of a rendering of the (correctly looking) TeX formula. Is it just me (MacOSX 10.6, Sage 4.7.apha5)?

PS. I looked at it in hope of finding code to supply the addition operation on the spanning trees, but to no avail :-)

[dimpase]

comment:12

Replying to @sagetrac-dperkinson:

Hmm... I am not having that problem (Ubuntu 10.10, Sage Version 4.7, Release Date: 2011-05-23).

OK, I'll look further into this.

About spanning trees: are you thinking of adding them, using a bijection between them and elements of the sandpile group?

actually, I need it for directed graphs, in view of https://oeis.org/draft/A027362; the only reference in literature on sandpiles for directed graphs I know is in a recent paper by Lionel Levine --- and no explicit bijection is given there. It seems one has to roll his own here, no?

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:13

Hi David,

This is very nice and all seems to be working pretty well as far as patches and images and all that.

I have one doctest failure (same command twice, then a follow-on command fails). I'm using 4.7.1.alpha4. It could be I am behind? Has this changed? Which version are you testing on?

File "/sage/sage-4.7.1.alpha4/devel/sage-main/doc/en/thematic_tutorials/sandpile.rst", line 4189:
    sage: eff = D.effective_div()
Exception raised:
    Traceback (most recent call last):
      File "/sage/sage-4.7.1.alpha4/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/sage/sage-4.7.1.alpha4/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/sage/sage-4.7.1.alpha4/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_102[4]>", line 1, in <module>
        eff = D.effective_div()###line 4189:
    sage: eff = D.effective_div()
      File "/sage/sage-4.7.1.alpha4/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 4212, in effective_div
        return deepcopy(self._effective_div)
      File "/sage/sage-4.7.1.alpha4/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 3551, in __getattr__
        self._set_effective_div()
      File "/sage/sage-4.7.1.alpha4/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 4178, in _set_effective_div
        r = self.linear_system()
      File "/sage/sage-4.7.1.alpha4/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 4157, in linear_system
        return self._linear_system
      File "/sage/sage-4.7.1.alpha4/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 3549, in __getattr__
        return self.__dict__[name]
    KeyError: '_linear_system'

Same thing at line 4360.

Some comments on formatting, etc, in no particular order.

1. Other tutorials have a main title (in the index of tutorials) that is capitalized, so maybe yours should be also.

2. Maybe "is in the works" could read as "will appear as"?

3. Installing 4ti2. Does it really need the patch level and all? I thought it was smarter and sage -i 4ti2 would grab the newest spkg?

4. URL references to other parts of the documentation should perhaps be relative links, not full-blown http:// style. Sage should not presume an internet connection, and indeed, many may view the documentation locally, especially if coming to it from within the notebook. So

http://sagemath.org/doc/reference/sage/graphs/graph_generators.html 

could become

../reference/sage/graphs/graph_generators.html

There are also ways to link to documentation for classes, modules, functions, etc with syntax such as

:mod:`sage.graphs.graph_generators`

which might even work better (ask if you need help with this).

5. SandpileConfig, !^ operator: needs a double-colon for the examples, they are not being rendered verbatim.

6. Do you want triple-dashes to make full-width horizontal rules in your lists of methods? I'm just getting a short stubby thing, maybe you need more dashes?

7. Are Sage code examples in the "python blocks" being tested? (Break one and see.) I don't know - I've never used this construct in writing documentation. Doesn't matter either way, I think.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:14

Replying to @dimpase:

At http://localhost:8000/doc/live/thematic_tutorials/sandpile.html#zeros I see

I didn't see this problem, all looks well at #zeros.

Ubuntu 11.04, Sage 4.7.1.alpha4

[bc92013b-9220-40da-a45f-06c52942e68d]

Attachment: trac_11682_sandpile_doc.v4.patch.gz

first, apply trac_11682_sandpile_doc.v3.patch then trac_11682_sandpile_doc.v4.patch

[bc92013b-9220-40da-a45f-06c52942e68d]

first apply trac_11682_sandpile_doc.v3.patch then trac_11682_sandpile_doc.v4.patch

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:15

Attachment: trac_11682_sandpile_doc.v4.2.patch.gz

Rob: thanks for the comments!

I have addressed them all (see specifics below). I doctested the current version (v4) with the --optional and -long and all tests passed.

NOTE: First apply trac_11682_sandpile_doc.v3.patch, then trac_11682_sandpile_doc.v4.patch on top of that. Also, v4 and v4.2 are identical. I just tried to remove a comma from the description and ended up with two copies.

Thanks, Dave

I have one doctest failure (same command twice, then a follow-on command fails). I'm using 4.7.1.alpha4. It could be I am behind? Has this changed? Which version are you testing on?

The problem here is that you do not have 4ti2 installed and I forgot to put to include '# optional 4ti2' next to these examples. I have added '# optional 4ti2' in these two places in v4.

(I am testing on version 4.7.1 now.)

1. Other tutorials have a main title (in the index of tutorials) that is capitalized, so maybe yours should be also.

Fixed.

2. Maybe "is in the works" could read as "will appear as"?

Fixed (I removed the reference entirely for the time being).

3. Installing 4ti2. Does it really need the patch level and all? I thought it was smarter and sage -i 4ti2 would grab the newest spkg?

I just tested this again. The command 'sage -i 4ti2' attempts to install the wrong version of 4ti2 and crashes, whereas 'sage -i 4ti2.p0' works fine. I sent a note to sage-devel about this.

4. URL references to other parts of the documentation should perhaps be.relative links, not full-blown http:// style. Sage should not presume an internet connection, and indeed, many may view the documentation locally, especially if coming to it from within the notebook. So

http://sagemath.org/doc/reference/sage/graphs/graph_generators.html

could become

../reference/sage/graphs/graph_generators.html

There are also ways to link to documentation for classes, modules, functions, etc with syntax such as

:mod:sage.graphs.graph_generators

which might even work better (ask if you need help with this).

Fixed. I used your former suggestion.

5. SandpileConfig, ^ operator: needs a double-colon for the examples, they are not being rendered verbatim.

Fixed.

6. Do you want triple-dashes to make full-width horizontal rules in your lists of methods? I'm just getting a short stubby thing, maybe you need more dashes?

I am getting em-dashes from '---' in the rst file. I don't understand why you are not getting longer dashes.

7. Are Sage code examples in the "python blocks" being tested? (Break one and see.) I don't know - I've never used this construct in writing documentation. Doesn't matter either way, I think.

I ascertained that the python blocks were not being tested. So I checked each manually, found several problems (due to out-of-date syntax), and fixed them. I do not want to have the blocks labeled as 'EXAMPLES'. I putua warning at the top of sandpile.rst that these blocks need to be tested by hand.

[jhpalmieri]

comment:16

I ascertained that the python blocks were not being tested. So I checked each manually, found several problems (due to out-of-date syntax), and fixed them. I do not want to have the blocks labeled as 'EXAMPLES'. I putua warning at the top of sandpile.rst that these blocks need to be tested by hand.

This code must be tested automatically.

To do this, you don't have to label them as EXAMPLES, you just need to delimit them with a double colon, say like this:

@@ -74,16 +77,14 @@ configuration `c'=(1,1,3)`.  Here, `4` g
 these has gone to the sink vertex (and forgotten), one has gone to vertex 1,
 and two have gone to vertex 2, since the edge from 1 to 2 has weight 2.
 Vertex 3 in the new configuration is now unstable.  The Sage code for this
-example looks like this:
-
-.. code-block:: python
-
-    Create the sandpile:
+example looks like this::
+
+   Create the sandpile:

         sage: g = {'sink':{},
-                   1:{'sink':1, 2:1, 3:2},
-                   2:{1:1, 3:1},
-                   3:{1:1, 2:1}}
+        ...        1:{'sink':1, 2:1, 3:2},
+        ...        2:{1:1, 3:1},
+        ...        3:{1:1, 2:1}}
         sage: S = Sandpile(g, 'sink')
         sage: S.show(edge_labels=true)  # to display the graph

(The triple dots are to denote continuation lines.) I would also suggest that you put .. linkall near the top of the file to tell Sage to link all of the examples when doctesting, since you define S in one block and then use it in the next one.

When I made changes like the above, I got a bunch of doctest failures, e.g.

sh: /Applications/sage/local/bin/zsolve: No such file or directory
sh: /Applications/sage/local/bin/zsolve: No such file or directory
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/doc/en/thematic_tutorials/sandpile.rst", line 212:
    sage: S.is_recurrent(c)
Exception raised:
    Traceback (most recent call last):
      File "/Applications/sage/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Applications/sage/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Applications/sage/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[23]>", line 1, in <module>
        S.is_recurrent(c)###line 212:
    sage: S.is_recurrent(c)
      File "/Applications/sage/local/lib/python/site-packages/sage/sandpiles/sandpile.py", line 416, in __getattr__
        raise AttributeError, name
    AttributeError: is_recurrent
**********************************************************************
File "/Applications/sage_builds/sage-4.7.2.alpha2/devel/sage-new/doc/en/thematic_tutorials/sandpile.rst", line 317:
    sage: S.reduced_laplacian().dense_matrix().smith_form()
Expected:
    ([1 0 0]
    [0 1 0]
    [0 0 3],
     [ 0  0  1]
    [ 1  0  0]
    [ 0  1 -1],
     [3 1 4]
    [4 1 6]
    [4 1 5])
Got:
    (
    [1 0 0]  [ 0  0  1]  [3 1 4]
    [0 1 0]  [ 1  0  0]  [4 1 6]
    [0 0 3], [ 0  1 -1], [4 1 5]
    )

There were 32 failures in all, some of which are minor, like the spacing in the matrix, but some look more significant.

[bc92013b-9220-40da-a45f-06c52942e68d]

Attachment: trac_11682_sandpile_doc.v5.patch.gz

this patch replaces all of the previous patches

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:17

Thanks for the useful comments!

I have moved all of the sage examples that were in python code-blocks so that they are doctest-able. Running the doctests made me aware of several significant problems, which I fixed. When I now run sage -t --verbose -long --optional on sandpile.rst, all tests pass.

The current patch, trac_11682_sandpile_doc.v5.patch, replaces all the others, i.e, it should not be applied on top of any of the previous patches.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

Reviewer: Rob Beezer, John Palmieri

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:18

David,

I think this is looking real good. It'll be a very nice contribution.

And despite my earlier (unconsidered) ambivalence, the Python blocks really should be doctested, or they will eventually become useless (and an embarassment). So I'm glad John P brought it up and that you have those reworked.

Just one technical problem. The six image files are not available. I don't see a "sandpile" subdirectory in doc/en/thematic_tutorials/media/ after applying the patch, and from the sizes of your patches, it looks like a healthy number of bytes are AWOL.

How about manufacturing a patch with just the images? That'll be really easy to check as a patch on top of the "v5" patch. I'll presume you've done this once and can do it again, but feel free to ask for guidance. With this done, this should move to positive review.

Thanks for this substantial contribution.

Rob

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:19

Hopefully David can easily include the media files back in. I tried to make a cumulative patch but I'm not sure where to put them. In case someone wants to beat David to this, I put a copy of the missing media files at http://sage.math.washington.edu/home/mhampton/sandpile_media.zip -Marshall

[bc92013b-9220-40da-a45f-06c52942e68d]

Attachment: trac_11682_sandpile_doc.v6.patch.gz

Included forgotten images. This patch replaces all the previous ones.

[bc92013b-9220-40da-a45f-06c52942e68d]

comment:20

Patch v6 includes the image files. The computer I was using did not have the lines

[diff] git=1

in its .hgrc file.

Thanks again.

[1d7ec08f-60ae-4512-91a6-8324c06eab9f]

comment:21

Done! Looks good. Images are present and included properly.

Did a full test of the new sandpile.rst file with -long -optional while the 4ti2.p0.spkg spkg installed and all tests pass. Positive review (and nice job!).

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:22

Replying to @rbeezer:

Did a full test of the new sandpile.rst file with -long -optional while the 4ti2.p0.spkg spkg installed and all tests pass.

For the record, there's a (not that) new 4ti2 spkg which will be "included" in Sage 4.7.2.alpha3. (It's still an optional package; cf. #8217.)

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

Description changed:

--- 
+++ 
@@ -1 +1,12 @@
 I would like to add a thematic tutorial on the abelian sandpile model.
+
+---
+
+Apply only [attachment: trac_11682_sandpile_doc.v6.patch](https://github.com/sagemath/sage-prod/files/10653455/trac_11682_sandpile_doc.v6.patch.gz) to the Sage library.
+
+
+
+
+Note: To fully make use of it, the optional 4ti2 spkg is required; see comments below.
+
+

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:24

Replying to @nexttime:

Replying to @rbeezer:

Did a full test of the new sandpile.rst file with -long -optional while the 4ti2.p0.spkg spkg installed and all tests pass.

For the record, there's a (not that) new 4ti2 spkg which will be "included" in Sage 4.7.2.alpha3. (It's still an optional package; cf. #8217.)

FWIW, passes all (long, optional) doctests in sage/sandpiles/ and doc/en/thematic_tutorials/sandpile.rst with the newer 4ti2 spkg and the Sage 4.7.2.alpha3 prerelease as well.

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

Merged: sage-4.7.2.alpha3