Substitutions over unit cube faces (Rauzy fractals)

[videlec]

This patch introduces unit cube faces and substitutions over them, as defined in the article Pisot substitutions and Rauzy fractals by Arnoux and Ito.

Three new classes are defined:

• Face -- models a unit cube face
• Patch -- models a finite collection of faces
• E1Star -- models the the E_1!^(sigma)* substitution (over faces) defined by a unimodular substitution sigma

The plotting features enable us draw approximations of Rauzy fractals, or to generate patches of discrete planes.

The dimension of the faces can be of any dimension (and the substitutions work accordingly), but the plotting features work only in dimension three (with three-letter alphabet substitutions).

CC: @sagetrac-sage-combinat @seblabbe @sagetrac-abmasse @sagetrac-tmonteil

Component: combinatorics

Keywords: word morphism unit face generalized substitution rauzy fractal

Author: Vincent Delecroix, Timo Jolivet, Franco Saliola, Štěpán Starosta

Reviewer: Sébastien Labbé, Alexandre Blondin Massé

Merged: sage-4.6.1.alpha2

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

[seblabbe]

comment:3

I add myself in cc because I am interested.

[sagetrac-tjolivet]

Changed keywords from word morphism to word morphism unit face generalized substitution rauzy fractal

[sagetrac-tjolivet]

comment:4

Attachment: trac_8431_E1Star.patch.gz

[sagetrac-tjolivet]

Changed author from vdelecroix, sstarosta to vdelecroix, tjolivet, sstarosta

[mwhansen]

comment:7

I feel like Patch, Face, E1Star might be too domain specific to import into the global namespace.

[seblabbe]

comment:8

Cher Timo,

Thanks a lot for your recent effort in polishing that code. I am actually needing it rigth now!! It will be of great help to me.

I just read through the patch from my web browser and got those comments :

1. As Mike Hanson, I think those three classes should not be in the global namespace. To create a E1Star, I recommand to add a method in the WordMorphism class.
2. Add the file to the documentation. To do this you must edit the file sage-your-branch/doc/en/reference/combinat.rst
3. Each sage block must be preceded by ::.
4. No example using color in Face __init__ function.
5. Examples of all the possible drawings.
6. Rename _image_by_substitution to _apply_substitution in Face class.
7. Face._image_by_substitution should only accept E1Star object. If not, it should raise an TypeError and not try to coerce the input to an E1Star object.
8. Patch.translate method forgets the color of the faces.
9. Patch.apply_substitution should only accept E1Star object. If not, it should raise an TypeError and not try to coerce the input to an E1Star object.
10. _M and _inv_M should become lazy_attributes
11. _inv_M should be computed from _M
12. For the matrix method of E1Star, should _inv_M be the "matrix associated with self" more than _M ?
13. When I used these classes last week, I needed the method __eq__ for Patch. Here is my code :

    def __eq__(self, other):
        r"""
        EXAMPLES::

            TODO!!

        """
        return (isinstance(other, Patch) and
                set(self) == set(other) )

I am going to download, apply and use the patch real soon...and I guess I will have more comments...

[seblabbe]

Changed author from vdelecroix, tjolivet, sstarosta to Vincent Delecroix, Timo Jolivet, Stepan Starosta, Franco Saliola

[seblabbe]

comment:9

I suggest to add this example for the method __eq__ for Patch class :

    def __eq__(self, other):
        r"""
        EXAMPLES::
            
            sage: from sage.combinat.e_one_star import E1Star, Face, Patch
            sage: x = WordMorphism('0->02,1->012,2->2')
            sage: y = WordMorphism('0->012,1->12,2->2')
            sage: p = Patch([Face((0,0,0),1), Face((0,0,0),2), Face((0,0,0),3)])
            sage: E1Star(x) (p) == E1Star(y) (p)
            False
            sage: E1Star(x * y) (p) == E1Star(y) (E1Star(x) (p))
            True

        """
        return (isinstance(other, Patch) and
                set(self) == set(other) )

I also suggest to add a __len__ method and change the __repr__ to behave like Graphs (Graph of 45 vertices).

    def __repr__(self):
        r"""
        String representation of a patch.

        EXAMPLES:

            sage: x = [Face((0,0,0),t) for t in [1,2,3]]
            sage: P = Patch(x)
            sage: P
            Patch of 3 faces
        """
        return "Patch of %s faces"%len(self)

    def __len__(self):
        r"""
        Returns the number of faces.

        EXAMPLES::

            sage: x = [Face((0,0,0),t) for t in [1,2,3]]
            sage: P = Patch(x)
            sage: len(P)       #indirect doctest
            3
        """
        return len(self._faces)

