Support for one-dimensional shifts of finite type

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Hi, as discussed with some people from the SAGE combinat group I (together with two students of mine) developed a class for subshifts of finite type which I would like to get feedback on and which could (hopefully should) be included into SAGE eventually.

The code already includes the basic features for playing around with those symbolic dynamical systems, but of course it will be extended over time. Just thought it would be nice to get some feedback on this first version right now, especially as the code is already long.

Apply:

• attachment: trac_12996_SFT_final_version-MHS.patch
• attachment: trac_12996_SFT_addressed_final_comments-MHS.patch
• attachment: trac_12996_SFT_ouput_shortened-MHS.patch
• attachment: trac12996_SFT_output_modified_methods_renamed-MHS.patch
• attachment: trac_12996_SFT_solved_warnings-MHS.patch

CC: @sagetrac-tmonteil @videlec @sagetrac-tjolivet @seblabbe

Component: combinatorics

Keywords: symbolic dynamics

Author: Michael Schraudner

Branch/Commit: public/12996 @ 5b28e76

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

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Changed keywords from symblic dynamics to symbolic dynamics

[edd8e884-f507-429a-b577-5d554626c0fe]

comment:2

Hi Michael,

i got the following error :

IndentationError: unindent does not match any outer indentation level (finite_type_shift.py, line 2415)

One space is missing at line 2415. After fixing this, the tests do pass.

Also, don't forget to add yourself on the first page of the trac.

[a-andre]

comment:4

You often wrote

arbitrary text:
::

use

arbitrary text::

instead (notice the colons).

You need to add a proper commit message to the patch.

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

first version of a class providing support for one-dimensional shifts of finite type

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:5

Attachment: trac12996_initial.patch.gz

Fixed the indentation error on line 2415. Changed all the :: issues mentioned by aapitzsch

[seblabbe]

comment:7

Hi,

I looked very quickly at the code on a friend's computer, and suggest to chqnge the code of the method entropy from:

if logarit == True:
    if self._is_empty:
        return -Infinity
    else:
        return log(max([x for x in self._matrix.eigenvalues()
                          if x in RR]))
elif logarit == False:
    if self._is_empty:
        return 0
    else:
        return max([x for x in self._matrix.eigenvalues() if x in RR])
else:
    raise ValueError("logarit must be either True or False")

to:

if self._is_empty:
    if logarit:
        return -Infinity
    else:
        return 0
else:
    M = max([x for x in self._matrix.eigenvalues() if x in RR])
    if logarit:
        return log(M)
    else:
        return M

This is simply an example to show how to deal with conditions and booleans. Also, in this case, the value error was not necessary since python will return an error if logarith does not evaluate to a bool.

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Taken care of slabbe's comment (entropy method and boolean handling)

[videlec]

comment:9

Attachment: trac12996_initial_v1.1.patch.gz

I get a warning while building the doc

/opt/sage-5.1.rc1/devel/sage/doc/en/reference/dynamics.rst:4: WARNING: toctree contains reference to nonexisting document u'sage/dynamics/symbolic/finite_type_shift'

does it work for you?

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:10

Hi,

I also get doc building warnings, which (as usual) are due to some minor formatting errors.

Otherwise all the tests pass on my sage 5.0.1.

I've played quite a lot with the SFT class, I found it very usable and found no bugs. Thanks!

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:11

Hi, thanks for the comments.

So what do I have to do now? How can I get rid of the doc build warnings? What else is needed to get a positive review?

Replying to @sagetrac-tjolivet:

Hi,

I also get doc building warnings, which (as usual) are due to some minor formatting errors.

Otherwise all the tests pass on my sage 5.0.1.

I've played quite a lot with the SFT class, I found it very usable and found no bugs. Thanks!

[seblabbe]

comment:12

So what do I have to do now? How can I get rid of the doc build warnings?

How many warnings do you get when building the documentation ? You need to fix all of them. That being said, the warning are not always self-expaining...

sage -b && sage -docbuild reference html

