Lecture "Organising information: trees", exercise 1

[essepuntato]

Write in Python a recursive function def breadth_first_visit(root_node). This function takes the root node of a tree and returns a list containing all the tree's nodes according to a breadth-first order. The breadth-first order considers all the nodes of the first level, then those of the second level, and so forth. For instance, considering the nodes created in Listing 2 in Chapter "Organising information: trees", 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.

[delete4ever]

from anytree import Node
book = Node("book")
chapter_1 = Node("chapter", book)
chapter_2 = Node("chapter", book)
paragraph_1 = Node("paragraph", chapter_1)
text_1 = Node("text_1", paragraph_1)
quotation_1 = Node("quotation", paragraph_1)
text_2 = Node("text_2", quotation_1)
text_3 = Node("text_3", paragraph_1)
quotation_2 = Node("quotation", paragraph_1)
text_4 = Node("text_4", quotation_2)
paragraph_2 = Node("paragraph", chapter_1)
text_5 = Node("text_5", paragraph_2)
paragraph_3 = Node("paragraph", chapter_1)
text_6 = Node("text_6", paragraph_3)
text_7 = Node("text_7", chapter_2)
text_8 = Node("text_8", book)

def test_dfv(root_node, expected):
    if breadth_first_visit(root_node) == expected:
        return True
    else:
        return False

def breadth_first_visit(root_node):
    result = list()
    h = root_node.height
    for i in range(1, h+2):
        indegree(root_node, i, result)
    return result
def indegree(root_node, level, result):
    if level == 1:
        result.append(root_node)
    else:
        for child in root_node.children:
            indegree(child, level - 1, result)     

print(test_dfv(book, [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])) #True

[n1kg0r]

from anytree import Node

# Test case for the function
def test_breadth_first_visit(root_node, expected):
    result = breadth_first_visit(root_node)
    if expected == result:
        return True
    else:
        return False

def breadth_first_visit(root):
    h = root.height
    result = list()
    for i in range(0, h+1):
        append_nodes_of_ith_level(root, i, result)
    print(result)
    return result

def append_nodes_of_ith_level(root, level, l):
    if root is None:
        return
    if level == 0:
        l.append(root)
    elif level > 0:
        for child_node in root.children:
            append_nodes_of_ith_level(child_node, level-1, l)

# Tests
book = Node("book")
chapter_1 = Node("chapter1", book)
chapter_2 = Node("chapter2", book)
paragraph_1 = Node("paragraph1", chapter_1)
text_1 = Node("text1", paragraph_1)
quotation_1 = Node("quotation1", paragraph_1)
text_2 = Node("text2", quotation_1)
text_3 = Node("text3", paragraph_1)
quotation_2 = Node("quotation2", paragraph_1)
text_4 = Node("text4", quotation_2)
paragraph_2 = Node("paragraph2", chapter_1)
text_5 = Node("text5", paragraph_2)
paragraph_3 = Node("paragraph3", chapter_1)
text_6 = Node("text6", paragraph_3)
text_7 = Node("text7", chapter_2)
text_8 = Node("text8", book)
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]
bfv_from_chapter_2 = [chapter_1, paragraph_1, paragraph_2, paragraph_3, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]

print(test_breadth_first_visit(book, bfv))
print(test_breadth_first_visit(chapter_1, bfv_from_chapter_2))

[n1kg0r]

@essepuntato Professor, the function in the solutions seems to fail on non-root inputs

*in case it was supposed to work with such inputs

bfv_from_chapter_2 = [chapter_1, paragraph_1, paragraph_2, paragraph_3, text_1, quotation_1, text_3, quotation_2, text_5, text_6, text_2, text_4]
print(test_breadth_first_visit(chapter_1, bfv_from_chapter_2))

#   File "/Users/nikolay/UNIBO/comp-think/homework/hw1612 copy.py", line 23, in breadth_first_visit
#     queue.extend(root_node.children)
# AttributeError: 'str' object has no attribute 'extend'

[essepuntato]

Hi @n1kg0r,

Indeed, it is not supposed to work on non-root if they are used in the first call. This is because of the following line of code:

if len(root_node.ancestors) == 0:  # It is the first call
        root_node.parent = Node(deque())

If you start from a non-root node, this won't be executed, returning an error in the following pieces of code. Anyway, some of the solutions you have proposed here try to address this limitation, indeed!