Support for one-dimensional shifts of finite type

[sagetrac-mhs]

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

[sagetrac-mhs]

Changed keywords from symblic dynamics to symbolic dynamics

[sagetrac-tmonteil]

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.

[sagetrac-mhs]

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

[sagetrac-mhs]

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.

[sagetrac-mhs]

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?

[sagetrac-tjolivet]

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!

[sagetrac-mhs]

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?

[sagetrac-mhs]

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

[sagetrac-tjolivet]

doc errors fixing

[sagetrac-tjolivet]

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...

[fchapoton]

comment:38

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

[sagetrac-tjolivet]

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

[fchapoton]

comment:46

this does not apply and needs to be rebased

[videlec]

Branch: public/12996

[videlec]

Commit: 48bb9df

[videlec]

comment:50

Hello,

I am with Pierre Guillon in Marseille and we would like to put that patch in. I created a public branch for that and we will start from there.

Vincent

---

New commits:

4d62cc6	#12996 Support for one-dimensional shifts of finite type
9df1772	trac 12996: minor changes to address comments by vdelecroix
ad6fb46	trac 12996: shortened output, renamed an_element method
16f218a	c 12996: modified output, renamed three methods
48bb9df	trac 12996: solved warning style issue, solved doctests

[sagetrac-git]

Changed commit from 48bb9df to dacacd2

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

764a6e5	Merge branch 'public/12996' into 6.9.b0
dacacd2	trac #12996 making sure the doc builds

[fchapoton]

comment:53

+Missing doctests dynamics/symbolic/finite_type_shift.py 35 / 42 = 83%

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

38741de	Merge branch 'public/12996' into 7.3.b4
5b28e76	refresh the branch on top of 7.3.b4

[sagetrac-git]

Changed commit from dacacd2 to 5b28e76