After taking a look at the patch, I believe many of the warning are of the same type. Indeed, an empty line is needed before any enumeration. Instead of

        - ``format`` - (default: 'edge') this flag selects one of two possible 
          representations for the SFT: 
            - 'vertex' - a representation of the SFT as a vertex shift 
            - 'edge' - a representation of the SFT as an edge shift 
          If this parameter is not provided in the constructor the 'edge' 
          representation is chosen by default. 

you need to write

        - ``format`` - (default: 'edge') this flag selects one of two possible 
          representations for the SFT: 

            - 'vertex' - a representation of the SFT as a vertex shift 
            - 'edge' - a representation of the SFT as an edge shift 
          If this parameter is not provided in the constructor the 'edge' 
          representation is chosen by default. 

How many warnings do you get when you add those empty lines before every enumeration?

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:13

Hey slabbe, thanks for the comment. I tried it, but still get some docbuild warnings, see below. It appears there are empty lines missing also after certain blocks, but I dont know exactly where.

Is there any way to see where exactly they are produced? the numbers seem not to match line numbers in the .py file. Is there any good reference for sphinx or the syntax I should use for SAGE to build the doc without warnings?

Very annoying this sphinx thing!

Any comment very welcome. Thanks. MHS

sphinx-build -b html -d /usr/sage-4.8/devel/sage/doc/output/doctrees/en/reference /usr/sage-4.8/devel/sage/doc/en/reference /usr/sage-4.8/devel/sage/doc/output/html/en/reference

Running Sphinx v1.1.2

loading pickled environment... done

building [html]: targets for 1 source files that are out of date

updating environment: 0 added, 1 changed, 0 removed

reading sources... [100%] sage/dynamics/symbolic/finite_type_shift

/usr/sage-4.8/local/lib/python2.6/site-packages/sage/dynamics/symbolic/finite_type_shift.py:docstring of sage.dynamics.symbolic.finite_type_shift.SFT.bowen_franks_group:143: WARNING: Inline substitution_reference start-string without end-string.

/usr/sage-4.8/local/lib/python2.6/site-packages/sage/dynamics/symbolic/finite_type_shift.py:docstring of sage.dynamics.symbolic.finite_type_shift.SFT.draw_graph:14: WARNING: Inline strong start-string without end-string.

looking for now-outdated files... none found

pickling environment... done

checking consistency... /usr/sage-4.8/devel/sage/doc/en/reference/sage/dynamics/symbolic/finite_type_subshift.rst:: WARNING: document isn't included in any toctree

done

preparing documents... done

writing output... [ 33%] dynamics

writing output... [ 66%] index

writing output... [100%] sage/dynamics/symbolic/finite_type_shift

[5173d111-1d42-477d-8dcf-3dafadf95618]

doc errors fixing

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:14

Attachment: 12996-docfix-tj.patch.gz

Hi, I uploaded a patch which fixes the 18 docbuild errors/warnings I had on my machine (I hope it works on other systems as well). These were quite nasty to find, it can drive one crazy.

The most common were : no blank line after at the end of a "-" list of items.

There was also the special character sequence that consists of two concatenated "*", which placed alone in text caused problems.

I fixed a few other things as well.

Having used the patch and analysed it I'd be ready to give it a positive review.

Also, one of the most useful and not-too-long-to-implement would be state splittings/amalgamations which are very easy to program using matrix line/columns operations (already in Sage :p).

[seblabbe]

comment:15

Is there any way to see where exactly they are produced? the numbers seem not to match line numbers in the .py file. Is there any good reference for sphinx or the syntax I should use for SAGE to build the doc without warnings?

Very annoying this sphinx thing!

Yes... it is. The number refers to the line number inside each doctring, but you don't know which... By chance, we write documentation almost always the same way and there are few rules to learn. Here is what I suggest. You first read

http://docutils.sourceforge.net/docs/user/rst/quickref.html

Then, you practice yourself with the script SAGE_ROOT/local/bin/rst2html.py

For example, you copy a doctring between r""" and """ of your file into a file fichier.rst like this one:

INPUT: 

