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 nodes of the tree according to a breadth-first order. The breadth-first order considers 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.

[diegochillo]

I feed the recursive function with the items of a list compiled by the function itself.

from anytree import Node

def test_breadth_first_visit(root_node, expected):
    result = breadth_first_visit(root_node)
    return result == expected

# Service lists:
finallist = []
indexrec = []

def breadth_first_visit(root_node):

    if root_node == root_node.root:  # Cleans up service lists and puts in the root node at first
        del finallist[:]
        del indexrec[:]
        finallist.append(root_node)

    if len(indexrec) != len(root_node.root.descendants) - 1:  # if it hasn't finished checking nodes
        finallist.extend(root_node.children)
        indexrec.append(1)
        breadth_first_visit(finallist[len(indexrec)])

    return finallist

############### TEST CASES ##################

# My tree definition and test
mytree = Node("mytree")
branch1 = Node("branch1", mytree)
sprig11 = Node("sprig11", branch1)
leaf111 = Node("leaf111", sprig11)
sprig12 = Node("sprig12", branch1)
branch2 = Node("branch2", mytree)
sprig21 = Node("sprig21", branch2)
sprig22 = Node("sprig22", branch2)
branch3 = Node("branch3", mytree)
sprig23 = Node("sprig23", branch2)
sprig31 = Node("sprig31", branch3)
leaf311 = Node("leaf311", sprig31)
leaf312 = Node("leaf312", sprig31)
sprig32 = Node("sprig32", branch3)

print(test_breadth_first_visit(mytree,
                               [mytree, branch1, branch2, branch3, sprig11, sprig12, sprig21, sprig22, sprig23, sprig31,
                                sprig32, leaf111, leaf311, leaf312]))

# Peroni's tree definition and test
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)

print(test_breadth_first_visit(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]))

[dbrembilla]

I tried my best to solve this exercise, but I keep getting recursion errors that should not happen and I don't understand why. This is what I came up with.

'''
The node tree looks like this:
ROOT: forest
Children: pine1, pine2, birch1, birch2,birch3, fallen_branch
Grandchildren(pine1): branch1, branch2, branch3
Grandchildren(pine2): branch4, branch5
Grandchildren(birch1): branch6
Grandchildren(birch2): branch7, branch8
Grandchildren(birch3): branch9, branch10, branch11
Grandgrandchildren(branch6): leaf1
'''
from anytree import Node
from collections import deque

expected_result = ["forest", "pine1", "pine2", "birch1", "birch2", "birch3", "fallenbranch", "branch1", "branch2", "branch3", "branch4", "branch5", "branch6", "branch7", "branch8", "branch9", "branch10", "branch11", "leaf1"]

forest = Node("forest")
pine1 = Node("pine1", forest)
pine2 = Node("pine2", forest)
birch1 = Node("birch1", forest)
birch2 = Node("birch2", forest)
birch3 = Node("birch3", forest)
fallen_branch = Node("fallenbranch", forest)
branch1= Node("branch1", pine1)
branch2= Node("branch2", pine1)
branch3= Node("branch3", pine1)
branch4= Node("branch4", pine2)
branch5= Node("branch5", pine2)
branch6= Node("branch6", birch1)
branch7= Node("branch7", birch2)
branch8= Node("branch8", birch2)
branch9= Node("branch9", birch3)
branch10= Node("branch10", birch3)
branch11=Node("branch11", birch3)
leaf1=Node("leaf1", branch6)

#temporary lists
tmp_ancestors = [] #used to distinguish the first run from the others
tmp_siblings = deque() #used as a queue to popleft each element
tmp_sibling_children = [] #used to gather all the children elements for the next level

#conditions
has_no_ancestors = len(tmp_ancestors) == 0
has_no_siblings = len(tmp_siblings) <= 1
has_sibling_children = len(tmp_sibling_children) != 0

def breadth_first_visit(root_node):
    result = []
    if (not has_no_ancestors) and has_no_siblings and (not has_sibling_children):
        result.append(root_node.name)
        return result
    elif has_no_ancestors and has_no_siblings and (not has_sibling_children): #1st run
        tmp_ancestors.append(root_node)
        tmp_siblings.extend(root_node.children)
        result.append(root_node.name)
        next_item = [breadth_first_visit(tmp_siblings[0])]
        return result.extend(next_item)
    elif has_no_siblings and has_no_ancestors and has_sibling_children:
        tmp_sibling_children.extend(root_node.children)
        tmp_sibling_children.clear()
        tmp_siblings.popleft()
        tmp_siblings.extend(tmp_sibling_children)
        result.append(root_node.name)
        return result.extend(breadth_first_visit(tmp_siblings[0]))
    elif not has_no_siblings:
        tmp_sibling_children.extend(root_node.children)
        tmp_siblings.popleft()
        result.append(root_node.name)
        return result.extend(breadth_first_visit(tmp_siblings[0]))

