standardize the interface to TransitiveIdeal and friends

[nthiery]

1. Implement a single entry point for recursively enumerated sets:

     RecursivelyEnumeratedSet(seeds, successors, structure=..., enumeration=...)

where structure takes values in the set [None, 'forest', 'graded', 'symmetric'] and enumeration takes values in the set [None, 'depth', 'breadth', 'naive'].

2. Deprecate TransitiveIdeal, TransitiveIdealGraded and SearchForest as entry point.

3. TransitiveIdeal(succ, seeds) keeps the same behavior as before and is now the same as RecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='naive').

4. TransitiveIdealGraded(succ, seeds, max_depth) keeps the same behavior as before and is now the same as RecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='breadth', max_depth=max_depth).

Remarks:

A. For now the code of SearchForest is still in sage/combinat/backtrack.py. It should be moved in sage/sets/recursively_enumerated_set.pyx. See #16351.

B. TransitiveIdeal and TransitiveIealGraded are used in the code of sage/combinat, sage/categories and sage/groups at least. These should be updated to use RecursivelyEnumeratedSet for speed improvements and also to avoid issues explained in C below. See #16352.

C. Note that there were some issues with TransitiveIdeal and TransitiveIdealGraded, namely:

• Enumeration of TransitiveIdeal is claimed to be depth first search in the top level file backtrack.py, but in fact, it is neither breadth first neither depth first. It is what I call a naive search.
• Enumeration of TransitiveIdealGraded is indeed breadth first as claimed but it does not make use of the graded hypothesis at all because it remembers every generated elements.

See my status report at SageDays57 for more info.

Depends on #14052

CC: @sagetrac-sage-combinat @hivert

Component: combinatorics

Keywords: backtrack, enumerated set, transitive closure, days57

Author: Sébastien Labbé

Branch: 3191690

Reviewer: Travis Scrimshaw

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

[seblabbe]

comment:1

Here are some discussions related to this ticket:

• TransitiveIdeal vs TransitiveIdealGraded on sage-combinat, Feb 2013.

• Comment of Nicolas Thiéry at #14052, Feb 2013

• SearchForest and post_process..., on sage-devel, Oct. 2012.

• Sage modules and forking on sage-devel, a comment by Florent Hivert, Oct. 2012.

• Parallel map reduce on SearchForest #13580, patch available on sage-combinat : trac_13580-map_reduce-fh.patch

[seblabbe]

comment:4

In a tentative to find good choices for name and so on, here is how I see this.

• Let X be a set.
• Let R be a binary relation on X, that is R is a subset of the cartesian product of X times X.
• Denote by xRy if x is R-related to y.

Now

• Let seeds be a subset of X.
• Let succ be a callable python object X -> 2^X such that xRy if and only if y is in succ(x).

We are interested in the subset S of X that can be generated from the seeds using the succ recursively. More precisely in the set

S = {y : x = x1 R x2 R x3 R ... R xn = y and x in seeds}.

Moreover, we are interested in the enumeration of S itself and we consider depth-first and breadth-first as different and both usefull.

Such a relation G = (X,R) can be seen as a directed graph. I think this remark is useful as it may provide some vocabulary. Indeed the set S is the connected components of the generators in the digraph G.

I see some different cases :

1. We do not know anything more about the relation. We need to save in memory all the known objects to avoid duplicates. This is what is currently done in TransitiveIdeal (depth-first search) and (curiously) in TransitiveIdealGraded (breadth-first search) also.

2. The directed graph S is a forest with given seeds. Equivalently, one may say that S do not contain cycle (oriented or not). This is what is currently done in SearchForest.

3. The relation is graded. By graded here I mean what I thought TransitiveIdealGraded was doing until I look more carefully at the doc and the code. More seriously, by graded I mean the following : for all (x1 in seeds) and (y1 in seeds),

if (x1 R x2 R ... R xn) and (y1 R y2 R ... R ym) and (xn=ym), then (n=m).

The relation is graded if all path from the origin to an element have the same length. In this case, we only need to save in memory the current level.

4. The relation is symmetric. If the relation is symmetric, we only need to keep in memory the last two level of depth. This is what I needed and coded this week. And this is why I started to look more carefully at the code in sage/combinat/backtrack.py...

That is it for now!

[nthiery]

comment:5

I totally agree with the analysis!

I don't know yet what would be the best name for the argument provided by the user to describe the relation. Behind the scene we are definitely modelling relation. But what the user provide is not the relation but a function that computes the (out) neighbors for this relation. If at the end of the day we choose "TransitiveClosure" as name for the main entry point, then "neighbors" would be consistent. If we go for "RecursiveSet" (or RecursiveEnumeratedSet or variant thereof) then "operators" would be consistent.

Cheers,
Nicolas

[seblabbe]

comment:6

I think relation would not be too bad for the name of the successor keyword and should be considered as well. In some sense, a binary relation is a function f: X -> 2^X and a function is a relation such that |f(x)|=1 for all x.

Possibilities for successor keyword :

• succ : suitable for non symmetric relation, currently used in TransitiveIdeal and TransitiveIdealGraded
• successors
• operators
• neighbors : suitable vocabulary for symmetric relation
• children : suitable vocabulary for non symmetric relation, currently used in SearchForest.
• relatives : suitable vocabulary for symmetric relation

Possibilities for generators keyword :

• generators
• gens
• roots
• seeds

[seblabbe]

comment:7

If we go for RecursiveSet (or RecursiveEnumeratedSet or variant thereof)