- ``init_obj`` - (default: None) can be any of the following: 
    - a directed (multi)graph 
    - a square matrix with non-negative integer entries 
    - a list of forbidden words (over some alphabet) either given as 
        - a list of strings (with or without symbol separators), e.g. 
          ['11', '123', '4'] (no separator) or ['1.1', '1.2.3', '4'] 
          ('.' used as separator) 
        - a list of lists containing elements of the alphabet, e.g. 
          [[1, 1], [1, 2, 3], [4]] or [['a', 'a'], ['a', 'b', 'b']] 
        - a list of instances of the SAGE class Words (over the alphabet), 
          e.g. [Word("11"), Word(["1", "2", "3"]), Word("4")] 
  If this parameter is not provided the full-shift over the specified 
  alphabet will be created. If neither this parameter nor an alphabet 
  is given the empty shift will be created. 

- ``alph`` - (default: None) a list of symbols (the alphabet) used in the 
  definition of the SFT. If this parameter is not provided a standard 
  alphabet will be created (whenever possible) from the ``init_obj``. The 
  elements of the alphabet can be general SAGE objects which do not 
  contain the substring ``symb_sep`` in their string representation. 
  Nevertheless it is preferable to use symbols which are either 
  non-negative integers or short strings (e.g. single letters). 

  The alphabet is not allowed to contain repetitions (literal copies as 
  well as symbols whose string representations do coincide) and whenever 
  its elements have distinct lengths the use of ``symb_sep`` is strongly 
  advised. We also highly recommend the use of unambiguous alphabets! 

Then, you call the following command on it :

$ ~/Applications/sage-5.2/local/bin/rst2html.py fichier.rst fichier.html
fichier.rst:14: (WARNING/2) Definition list ends without a blank line; unexpected unindent.

Now, the number 14 refers really to the line 14 in the file fichier.rst. You may also open the html file to see where is the warning :

$ open fichier.html

You may also copy and paste docstring into this website I just found and never used before :

http://rst.ninjs.org/

[seblabbe]

comment:16

After taking a look at the patch, I believe many of the warning are of the same type. Indeed, an empty line is needed before any enumeration.

I now think the empty line is needed after not before any enumeration... sorry. I usually put empty lines before and after...and forgot only after was giving warnings...

[seblabbe]

comment:17

I am becoming fool, from http://docutils.sourceforge.net/docs/user/rst/quickref.html, a blank line should be needed before as well as after:

Note that a blank line is required
before the first item and after the
last, but is optional between items. 

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:18

Thanks slabbe, for your comments and thanks tjolivet for the update on the patch. I will check it tomorrow. As you said there are some methods not yet implemented which would be nice (like the splittings and amalgamations). Also we already have some additional methods which I did not include in the first patch (which is quiet long already), but which can be included in a second step.

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:19

tjolivet, I attached a new version of the patch. Now the docbuild should not produce any warnings and I also included the methods for admissible words (2) and an_element.

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:20

Hi,

I still get 22 warnings when building the doc.

It seems that your patch doesn't take into account the doc fixes I provided. (All the blank lines and the little details I fixed in my patch.) Did you forget to apply the patch?

Cheers, Timo

[5173d111-1d42-477d-8dcf-3dafadf95618]

Description changed:

--- 
+++ 
@@ -2,3 +2,5 @@

 The code already includes the basic features for playing around with those symbolic dynamical systems, but of course it will be extended over time. Just thought it would be nice to get some feedback on this first version right now, especially as the code is already long.

+Apply trac_12996_SFT_final_version-MHS.patch
+

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Attachment: trac_12996_SFT_final_version-MHS.patch.gz

The (hopefully) last version, resolved docbuild warnings and included admissible words methods

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:22

I'm now ready to give the patch a positive review.

For the patchbot:

Apply trac_12996_SFT_final_version-MHS.patch

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:23

Replying to @sagetrac-tjolivet:

I'm now ready to give the patch a positive review.

For the patchbot:

Apply trac_12996_SFT_final_version-MHS.patch

So what else is needed to close this patch with a positive outcome?

[videlec]

comment:24

hi,

Few more remarks

• the output is too verbose. When I print a number I do not want to see "Number 3112. It is not prime and its divisors are 1, 2, 4, 8, 389, 778, 1556 and 3112." but only "3112". The same for shifts. Methods are here to get more informations.

• Because you inherit from SageObject, the method repr with two underscores should be modified into a repr with one underscore (see the code and the documentation of SageObject). In particular, SageObject takes care of custom names.

