SearchForest and post_process...

[Florent Hivert]

Hi There,

Thanks to Nicolas the Little, Sage has a SearchForest class. It is a very nice
tools to iterate through sets defined by a recursive choice
tree. Unfortunately, currently due to the name someone who doesn't know that
it exists has no chance to find it. It seems that there is an agreement that
the mane should be changed but we didn't yet find a good one. Let me describe
a little what it does (please refer to the doc for more informations and
examples):

The enumerated set is mostly described by two data:
- roots which are the starting nodes of the recursive generation
- children with compute the immediate successors of a node in the generation
tree.
One can also provide a post_process function that allows for customizing the
nodes that are actually produced. Furthermore, if it returns None, then the
node won't be output at all.

I'd like to gather proposal and find an agreement on the names for
SearchForest and post_process.

Here are some proposal for search forest:
- TreeGeneratedSet
- ForestGeneratedSet
- RecursivelyGeneratedSet
- ChoiceTree
- ChoiceForest
...

Nathann Cohen suggested to rename post_process with map_function, underlying
the fact that post_process is mapped on the sets of node of the tree. I'd like
to have a vote on this rename, possibly with alternative proposal.

\begin{pub}
I'm finishing to polish a class named currently
{{{SearchForestMapReduce}}} which allows to apply in a parallel and
distributed way a map-reduce scheme on the node generated by a such a
forest. For example, here's the Sage code for binary words of length less
or equal that 16:

sage: S = SearchForest(
... roots = [[]],
... children = lambda l: [l+[0], l+[1]] if len(l) < 16 else [])
sage: S.map_reduce(
... map_function = lambda z: x**len(z),
... reduce_function = lambda x,y: x+y,
... reduce_init = 0 )
65536*x^16 + 32768*x^15 + 16384*x^14 + 8192*x^13 + 4096*x^12 + 2048*x^11 + 1024*x^10 + 512*x^9 + 256*x^8 + 128*x^7 + 64*x^6 + 32*x^5 + 16*x^4 + 8*x^3 + 4*x^2 + 2*x + 1
\end{pub}

Thanks for your suggestions,

Florent

[Simon King]

Hi Florent,

On 2012-10-10, Florent Hivert <Florent...@lri.fr> wrote:
> The enumerated set is mostly described by two data:
> - roots which are the starting nodes of the recursive generation
> - children with compute the immediate successors of a node in the generation
> tree.
> One can also provide a post_process function that allows for customizing the
> nodes that are actually produced. Furthermore, if it returns None, then the
> node won't be output at all.
>
> I'd like to gather proposal and find an agreement on the names for
> SearchForest and post_process.
>
> Here are some proposal for search forest:
> - TreeGeneratedSet
> - ForestGeneratedSet
> - RecursivelyGeneratedSet

Why not "RecursiveSet"? The word "Generated" seems redundant to me.

And what you tell about the role of "post_process" makes me think it could be
renamed into "branch_cut".

Best regards,
Simon

[Nicolas Borie]

Le 10/10/2012 15:53, Simon King a �crit :

>
> Why not "RecursiveSet"? The word "Generated" seems redundant to me.
>
> And what you tell about the role of "post_process" makes me think it could be
> renamed into "branch_cut".
>
> Best regards,
> Simon

Hello,

The post_process hardly depend on a fonction (placed in itertools of
sage) which is "imap_and_filter_none". There are two points on this
output processing : you cut branches and you also apply an output
fonction...

I like the Set suffix for the name. As the feature returns a parent with
category, it seems fine for me the name should be close to blablablaSet.
IMHO, the feature accept multiples roots but no one would search for
"forest", we naturally search for Tree, TreeLikeStruture, ...

In an other directions, we should make a micro patch to modify the
documentation of EnumeratedSet, FiniteEnumeratedSet, ...Set to advertise
the user of the existance of the searchForest (old name) feature. I
don't know if sphnix accept such references... Just putting in other doc
: for set defined with roots and a children fonction,
see:..../SearchForest. Perhaps also, the code should be moved out from
bactrack.py...

Cheers,
Nicolas B.

[Jason Grout]

On 10/10/12 8:53 AM, Simon King wrote:
> And what you tell about the role of "post_process" makes me think it could be
> renamed into "branch_cut".

Or it could renamed "visit" or "trim" or even just "callback"

Jason

[Florent Hivert]

Hi Simon,

