Lecture "Organising information: trees", exercise 1

[essepuntato]

Write in Python a recursive function def breadth_first_visit(root_node) that takes the root node of a tree and returns a list containing all the nodes of the tree according to a breadth first order, which first consider all the nodes of the first level, then those ones of the second level, and so forth. For instance, considering the nodes created in Listing 2, the function called on the node book should return the following list: [book, chapter_1, chapter_2, text_8, paragraph_1, paragraph_2, paragraph_3, text_7, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]. Accompany the implementation of the function with the appropriate test cases.

[SeverinJB]

@essepuntato, Could you please clarify whether I interpreted the exercise correctly? I struggle(d) with this exercise because of your request "[...] should return the following list: [book, chapter_1, chapter_2, text_8, ...]". In beginning, I tried to take you literally and to return a list which contains [book, chapter_1, chapter_2, text8, ...]. After studying the documentation of anytree_, however, I realised this is kind of meta-meta-programming and not easily done. Also, I realised you would have written the strings in quotes: ["book", "chapter_1", "chapter_2", "text_8", ...]. The following algorithm, hence, returns a list which contains in level-order (your requested order) all nodes of any given tree, i.e. [Node('/book'), Node('/book/chapter'), Node('/book/chapter'), Node('/book/...'), ...]

Note: The following test case [print(test_breadth_first_visit(book, list(LevelOrderIter(book))))] only works if the tree provided by Silvio is part of the same file. The complete code (with the tree) is in the correct order in the second snippet.

Bugfix: The list result did not reset itself after an execution of the algorithm. Consequently, every following execution just added its results to the existing list result. The bug was successfully fixed.

Update: The suggestion of Peroni was implemented. Both if conditions "if len(queue) >= 1:" and "if len(queue) != 0:" are now reduced to "if queue:". Sleek!

+++ Algorithm with Test Cases +++

from anytree import Node, LevelOrderIter

# Test Function
def test_breadth_first_visit(input, expected):
    return expected == breadth_first_visit(input)

# Algorithm
def breadth_first_visit(input, queue=[]):
    if queue:
        queue.remove(queue[0])

    result = [input]
    queue.extend(input.children)

    if queue: 
        result.extend(breadth_first_visit(queue[0]))

    return result

# Test Case
print(test_breadth_first_visit(book, list(LevelOrderIter(book))))
print(test_breadth_first_visit(book, list(LevelOrderIter(book))))

+++ Algorithm with Test Cases and Silvio's Tree +++

from anytree import Node, LevelOrderIter

# Silvio's Tree
book = Node("book")
chapter_1 = Node("chapter", book)
chapter_2 = Node("chapter", book)

paragraph_1 = Node("paragraph", chapter_1)
text_1 = Node("Alice was beginning to get very tired of sitting by "
              "her sister on the bank, and of having nothing to do: "
              "once or twice she had peeped into the book her sister "
              "was reading, but it had no pictures or conversations "
              "in it, ", paragraph_1)
quotation_1 = Node("quotation", paragraph_1)
text_2 = Node("“and what is the use of a book,”", quotation_1)
text_3 = Node(" thought Alice, ", paragraph_1)
quotation_2 = Node("quotation", paragraph_1)
text_4 = Node("“without pictures or conversations?”", quotation_2)

paragraph_2 = Node("paragraph", chapter_1)
text_5 = Node("So she was considering in her own mind, (as well as "
              "she could, for the hot day made her feel very sleepy "
              "and stupid,) whether the pleasure of making a "
              "daisy-chain would be worth the trouble of getting up "
              "and picking the daisies, when suddenly a white rabbit "
              "with pink eyes ran close by her.", paragraph_2)

paragraph_3 = Node("paragraph", chapter_1)
text_6 = Node("...", paragraph_3)
text_7 = Node("...", chapter_2)
text_8 = Node("...", book)

# Test Function
def test_breadth_first_visit(input, expected):
    return expected == breadth_first_visit(input)

# Algorithm
def breadth_first_visit(input, queue=[]):
    if queue:
        queue.remove(queue[0])

    result = [input]
    queue.extend(input.children)

    if queue: 
        result.extend(breadth_first_visit(queue[0]))

    return result

# Test Case
print(test_breadth_first_visit(book, list(LevelOrderIter(book))))
print(test_breadth_first_visit(book, list(LevelOrderIter(book))))

[essepuntato]

Hi @SeverinJB,

The following algorithm, hence, returns a list which contains in level-order (your requested order) all nodes of any given tree, i.e. [Node('/book'), Node('/book/chapter'), Node('/book/chapter'), Node('/book/...'), ...]

This is exactly what I wanted, since the various variables I've used in the example in the text of exercise the are actually references to objects.

[SeverinJB]

This is exactly what I wanted, since the various variables I've used in the example in the text of exercise the are actually references to objects.

@essepuntato Thanks, for the response.

[essepuntato]

Hi all,

I'm posting here my take on the exercise - you can find the source of this online as usual.

The solution I prepared does not change the signature of the function (i.e. the way the input parameters are defined), but actually specifies different variables as input of the recursive calls – this is possible in Python since it is a dynamically typing language. In practice, I reconstruct, in a ditionary, all the nodes in all the levels of the tree, and only at the very end (i.e. within the first call) I reconstruct the list to return.

Of course, this is not the only approach that can be used. In fact, as far as I can see, @SeverinJB's one works very well, and (at least from what I can see) it is even more elegant than the one I'm proposing here. Great job!

from tree_instructions import *

# Test case for the algorithm
def test_breadth_first_visit_recursive(root_node, expected):
    result = breadth_first_visit_recursive(root_node)
    if expected == result:
        return True
    else:
        return False

# Code of the algorithm
def breadth_first_visit_recursive(root_node):
    n_ancestors = len(root_node.ancestors)

    if n_ancestors == 0:
        cur_node = root_node
        levels = {}
    else:
        cur_node = root_node[0]
        levels = root_node[1]

    max_level = n_ancestors
    add_to_level(cur_node, n_ancestors, levels)

    for child in cur_node.children:
        cur_level = breadth_first_visit_recursive((child, levels))
        if cur_level > max_level:
            max_level = cur_level

    if n_ancestors:
        return max_level
    else:
        result = []
        for level in range(max_level + 1):
            result.extend(levels[level])
        return result

def add_to_level(node, level, levels):
    if level not in levels:
        levels[level] = []
    levels[level].append(node)

bfv = [book,
       chapter_1, chapter_2, text_8,
       paragraph_1, paragraph_2, paragraph_3, text_7,
       text_1, quotation_1, text_3, quotation_2, text_5, text_6,
       text_2, text_4]
print(test_breadth_first_visit_recursive(book, bfv))