search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.46k stars 484 forks source link

Depth/Breadth improvement for SearchForest #8288

Closed 0f5ae6f6-e03a-45d9-b571-4ce01615e676 closed 13 years ago

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago

The goal of this patch is to include breadth enumeration method for SearchForest, categorify SearchForest and make it very simple for inherit from it.

Add an example of Parent which inherit from SearchForest should be also fine.

Note to the buildbot / release manager: apply trac_8288_search_forest_depth_and_breath_improvement-nb.patch

CC: @sagetrac-sage-combinat @nthiery

Component: combinatorics

Keywords: enumeration depth breadth forest children

Author: Nicolas Borie

Reviewer: Florent Hivert, Minh Van Nguyen, Nicolas M. Thiéry

Merged: sage-4.7.alpha4

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

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago
comment:1

One more time, my english is still bad... Feel free to point and thus, make my english increasing....

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 14 years ago
comment:2

Hello !! I know nothing about the file sage/combinat/backtrack.py, and I intend to read it as soon as possible but I saw on TRAC the same of this patch, and I was convinced it woukd be using the Graph library : in sage/graphs/base/c_graph.pyx are written iterators for depth/breadth-first-search in general graphs.. Wouldn't it be better for this class to use such functions, are they are written in Cython and should be more efficient ? Or directly use the Graph structure, as it would automatically call these functions.. :-)

Nathann

mwhansen commented 14 years ago
comment:3

Nathann, using the code the graphs code is not appropriate here as that would require the entire search tree to be created/known beforehand.

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 14 years ago
comment:4

while it is not... Ok, I got it, then you can forget what I said :-)

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago

Description changed:

--- 
+++ 
@@ -5,3 +5,5 @@
 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.
hivert commented 14 years ago
comment:6

As discussed with Nicolas on irc. the patch needs some cleanup.

hivert commented 14 years ago
comment:8

Discussed on trac: there is an algorithmic problem: Here is my tests example:

    I = SearchForest([[3]], lambda l: (l+[i] for i in range(l[-1])))

Do you have an easy father function for this tree ? Yes : lambda l -> l[:-1] It simply generate strictly decreasing lists starting with 3. For me a call to

    list(I.element_of_depth_iterator(2, "Children"))

raise a StopIteration ... Whereas:

    sage: list(I.element_of_depth_iterator(2))
    [[3, 1, 0], [3, 2, 0], [3, 2, 1]]
0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago

Attachment: search_forest_depth_and_breath_improvement-nb.patch.gz

One more time, my english is still bad... Feel free to point them and thus, make my english increasing....

7c09a680-e216-4024-bb8e-9bfd4aa7f313 commented 14 years ago

Attachment: trac_8288-reviewer.patch.gz

7c09a680-e216-4024-bb8e-9bfd4aa7f313 commented 14 years ago

Author: Nicolas Borie

7c09a680-e216-4024-bb8e-9bfd4aa7f313 commented 14 years ago

Reviewer: Florent Hivert, Minh Van Nguyen

7c09a680-e216-4024-bb8e-9bfd4aa7f313 commented 14 years ago
comment:10

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.

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".

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.

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.

Other general remarks:

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.

7c09a680-e216-4024-bb8e-9bfd4aa7f313 commented 14 years ago

Description changed:

--- 
+++ 
@@ -7,3 +7,8 @@
 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. [search_forest_depth_and_breath_improvement-nb.patch](https://github.com/sagemath/sage-prod/files/10648117/search_forest_depth_and_breath_improvement-nb.patch.gz)
+2. [trac_8288-reviewer.patch](https://github.com/sagemath/sage-prod/files/10648118/trac_8288-reviewer.patch.gz)
hivert commented 14 years ago
comment:11

Hi Nicolas,

I'm currently using search forest and I run into some troubles... I also want to suggest some improvements in the code:

Thanks for all this ! I'm using it...

Florent

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago

Description changed:

--- 
+++ 
@@ -1,14 +1,5 @@
-The goal of this patch is to include breadth enumeration method for SearchForest...
+The goal of this patch is to include breadth enumeration method for SearchForest, categorify SearchForest and make it very simple for inherit from it.

-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.
+Add an example of Parent which inherit from SearchForest should be also fine.

 #8361 #6812  will follow after this ticket.
-
-Apply patches in this order:
-
-1. [search_forest_depth_and_breath_improvement-nb.patch](https://github.com/sagemath/sage-prod/files/10648117/search_forest_depth_and_breath_improvement-nb.patch.gz)
-2. [trac_8288-reviewer.patch](https://github.com/sagemath/sage-prod/files/10648118/trac_8288-reviewer.patch.gz)
0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago
comment:12

I upload a patch for this ticket to be discussed on http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/fbedf039a549c68b

Thanks for your comments Florent.

Nicolas.

hivert commented 14 years ago
comment:14

Replying to @sagetrac-nborie:

Some more remarks: please check your sphinx markup:

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago
comment:15

the last trac_8288_search_forest_depth_and_breath_improvement-nb.patch is ready from my side...

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago
comment:16

rebased for 4.5.1

mwhansen commented 14 years ago
comment:17

I put a patch up with some minor changes on the patch server. Do you want to fold them into your patch.

Florent, what is the status of this ticket?

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,4 @@

 Add an example of Parent which inherit from SearchForest should be also fine.

-#8361 #6812  will follow after this ticket.
+#6812  will follow after this ticket.
0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 14 years ago
comment:18

Thanks Mike for yours changes.

I folded your patch in mine and uploaded it to the trac. I also just checked (one more time) it apply well on 4.6, that all the tests pass and the doc seems fine to me (accordingly I am a bad English language reviewer).

It will be fine to finalize this work... (Was this point in your TODO list Nicolas ?)

nthiery commented 13 years ago
comment:19

Yes: we should just take 1/2 hour shortly to finalize this together.

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

Description changed:

--- 
+++ 
@@ -2,4 +2,5 @@

 Add an example of Parent which inherit from SearchForest should be also fine.

-#6812  will follow after this ticket.
+Note to the buildbot / release manager:
+apply trac_8288_search_forest_depth_and_breath_improvement-nb.patch
0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago
comment:21

Sorry for this post but with some hope that the buildbot take in care :

apply trac_8288_search_forest_depth_and_breath_improvement-nb.patch

nthiery commented 13 years ago
comment:22

Hi Nicolas,

I just made a couple minor improvements to the documentation on the sage-combinat patch server (directly in your patch). Please have a quick look, upload the new version to trac, and set a positive review on my behalf if you agree with my changes.

Cheers, Nicolas

nthiery commented 13 years ago

Changed reviewer from Florent Hivert, Minh Van Nguyen to Florent Hivert, Minh Van Nguyen, Nicolas M. Thiéry

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago

Attachment: trac_8288_search_forest_depth_and_breath_improvement-nb.patch.gz

0f5ae6f6-e03a-45d9-b571-4ce01615e676 commented 13 years ago
comment:23

It is ok with your changes. Let it go in!

6bdad4c1-1e26-4f2f-a442-a01a2292c181 commented 13 years ago
comment:24

Oh my GOD O_O

This ticket is reviewed !! O_O

Well done :-)

Nathann

jdemeyer commented 13 years ago

Merged: sage-4.7.alpha4