Lecture "Organising information: trees", exercise 2
essepuntato opened this issue · 7 comments
essepuntato commented
Write in Python the pure iterative version of the function defined in the previous exercise.
diegochillo commented
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 commented
'''
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 commented
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 commented
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 commented
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 commented
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 commented
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