Opened 11 years ago

Closed 10 years ago

#8288 closed enhancement (fixed)

Depth/Breadth improvement for SearchForest

Reported by: nborie Owned by: sage-combinat
Priority: major Milestone: sage-4.7
Component: combinatorics Keywords: enumeration depth breadth forest children
Cc: sage-combinat, nthiery Merged in: sage-4.7.alpha4
Authors: Nicolas Borie Reviewers: Florent Hivert, Minh Van Nguyen, Nicolas M. Thiéry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by nborie)

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

Attachments (3)

search_forest_depth_and_breath_improvement-nb.patch (24.0 KB) - added by nborie 11 years ago.
One more time, my english is still bad... Feel free to point them and thus, make my english increasing.…
trac_8288-reviewer.patch (16.2 KB) - added by mvngu 11 years ago.
trac_8288_search_forest_depth_and_breath_improvement-nb.patch (35.6 KB) - added by nborie 10 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 11 years ago by nborie

  • Status changed from new to needs_review

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

comment:2 Changed 11 years ago by ncohen

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

comment:3 Changed 11 years ago by mhansen

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

comment:4 Changed 11 years ago by ncohen

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

comment:5 Changed 11 years ago by nborie

  • Description modified (diff)

comment:6 Changed 11 years ago by hivert

  • Status changed from needs_review to needs_work

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

comment:7 follow-up: Changed 11 years ago by nborie

  • Status changed from needs_work to needs_review

comment:8 in reply to: ↑ 7 Changed 11 years ago by hivert

  • Status changed from needs_review to needs_work

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]]

comment:9 Changed 11 years ago by nborie

  • Status changed from needs_work to needs_review

Changed 11 years ago by nborie

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

Changed 11 years ago by mvngu

comment:10 Changed 11 years ago by mvngu

  • Authors set to Nicolas Borie
  • Description modified (diff)
  • Reviewers set to Florent Hivert, Minh Van Nguyen
  • Status changed from needs_review to needs_work

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:

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

comment:11 Changed 11 years ago by hivert

Hi Nicolas,

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

  • please define method _repr_ (Sage way) rather than __repr__ (Python's way).
  • when you need to link a class in the same file you don't have to give the full path for exampe :class:`SearchForest` is sufficient compared to :class:`~sage.combinat.backtrack.SearchForest`
  • please make sure and document that a common intended use of SearchForest is to inherit from it, calling only Parent.__init__ and overload the methods roots, children, post_process rather than passing them to the constructors. Please make sure to specify their result type (iterable vs. iterator). By the way, should'nt those methods be private methods (eg: _roots vs. roots. I don't expect the user to call them in my use-case.

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

Florent

comment:12 Changed 11 years ago by nborie

  • Description modified (diff)

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.

comment:13 follow-up: Changed 11 years ago by nborie

  • Status changed from needs_work to needs_review

comment:14 in reply to: ↑ 13 Changed 11 years ago by hivert

  • Status changed from needs_review to needs_work

Replying to nborie:

Some more remarks: please check your sphinx markup:

  • `...` is for mathematic ie is set up by TeX
  • ``...`` is for Sage/Python? code. There are some `__init__` which doesn't compile.

comment:15 Changed 11 years ago by nborie

  • Status changed from needs_work to needs_review

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

comment:16 Changed 11 years ago by nborie

rebased for 4.5.1

comment:17 Changed 10 years ago by mhansen

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?

comment:18 Changed 10 years ago by nborie

  • Cc nthiery added
  • Description modified (diff)

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 ?)

comment:19 Changed 10 years ago by nthiery

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

comment:20 Changed 10 years ago by nborie

  • Description modified (diff)

comment:21 Changed 10 years ago by nborie

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

comment:22 Changed 10 years ago by nthiery

  • Reviewers changed from Florent Hivert, Minh Van Nguyen to Florent Hivert, Minh Van Nguyen, Nicolas M. Thiéry

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

comment:23 Changed 10 years ago by nborie

  • Status changed from needs_review to positive_review

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

comment:24 Changed 10 years ago by ncohen

Oh my GOD O_O

This ticket is reviewed !! O_O

Well done :-)

Nathann

comment:25 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.