[seblabbe]

comment:10

The method __call__ of E1Star should pass the possible kwds to apply_substitution method :

    def __call__(self, patch, **kwds):
        r"""
        EXAMPLES:

            sage: p = Patch([Face((0,0,0),t) for t in [1,2,3]])
            sage: sigma = WordMorphism('1->12,2->13,3->1')
            sage: E = E1Star(sigma)
            sage: E(p)
            Patch: [[(1, 0, -1), 1]*, [(0, 1, -1), 2]*, [(0, 0, 0), 3]*, [(0, 0, 0), 1]*, [(0, 0, 0), 2]*]
        """
        patch = Patch(patch)
        patch.apply_substitution(self, **kwds)
        return patch

[seblabbe]

comment:11

The last lines of plot_tikz should be :

        s += '\\end{tikzpicture}\n'
        return LatexExpr(s)

Make sure to add the following line in the beginning of the file :

from sage.misc.latex import LatexExpr

This is to avoid latex(a_patch.plot_tikz()) be edited wrongly.

[seblabbe]

comment:12

The function plot_tikz should be renamed _latex_.

A graph in Sage has methods plot, plot3d and _latex_ and I think we can follow the same behavior.

[sagetrac-tjolivet]

Changed author from Vincent Delecroix, Timo Jolivet, Stepan Starosta, Franco Saliola to Vincent Delecroix, Timo Jolivet, Franco Saliola, Stepan Starosta

[sagetrac-tjolivet]

small fixes

[sagetrac-tjolivet]

comment:36

Attachment: trac_8431-smallfixes-tj.patch.gz

Hi,

This patch (trac_8431-smallfixes-tj.patch) corrects three bugs and adds three minor features:

• in .plot_tikz, the option edgecolor='facecolor' didnt't work
• in .plot_tikz, the option print_tikz_env=False caused an error message
• in .plot3d, the plot was rotated uselessly (it was confusing)
• patches can now be added (which gives their union)
• E1Star morphisms can now be multiplied (according to the rule E1Star(st) = E1Star(t)E1Star(s))

Patches need to be applied in this order:

1. trac_8431_e_one_star.patch
2. trac_8431_review-sl.patch
3. trac_8431_might_be_final_tj.patch
4. trac_8431_colors_tikz-sl.patch
5. trac_8431_sigma_type_fix.patch
6. trac_8431-wordmorphism-sl.patch
7. trac_8431-smallfixes-tj.patch

[sagetrac-tjolivet]

comment:37

Replying to tjolivet:

• in .plot3d, the plot was rotated uselessly (it was confusing)

A precision about the .plot3d fix, the removal of these two lines:

911 P.aspect_ratio((1,1,1))
912 P = P.rotateY(pi/2).rotateX(pi/2)

The first line doesn't change anything. The only way to control the aspect ratio of the rendered object in Jmol is to include it into a cube that contains everything, because Jmol will automatically take the smallest 3D rectangle that contains the object, and deform it to a cube (hence changing the aspect ratio). If a cube bounds everything, we get an actual aspect ratio of (1,1,1).

The second line was initally written to "turn" the patch so that it faces the viewer when Jmol opens. The problem is that rotate does not change the point of view, but rotates the object itself, which is very confusing when we want to plot something else with the Patch (normal vectors or contracting planes, for example).

[sagetrac-tjolivet]

Attachment: trac_8431-alphaset-tj.patch.gz

[sagetrac-tjolivet]

comment:38

I just added a new patch (trac_8431-alphaset-tj.patch) that applies over the previous ones, and that allows to set the alpha parameter in the .plot method. It is useful if we want to plot fractals without seeing the unit cube edges.

[sagetrac-abmasse]

comment:39

Hi, Timo !

I tried applying the various patches on a sage-4.6 clone and the patch trac_8431-smallfixes-tj.patch fails. Here's what I get.

labo [~/Applications/sage/devel/sage-t8431/sage/combinat]
 $ hg qseries
trac_8431_e_one_star.patch
trac_8431_review-sl.patch
trac_8431_might_be_final_tj.patch
trac_8431_colors_tikz-sl.patch
trac_8431_sigma_type_fix.patch
trac_8431-wordmorphism-sl.patch
trac_8431-smallfixes-tj.patch