• the option "alph" is named "alphabet" in the words library but they should have the same name·

• the alphabet in your class are lists but there is a class for alphabet in sage.combinat.words.alphabet, why not using it?

• The name of the method an_element is not appropriate. an_element should return an element of the subshift.

Vincent

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:25

Hi Vincent,

I addressed most of your comments:

• renamed method "repr" to "repr". (although I still dont see the difference - I looked at the documentation of SageObject, but did not get the point - can you explain this, maybe in a private email)
• renamed option "alph" to "alphabet"
• the option "alphabet" accepts as input both a list and an alphabet (as defined in the word class), so externally there is no difference. Internally I prefer the standard type list - it has less overhead, especially as it is accessed a lot in building admissible words etc.
• changed documentation of "an_element". Your comment seems to be based on a misunderstanding as the method already DID return an element of the SFT in form of an iterator - how else would you represent an infinite sequence of symbols? Comments welcome.

Your first comment is not yet addressed, as I dont know what you would like to see as output. If the SFT has a name this name is returned, but if it does not? The method could just return "An SFT", but what is the point of this, you could just check "isinstance" - it is not very informative, so I thought having at least the alphabet would be helpful. Any suggestions on this from your side would be very welcome.

Best M.

Replying to @videlec:

hi,

Few more remarks

• the output is too verbose. When I print a number I do not want to see "Number 3112. It is not prime and its divisors are 1, 2, 4, 8, 389, 778, 1556 and 3112." but only "3112". The same for shifts. Methods are here to get more informations.

• Because you inherit from SageObject, the method repr with two underscores should be modified into a repr with one underscore (see the code and the documentation of SageObject). In particular, SageObject takes care of custom names.

• the option "alph" is named "alphabet" in the words library but they should have the same name·

• the alphabet in your class are lists but there is a class for alphabet in sage.combinat.words.alphabet, why not using it?

• The name of the method an_element is not appropriate. an_element should return an element of the subshift.

Vincent

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Attachment: trac_12996_SFT_addressed_final_comments-MHS.patch.gz

Addressed the comments by vdelecroix

[videlec]

comment:26

Hi Michael,

• renamed method "repr" to "repr". (although I still dont see the difference - I looked at the documentation of SageObject, but did not get the point - can you explain this, maybe in a private email) Your first comment is not yet addressed, as I dont know what you would like to see as output. If the SFT has a name this name is returned, but if it does not? The method could just return "An SFT", but what is the point of this, you could just check "isinstance" - it is not very informative, so I thought having at least the alphabet would be helpful. Any suggestions on this from your side would be very welcome.

The SageObject implements custom names and it is not needed to reimplement it

sage: class A(SageObject): 
....:     pass
sage: a = A()           
sage: a
<class '__main__.A'>
sage: a.rename('toto')
sage: a
toto
sage: a.reset_name()
sage: a
<class '__main__.A'>

The method __repr__ of SageObject precisely choose whether to use the custom name or the method _repr_ that are implemented in derived classes.

• renamed option "alph" to "alphabet"
• the option "alphabet" accepts as input both a list and an alphabet (as defined in the word class), so externally there is no difference. Internally I prefer the standard type list - it has less overhead, especially as it is accessed a lot in building admissible words etc.

Cool! I hope that in a next future it would be simpler and faster to use alphabet.

• changed documentation of "an_element". Your comment seems to be based on a misunderstanding as the method already DID return an element of the SFT in form of an iterator - how else would you represent an infinite sequence of symbols? Comments welcome.

I agree that mathematically the sequence belongs to the SFT but as a Python object it is an iterator and not an element of the subshift. What I mean by an element is something that knows what its parent is. In other words with the following behavior

sage: S = MySFT()
sage: S
My SFT
sage: s = S.an_element()
sage: s in S
True
sage: s.parent()
My SFT

