Lecture "Organising information: trees", exercise 2

[essepuntato]

Write in Python the pure iterative version of the function defined in the previous exercise.

[diegochillo]

from anytree import Node


def test_breadth_iter(root_node, expected):
    result = breadth_iter(root_node)
    return result == expected


def breadth_iter(root_node):
    breadth_result = [root_node]
    levellist = [root_node]
    totalsons = []

    while levellist != []:  # Repeats until there are levels

        del totalsons[:]
        for thisnode in levellist:  # Cycles all the elements of the tree level
            nodesons = thisnode.children
            totalsons.extend(nodesons)  # Puts all the children of sibling nodes in the same list

        breadth_result.extend(totalsons)  # Adds brothers and cousins to the result list

        del levellist[:]
        levellist.extend(totalsons)  # Repeats with the list of brothers and cousins, if not empty

    return breadth_result


############### 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_iter(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_iter(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]

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

def test_node(root_element, expected):
    return breadth_first_visit(root_element) ==expected

def breadth_first_visit(root_node):
    result = []
    to_add = deque() #queue
    to_add.append(root_node)
    while len(to_add) != 0 :
        child= to_add.popleft()
        result.append(child.name)
        to_add.extend(child.children)
    return result
print(test_node(forest, expected_result))

[ConstiDami]

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()
        #This time the deque has to have an element in it in order to go into the while looop
        tree_list.append(root_node)
        tree_deque.append(root_node)

    while len(tree_deque) > 0:
        #erasing the root element from the deque, otherwise the firsts childs will be added to the list twice
        if root_node == root_node.root:
            tree_deque.clear()
        if root_node.children != ():
            tree_list.extend(root_node.children)
            tree_deque.extend(root_node.children)
        root_node = tree_deque.popleft()

    return tree_list


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

[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()
    for item in reversed(root_node.descendants):
        if item != root_node and item not in result:
            result.append(item.name)
            for item1 in item.siblings:
                result.append(item1.name)
    final = list()
    for item in reversed(result):
        final.append(item)
    return final

print(breadth_first_visit(book))

I think it does what it is supposed to do: underlining the 'I think' and 'supposed' in the previous sentence.

[fcagnola]

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

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)

def traversal_level_iterative(node):
    result = []  # empty variable result
    q = deque()
    q.append(node)

    while len(q) > 0:
        child = q.popleft()
        result.append(child.name)
        q.extend(child.children)

    return result

print(traversal_level_iterative(betty))

print(test_1_parameter(traversal_level_iterative, betty, ['betty', 'donald', 'bill', 'gerry', 'sally', 'bobby', 'joan', 'peggy', 'kenny', 'pete', 'terry', 'gina', 'bert', 'lane', 'roger', 'harry']))

[AlessandraFa]

from anytree import Node


def test_iterative_bfv(root, expected):
    return iterative_bfv(root) == expected


def iterative_bfv(root):
    result = []
    current_level = [root]
    while True:
        for node in current_level:
            result.append(node.name)    # appends nodes currently stored in current_level to result list
        tmp = []                        # initialises empty temporary list
        for node in current_level:      # iterates on elements in list current_level
            for child in childr(node):  # function childr(node) returns a list of children for each node in current_level
                tmp.append(child)       # each child node in the list of children is appended to the temporary list
        if len(tmp) == 0:               # stops iteration if node is a leaf node
            break
        else:
            current_level = tmp         # stores tmp's items in the list current_level for new iteration
    return result


def childr(node):
    ch_list = []
    for n in node.children:
        ch_list.append(n)
    return ch_list


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_iterative_bfv(book, ['book', 'chapter', 'chapter', '...', 'paragraph', 'paragraph', 'paragraph', '...', '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, ', 'quotation', ' thought Alice, ', 'quotation', '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.', '...', '“and what is the use of a book,”', '“without pictures or conversations?”']))

[yunglong28]

I have used a method that it's part of the anytree package: I hope this doesn't look like cheating, I've been through a lot of tests and reading before finding this. Being breadth-first a way of sorting according to the level of depth of nodes, this method was effective. Let me know if it could be considered correct.

from anytree import Node
from anytree import RenderTree
from anytree import LevelOrderIter

def iterative_breadt_first_search(root_node):
    result = []
    result = [node for node in LevelOrderIter(root_node)]
    return result


def test_iterative_breadt_first_search(root_node, expected):
    result = iterative_breadt_first_search(root_node)
    if result == expected:
        return True
    else:
        return False

#test
#mytree
#Root, L = 0
Socrate = Node('Socrate')

#Childrens, L = 1
Platone = Node('Plato', parent= Socrate)
Aristotele  = Node('Aristotele', parent = Socrate)

#Grandchildren, L = 2
StAg = Node('Agostino', parent= Platone)
Marsilio = Node('Marsilio Ficino', parent=Platone)
StThom = Node('San Tommaso', parent= Aristotele)
Avicenna = Node('Avicenna', parent=Aristotele)

#Descendants, L = 3
Scoto = Node('Scoto Eriugena', parent=StThom)
Dante = Node('Dante Alighieri', parent=StThom)

print(test_iterative_breadt_first_search(Socrate, [Socrate, Platone, Aristotele, StAg, Marsilio, StThom, Avicenna, Scoto, Dante])) #returns True

#test with Professor's tree
print(test_iterative_breadt_first_search(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]))  #returns True