labo [~/Applications/sage/devel/sage-t8431/sage/combinat]
 $ hg qtop
trac_8431-smallfixes-tj.patch

labo [~/Applications/sage/devel/sage-t8431/sage/combinat]
 $ hg qpop
now at: trac_8431-wordmorphism-sl.patch

labo [~/Applications/sage/devel/sage-t8431/sage/combinat]
 $ hg qpush
applying trac_8431-smallfixes-tj.patch
patching file sage/combinat/e_one_star.py
Hunk #6 FAILED at 1337
1 out of 7 hunks FAILED -- saving rejects to file sage/combinat/e_one_star.py.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_8431-smallfixes-tj.patch

Could you please fix it? Or is it because the order is not correct? Here's the output for the rejected hunk:

labo [~/Applications/sage/devel/sage-t8431/sage/combinat]
 $ cat e_one_star.py.rej 
--- e_one_star.py
+++ e_one_star.py
@@ -1230,49 +1338,6 @@
                 X[letter].append((v, k))
         return X
 
-    def __call__(self, patch, iterations=1):
-        r"""
-        Apply a generalized substitution to a Patch; this returns a new
-        object.
-        
-        The color of every new face in the image is given the same color as its preimage.
-
-        INPUT:
-
-        - ``patch`` - a patch
-        - ``iterations`` - integer (optional, default: 1) number of iterations
-
-        OUTPUT:
-            
-            a patch
-
-        EXAMPLES::
-
-            sage: from sage.combinat.e_one_star import E1Star, Face, Patch
-            sage: P = Patch([Face((0,0,0),t) for t in [1,2,3]])
-            sage: sigma = WordMorphism({1:[1,2], 2:[1,3], 3:[1]})
-            sage: E = E1Star(sigma)
-            sage: R = E(P)
-            sage: len(R)
-            5
-
-        ::
-
-            sage: x = (0,0,0)
-            sage: p = Patch([Face(x, 1, 'red'), Face(x, 2, 'yellow'), Face(x, 3, 'green')])
-            sage: p = E(p, iterations=4)
-            sage: p
-            Patch of 31 faces
-        """
-        old_faces = patch
-        for i in xrange(iterations):
-            new_faces = []
-            for f in old_faces:
-                new_faces.extend(self._call_on_face(f, color=f.color()))
-            old_faces = new_faces
-
-        return Patch(new_faces)
-
     def _call_on_face(self, face, color=None):
         r"""
         Returns an iterator of faces obtained by applying self on the face.

[sagetrac-tjolivet]

comment:40

Hi !

Well, that's very strange: I just compiled 4.6, made a fresh clone, and I could apply all the patches without any problem:

timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qseries
trac_8431_e_one_star.patch
trac_8431_review-sl.patch
trac_8431_might_be_final_tj.patch
trac_8431_colors_tikz-sl.patch
trac_8431_sigma_type_fix.patch
trac_8431-wordmorphism-sl.patch
trac_8431-smallfixes-tj.patch
trac_8431-alphaset-tj.patch
timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qtop
trac_8431-alphaset-tj.patch
timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qpop
now at: trac_8431-smallfixes-tj.patch
timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qpop
now at: trac_8431-wordmorphism-sl.patch
timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qpush
applying trac_8431-smallfixes-tj.patch
now at: trac_8431-smallfixes-tj.patch
timo@ukko:~/sage-4.6/devel/sage-haha$ ../../sage -hg qpush
applying trac_8431-alphaset-tj.patch
now at: trac_8431-alphaset-tj.patch

Could you try it again? There's no reason that it works for me but not for you!

(And don't forget the last patch trac_8431-alphaset-tj.patch !)

To recap, the order is:

1. trac_8431_e_one_star.patch
2. trac_8431_review-sl.patch
3. trac_8431_might_be_final_tj.patch
4. trac_8431_colors_tikz-sl.patch
5. trac_8431_sigma_type_fix.patch
6. trac_8431-wordmorphism-sl.patch
7. trac_8431-smallfixes-tj.patch
8. trac_8431-alphaset-tj.patch

[BTW, a question: when I need to apply such a sequence of patches, do I have to do "import, qpush, import, qpush, import, qpush, ...", with an import and a qpush for each patch ?]

[sagetrac-tjolivet]

comment:41

Attachment: trac_new-fixes-final-tj.patch.gz

Hi. Sorry, this error message was because of a manipulation error from my part. (I misapplied the wordmorphism-sl patch, and my two last patches were based on this misapplying.)

I made a new patch that applies correctly over wordmorphism-sl, and that takes into account my two last patches (which should now be ignored; it's a shame that we can't delete patches from the ticket!).

Patches should be applied in this order:

1. trac_8431_e_one_star.patch
2. trac_8431_review-sl.patch
3. trac_8431_might_be_final_tj.patch
4. trac_8431_colors_tikz-sl.patch
5. trac_8431_sigma_type_fix.patch
6. trac_8431-wordmorphism-sl.patch
7. trac_new-fixes-final-tj.patch

(Sorry for misnaming the last patch, I forgot "8431"... And sorry if this made you lose some time!)

[sagetrac-tjolivet]

Attachment: trac_8431_typos-docfix-tj.patch.gz

[sagetrac-tjolivet]

comment:42

Thanks for you final remarks. The last patch is trac_8431_typos-docfix-tj.patch, and the sequence is:

1. trac_8431_e_one_star.patch
2. trac_8431_review-sl.patch
3. trac_8431_might_be_final_tj.patch
4. trac_8431_colors_tikz-sl.patch
5. trac_8431_sigma_type_fix.patch
6. trac_8431-wordmorphism-sl.patch
7. trac_new-fixes-final-tj.patch
8. trac_8431_typos-docfix-tj.patch

[sagetrac-abmasse]

Apply on top of preceding patches

[sagetrac-abmasse]

comment:43

Attachment: trac_8431_doctest_fix-abm.patch.gz

Hi Timo and Sébastien !

I just uploaded a (I hope last) patch that fixes a minor doctest failure (decimal number, on my computer but not Timo's).

I tested all of it on sage-4.6. I'm satisfied with the code and the documentation looks good (no warning neither).

Before setting this ticket to "positive review", I want to know if Sébastien is ok with it, since he reviewed big parts, and if Timo agrees with my last patch (Timo, just make sure it still passes on your machine).

[sagetrac-tjolivet]

comment:44

Yes, the patch applies fine, and the doctest passes. Everything seems to be fine now.

Just a recap:

1. trac_8431_e_one_star.patch
2. trac_8431_review-sl.patch
3. trac_8431_might_be_final_tj.patch
4. trac_8431_colors_tikz-sl.patch
5. trac_8431_sigma_type_fix.patch
6. trac_8431-wordmorphism-sl.patch
7. trac_new-fixes-final-tj.patch
8. trac_8431_typos-docfix-tj.patch
9. trac_8431_doctest_fix-abm.patch

[seblabbe]

comment:45

Before setting this ticket to "positive review", I want to know if Sébastien is ok with it, since he reviewed big parts, and if Timo agrees with my last patch (Timo, just make sure it still passes on your machine).

All test pass on my machine. Coverage is 100%. Documentation builds fine. Positive review!

I just folded the 9 patches into one : trac_8431_folded.patch. It might be easier for the release manager.

Great work!

[jdemeyer]

comment:46

1. Please update the commit message of the folded patch (use hg qrefresh -e for that). Make sure the first line contains the ticket number and a short summary of the whole patch. The next lines can contain a longer description.

2. The copyright message in the files MUST be changed to state

#  Distributed under the terms of the GNU General Public License (GPL) 
#  as published by the Free Software Foundation; either version 2 of 
#  the License, or (at your option) any later version.  
#                  http://www.gnu.org/licenses/  
#***************************************************************************** 

[seblabbe]

Folded all the 9 appropriate patches.

[seblabbe]

comment:47

Attachment: trac_8431_folded.patch.gz

I just re-uploaded the folded patch.

1. Please update the commit message of the folded patch (use hg qrefresh -e for that).

Done.

2. The copyright message in the files MUST be changed to state

Done. I did not know the copyright message changed.

Needs review.

[sagetrac-abmasse]

comment:48

I just checked that the fixes required by the release manager have indeed been done.

All tests still pass.

Positive review.

[jdemeyer]

Merged: sage-4.6.1.alpha2

[fchapoton]

Changed author from Vincent Delecroix, Timo Jolivet, Franco Saliola, Stepan Starosta to Vincent Delecroix, Timo Jolivet, Franco Saliola, Štěpán Starosta