Lecture "Organising information: trees", exercise 2

[essepuntato]

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

[ereuhl]

from anytree import Node


def breadth_first_visit(root_node):
    discovered_nodes = [root_node]
    visited_nodes = []
    while discovered_nodes:
        current_node = discovered_nodes.pop(0)
        visited_nodes.append(current_node)
        if current_node.children:
            for child in current_node.children:
                discovered_nodes.append(child)
    return visited_nodes


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


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]))  # True
print(test_breadth_first_visit(chapter_2, [chapter_2, text_7]))  # True
print(test_breadth_first_visit(text_1, [text_1]))  # True

Am I missing another type of test case?

[FrancescoFernicola]

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)

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


def breadth_first_visit(root_node):
    node_list = []
    base_node = [root_node]
    while base_node:
        other_node = base_node.pop(0)
        node_list.append(other_node)
        if other_node.children:
            for child in other_node.children:
                base_node.append(child)
    return node_list


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

[NoonShin]

from anytree import Node

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

def breadth_first_visit(root):
    lst = list()
    lst.append(root)
    for item in lst:
      lst.extend(item.children)
    return lst

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

[arcangelo7]

I just understood @NoonShin solution and changed the names of the variables with more semantic names.

from anytree import Node


def test_breadth_first_visit(root, expected):
    if breadth_first_visit(root) == expected:
        return True
    else:
        return False


def breadth_first_visit(root):
    visited_nodes = list()
    visited_nodes.append(root)
    for node in visited_nodes:
        visited_nodes.extend(node.children)

    return visited_nodes


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

[essepuntato]

Hi all,

please find attached my personal solution – also available online:

# 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


# Code of the function
def breadth_first_visit(root_node):
    result = list()
    to_visit = deque()
    to_visit.append(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


# 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]
print(test_breadth_first_visit(book, bfv))