(the notion of element/parent is explained in the Sage reference http://www.sagemath.org/doc/reference/coercion.html)

In your case you may use infinite which can be initialized from iterators. A basic example is as follows

sage: W = Words('ab')
sage: from itertools import count
sage: W('a' if (n%5+1)%3 else 'b' for n in count())
word: aabaaaabaaaabaaaabaaaabaaaabaaaabaaaabaa...

Anyway, the issue about element/parent will be solved with the "categorification" of shifts and languages (ticket #12224).

• the output is too verbose. When I print a number I do not want to see "Number 3112. It is not prime and its divisors are 1, 2, 4, 8, 389, 778, 1556 and 3112." but only "3112". The same for shifts. Methods are here to get more informations.

My comment about the output is no more than a comment. I find it too verbose but I do not know what is better. For graphs the ouptut is simply "Graph on 12 vertices". You may choose "SFT over {a, b, c}" where {a, b, c} is replaced by whatever is the alphabet but you may prefer as well to keep the old version.

Hoping that the definitive version is not far away.

Best, Vincent

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:27

Apply trac_12996_SFT_final_version-MHS.patch trac_12996_SFT_addressed_final_comments-MHS.patch

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Shortened output and renamed an_element method

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:28

Attachment: trac_12996_SFT_ouput_shortened-MHS.patch.gz

Apply trac_12996_SFT_final_version-MHS.patch trac_12996_SFT_addressed_final_comments-MHS.patch trac_12996_SFT_ouput_shortened-MHS.patch

[seblabbe]

comment:29

They put comma here : http://wiki.sagemath.org/buildbot, so let's try this syntax :

Apply trac_12996_SFT_final_version-MHS.patch, trac_12996_SFT_addressed_final_comments-MHS.patch, trac_12996_SFT_ouput_shortened-MHS.patch

[robertwb]

comment:30

Apply only trac_12996_SFT_final_version-MHS.patch, trac_12996_SFT_addressed_final_comments-MHS.patch, trac_12996_SFT_ouput_shortened-MHS.patch

[videlec]

comment:31

Hi all,

ping

What is the status of that ticket ? My question is partly because of ticket #12224 which modifies the structure of words. There are evident conflict with this one, but it won't be hard to merge them (I can even do it). I suggest that this one goes first, in which case I will put a dependency on #12224 and do the merge within #12224.

Comment on last modifications:

• you used "on {a,b,c}" instead of "over {a,b,c}" which is currently in used in words

What do you think ?

Best, Vincent

[videlec]

comment:32

Hello,

Some more comments:

• At the begining of the file finite_type_shift.py you modify the global behavior of warnings! It can not be done that way as you affect the whole SAGE.
• the two methods admissible_words_iter and forbidden_words_iter may be renamed in admissible_word_iterator and forbidden_word_iterator (which is more how other iterator methods looks like within SAGE). Moreover, both of them may use the SearchForest in sage.combinat.backtrack which is dedicated to that sort of iteration... you will end up with 3 lines algorithms! I may help if you are stuck with the use of SearchForest.
• a_point_iter must be renamed as random_element; or an_element if it is not random (Sage standards).

Cheers, Vincent

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:33

Hi, some quick comments on the previous ones:

1) Can anybody tell me how to do this? I understand (and agree) that it is not good coding practice, but I would like to have the warnings show up every time in my class SFT. Is there a way to alter the behaviour just for the methods in a single class? (I did look at the Python documentation, but did not find anything specific.)

2+3) I will do this. No problem here.

Thanks. Best Michael

[videlec]

comment:34

Hi,

1) I can solve half of the problem. For affecting only your module for the "always" part, you just need to replace

warnings.simplefilter("always")

by

warnings.filterwarnings(action="always",
                        module="sage.dynamics.symbolic.finite_type_shift")

For the formatting, I don't think there is a viable solution. Moreover, the way you do corresponds to modify the library (Python is sometimes dangerous)! So I propose you to just let the format as it is by default.

Hope to see the last changes soon in order to put a positive review! Vincent

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

"SFT over alphabet" modification and methods admissible_words_iterator, forbidden_words_iterator, random_element renamed

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:35

Attachment: trac12996_SFT_output_modified_methods_renamed-MHS.patch.gz

Hi all,

coming back from my summer vacations I uploaded a new patch.