> On 2012-10-10, Florent Hivert <Florent...@lri.fr> wrote:
> > I'd like to gather proposal and find an agreement on the names for
> > SearchForest and post_process.
>

> I don't know if my answer to sage-devel will automatically appear here
> as well. If not: I suggested "RecursiveSet" and "branch_cut" as new
> names for SearchForest and post_process (though I am not so sure if
> "branch_cut" is the actual purpose of post_process).

Thanks for your suggestion. Actually "branch_but" doesn't describe what
"post_process" does. Cutting branch is done by children. The precise
description of the purpose of post_process is the following:

Through roots and children we are given a recursive tree of nodes n. From this
tree we want to derive a set S. First of all, often we need to apply a certain
function f(n) to compute the actual element of S. So in this sense we are just
applying a map f to the set of the node. On the other hand sometimes, all the
nodes are used to build element of S. Sometime only certain node are kept (eg
leaves), the other node are just intermediate steps of the recursion. In this
case f can return None to indicate that no element of s is associated to the
node n.

For example, suppose that you want to iterate through all permutations of a
given set S. One solution is to take element of S one by one an to insert them
at every position. So a node contains two informations
- the list lst of already inserted element
- the set st of the yet to be inserted element
You want to generate a permutation only if st is empty (leaves on the
tree). Also instead of list you may want to generate tuples. Here is the code:

sage: def children((lst, st)):
... st = set(st) # make a copy
... if st:
... el = st.pop()
... for i in range(0, len(lst)+1):
... yield (lst[0:i]+[el]+lst[i:], st)
sage: list(children(([1,2], {3,7,9})))
[([9, 1, 2], set([3, 7])), ([1, 9, 2], set([3, 7])), ([1, 2, 9], set([3, 7]))]
sage: S = SearchForest( [([], {1,3,6,8})],
... children,
... post_process = lambda (l, s): tuple(l) if not s else None,
... category=FiniteEnumeratedSets())
sage: S.list()
[(6, 3, 1, 8), (3, 6, 1, 8), (3, 1, 6, 8), (3, 1, 8, 6), (6, 1, 3, 8), (1, 6, 3, 8), (1, 3, 6, 8), (1, 3, 8, 6), (6, 1, 8, 3), (1, 6, 8, 3), (1, 8, 6, 3), (1, 8, 3, 6), (6, 3, 8, 1), (3, 6, 8, 1), (3, 8, 6, 1), (3, 8, 1, 6), (6, 8, 3, 1), (8, 6, 3, 1), (8, 3, 6, 1), (8, 3, 1, 6), (6, 8, 1, 3), (8, 6, 1, 3), (8, 1, 6, 3), (8, 1, 3, 6)]
sage: S.cardinality()
24

By the way, I'm adding this to the documentation ;-)

Nathann is suggesting to call post_process "map_function" because we just map
it on the node, dropping the None results.

I hope it is more clear,

Cheers,

Florent

[Nicolas M. Thiery]

Hmm, it could indeed be used as a call back (or visitor). But the
intention is more to do a transformation before the iterator hands
back the result to the user.

By the way, to throw in some more keyword: SearchForest and
TransitiveIdeal are really about computing the *closure* of a set
under some operations. So at this point my two preferred variants are
RecursiveSet or anything build with close: ClosedSet? ClosureOfSet?
ClosureSet? However this is a bit too general and could get people to
think that this is about analysis-related topology.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[Simon King]

Hi Nicolas,

On 2012-10-12, Nicolas M. Thiery <Nicolas...@u-psud.fr> wrote:
> By the way, to throw in some more keyword: SearchForest and
> TransitiveIdeal are really about computing the *closure* of a set
> under some operations. So at this point my two preferred variants are
> RecursiveSet or anything build with close: ClosedSet? ClosureOfSet?
> ClosureSet? However this is a bit too general and could get people to
> think that this is about analysis-related topology.

In my former life (until PhD), I mainly did topology, and indeed
ClosedSet would remind me of topology. AlgorithmicallyClosedSet would
avoid that association, but is too long. Hence, I still prefer
RecursiveSet.

By the way, did you think about a construction functor for the new
parents? If I understand correctly, you have some algorithmic procedure
A that you apply to some basic data (a root) R. Hence, it would not be
totally absurd to have an AlgorithmicClosure functor F(A), such that
F(A) applied to R returns the associated RecursiveSet. The existence of
a construction functor would support the construction of coerce maps -
*IF* one is able to guess the priority of F(A) (i.e., would one first
apply F(A) or another functor in a pushout?) and how it merges/commutes
with other functors - both would depend on the mathematical properties of A.

