Lecture "Organising information: trees", exercise 2

[essepuntato]

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

[frammenti]

from anytree import Node
from tree_instructions import *

def test_breadth_first_visit_it(root_node, expected):
    return breadth_first_visit_it(root_node) == expected

def breadth_first_visit_it(root_node):
    tree_list = []
    tree_list.append(root_node)
    while len(root_node.children) > 0:
        for child in root_node.children:
            tree_list.append(child)
            for grandchild in child.children:
                grandchild.parent = root_node
            child.parent = None
    return tree_list

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

print(test_breadth_first_visit_it(book, test_list))

[Liber-R]

[qwindici]

Functions:

from collections import deque 

def breadth_first_visit_iteration(root_node):
   q = deque([root_node])
   result = [root_node]

   while q:
      current_node = q.popleft()
      q.extend(current_node.children)
      result.extend(current_node.children)
   
   return result


def test_breadth_first_visit_iteration(root_node, expected):
   if breadth_first_visit_iteration(root_node) == expected:
      return True
   else:
      return False
   
test_breadth_first_visit_iteration(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
test_breadth_first_visit_iteration(one, [one, two, three, four, five, six, seven, eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen]) # True
test_breadth_first_visit_iteration(one_node, [one_node]) # True

Trees:

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


one = Node("1")
# children of one
two = Node("2", one)
three = Node("3", one)
four = Node("4", one)
# children of 2
five = Node("5", two)
six = Node("6", two)
# children of 3
seven = Node("7", three)
eight = Node("8", three)
nine = Node("9", three)
# children of 4
ten = Node("10", four)
eleven = Node("11", four)
# children of 5
twelve = Node("12", five)
# children of 7
thirteen = Node("13", seven)
fourteen = Node("14", seven)
# children of 9
fifteen = Node("15", nine)

print(RenderTree(one))


one_node = Node('only node')

[rufferbaraldi]

from anytree import Node
from anytree import RenderTree
from collections import deque

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_node):
    result = []
    queue = deque([root_node])

    while queue:
        current_node = queue.popleft()
        result.append(current_node)
        for child in current_node.children:
            queue.append(child)

    return result


# Tests
book = Node("book")
chapter_1 = Node("chapter1", book)
chapter_2 = Node("chapter2", book)
paragraph_1 = Node("paragraph1", chapter_1)
paragraph_2 = Node("paragraph2", chapter_1)
paragraph_3 = Node("paragraph3", chapter_1)
text_1 = Node("text1", paragraph_1)
text_2 = Node("text2", paragraph_1)
text_3 = Node("text3", paragraph_2)
text_4 = Node("text4", paragraph_3)
text_5 = Node("text5", chapter_2)
text_6 = Node("text6", book)


renderer = RenderTree(book)

print(test_breadth_first_visit(book, [book, chapter_1, chapter_2, text_6, paragraph_1, paragraph_2, paragraph_3, text_5, text_1, text_2, text_3, text_4]))
print(renderer)