1) I changed the output from "A SFT on alphabet" to "A SFT over alphabet" 2) I changed the names of three methods (as indicated by vdelecroix) 3) I changed the "warnings" line, so only my module is affected (thanks for pointing out how to do this vdelecroix) 4) I played around with the SearchForest, but fially decided to keep the code as was before (I was not able to use SearchForest to produce the admissible words in the order I intended) and with a postprocessing step the code is clumpsy and slower

One final thing to do: If I delete the "warnings.formatwarning = sft_warning_style" line 130 the output of two tests (producing a Warning) are modified including a file name and a non-standard line number which gets me into trouble with the doctest. Any idea how to tell SAGE to ignore the filename and line-number in the output of the doctest?

Best M.

[seblabbe]

comment:36

Replying to @sagetrac-mhs:

One final thing to do: If I delete the "warnings.formatwarning = sft_warning_style" line 130 the output of two tests (producing a Warning) are modified including a file name and a non-standard line number which gets me into trouble with the doctest. Any idea how to tell SAGE to ignore the filename and line-number in the output of the doctest?

In the output of a doctest, you can put three dots ... and it replaces anything. Like * does for regular expression. Of course, use it parsimoniously by replacing only the line-number by the three dots.

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

removed personal warnings style, all doctests pass

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

comment:37

Attachment: trac_12996_SFT_solved_warnings-MHS.patch.gz

Replying to @seblabbe:

Replying to @sagetrac-mhs:

One final thing to do: If I delete the "warnings.formatwarning = sft_warning_style" line 130 the output of two tests (producing a Warning) are modified including a file name and a non-standard line number which gets me into trouble with the doctest. Any idea how to tell SAGE to ignore the filename and line-number in the output of the doctest?

In the output of a doctest, you can put three dots ... and it replaces anything. Like * does for regular expression. Of course, use it parsimoniously by replacing only the line-number by the three dots.

Great, this is exactly what I needed to know. Thanks a lot!

I modified the file accordingly, so the warning style is not changed and still the doctests pass. I hope this is all that is needed to close this ticket. Thanks for all your help and comments.

[fchapoton]

Description changed:

--- 
+++ 
@@ -2,5 +2,6 @@

 The code already includes the basic features for playing around with those symbolic dynamical systems, but of course it will be extended over time. Just thought it would be nice to get some feedback on this first version right now, especially as the code is already long.

