Lecture "Organising information: trees", exercise 2

[essepuntato]

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

[SeverinJB]

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.

+++ Algorithm with Test Cases +++

from anytree import Node, LevelOrderIter

def test_iterating(input, expected):
    return expected == iterating(input)

def iterating(input, queue=list()):
    result = [input]
    queue.extend(input.children)

    while len(queue) > 0:
        result.append(queue[0])
        queue.extend(queue[0].children)
        queue.remove(queue[0])

    return result

print(test_iterating(book, list(LevelOrderIter(book))))
print(test_iterating(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_iterating(input, expected):
    return expected == iterating(input)

# Algorithm
def iterating(input, queue=list()):
    result = [input]
    queue.extend(input.children)

    while len(queue) > 0:
        result.append(queue[0])
        queue.extend(queue[0].children)
        queue.remove(queue[0])

    return result

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

[friendlynihilist]

@essepuntato: that's my take on the exercise. It was very hard to understand how to manipulate properly nodes and I'm not quite sure about it. In the end I've used queues and lists to store "discovered" and "visited" nodes. I'll tweak it later. Also, as mentioned by @SeverinJB, I don't know if I was supposed to print node names or not. I've attached tree rendering and printed queue: EDIT: updated with test case.

from anytree import Node, RenderTree, AsciiStyle
from collections import deque

book = Node("Lanark")
chapter_1 = Node("Chapter I", book)
chapter_2 = Node("Chapter II", book)
paragraph_1 = Node("Paragraph 1", chapter_1)
paragraph_2 = Node("Paragraph 2", chapter_1)
paragraph_3 = Node("Paragraph 1", chapter_2)
paragraph_4 = Node("Paragraph 2", chapter_2)
quotation_1 = Node("He looked at them and saw their faces did not fit."
                   " The skin on the skulls crawled and twitched like half-solid paste.", paragraph_1)

renderer = RenderTree(book)
print(RenderTree(book, style=AsciiStyle()).by_attr())

def test_breadth_first_order(root_node, expected):
    result = breadth_first_order(root_node)
    if expected == result:
        return True
    else:
        return False

def breadth_first_order(root_node):
    queue = deque()
    result = [root_node.name]
    queue.append(root_node)

    while len(queue) > 0:
        for item in queue.popleft().children:
            result.append(item.name)
            queue.append(item)

    return result

print(test_breadth_first_order(book, ['Lanark', 'Chapter I', 'Chapter II', 'Paragraph 1', 'Paragraph 2', 'Paragraph 1', 'Paragraph 2', 'He looked at them and saw their faces did not fit. The skin on the skulls crawled and twitched like half-solid paste.']))

[essepuntato]

Hi all,

I'm posting here my take on the exercise - you can find the source of this online as usual. It is worth mentioning that, usually, the breadth visit of a tree is seen as a typical example of iterative algorithm – that's why the solution of this exercise is smaller and more "natural" (at least from my perspective) than the recursive one.

from tree_instructions import *
from collections import deque

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

# Code of the algorithm
def breadth_first_visit_iterative(root_node):
    result = []
    to_visit = deque([root_node])

    while to_visit:
        node_to_visit = to_visit.popleft()
        result.append(node_to_visit)
        to_visit.extend(node_to_visit.children)

    return result

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_iterative(book, bfv))

[delfimpandiani]

I had written this code before, but was still struggling to find a way of producing the desired output without knowing beforehand the number of generations present in the input tree. Now that I have seen Prof. Peroni's take, mine seems a tad convoluted. But I am happy it works, at least with the test case provided by Silvio.

def test_breadth_first_visit(root_node, expected):
    result = breadth_first_visit_iterative(root_node)
    if expected == result:
        return True
    else:
        return False

def breadth_first_visit(input):
    result = [input]
    generation1 = [input.children]
    generation2 = []
    generation3 = []
    generation4 = []
    generation_list = [generation1, generation2, generation3, generation4]
    for generation in generation_list:
        for gen_el in generation:
            result.append(gen_el)
            generation_list[index(generation) + 1].extend([gen_el.children])
    return result

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(book, bfv))
# True