#8288: Depth/Breadth improvement for SearchForest
-----------------------------------------------+----------------------------
Reporter: nborie | Owner: sage-combinat
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.4
Component: combinatorics | Keywords: enumeration
depth breadth forest children
Author: Nicolas Borie | Upstream: N/A
Reviewer: Florent Hivert, Minh Van Nguyen | Merged:
Work_issues: |
-----------------------------------------------+----------------------------
Changes (by newvalueoldvalue):
* status: needs_review => needs_work
* reviewer: => Florent Hivert, Minh Van Nguyen
* author: => Nicolas Borie
Old description:
> The goal of this patch is to include breadth enumeration method for
> SearchForest...
>
> The interested is for enumerated Set defined by a set of roots and a
> children function. For a finite set of roots but infinite set (infinite
> depth of the tree), the breadth method is a necessity.
>
> The breadth method is also a need to define properly indices of infinite
> Graded algebra (but finite degree by degree). The patch contains method
> returning iterator of all element of given depth.
>
> Using extra argument : father and next_brother method, it is possible to
> enumerate not starting from the roots of trees. a _iter_from_to method
> build an iterator keeping nothing in memory than the first and the last
> point.
>
> #8361 #6812 will follow after this ticket.
New description:
The goal of this patch is to include breadth enumeration method for
SearchForest...
The interested is for enumerated Set defined by a set of roots and a
children function. For a finite set of roots but infinite set (infinite
depth of the tree), the breadth method is a necessity.
The breadth method is also a need to define properly indices of infinite
Graded algebra (but finite degree by degree). The patch contains method
returning iterator of all element of given depth.
Using extra argument : father and next_brother method, it is possible to
enumerate not starting from the roots of trees. a _iter_from_to method
build an iterator keeping nothing in memory than the first and the last
point.
#8361 #6812 will follow after this ticket.
Apply patches in this order:
1. [http://trac.sagemath.org/sage_trac/attachment/ticket/8288
/search_forest_depth_and_breath_improvement-nb.patch
search_forest_depth_and_breath_improvement-nb.patch]
1.
[http://trac.sagemath.org/sage_trac/attachment/ticket/8288/trac_8288-reviewer.patch
trac_8288-reviewer.patch]
--
Comment:
Don't use the keyword "method" to specify the algorithm to be used.
Instead use "algorithm". See #6094 and #7971 for two attempts to get rid
of using "method" for specifying the algorithm to be used. My reviewer
patch makes this change to your implementation.
[[BR]]
For any argument that can take more than one value, provide all the
possible values. For example, if possible, list all the possible values
for the argument "algorithm".
[[BR]]
There is a slight bug in the method `search_forest_iterator()`. If
`method="depth"`, then we would use depth-first search. But to get
`search_forest_iterator()` to use breadth-first search, we could assign
any value to the keyword `method`:
{{{
sage: from sage.combinat.backtrack import search_forest_iterator
sage: list(search_forest_iterator([[]], lambda l: [l+[0], l+[1]] if len(l)
< 3 else [], method="breadth"))
[[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0,
1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
sage: list(search_forest_iterator([[]], lambda l: [l+[0], l+[1]] if len(l)
< 3 else [], method=None))
[[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0,
1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
sage: list(search_forest_iterator([[]], lambda l: [l+[0], l+[1]] if len(l)
< 3 else [], method="some sanity"))
[[], [0], [1], [0, 0], [0, 1], [1, 0], [1, 1], [0, 0, 0], [0, 0, 1], [0,
1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
}}}
To remedy this bug, we could explicitly test for "breadth" and "depth" and
set the value `position` accordingly. For any other value assigned to
`algorithm`, we raise an exception. The reviewer patch implements this
fix.
[[BR]]
There is a slight bug in the method `element_of_depth_iterator()`. From
your example given for that method, we can do this:
{{{
sage: father = lambda t: (t[0]-1,0) if t[1] == 0 else (t[0],t[1]-1)
sage: I = SearchForest([(0,0)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if
l[1] == 0 else [(l[0], l[1]+1)], father=father)
sage: list(I.element_of_depth_iterator(10, method="father"))
[(10, 0), (9, 1), (8, 2), (7, 3), (6, 4), (5, 5), (4, 6), (3, 7), (2, 8),
(1, 9), (0, 10)]
}}}
But then, we could assign the keyword `method` with any value and get the
same result as above:
{{{
sage: father = lambda t: (t[0]-1,0) if t[1] == 0 else (t[0],t[1]-1)
sage: I = SearchForest([(0,0)], lambda l: [(l[0]+1, l[1]), (l[0], 1)] if
l[1] == 0 else [(l[0], l[1]+1)], father=father)
sage: list(I.element_of_depth_iterator(10, method="mother"))
[(10, 0), (9, 1), (8, 2), (7, 3), (6, 4), (5, 5), (4, 6), (3, 7), (2, 8),
(1, 9), (0, 10)]
sage: list(I.element_of_depth_iterator(10, method="grandma"))
[(10, 0), (9, 1), (8, 2), (7, 3), (6, 4), (5, 5), (4, 6), (3, 7), (2, 8),
(1, 9), (0, 10)]
sage: list(I.element_of_depth_iterator(10, method="abc"))
[(10, 0), (9, 1), (8, 2), (7, 3), (6, 4), (5, 5), (4, 6), (3, 7), (2, 8),
(1, 9), (0, 10)]
}}}
One way to fix this is to make `full_generation` into a boolean keyword.
If `full_generation=True`, the search starts from the root and generate
all elements until the given depth is reached. If `full_generation=False`,
the search algorithm makes use of the `father` and `next_brother` methods.
My reviewer patch makes this change.
[[BR]]
Other general remarks:
* Whenever possible, avoid going over 79 characters per line.
* When testing for `None`, don't use "!=". Instead use "is not", which is
much faster than "!=". The same remark applies when testing for equality
of an object with `None`.
* For the method `first_element_of_depth()`, I don't understand what is
the purpose of the keyword "father_with_depth". You need to document that
keyword.
* Some stylistic clean-ups in accordance with
[http://www.python.org/dev/peps/pep-0008/ PEP 8].
I have provided a reviewer patch that implements some changes on top of
nborie's patch. Someone needs to review the technical aspect of the
features implemented by nborie's patch.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8288#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