I like RecursiveSet. Maybe RecursiveEnumeratedSet is more related to what we do but is also longer.

Some links:

• http://en.wikipedia.org/wiki/Recursive_set
• http://en.wikipedia.org/wiki/Recursively_enumerable_set

[seblabbe]

comment:8

I don't know yet what would be the best name for the argument provided by the user to describe the relation.

For the above 4 cases, I would suggest arguments like the following :

RecursiveSet(seeds, succ)
RecursiveSet(seeds, succ, structure="forest")
RecursiveSet(seeds, succ, structure="graded")
RecursiveSet(seeds, succ, structure="symmetric")

[seblabbe]

Attachment: trac_6637_recursive_set-sl.patch.gz

[seblabbe]

comment:9

I just added a patch. It implements the RecursiveSet_symmetric class and creates factory called RecursiveSet. For now, RecursiveSet returns either an instance of TransitiveIdeal, SearchForest or RecursiveSet_symmetric. I started an empty class RecursiveSet_graded. See examples inside the docstring of the class RecursiveSet.

It is not ready for review, but comments are welcome to help me continue this work.

Actually, my questions are :

• How should I merge RecursiveSet with TransitiveIdeal and SearchForest?
• Do we like this interface?

[seblabbe]

Dependencies: #14052

[seblabbe]

Commit: c2861f0

[seblabbe]

New commits:

c2861f0

Some fixes to TransitiveIdeal and TransitiveIdealGraded, added RecursiveSet factory

[seblabbe]

Branch: u/slabbe/6637

[sagetrac-git]

Changed commit from c2861f0 to 5924b46

[sagetrac-git]

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

5924b46

Cleaning RecursiveSet and subclasses

[sagetrac-git]

Changed commit from 5924b46 to 29aebab

[sagetrac-git]

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

29aebab

now 100% coverage, seeds instead of gens

[sagetrac-git]

Changed commit from 29aebab to b363c54

[sagetrac-git]

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

b363c54

Cleaning documentation and reverting some changes to TransitiveIdeals

[sagetrac-git]

Changed commit from b363c54 to b8108ae

[tscrim]

comment:46

Also FTR, I liked your usage of the metaclass (and I can't check the doc until I get my docbuilder to actually work again... :/ ).

[seblabbe]

comment:47

If you agree Travis, I will try to put the metaclass use back in. Also, maybe Florent can say a word about it. He coached me on how to implement it.

[seblabbe]

comment:48

Replying to @tscrim:

As I recall, metaclasses are not supported in extension classes by Cython. The metaclass should not change the speed since it's only called/used upon object creation.

Ok, now I see what you mean. When the class is cdef, then the __classcall_private__ do not get called instead of the __init__:

sage: f = lambda a: [a-1,a+1]
sage: RecursivelyEnumeratedSet([0], f)
A recursively enumerated set (depth first search)
sage: RecursivelyEnumeratedSet([0], f, structure='symmetric')
Traceback (most recent call last):
...
TypeError: __init__() got an unexpected keyword argument 'structure'

I also saw in the doc that: "For a Cython class (not cdef since they doesn’t allows metaclasses)"

[seblabbe]

comment:49

I pushed on my branch a commit using metaclass. In the end, I had to create a factory def outside of the class...

[sagetrac-git]

Changed commit from 3191690 to dd72bfc

[sagetrac-git]

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

34c9db2	Removed _generic from base class and added _factory to function.
dd72bfc	Merge branch 'public/ticket/6637' of trac.sagemath.org:sage into public/ticket/6637

[tscrim]

comment:51

Looking at your commit, I don't see any benefit in using the metaclass. However I'm not opposed to the renaming, so I've just pushed that.

[seblabbe]

comment:52

Replying to @tscrim:

Looking at your commit, I don't see any benefit in using the metaclass.

Yes exactly. I needed to play with it to understand what you meant.

However I'm not opposed to the renaming, so I've just pushed that.

Well, the renaming was just an easy way for me to check that sage -t recursively_enumerated_set.pyx was ok after I realised that __classcall_private__ was ignored by cdef class. It was not a suggestion, but it would not be the first renamed function:

sage: import_statements(sum)
from sage.misc.functional import symbolic_sum

So, we go with commit ​dd72bfc instead of ​3191690 ?

[tscrim]

comment:53

If that's okay with you.

[seblabbe]

comment:54

Replying to @tscrim:

If that's okay with you.

The more I think about it, the less I like it. I think ​dd72bfc can be confusing for someone looking at the file for the first time. Until that person looks at the file sage/sets/all.py he will not understand how the __init__ handles the structure argument. And the key will always be hidden in some other file sage/sets/all.py. I suggest we go with your initial factory function. More precisely with commit ​3191690. Do you agree?

If so, I do not know what should we do then (git question). Should we update the commit field? Should we reset the HEAD of the branch? Should we create a new branch pointing to the commit?

[tscrim]

comment:55

Good point. What we'll do is create a new branch which just points to the old commit (afterwards we can delete our old branches). Do you want to do this or should I?

[seblabbe]

comment:56

Let me try.

[seblabbe]

Changed commit from dd72bfc to 3191690

[seblabbe]

Changed branch from public/ticket/6637 to public/ticket/6637a

[seblabbe]

comment:57

The following did the trick:

git checkout 3191690 -b t/6637a

[tscrim]

comment:58

Then let's get this in. Thanks Sébastien.

[seblabbe]

comment:59

Thanks for the review and cython improvements!

[vbraun]

Changed branch from public/ticket/6637a to 3191690

[seblabbe]

Changed commit from 3191690 to none