def test_tree(root_test, expected):
    return breadth_first_visit(root_test) == expected

print(test_tree(forest, expected_result))

[ConstiDami]

Both tests return True. It took me a very long time to figure out how to proceed... After a lot of tests I found that the deque was a good solution!

from anytree import Node
from collections import deque

#the list is used to store the final result,
#the deque makes sure to add the children in the right order (breadth first approach)
tree_list = []
tree_deque = deque()

def breadth_first_visit(root_node):

    #this if statement clears the global variables, to start over at every call of the function with a different tree
    if root_node == root_node.root:
        tree_list.clear()
        tree_deque.clear()
        # only the list takes the root node, because the deque has to call the function with the first child
        # and not the root a second time
        tree_list.append(root_node)

    #Adding the children if they exist, otherwise calling the function with the next element in the deque
    if root_node.children != ():
        tree_list.extend(root_node.children)
        tree_deque.extend(root_node.children)
        breadth_first_visit(tree_deque.popleft())
    elif len(tree_deque) != 0:
        breadth_first_visit(tree_deque.popleft())

    #if there are no more elements in the deque => if we have reached all the descendants of the root,
    #returning the list
    if len(tree_deque) == 0:
        return tree_list

    #return statement for all the other times the function is called
    else:
        return

def test_breadth_first_visit(root_node, expected):
    return expected == breadth_first_visit(root_node)

###Test cases

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)

print(test_breadth_first_visit(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]))

grandma = Node("Nonna")
uncle = Node("Davide", grandma)
mum = Node("Elisabetta", grandma)
brother_1 = Node("Hadrien", mum)
brother_2 = Node("Clément", mum)
sister = Node("Constance", mum)
cousin_1 = Node("Nicola", uncle)
cousin_2 = Node("Benoit", uncle)
cousin_3 = Node("Quentin", uncle)

print(test_breadth_first_visit(grandma, [grandma, uncle, mum, cousin_1, cousin_2, cousin_3, brother_1, brother_2, sister]))

[AlessandroBertozzi]

My function run as a depth first-visit function (development exercise) and order all the nodes by the len of their ancestors: from the shorter node (root node) to the longest ones.

from anytree import Node, RenderTree

# 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 case for the algorithm
def test_breadth_first_visit(node, expected):
    result = breadth_first_visit(node)
    if expected == result:
        return True
    else:
        return False

# Algorithm
def breadth_first_visit(node):
    result = list()
    breadth_first_visit_recursive(node, result)
    return result

def breadth_first_visit_recursive(node, list):
    if node == node.root:
        list.append(node)
    else:
        for nodes in reversed(list):
            if len(nodes.ancestors) <= len(node.ancestors):
                position = list.index(nodes)
                list.insert(position + 1, node)
                break
    for child in node.children:
        breadth_first_visit_recursive(child, list)

print(breadth_first_visit(book))
print(test_breadth_first_visit(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]))

[fcagnola]

It took me so much time that when it finally returned True I couldn't believe it, and ran a thousand additional tests. I pasted just the first one because trees take up quite a lot of space

# 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 nodes of the tree according to a breadth-first order. The breadth-first order
# considers 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.

from testing_functions import test_1_parameter
from collections import deque
from anytree import Node, RenderTree

queue = deque()

def traversal_level(node):
    result = []  # empty variable result

    if node.name not in result:  # if the node passed as input is not in the result list, add it immediately
        result.append(node.name)

    if node.children != ():  # additionally, if the node has children, add these to the queue
        for n in node.children:
            queue.append(n)

    while len(queue) > 0:  # while the queue is not empty, run the function recursively with the queue's elements as input
        result.extend(traversal_level(queue.popleft()))

    return result  # finally (and for each recursive call) return the list generated

betty = Node("betty")
donald = Node("donald", betty)
bill = Node("bill", betty)
gerry = Node("gerry", betty)
sally = Node("sally", donald)
bobby = Node("bobby", donald)
joan = Node("joan", bill)
peggy = Node("peggy", bill)
kenny = Node("kenny", gerry)
pete = Node("pete", gerry)
terry = Node("terry", sally)
gina = Node("gina", joan)
bert = Node("bert", joan)
lane = Node("lane", kenny)
harry = Node("harry", bert)
roger = Node("roger", pete)
r = RenderTree(betty)
print(r)
print(test_1_parameter(traversal_level, betty, ['betty', 'donald', 'bill', 'gerry', 'sally', 'bobby', 'joan', 'peggy', 'kenny', 'pete', 'terry', 'gina', 'bert', 'lane', 'roger', 'harry'])) # returns True

