Include David Perkinson's sandpile module in the sage library #10618

sagetrac-mhampton · 2011-01-13T04:35:42Z

Since David Perkinson's sandpile module (for studying the Abelian Sandpile Model; see for example: http://en.wikipedia.org/wiki/Bak-Tang-Wiesenfeld_sandpile or http://people.reed.edu/~davidp/sand/) is already written as a properly formatted Sage module it makes sense to include it in the Sage library.

This module involves a variety of mathematics so it is added in its own module.

Some parts of the module require 4ti2, currently an experimental package (but there is no reason it can't be at least an optional package), but this can be explained in the relevant docstrings. Currently the 4ti2 package at:
http://sage.math.washington.edu/home/mhampton/4ti2-1.3.2.p1.spkg
is best to use.

In case any mathematical justification is needed, this model is of considerable and rising interest. For example, at the joint math meetings in 2011 there was a talk by Yuval Peres of Microsoft Research surveying it: http://www.ams.org/amsmtgs/2125_abstracts/1067-a0-38.pdf.

Only apply:
trac_10618_sandpiles.3.patch

CC: @sagetrac-dperkinson @wdjoyner @dandrake

Component: graph theory

Keywords: abelian sandpile model

Author: David Perkinson, Marshall Hampton

Reviewer: David Joyner

Merged: sage-4.7.alpha2

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

sagetrac-mhampton · 2011-01-13T04:36:19Z

Attachment: sandpile-2.3.patch.gz

adds module to graphs folder and the all.py in graphs

wdjoyner · 2011-01-14T19:56:52Z

comment:4

This applies fine to a clone of sage-4.6.1.rc1. However, it fails a ton of doctests. These might pass if the (optional/experimanetal) spkgs were installed. The point is, it should pass if nothing is installed. However, there were also these:


    sage: D.__dict__
Expected:
    {'_sandpile': Digraph on 3 vertices, '_effective_div': [{0: 2, 1: 0, 2: 0}, {0: 0, 1: 1, 2: 1}], '_linear_system': {'inhomog': [[1, 0, 0], [0, -1, -1], [0, 0, 0]], 'num_inhomog': 3, 'num_homog': 2, 'homog': [[-1, -1, -1], [1, 1, 1]]}, '_vertices': [0, 1, 2]}
Got:
    {'_sandpile': Digraph on 3 vertices, '_vertices': [0, 1, 2]}

and


    sage: D._set_linear_system()
Expected nothing
Got:
    <BLANKLINE>
                     **********************************
                     *** This method requires 4ti2. ***
                     **********************************
    <BLANKLINE>
                Read the beginning of sandpile.sage or see the Sage Sandpiles
                documentation for installation instructions.
    <BLANKLINE>
}}
for example.

This occurred on both an ubuntu machine and a 10.6.6 mac.

sagetrac-mhampton · 2011-01-15T18:40:24Z

comment:5

Thanks for taking a look. I'll try to fix this up. I think the 4ti2 functions can be flagged "optional".

sagetrac-mhampton · 2011-01-16T10:51:20Z

comment:6

OK, all tests pass for me now and the coverage is 100%.

The only problem that I see now is how to deal with namespace issues. I think classes like "Divisor" have too general a name to get imported into Sage at the top level, which is what this patch currently does. I see three alternatives at least:

Rename functions and classes to be clearly sandpile specific. E.g., rename the Divisor class to something like SandpileDivisor.
Don't import this module into the namespace at all, so users would have to do:

sage: from sage.sandpiles import *

themselves.

Import the module in its own namespace, so for instance you would have to do:

sage: S = sandpiles.complete_sandpile(4)

I would rank these as 1 > 2 > 3, but this is an important decision since it will be a pain to change later.

wdjoyner · 2011-01-16T17:10:10Z

comment:7

Replying to @sagetrac-mhampton:

OK, all tests pass for me now and the coverage is 100%.

Not for me:

sage -t -force_lib "devel/sage/sage/sandpiles/sandpile.py"  
**********************************************************************
File "/Users/wdj/sagefiles/sage-4.6.1.rc1/devel/sage/sage/sandpiles/sandpile.py", line 5173:
    sage: for p in P:
       sum([partition_sandpile(S, i).betti(verbose=False)[-Integer(1)] for i in p])
