Opened 7 years ago

Last modified 3 years ago

#12996 needs_work enhancement

Support for one-dimensional shifts of finite type

Reported by: mhs Owned by: sage-combinat
Priority: major Milestone: sage-6.9
Component: combinatorics Keywords: symbolic dynamics
Cc: tmonteil, vdelecroix, tjolivet, slabbe Merged in:
Authors: Michael Schraudner Reviewers:
Report Upstream: N/A Work issues:
Branch: public/12996 (Commits) Commit: 5b28e76952ecbda35d49eb6fd36ac50293b7cff2
Dependencies: Stopgaps:

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

Attachments (8)

trac12996_initial.patch (117.8 KB) - added by mhs 7 years ago.
first version of a class providing support for one-dimensional shifts of finite type
trac12996_initial_v1.1.patch (115.8 KB) - added by mhs 7 years ago.
Taken care of slabbe's comment (entropy method and boolean handling)
12996-docfix-tj.patch (20.9 KB) - added by tjolivet 7 years ago.
doc errors fixing
trac_12996_SFT_final_version-MHS.patch (130.5 KB) - added by mhs 7 years ago.
The (hopefully) last version, resolved docbuild warnings and included admissible words methods
trac_12996_SFT_addressed_final_comments-MHS.patch (8.5 KB) - added by mhs 7 years ago.
Addressed the comments by vdelecroix
trac_12996_SFT_ouput_shortened-MHS.patch (23.2 KB) - added by mhs 6 years ago.
Shortened output and renamed an_element method
trac12996_SFT_output_modified_methods_renamed-MHS.patch (28.8 KB) - added by mhs 6 years ago.
"SFT over alphabet" modification and methods admissible_words_iterator, forbidden_words_iterator, random_element renamed
trac_12996_SFT_solved_warnings-MHS.patch (2.5 KB) - added by mhs 6 years ago.
removed personal warnings style, all doctests pass

Download all attachments as: .zip

Change History (62)

comment:1 Changed 7 years ago by mhs

  • Cc thierry.monteil@… added
  • Keywords symbolic added; symblic removed
  • Status changed from new to needs_review

comment:2 Changed 7 years ago by tmonteil

  • Cc tmonteil added; thierry.monteil@… removed
  • Status changed from needs_review to needs_work

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.

comment:3 Changed 7 years ago by tmonteil

  • Cc vdelecroix tjolivet slabbe added

comment:4 Changed 7 years ago by aapitzsch

You often wrote

arbitrary text:
::

use

arbitrary text::

instead (notice the colons).

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

Changed 7 years ago by mhs

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

comment:5 Changed 7 years ago by mhs

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

Last edited 7 years ago by mhs (previous) (diff)

comment:6 Changed 7 years ago by mhs

  • Status changed from needs_work to needs_review

comment:7 Changed 7 years ago by slabbe

  • Status changed from needs_review to needs_work

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.

comment:8 Changed 7 years ago by mhs

  • Status changed from needs_work to needs_review

Changed 7 years ago by mhs

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

comment:9 Changed 7 years ago by vdelecroix

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?

comment:10 follow-up: Changed 7 years ago by 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!

comment:11 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by mhs

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

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by slabbe

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?

comment:13 follow-up: Changed 7 years ago by mhs

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

Changed 7 years ago by tjolivet

doc errors fixing

comment:14 Changed 7 years ago by tjolivet

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

Last edited 7 years ago by tjolivet (previous) (diff)

comment:15 in reply to: ↑ 13 Changed 7 years ago by slabbe

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/

comment:16 in reply to: ↑ 12 ; follow-up: Changed 7 years ago by slabbe

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

comment:17 in reply to: ↑ 16 Changed 7 years ago by slabbe

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. 

comment:18 Changed 7 years ago by mhs

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.

comment:19 Changed 7 years ago by mhs

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.

comment:20 Changed 7 years ago by tjolivet

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

comment:21 Changed 7 years ago by tjolivet

  • Description modified (diff)

Changed 7 years ago by mhs

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

comment:22 follow-up: Changed 7 years ago by tjolivet

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

For the patchbot:

Apply trac_12996_SFT_final_version-MHS.patch

comment:23 in reply to: ↑ 22 Changed 7 years ago by mhs

Replying to 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?

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

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

comment:25 in reply to: ↑ 24 ; follow-up: Changed 7 years ago by mhs

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 vdelecroix:

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

Changed 7 years ago by mhs

Addressed the comments by vdelecroix

comment:26 in reply to: ↑ 25 Changed 7 years ago by vdelecroix

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

comment:27 Changed 7 years ago by tjolivet

Apply trac_12996_SFT_final_version-MHS.patch trac_12996_SFT_addressed_final_comments-MHS.patch

Changed 6 years ago by mhs

Shortened output and renamed an_element method

comment:28 follow-up: Changed 6 years ago by mhs

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

comment:29 in reply to: ↑ 28 Changed 6 years ago by slabbe

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

comment:30 Changed 6 years ago by robertwb

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

comment:31 Changed 6 years ago by vdelecroix

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

comment:32 follow-up: Changed 6 years ago by vdelecroix

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

comment:33 in reply to: ↑ 32 Changed 6 years ago by mhs

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

comment:34 Changed 6 years ago by vdelecroix

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

Changed 6 years ago by mhs

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

comment:35 follow-up: Changed 6 years ago by mhs

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.

comment:36 in reply to: ↑ 35 ; follow-up: Changed 6 years ago by slabbe

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

Last edited 6 years ago by slabbe (previous) (diff)

Changed 6 years ago by mhs

removed personal warnings style, all doctests pass

comment:37 in reply to: ↑ 36 Changed 6 years ago by mhs

Replying to slabbe:

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

comment:38 Changed 6 years ago by chapoton

  • Description modified (diff)

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

comment:39 Changed 6 years ago by mhs

  • Description modified (diff)

comment:40 Changed 6 years ago by tjolivet

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

comment:41 Changed 6 years ago by slabbe

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

comment:42 Changed 6 years ago by slabbe

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

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

Last edited 6 years ago by slabbe (previous) (diff)

comment:43 Changed 6 years ago by chapoton

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

comment:44 Changed 6 years ago by chapoton

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

comment:45 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:46 Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

this does not apply and needs to be rebased

comment:47 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:48 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:49 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:50 Changed 5 years ago by vdelecroix

  • Branch set to public/12996
  • Commit set to 48bb9df776f38e67548cc75df41a0a040634365b

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
9df1772trac 12996: minor changes to address comments by vdelecroix
ad6fb46trac 12996: shortened output, renamed an_element method
16f218ac 12996: modified output, renamed three methods
48bb9dftrac 12996: solved warning style issue, solved doctests

comment:51 Changed 4 years ago by git

  • Commit changed from 48bb9df776f38e67548cc75df41a0a040634365b to dacacd2882c26fc9f48982b5f1c56c9cc64c6c5f

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

764a6e5Merge branch 'public/12996' into 6.9.b0
dacacd2trac #12996 making sure the doc builds

comment:52 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.9

comment:53 Changed 4 years ago by chapoton

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

comment:54 Changed 3 years ago by git

  • Commit changed from dacacd2882c26fc9f48982b5f1c56c9cc64c6c5f to 5b28e76952ecbda35d49eb6fd36ac50293b7cff2

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

38741deMerge branch 'public/12996' into 7.3.b4
5b28e76refresh the branch on top of 7.3.b4
Note: See TracTickets for help on using tickets.