That's a pretty big "if". So, perhaps having construction functors would
be unfeasible. But perhaps you have ideas of how to make it work.

Best regards,
Simon

[Nicolas M. Thiery]

On Sat, Oct 13, 2012 at 07:09:33AM +0000, Simon King wrote:
> By the way, did you think about a construction functor for the new
> parents? If I understand correctly, you have some algorithmic procedure
> A that you apply to some basic data (a root) R. Hence, it would not be
> totally absurd to have an AlgorithmicClosure functor F(A), such that
> F(A) applied to R returns the associated RecursiveSet. The existence of
> a construction functor would support the construction of coerce maps -
> *IF* one is able to guess the priority of F(A) (i.e., would one first
> apply F(A) or another functor in a pushout?) and how it merges/commutes
> with other functors - both would depend on the mathematical properties of A.
>
> That's a pretty big "if". So, perhaps having construction functors would
> be unfeasible. But perhaps you have ideas of how to make it work.

Interesting. On a similar note, in MuPAD-Combinat, we had things
like:

M.monoid_closure(generators) (based on TransitiveIdeal)
G.group_closure(generators) (based on TranstivieIdeal; of
course for permutation/matrix
groups we should do better)

V.module_closure(generators, operators)
A.algebra_closure(generators) (based on the above)
C.coalgebra_closure(generators)
K.kac_algebra_closure(generators)

We need to implement those and think along the way about a nice
functorial approach if there is one!

Hmm, the above suggests to have S.set_closure(generators, operators)
as idiom for TransitiveIdeal ? The inconvenient is that we need to
have a set S under hand.

[Sébastien Labbé]

Hi,

I really like SearchForest and have been using it some times. But, other times, my children rules are such that two disctinct branches overlap. So, just last weekend, I coded a similar SearchGraph class taking as input a set of roots and a children rule where an element can  be obtained in a non unique path. The difference with SearchForest is that it returns an iterator over all distinct elements (it remembers if an element as been reached already).

So if SearchForest get renamed to RecursiveSet, what name should be given to SearchGraph? It sounds like RecursiveSet could be a good name as well for SearchGraph...

Also, if SearchForest was giving me the intuition about the unique way to get to a node of the forest, RecursiveSet doesn't not. Is this a problem?

Sébastien

[Florent Hivert]

On Mon, Oct 15, 2012 at 02:51:11PM -0700, S�bastien Labb� wrote:
> Hi,
>
> I really like SearchForest and have been using it some times. But, other
> times, my children rules are such that two disctinct branches overlap. So,
> just last weekend, I coded a similar SearchGraph class taking as input a
> set of roots and a children rule where an element can be obtained in a non
> unique path. The difference with SearchForest is that it returns an
> iterator over all distinct elements (it remembers if an element as been
> reached already).

It seems that your SearchGraph is what is already implemented under
TransitiveIdeal in the same file than SearchForest... Can you check if it is
redundant ?

Cheers,

Florent

[Sébastien Labbé]

It seems that your SearchGraph is what is already implemented under
TransitiveIdeal in the same file than SearchForest... Can you check if it is
redundant ?

It is indeed redundent. I did search for a SearchGraph implementation in Sage. I saw the comment """"See also "GenericBacktracker", "TransitiveIdeal", and "TransitiveIdealGraded".""" in the documentation of SearchForest. But, I was sure TransitiveIdeal was for something else. Of course, if I had read the line """Returns the set S of elements that can be obtained by repeated application of "relation" on the elements of "generators".""" inside the documentation of TransitiveIdeal, then I would not have coded a SearchGraph class. By chance, my SearchGraph code was no more than 20 lines.

So, what about the following common interface for forests, graded graph and graphs :

class RecursiveSet:
    def __init__(self, roots, children, structure=None, other_arguments_like_post_process):
         r"""
         Returns the set S of elements that can be
         obtained by repeated application of "children"
         on the elements of "roots".

          INPUT:
   
             * "roots" : a list (or iterable)
   
             * "children" : a function returning a list (or iterable, or
               iterator)

             * "structure" : string (default=None), can take one
                of the following values:
                 * "tree" or "forest" : each element of the set
                   can be reached by a unique sequence of
                   application of children rules
                 * "graded" : one or more sequences of
                   application of children rules can lead to the same
                   element, but they all have the same length
                 * None : no structure is assumed on the set
           """

Sébastien