[giorgiasampo]

from anytree import Node, RenderTree

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)

print(RenderTree(book))

def breadth_first_visit(root_node):
    result=list()
    result.append(root_node)
    result.append(root_node.children)
    child_list = list()
    for item in root_node.descendants:
        if item.children != ():
            for element in item.children:
                child_list.append(element.name)
                breadth_first_visit(element)
                if child_list not in result:
                    result.append(child_list)
    return result

print(breadth_first_visit(book))

I think it works but I got a bit lost on it...

[laurentfintoni]

I'm confused about something @essepuntato - in your exercise description you say that the resulting list for the nodes from Listing 2 should be [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]. But when I use the solution you gave and print the function (not the test) I get [Node('/book'), Node('/book/chapter1'), Node('/book/chapter2'), Node('/book/text8'), Node('/book/chapter1/paragraph1'), Node('/book/chapter1/paragraph2'), Node('/book/chapter1/paragraph3'), Node('/book/chapter2/text7'), Node('/book/chapter1/paragraph1/text1'), Node('/book/chapter1/paragraph1/quotation1'), Node('/book/chapter1/paragraph1/text3'), Node('/book/chapter1/paragraph1/quotation2'), Node('/book/chapter1/paragraph2/text5'), Node('/book/chapter1/paragraph3/text6'), Node('/book/chapter1/paragraph1/quotation1/text2'), Node('/book/chapter1/paragraph1/quotation2/text4')]

What's confusing me is that based on how you wrote the exercise description I was expecting that running the function should print the list exactly how you have it in the description. But if I understand correctly that's not possible and instead it will always print with Node('node_name'), but those node values are equivalent to their titles (hence why it matches the bfv value you use in your solution)?

I hope that makes sense? I've spent the past two weeks trying to understand how to get python to print the node's value name only because the way you formatted the description totally threw me off.

lmk thanks

[laurentfintoni]

actually I also just realized that the elements of Listing 2 needed renaming, i've been using them as they are in the tree_instructions.py file and that has totally thrown me off as well.

[LuisAmmi]

I finally succeeded! I do not deny that I also viewed the solutions shared by others (especially the code written by Constance), but they helped me so much to get the sense. I know that it is missing the test, but I'll complete it in the next days. For now, I'm quite satisfied :') I tried to use my family tree as example, in order to check if with many branches it still works.

from collections import deque
from anytree import Node, RenderTree

tree_queue = deque()
result = list()

def breadth_first_visit(root_node):

    if len(root_node.ancestors) == 0:  # That means we're dealing with the root-node (It happens only one time)
        tree_queue.clear()   #we need to clean our queue and list, beacuse they're outside the function, so
        result.clear()       # if we want to re-call the function with different data, it will continue printing the first tree
        result.append(root_node)
    if root_node.children != ():       # if we're not in the leaf condition
        result.extend(root_node.children)
        tree_queue.extend(root_node.children)
        breadth_first_visit(tree_queue.popleft())
    elif len(tree_queue) != 0:                    # we need this condition to complete the sequence of leafs
        breadth_first_visit(tree_queue.popleft())
    return result

grandpa = Node("Nonno Giuseppe")
aunt_Antonietta = Node("Antonietta", grandpa)
uncle_Filippo = Node("Filippo", grandpa)
aunt_Catia = Node("Caterina", grandpa)
uncle_Enrico = Node("Enrico", grandpa)
dad = Node("Adriano", grandpa)
Pietro = Node("Pietro", aunt_Antonietta)
Roberto = Node("Roberto", aunt_Antonietta)
Giuseppe = Node("Giuseppe", uncle_Filippo)
Arianna = Node("Arianna", uncle_Enrico)
Raffaele = Node("Raffaele", aunt_Catia)
Antonella = Node("Antonella", aunt_Catia)
Rossana = Node("Rossana", uncle_Enrico)
Anna = Node("Anna", aunt_Catia)
Annapaola = Node("Annapaola", uncle_Filippo)
Peppe = Node("Peppe", uncle_Enrico)
Anna_sister = Node("Anna", dad)
Me = Node("Luisa", dad)
Ilaria = Node("Ilaria", Giuseppe)
Chiara = Node("Chiara", Giuseppe)
Giuseppe_junior = Node("Giuseppe_junior", Roberto)
Fatima = Node("Fatima", Raffaele)
Naima = Node("Naima", Antonella)
Chico = Node("Chico", Rossana)
Mattias = Node("Mattias", Antonella)
Antonio = Node("Antonio", Raffaele)

print(breadth_first_visit(grandpa))
render = RenderTree(grandpa)
print(render)