Move RecursivelyEnumeratedSet_forest code to sage/sets/recursively_enumerated_set.pyx, remove deprecated classes SearchForest, TransitiveIdeal, TransitiveIdealGraded

[seblabbe]

Move the code of SearchForest from sage/combinat/backtrack.py to sage/sets/recursively_enumerated_set.pyx into a class named RecursivelyEnumeratedSet_forest.

This is a follow up of #6637.

CC: @tscrim @slel

Component: combinatorics

Author: Matthias Koeppe

Branch: 908acba

Reviewer: Vincent Delecroix

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

[hivert]

Branch: u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx

[hivert]

Commit: 2effaf7

[hivert]

comment:3

I just added some old doc from Nathann and myself which is worth being integrated when cleaning this up.

---

Last 10 new commits:

7a33037	Work in progress on the DOC
168ceae	Added architecture picture for map_reduce
366fc17	More Doc
6c12752	Tested timeout option
493bb52	Done the doc of Map/Reduce
2534f12	Moved map/reduce to sage/parallel
e5b7477	Merge 6.10.rc1 + fixed conflict
82fd1e4	Fixed links according to deprecation/rebase
68b6530	Removed TODO in doc
2effaf7	Revert "Removed TODO in doc"

[tscrim]

Dependencies: #13580

[tscrim]

comment:4

I would like to squeeze out some more speed of the SearchForest code, so I'm interested in this. I made #13580 a dependency since that is likely a lot closer than this is to getting into Sage. If you disagree, then we can reverse the order of the dependencies and I'd do the review once this is ready.

[seblabbe]

comment:5

The actual branch contains many commits from the #13580, so I can't see what is the goal of the branch put here and how it is related to this ticket.

[sagetrac-git]

Changed commit from 2effaf7 to 1bf8c97

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

f984165	Fixed the doc
a5f4d67	Improved doc for map-reduce
569de0d	Merge branch 'develop' into t/13580/map_reduce
b07dfe2	Doc of the two implementationsof ActiveTaskCounter
beebcbc	#13580: Added comment on timing in the doc
58eca2e	#13580: Removed comment which is now in the doc
1badd8a	#13580: Renamed ActiveTaskCounter(Posix)
46cbab9	13580: Fixed doctests to pass on Darwin
134c1fa	13580: doc rereading
1bf8c97	Merge branch 'u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx' of git://trac.sagemath.org/sage into t/13580/map_reduce

[hivert]

comment:7

Replying to @seblabbe:

The actual branch contains many commits from the #13580, so I can't see what is the goal of the branch put here and how it is related to this ticket.

I just rebased this ticket on top of #13580 the code contains only an explanation of what SearchForest does with a nice picture from Nathann, Nicolas and nyself. It should be integrated during the move and the documentation cleanup.

[tscrim]

comment:8

Something else that we should do while-we-are-at-it, we should consider using collections.deque since it supports fast popping from both ends (list can become really slow when popping at the front, but deque is still twice as slow popping at the front).

[nthiery]

comment:9

Now that #13580 is in, the current branch contains just a small
self-contained documentation improvement. It seems worth and easy to
integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

And refocus this one on moving the SearchForest code to
sage/sets/recursively_enumerated_set.pyx (more than by just a single
alias)?

[seblabbe]

comment:10

Replying to @nthiery:

Now that #13580 is in, the current branch contains just a small
self-contained documentation improvement. It seems worth and easy to
integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

Please yes.

And refocus this one on moving the SearchForest code to
sage/sets/recursively_enumerated_set.pyx (more than by just a single
alias)?

Yes.

[mkoeppe]

comment:12

Replying to @seblabbe:

Replying to @nthiery:

Now that #13580 is in, the current branch contains just a small
self-contained documentation improvement. It seems worth and easy to
integrate soon, but somehow unrelated to this ticket, right?

Shall we create a separate ticket for that documentation chunk?

Please yes.

This is now #29882.

[mkoeppe]

Changed commit from 1bf8c97 to none

[mkoeppe]

Changed branch from u/hivert/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx to none

[mkoeppe]

Changed dependencies from #13580 to none

[mkoeppe]

Branch: u/mkoeppe/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx

[mkoeppe]

comment:15

Moved it, now need to clean up some lazy_import business

---

New commits:

7e1c6d2	WIP
143604d	WIP: Move SearchForest code to sage/sets/recursively_enumerated_set.pyx

[mkoeppe]

Commit: 143604d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

364d7b3	Move SearchForest code to sage/sets/recursively_enumerated_set.pyx
68f7bd5	sage.combinat.integer_vectors_mod_permgroup: Update to use RecursivelyEnumeratedSet_forest
1764ca4	Update remaining uses of SearchForest to use RecursivelyEnumeratedSet_forest

[sagetrac-git]

Changed commit from 143604d to 1764ca4

[mkoeppe]

comment:17

Let's see what the patchbot has to say.

I have made not made any attempt to cythonize anything; this is really just pure Python code moved into the pyx file.

[mkoeppe]

Author: Matthias Koeppe

[mkoeppe]

comment:18

Also, I added a lazy_import for SearchForest but it seems that SearchForest was already deprecated -- perhaps now it can be removed completely?

[mkoeppe]

comment:19

(deprecation in #6637, 6 years ago)

[sagetrac-git]

Changed commit from 1764ca4 to 1ac0a09

[sagetrac-git]

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

1ac0a09

sage.combinat.backtrack: Remove deprecated class SearchForest

[mkoeppe]

comment:21

Also TransitiveIdeal and TransitiveIdealGraded were deprecated in #6637.

[sagetrac-git]

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

908acba

sage.combinat.backtrack: Remove deprecated classes TransitiveIdeal and TransitiveIdealGraded

[sagetrac-git]

Changed commit from 1ac0a09 to 908acba

[videlec]

comment:24

It seems to me that with your changes SearchForest does not exist anymore. If so, you must add a lazy import with deprecation warning in backtrack.py. The SearchForest was documented as a deprecated class but was not making any deprecation warning when used.

[mkoeppe]

comment:25

That's right, these deprecated classes are deleted.

The deprecation happened in #6637 and announced on the ticket, I guess before deprecation warnings were invented?

[videlec]

Reviewer: Vincent Delecroix

[videlec]

comment:26

This is somehow annoying. Let us hope that nobody uses it in her code.

[mkoeppe]

comment:27

Thanks!

[slel]

comment:29

In the same general area, any interest in #22184 and #27537 anyone?

[vbraun]

Changed branch from u/mkoeppe/move_searchforest_code_to_sage_sets_recursively_enumerated_set_pyx to 908acba

[seblabbe]

comment:31

Thanks for finishing this task.I feel ashame I never finished it myself.

As a further todo, I think it will be nice to have

-class RecursivelyEnumeratedSet_forest(Parent):
+class RecursivelyEnumeratedSet_forest(RecursivelyEnumeratedSet_generic):

There are few methods like to_digraph from the generic class that I like to use but are currently not available for the forest type.

[seblabbe]

Changed commit from 908acba to none

[seblabbe]

comment:32

A follow-up ticket is here: #30238