Changes between Version 5 and Version 10 of Ticket #8288


Ignore:
Timestamp:
04/19/10 02:59:42 (11 years ago)
Author:
mvngu
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.

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.

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #8288

    • Property Status changed from needs_review to needs_work
    • Property Reviewers changed from to Florent Hivert, Minh Van Nguyen
    • Property Authors changed from to Nicolas Borie
  • Ticket #8288 – Description

    v5 v10  
    88
    99#8361 #6812  will follow after this ticket.
     10
     11Apply patches in this order:
     12
     13 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]
     14 1. [http://trac.sagemath.org/sage_trac/attachment/ticket/8288/trac_8288-reviewer.patch trac_8288-reviewer.patch]