-Apply trac_12996_SFT_final_version-MHS.patch
+Apply:
+* [attachment: trac_12996_SFT_final_version-MHS.patch](https://github.com/sagemath/sage-prod/files/10655597/trac_12996_SFT_final_version-MHS.patch.gz)

[fchapoton]

comment:38

Could you please write in the description what tickets have to be applied ?

[19709a2d-17f6-499d-a0c2-3fb18af54b3f]

Description changed:

--- 
+++ 
@@ -4,4 +4,8 @@

 Apply:
 * [attachment: trac_12996_SFT_final_version-MHS.patch](https://github.com/sagemath/sage-prod/files/10655597/trac_12996_SFT_final_version-MHS.patch.gz)
+* [attachment: trac_12996_SFT_addressed_final_comments-MHS.patch](https://github.com/sagemath/sage-prod/files/10655598/trac_12996_SFT_addressed_final_comments-MHS.patch.gz)
+* [attachment: trac_12996_SFT_ouput_shortened-MHS.patch](https://github.com/sagemath/sage-prod/files/10655599/trac_12996_SFT_ouput_shortened-MHS.patch.gz)
+* [attachment: trac12996_SFT_output_modified_methods_renamed-MHS.patch](https://github.com/sagemath/sage-prod/files/10655600/trac12996_SFT_output_modified_methods_renamed-MHS.patch.gz)
+* [attachment: trac_12996_SFT_solved_warnings-MHS.patch](https://github.com/sagemath/sage-prod/files/10655601/trac_12996_SFT_solved_warnings-MHS.patch.gz)

[5173d111-1d42-477d-8dcf-3dafadf95618]

comment:40

It seems about time to give this ticket a positive review, but why has the patchbot always been refusing to apply the patches?

[seblabbe]

comment:41

because you first need to get one patch into Sage for the patchbot to trust you.

[seblabbe]

comment:42

1. The file doc/en/reference/index.rst changed in a recent version of Sage. Hence, there is now a small reject with the first patch which should be fixed :

sage-5.8/devel/sage-slabbe $ hg qpush
applying trac_12996_SFT_final_version-MHS.patch
patching file doc/en/reference/index.rst
Hunk #1 FAILED at 58
1 out of 1 hunks FAILED -- saving rejects to file doc/en/reference/index.rst.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_12996_SFT_final_version-MHS.patch
10 slabbe@pol ~/Applications/sage-5.8/devel/sage-slabbe $ cat doc/en/reference/index.rst.rej
--- index.rst
+++ index.rst
@@ -59,6 +59,7 @@
    cryptography
    logic
    combinat/index
+   dynamics
    numerical
    probability
    stats 

2. The coverage of the folder sage/dynamics/symbolic is not 100% as it should:

sage/dynamics/symbolic $ sage -coverage .
------------------------------------------------------------------------
No functions in ./__init__.py
------------------------------------------------------------------------
No functions in ./all.py
------------------------------------------------------------------------
SCORE ./finite_type_shift.py: 83.3% (35 of 42)

Missing documentation:
     * line 129: def sft_warning_style(msg, category, filename, lineno, file=None, line=None)

Missing doctests:
     * line 2855: def _allwords(self, n)
     * line 2879: def _check_alph(self, n)
     * line 2915: def _create_empty(self)
     * line 2934: def _create_edge_label_DiGraph(self)
     * line 2972: def _create_vertex_label_DiGraph(self)
     * line 3002: def _create_fwords_DiGraph(self)
------------------------------------------------------------------------

I know it is hidden functions and so on, but they should be documented and doctested as any other.

3. I looked more carefully at the code for the first time. I realize that the SFT, which can be created from three distinct input types (digraph, matrix, forbidden words), compute everything at the creation of the SFT. For example:

   sage: X = SFT(["0101", "100"], alph=["0", "1"])  # computation of the matrix is done here
   sage: M = X.matrix()                             # not here

Since there is only one class for SFT, I understand why everything is computed in the init. Because, we want to make sure once the init is done, that every objects behave the same what ever input was given.

If I had to code such a class now, I would create four classes : SFT, SFT_from_digraph, SFT_from_matrix and SFT_from_forbidden_words. I would put methods that depends on the representation inside child classes and general methods in the top class.

class SFT(SageObject):
    def __classcall__(self, data):
        if data is a digraph:
            return SFT_from_digraph(data)
        elif data is a matrix:
            return SFT_from_matrix(data)
        if data is forbidden words:
            return SFT_from_forbidden_words(data)
    def matrix(self):
        raise NotImplementedError("this is a specific method and must be coded in the child class")
    def some_general_method(self):
        pass
class SFT_from_digraph(SFT):
    def __init__(self, data):
        self._graph = data
    def matrix(self):
        M = ... # compute the matrix from the graph
        return M
class SFT_from_matrix(SFT):
    def __init__(self, data):
        self._matrix = datta
    def matrix(self):
        return self._matrix
class SFT_from_forbidden_words(SFT):
    def __init__(self, data):
        self._forbidden = data
    def matrix(self)
        M = ... #compute the matrix from forbidden words
        return M

The advantage is that the code is closer to the reality (more clear, easier to maintain) and also more efficient (the matrix, for above example, is computed only if the user needs it).

This ticket is open since too long time. I feel bad for asking such modifications so late... Should we just make it get into Sage and make future improvements then? I am sure the code is usefull as it is now so... So Michael, what do you think? Are you still motivated to work on it now?

Sébastien

[fchapoton]

comment:43

instructions for the bot:

Apply trac_12996_SFT_final_version-MHS.patch trac_12996_SFT_addressed_final_comments-MHS.patch trac_12996_SFT_ouput_shortened-MHS.patch trac12996_SFT_output_modified_methods_renamed-MHS.patch trac_12996_SFT_solved_warnings-MHS.patch

[fchapoton]

comment:44

better instructions:

Apply trac_12996_SFT_final_version-MHS.patch trac_12996_SFT_addressed_final_comments-MHS.patch trac_12996_SFT_ouput_shortened-MHS.patch trac12996_SFT_output_modified_methods_renamed-MHS.patch trac_12996_SFT_solved_warnings-MHS.patch