Implement suffix walk for suffix tree

[enadeau]

A suffix walk takes a node path-labeled "aw" with "a" a letter and return the state path-labeled "w".

[enadeau]

New commits:

​5519165	Trac #23573: Implement count and skip trick for suffix tree
​080c179	Trac #23573: Implement suffix walk for suffix tree

[git]

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

​f9a5526

Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

[git]

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

​a723bd9

Minor formating changes

[vdelecroix]

Recursion is slow in Python. You would better implement a more direct loop.

[git]

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

​56ea6ec

Trac #23573: Derecusify _count_and_skip

[git]

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

​ee68817

Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

[git]

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

​bf1a23a

Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

[nadialafreniere]

In the documentation of the function, you should say what d is (the last parameter of the output). It is not specified anywhere.

[nadialafreniere]

There probably is something I don't understand, but I don't see why when the node is a leaf, the algorithm for self._count_and_skip() returns implicit just like if it stopped on an edge. For example,

sage: T = ImplicitSuffixTree(Word("cacao"))
sage: T._count_and_skip(3,(2,5))
('implicit', (3, 1), 3)

It's coherent with the condition in the code if (trans[0][1] != None [...]):, but I don't see how it is coherent with the documentation.

[git]

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

​0ba0630

Fixed the bug of leaf returned as implicit.

[enadeau]

Your last observation was in fact a mistake, it was introduced when I derecursify the _count_and_skip method.

I've fixed it with other minor improvements.

[git]

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

​e142b47

clarification in the doc of suffix_walk

[nadialafreniere]

Thanks for the fixes! It now looks good and I think it should enter in the next version of Sage.

[vbraun]

The documentation doesn't build:

[dochtml] [combinat ] The inventory files are in local/share/doc/sage/inventory/en/reference/combinat.
[dochtml] Error building the documentation.
[dochtml] Traceback (most recent call last):
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/runpy.py", line 174, in _run_module_as_main
[dochtml]     "__main__", fname, loader, pkg_name)
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/runpy.py", line 72, in _run_code
[dochtml]     exec code in run_globals
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__main__.py", line 2, in <module>
[dochtml]     main()
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 1719, in main
[dochtml]     builder()
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 354, in _wrapper
[dochtml]     getattr(get_builder(document), 'inventory')(*args, **kwds)
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 550, in _wrapper
[dochtml]     build_many(build_ref_doc, L)
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/site-packages/sage_setup/docbuild/__init__.py", line 288, in _build_many
[dochtml]     ret = x.get(99999)
[dochtml]   File "/local/sage-patchbot/sage/local/lib/python2.7/multiprocessing/pool.py", line 572, in get
[dochtml]     raise self._value
[dochtml] OSError: WARNING: error while formatting arguments for sage.combinat.words.suffix_trees.ImplicitSuffixTree.suffix_walk: unhashable type: 'list'
Makefile:2035: recipe for target 'doc-html' failed
make[1]: *** [doc-html] Error 1

[vbraun]

Note that the argument tuple unpacking was removed in Python 3: ​https://www.python.org/dev/peps/pep-3113/

[git]

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

​1967ce8

remove argument tuple unpacking

[nadialafreniere]

Replying to git:

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

​1967ce8

remove argument tuple unpacking

Does that affect ticket:28182?

Otherwise, the doc now seems to build.

[enadeau]

Yes ticket:28182 is affected. Minor changes in function call will be sufficient. I'm working on it.

[enadeau]

The patchbot does not pass the pyflakes test but the error mentioned is completely unrelated to the changes that were made. Moreover, as far as I can tell, the error reported is not a real error since the if statement on line 123-125 won't be entered on the first pass of the loop when old_s is still undefined. Hence, I don't think any change to the code is needed.

Is there any way to silence the error?

========== pyflakes ==========
git checkout patchbot/ticket_merged
Bereits auf 'patchbot/ticket_merged'
src/sage/combinat/words/suffix_trees.py:125: undefined name 'old_s'

found 1 pyflakes errors in the modified files
Traceback (most recent call last):
  File "/home/sage-patchbot/.local/lib/python3.5/site-packages/sage_patchbot/patchbot.py", line 1126, in test_a_ticket
    baseline=baseline, **kwds)
  File "/home/sage-patchbot/.local/lib/python3.5/site-packages/sage_patchbot/plugins.py", line 281, in pyflakes
    raise ValueError(full_msg)
ValueError: found 1 pyflakes errors in the modified files
pyflakes -- 0 seconds
========== end pyflakes ==========

[hderycke]

You can add old_s = None before the loop.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​a36e767

add a line to comply with pyflake

[kdilks]

I'll make some minor changes to the docstring phrasing while I'm at Sage Days to have it be a little bit more in line with the General Conventions ( ​http://doc.sagemath.org/html/en/developer/coding_basics.html#the-docstring-of-a-function-content ). Then you can feel free to reset positive review if you're ok with my changes.

[git]

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

​87e9c16

Merge branch 'u/enadeau/implement_suffix_walk_for_suffix_tree' of git://trac.sagemath.org/sage into t/23573/implement_suffix_walk_for_suffix_tree

[git]

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

​be5c111

improve docstring

[enadeau]

I've updated the branch for 8.9beta4 and updated the docstring. kdilks did you have anything other improvements in mind for the doctring?

[nadialafreniere]

Since kdilks doesn't answer, I am resetting the positive review. The patchbot tests now seem fine.

Thanks Émile for this contribution!