A draw_rauzy_fractal method for WordMorphism

[tjolivet]

New:

• 2012-07-05: added basis projection plotting
• Now there are two distinct methods rauzy_fractal_plot and rauzy_fractal_points.
• Translated copies of the fractal and its pieces can be plotted, allowing all kinds of tiling plots.
• Error message in the case where the eigenvalue is of degree one.
• New patch for version 5.0.1 (but doesn't apply with the bot for some reason).
• A few other things.

From the docstring:

Returns a plot of the Rauzy fractal associated with a substitution. The substitution does not have to be irreducible. The definition used can be found found for example in [1]. The usual definition of a Rauzy fractal requires that its dominant eigenvalue is a Pisot number. The present method doesn't require this, allowing to plot some interesting pictures in the non-Pisot case (see the examples below).

Plots with less than 100,000 points take a few seconds, and several millions of points can be plotted in reasonable time.

[tjolivet]

I've added a new version of the patch, with a new option opacity and an enhanced version of option color (see docstring).

[tjolivet]

I'd be glad if anyone can explain me why the patchbot says "TestsFailed?". sage -t and docbuild run fine on my machine.

[slabbe]

Maybe because of trailing whitespaces ?

The log says :

ValueError: Trailing whitespace inserted on 16 non-empty lines.

[tjolivet]

Thanks, there were indeed some ugly trailing whitespaces.

I removed them but the tests still fail and I can't decipher the log. It seems that the problems come from some code other than this patch. What's the problem then?

[ncohen]

Helloooooooo !!!

The tests do not pass, and the reason why you do not see it is that to actually test your patch you need both -optional and -long flags.

~/.Sage/devel/sage-2/sage/combinat/words$ sage -b 2 && sage -t -long -optional morphism.py 
[...]
sage -t -long -optional "devel/sage-2/sage/combinat/words/morphism.py"
**********************************************************************
File "/home/ncohen/.Sage/devel/sage-2/sage/combinat/words/morphism.py", line 2027:
    sage: s.plot_rauzy_fractal(color={1:'black', 2:'black', 3:'black'})    # optional long time
Exception raised:
    Traceback (most recent call last):
      File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/ncohen/.Sage/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/ncohen/.Sage/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_42[18]>", line 1, in <module>
        s.plot_rauzy_fractal(color={Integer(1):'black', Integer(2):'black', Integer(3):'black'})    # optional long time###line 2027:
    sage: s.plot_rauzy_fractal(color={1:'black', 2:'black', 3:'black'})    # optional long time
      File "/home/ncohen/.Sage/local/lib/python/site-packages/sage/combinat/words/morphism.py", line 2139, in plot_rauzy_fractal
        G += points(D[a], color=col_dict[a], alpha=opacity[a], size=point_size)
    KeyError: 1
~/.Sage/devel/sage-2/sage/combinat/words$

Actually, only a -long flag should be needed here (by removing the keyword 'optional' from the commented lines), shouldn'it ?

Nathann

[tjolivet]

Replying to ncohen:

Helloooooooo !!!

The tests do not pass, and the reason why you do not see it is that to actually test your patch you need both -optional and -long flags.

Thanks! I fixed the doc mistake, let's hope it works now.

[vdelecroix]

Hello,

Nice, all tests pass. The documentation is clear and the examples very interesting.

1) For the construction of colors, there is a built in functions "rainbow" in sage.plot.colors (you can call it with 'rgbtuple' option).

2) You should never use an error catch (try ... except ...) which catches all errors. The way you did, it would be impossible to send a stop signal to the process using C-c. You have to write something like

try:

blabla

except TypeError?,ValueError?:

pass

where the tuple of errors you use is the one which may be raised by the code in blabla. Errors may be produced from other part of the code and you should not intercept them!

2') The loop you use for finding a fixed point (actually a periodic point) is very dirty!! You should be able to compute the smallest k for which sigmak(0) starts with 0... For example you can build the substitution tau which sends alpha to the first letter (or last if reversal) of sigma(alpha). And then, you can search for a cycle of tau which gives you periodic points. The best way would be to add a method in WordMorphism? which does it for you... (perhaps an other ticket).

Next to come. If you like I can implement 2') in another ticket ?

Vincent

[tjolivet]

Hi Vincent, thanks for you review.

Replying to vdelecroix:

1) For the construction of colors, there is a built in functions "rainbow" in sage.plot.colors (you can call it with 'rgbtuple' option).

Yes, I'm aware of the rainbow function, but colormaps offers many color schemes and it works fine, so I used it.

2) and 2')

Yes, indeed this is not very clean and I should have done otherwise... Yes you can implement 2') if you want! (Maybe we could add an option in the .fixed_point that forces to return a fixed point of the substitution (or a power), because it's annoying to have to trick with substitution which don't have a "true" fixed point.)

Cheers, Timo

[vdelecroix]

Replying to vdelecroix:

1) For the construction of colors, there is a built in functions "rainbow" in sage.plot.colors (you can call it with 'rgbtuple' option).

Yes, I'm aware of the rainbow function, but colormaps offers many color schemes and it works fine, so I used it.

I see. Your way is definitely better.

2) and 2')

It is now #12512. Could you replace your loop with either

u = iter(self.periodic_point(letter))

where letter is a parameter, or

u = iter(self.periodic_points()[0][0])

3) Why did you choose 1000 for the precision of the complex field ? It seems a little bit big for your purpose. Won't you make it a parameter (with a reasonable default value) ?

4) Why do you assume that the root is cubic ? On one hand, if they are ordered as |l_1| > |l_2| > 1 > |l_3| then you will get a strange Rauzy fractal, won't you ? On the other hand, I have examples for which the absolute values of eigenvalues are ordered as |l_1| > |l_2| > 1 > |l_3| > |l_4|. Then you can obtain a Rauzy fractal after a projection parallel to v_1 and v_2 on the plane generated by v_3 and v_4 (where v_i is an eigenvector associated to l_i). In other words, I'm a little bit confused with your restrictions.

Otherwise, everything is very nice. You should now write a tutorial with both methods for drawing Rauzy fractals with nice pictures and put it in the documentation ;-)

[vdelecroix]

Works with sage-5.1.rc1. Documentation builds.

Nice patch! Could you add some pictures to the gallery ​http://wiki.sagemath.org/pics when the patch will be in the stable release ?

[tjolivet]

Replying to vdelecroix:

Nice patch! Could you add some pictures to the gallery ​http://wiki.sagemath.org/pics when the patch will be in the stable release ?

Yeps! Thanks.

[jdemeyer]

Please write your real names in the Author/Reviewer? fields.

[jdemeyer]

This should be rebased to sage-5.2.rc1.

[tjolivet]

rebased to sage-5.2.rc1

[tjolivet]

A test fails but it doesn't seem to come from this patch.

It would be great if this could make it into sage-5.2.

[slabbe]

I am ready to give positive review provided the three following things are satisfied :

• doctest timing do not take too much longer than before
• documentation issue are fixed (done in my first review patch)
• method rauzy_fractal_points is split into two (done in my second review patch)

... and of course if Timo and others agree with my patches.

Indeed,

1. Testing the file morphism.py now takes way more time than before. I think sage -t sage_library_file.py should run in 10s and sage -t -long -optional sage_library_file.py in no more than 40 seconds (these are my standards, I don't know if there exist any in the Sage Developper Guide). Instead of drawing 10000 points, you can draw 100 points for the doctests. If you want to keep those doctests interesting for the user, you may add #not tested takes > 3 seconds. Or, you can add a remark at the beginning of the examples saying the value n=100 below is low for doctests purposes, larger values of n can be given by the user.

BEFORE:

 $ sage-5.2.rc0 -t morphism.py 
sage -t  "devel/sage-main/sage/combinat/words/morphism.py"  
	 [4.4 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 4.4 seconds
 $ sage-5.2.rc0 -t -long -optional morphism.py 
sage -t -long -optional "devel/sage-main/sage/combinat/words/morphism.py"
	 [6.6 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 6.6 seconds

AFTER:

 $ sage-5.2.rc0 -t morphism.py 
sage -t  "devel/sage-main/sage/combinat/words/morphism.py"  
	 [30.4 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 30.4 seconds

$ sage-5.2.rc0 -t -long -optional morphism.py 
sage -t -long -optional "devel/sage-main/sage/combinat/words/morphism.py"
	 [255.9 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 256.0 seconds

2. I uploaded two patches which applies on top of Timo's one. The first fixes some documentation issues.

3. The second patch splits the method rauzy_fractal_points into two. As I already explained verbaly to Timo, I dislike the idea of having output types (dict vs 2-tuple of dict) depending on the input. Instead I propose to split the method into two and doing it made me realize that the second output only depends on two of the inputs. So, now the user can obtain this output without generating points and by providing only the necessary two inputs.

[slabbe]

4. Also, if you could add a sentence explaining how the projection is obtained from the eigenvalue inside the doc of the method rauzy_fractal_projection, it would be great!

[tjolivet]

apply after the three above patches

[tjolivet]

Hi,

Thanks for the corrections which I find useful and clarifying.

I strongly improved the testing time and pointed (another time) the details of the construction to a reference in the doc.

Timo

[slabbe]

I just added some more improvements. Also added few tested doctest.

I give positive review to Timo's patches which answered my concerns. If he agrees with my patch, Timo can change the status of this ticket to positive review.

Sébastien

[slabbe]

Applies over all the preceding patches

[jdemeyer]

What's the rationale for code like

cm.__dict__["gist_gray"]

instead of more simply

cm.gist_gray

[tjolivet]

Replying to jdemeyer:

What's the rationale for code like

I don't think there is any, it's just inadvertent bad style.