Exception raised:
    Traceback (most recent call last):
      File "/Users/wdj/sagefiles/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/Users/wdj/sagefiles/sage-4.6.1.rc1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/Users/wdj/sagefiles/sage-4.6.1.rc1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_160[3]>", line 1, in <module>
        for p in P:###line 5173:
    sage: for p in P:
    NameError: name 'P' is not defined
**********************************************************************
1 items had failures:
   1 of   5 in __main__.example_160
***Test Failed*** 1 failures.

This sort of failure occurs on both a 10.6.6 imac and an ubuntu machine.

The only problem that I see now is how to deal with namespace issues.
I think classes like "Divisor" have too general a name to get imported into
Sage at the top level, which is what this patch currently does.
I see three alternatives at least:

Rename functions and classes to be clearly sandpile specific.
E.g., rename the Divisor class to something like SandpileDivisor.

I agree. I actually suggested this when David P was asking for suggestions
years ago in reply to his post asking for comments on a first version.

sagetrac-mhampton · 2011-01-16T23:38:41Z

Supersedes previous patch.

sagetrac-mhampton · 2011-01-16T23:39:28Z

comment:8

Attachment: trac_10618_sandpiles.patch.gz

Sorry about that, I'm not sure how I missed that. I have tried once again, new patch has same name as the last one.

wdjoyner · 2011-01-17T14:41:20Z

comment:9

This installed and pases sage -testall on imac running 10.6.6 and sage-4.6.1.rc1. However, the instll of 4ti2 failed. I'll try it on a linux machine.

wdjoyner · 2011-01-17T17:27:28Z

comment:10

Replying to @wdjoyner:

This installed and passes sage -testall on imac running 10.6.6 and
sage-4.6.1.rc1. However, the install of 4ti2 failed. I'll try it on a linux machine.

To be more precise, the instuctions on installing 4ti2 given in the
docstrings to this module fail. If you instead use the instructions
given in #8217 comment:5
then 4ti2 does install fine.

I'll report back on the results of running sage -testall -optional ASAP.

wdjoyner · 2011-01-17T22:31:03Z

comment:11

This looks good in the sense that the docstrings do not fail after 4ti2 (and glpk) is added.

I am willing to give this a positive review. However, there are still some problems with the docstrings - (a) the naming issue mentioned above, (b) one date in the AUTHOR field has the wrong year, (c) the instructions on installing 4ti2 lead to the old package which does not install.

Should these be fixed in a separate ticket?

sagetrac-mhampton · 2011-01-18T02:04:54Z

comment:12

No, I think we should get this pretty much right before it officially goes in - it would be annoying to change names later since we'd have to formally deprecate everything. I'll ask David Perkinson directly what he thinks about the namespace issues.

sagetrac-mhampton · 2011-01-27T04:51:32Z

Attachment: trac_10618_sandpiles.2.patch.gz

sagetrac-mhampton · 2011-01-27T04:58:45Z

comment:13

David Perkinson is OK with the idea of renaming some functions and classes to avoid confusion in the top namespace. The attached patch - trac_10618_sandpiles.2.patch - is a first attempt at resolving this aspect of the module.

wdjoyner · 2011-02-01T12:47:54Z

comment:14

Applying only trac_10618_sandpiles.2.patch to 4.6.1.rc0 on an ubuntu machine resulted in all tests passed in sage -testall. This is without 4ti2.

I think you still need
http://sage.math.washington.edu/home/mhampton/4ti2-1.3.2.p1.spkg
as opposed to the version on the sage webpage.
I will test this next.

Also, I think you need to add to the intro of this ticket that only the last patch need be applied.

jdemeyer · 2011-02-22T17:04:49Z

Reviewer: David Joyner

jdemeyer · 2011-02-22T17:04:49Z

comment:17

The commit message of the patch should contain the ticket number.

jdemeyer · 2011-03-04T13:27:51Z

comment:18

I get various doctest failures:

sage -t  -force_lib devel/sage/sage/sandpiles/sandpile.py
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/devel/sage-main/sage/sandpiles/sandpile.py", line 1815:
    sage: S.unsaturated_ideal().gens()
Expected:
    (x1^3 - x4*x3*x0, x2^3 - x5*x3*x0, x3^2 - x5*x2, x4^2 - x3*x1, x5^2 - x3*x2)
