Opened 8 years ago

Closed 7 years ago

Last modified 18 months ago

#12454 closed enhancement (fixed)

A draw_rauzy_fractal method for WordMorphism

Reported by: tjolivet Owned by: sage-combinat
Priority: major Milestone: sage-5.3
Component: combinatorics Keywords: rauzy fractal, substitution, word morphism, lounge
Cc: slabbe, tmonteil, vdelecroix, sstarosta Merged in: sage-5.3.beta1
Authors: Timo Jolivet Reviewers: Vincent Delecroix, Sébastien Labbé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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.

Attachments (5)

trac-12454-rauzyfractal-tj.patch (18.6 KB) - added by tjolivet 7 years ago.
rebased to sage-5.2.rc1
12454_review-sl.patch (4.5 KB) - added by slabbe 7 years ago.
12454_review_split-sl.patch (11.1 KB) - added by slabbe 7 years ago.
12454_tj-2.patch (12.0 KB) - added by tjolivet 7 years ago.
apply after the three above patches
12454_review_third-sl.patch (11.0 KB) - added by slabbe 7 years ago.
Applies over all the preceding patches

Download all attachments as: .zip

Change History (38)

comment:1 Changed 8 years ago by tjolivet

  • Description modified (diff)

comment:2 Changed 8 years ago by tjolivet

  • Status changed from new to needs_review

comment:3 Changed 8 years ago by tjolivet

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

comment:4 Changed 8 years ago by tjolivet

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

comment:5 Changed 8 years ago by slabbe

Maybe because of trailing whitespaces ?

The log says :

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

comment:6 Changed 8 years ago by 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?

comment:7 follow-up: Changed 8 years ago by ncohen

  • Status changed from needs_review to needs_work

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

comment:8 Changed 8 years ago by sstarosta

  • Cc sstarosta added

comment:9 in reply to: ↑ 7 Changed 8 years ago by 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.

comment:10 follow-up: Changed 8 years ago by vdelecroix

  • Reviewers set to 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

comment:11 in reply to: ↑ 10 ; follow-up: Changed 8 years ago by 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

comment:12 in reply to: ↑ 11 Changed 8 years ago by 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 ;-)

comment:13 Changed 7 years ago by tjolivet

  • Description modified (diff)

comment:14 Changed 7 years ago by tjolivet

  • Description modified (diff)
  • Status changed from needs_work to needs_review

comment:15 Changed 7 years ago by tmonteil

  • Keywords lounge added

comment:16 Changed 7 years ago by tjolivet

  • Description modified (diff)

comment:17 Changed 7 years ago by tjolivet

  • Description modified (diff)

comment:18 follow-up: Changed 7 years ago by vdelecroix

  • Status changed from needs_review to positive_review

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 ?

comment:19 in reply to: ↑ 18 Changed 7 years ago by 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.

comment:20 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.1 to sage-5.3

comment:21 Changed 7 years ago by jdemeyer

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

comment:22 Changed 7 years ago by tjolivet

  • Authors changed from tjolivet to Timo Jolivet
  • Reviewers changed from vdelecroix to Vincent Delecroix

comment:23 Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This should be rebased to sage-5.2.rc1.

Changed 7 years ago by tjolivet

rebased to sage-5.2.rc1

comment:24 Changed 7 years ago by tjolivet

  • Status changed from needs_work to needs_review

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.

comment:25 Changed 7 years ago by 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
  1. I uploaded two patches which applies on top of Timo's one. The first fixes some documentation issues.
  1. 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.

Changed 7 years ago by slabbe

Changed 7 years ago by slabbe

comment:26 Changed 7 years ago by slabbe

  • Status changed from needs_review to needs_work
  1. 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!

comment:27 Changed 7 years ago by slabbe

  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Sébastien Labbé

Changed 7 years ago by tjolivet

apply after the three above patches

comment:28 Changed 7 years ago by 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

comment:29 Changed 7 years ago by 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

comment:30 Changed 7 years ago by tjolivet

  • Status changed from needs_work to positive_review

Changed 7 years ago by slabbe

Applies over all the preceding patches

comment:31 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.3.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:32 follow-up: Changed 18 months ago by jdemeyer

What's the rationale for code like

cm.__dict__["gist_gray"]

instead of more simply

cm.gist_gray

comment:33 in reply to: ↑ 32 Changed 18 months ago by tjolivet

Replying to jdemeyer:

What's the rationale for code like

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

Note: See TracTickets for help on using tickets.