Got:
    [x1^3 - x4*x3*x0, x2^3 - x5*x3*x0, x3^2 - x5*x2, x4^2 - x3*x1, x5^2 - x3*x2]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/devel/sage-main/sage/sandpiles/sandpile.py", line 1817:
    sage: S.ideal().gens()
Expected:
    (x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2)
Got:
    [x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/devel/sage-main/sage/sandpiles/sandpile.py", line 1840:
    sage: S.ideal(True)
Expected:
    (x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2)
Got:
    [x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2]
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha2/devel/sage-main/sage/sandpiles/sandpile.py", line 1842:
    sage: S.ideal().gens()  # another way to get the generators
Expected:
    (x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2)
Got:
    [x2 - x0, x3^2 - x5*x0, x5*x3 - x0^2, x4^2 - x3*x1, x5^2 - x3*x0, x1^3 - x4*x3*x0, x4*x1^2 - x5*x0^2]
**********************************************************************

wdjoyner · 2011-03-14T14:32:55Z

comment:21

Installs fine to 4.7.a1 and passes sage -testall.

jdemeyer · 2011-03-16T11:28:27Z

comment:22

Again: you should change the commit message of the patch such that the first line mentions the ticket number. Use hg qrefresh -e for that.

jdemeyer · 2011-03-19T17:37:15Z

Work Issues: check "long time"

jdemeyer · 2011-03-19T17:37:15Z

comment:23

On which machine did you check where to write "# long time"? It seems that most of these "long time" doctests take less than 1 second on sage.math.washington.edu, which means that they should not be marked "long time".

For example, this doctest on line 196::

sage: from sage.sandpiles import *
sage: g = {0: {},                    \
               1: {0: 1, 2: 1, 3: 1},    \
               2: {1: 1, 3: 1, 4: 1},    \
               3: {1: 1, 2: 1, 4: 1},    \
               4: {2: 1, 3: 1}}
sage: S = Sandpile(g,0)
sage: S.resolution() # long time (minutes)
'R^1 <-- R^7 <-- R^15 <-- R^13 <-- R^4'

Even though the test claims "minutes", in reality it takes about half a second.

sagetrac-mhampton · 2011-03-19T19:53:44Z

Apply only this patch.

sagetrac-mhampton · 2011-03-19T19:55:48Z

comment:24

Attachment: trac_10618_sandpiles.3.patch.gz

I'm not sure why those used to take so much longer. Its possible that some changes in the Singular interface since then sped things up. Anyway, now testing everything without the 4ti2 dependencies takes abour 24 seconds on my laptop, and including the 4ti2 stuff it takes about 30 seconds. So I removed all the "long time" flags.

I also put the ticket number on the commit message.

wdjoyner · 2011-03-19T22:52:24Z

comment:25

Installs fine to 4.7.a1 and passes sage -testall.

Hope this stays as a positive review this time.

Thanks again Marshall for creating this.

jdemeyer · 2011-03-21T09:42:48Z

Merged: sage-4.7.alpha2

jdemeyer · 2011-03-21T09:42:48Z

Changed work issues from check "long time" to none

jdemeyer · 2011-04-18T16:02:12Z

comment:27

It seems that testing this module can give enormously different timings depending on the machine. Any clue why?

On sage.math.washington.edu:

$ ./sage -t "devel/sage/sage/sandpiles/sandpile.py"
[...]
Total time for all tests: 23.7 seconds

But on my laptop (Gentoo Linux, Intel Core 2 Duo, gcc 4.4.3):

$ ./sage -t "devel/sage/sage/sandpiles/sandpile.py"
sage -t  "devel/sage/sage/sandpiles/sandpile.py"
*** *** Error: TIMED OUT! PROCESS KILLED! *** ***

(i.e. it takes more than 360 seconds)

jdemeyer · 2011-04-18T16:45:22Z

comment:28

Please check the thread
http://groups.google.com/group/sage-devel/browse_thread/thread/5db90b3681e7dbcb

Something fishy with the sandpile.py timings...

sagetrac-mhampton mannequin added this to the sage-4.6.2 milestone Jan 13, 2011

sagetrac-mhampton mannequin added c: graph theory labels Jan 13, 2011

sagetrac-mhampton mannequin assigned jasongrout, nathanncohen and rlmill Jan 13, 2011

sagetrac-mhampton mannequin added the s: needs review label Jan 13, 2011

wdjoyner added s: needs work and removed s: needs review labels Jan 14, 2011

wdjoyner added s: needs review and removed s: needs work labels Jan 17, 2011

wdjoyner added s: needs info and removed s: needs review labels Jan 17, 2011

sagetrac-mhampton mannequin added s: needs work and removed s: needs info labels Jan 18, 2011

jdemeyer added s: needs work and removed s: positive review labels Feb 22, 2011

This comment has been minimized.

Sign in to view

sagetrac-mhampton mannequin added s: needs review and removed s: needs work labels Mar 14, 2011

wdjoyner added s: positive review and removed s: needs review labels Mar 14, 2011

jdemeyer added s: needs work and removed s: positive review labels Mar 16, 2011

sagetrac-mhampton mannequin added s: needs review and removed s: needs work labels Mar 19, 2011

wdjoyner added s: positive review and removed s: needs review labels Mar 19, 2011

jdemeyer removed the s: positive review label Mar 21, 2011

jdemeyer closed this as completed Mar 21, 2011

a-andre mentioned this issue Dec 19, 2014

Remove deprecated function aliases #16689

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Include David Perkinson's sandpile module in the sage library #10618

Include David Perkinson's sandpile module in the sage library #10618

sagetrac-mhampton mannequin commented Jan 13, 2011

sagetrac-mhampton mannequin commented Jan 13, 2011

wdjoyner commented Jan 14, 2011

sagetrac-mhampton mannequin commented Jan 15, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

wdjoyner commented Jan 16, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

wdjoyner commented Jan 17, 2011

wdjoyner commented Jan 17, 2011

wdjoyner commented Jan 17, 2011

sagetrac-mhampton mannequin commented Jan 18, 2011

sagetrac-mhampton mannequin commented Jan 27, 2011

sagetrac-mhampton mannequin commented Jan 27, 2011

wdjoyner commented Feb 1, 2011

jdemeyer commented Feb 22, 2011

jdemeyer commented Feb 22, 2011

jdemeyer commented Mar 4, 2011

This comment has been minimized.

wdjoyner commented Mar 14, 2011

jdemeyer commented Mar 16, 2011

jdemeyer commented Mar 19, 2011

jdemeyer commented Mar 19, 2011

sagetrac-mhampton mannequin commented Mar 19, 2011

sagetrac-mhampton mannequin commented Mar 19, 2011

wdjoyner commented Mar 19, 2011

jdemeyer commented Mar 21, 2011

jdemeyer commented Mar 21, 2011

jdemeyer commented Apr 18, 2011

jdemeyer commented Apr 18, 2011

Include David Perkinson's sandpile module in the sage library #10618

Include David Perkinson's sandpile module in the sage library #10618

Comments

sagetrac-mhampton mannequin commented Jan 13, 2011

sagetrac-mhampton mannequin commented Jan 13, 2011

wdjoyner commented Jan 14, 2011

sagetrac-mhampton mannequin commented Jan 15, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

wdjoyner commented Jan 16, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

sagetrac-mhampton mannequin commented Jan 16, 2011

wdjoyner commented Jan 17, 2011

wdjoyner commented Jan 17, 2011

wdjoyner commented Jan 17, 2011

sagetrac-mhampton mannequin commented Jan 18, 2011

sagetrac-mhampton mannequin commented Jan 27, 2011

sagetrac-mhampton mannequin commented Jan 27, 2011

wdjoyner commented Feb 1, 2011

jdemeyer commented Feb 22, 2011

jdemeyer commented Feb 22, 2011

jdemeyer commented Mar 4, 2011

This comment has been minimized.

wdjoyner commented Mar 14, 2011

jdemeyer commented Mar 16, 2011

jdemeyer commented Mar 19, 2011

jdemeyer commented Mar 19, 2011

sagetrac-mhampton mannequin commented Mar 19, 2011

sagetrac-mhampton mannequin commented Mar 19, 2011

wdjoyner commented Mar 19, 2011

jdemeyer commented Mar 21, 2011

jdemeyer commented Mar 21, 2011

jdemeyer commented Apr 18, 2011

jdemeyer commented Apr 18, 2011