-
Notifications
You must be signed in to change notification settings - Fork 1
/
FamilyTree.py
236 lines (190 loc) · 7.76 KB
/
FamilyTree.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
'''
Consider a binary tree.
-zeroth cousin: If two nodes are siblings (have the same immediately preceding ancestor, such as nodes "H" and "I") they are zeroth cousins.
-first cousin: Children of zeroth cousins are first cousins.
-second cousin: Grandchildren of zeroth cousins are second cousins.
-In general, i'th cousins have a grandparent or ancestor that is i levels up from their parents.
Suppose two people, P1 and P2, are i'th cousins. Let C1 be a child of P1 and C2 be a child of P2. Then, C1 is an i'th cousin of P2, 1 removed, and C2 is an i'th cousin of P1, 1 removed.
Let G1 now be a child of C1. G1 is an i'th cousin of P2, 2 removed.
In general, the type of cousin (what 'i' is) is the shorter distance to the ancestor of two people, and the amount removed is the difference between the distance to the common ancestor.
Class Member is a class that represents a single person in the family, and Class Family represents the whole family tree.
You are to write code for the method cousin of the class Family according to the docstring in FamilyTree.py and the definitions for degree removed and cousin type.
'''
class Member(object):
def __init__(self, founder):
"""
founder: string
Initializes a member.
Name is the string of name of this node,
parent is None, and no children
"""
self.name = founder
self.parent = None
self.children = []
def __str__(self):
return self.name
def add_parent(self, mother):
"""
mother: Member
Sets the parent of this node to the `mother` Member node
"""
self.parent = mother
def get_parent(self):
"""
Returns the parent Member node of this Member
"""
return self.parent
def is_parent(self, mother):
"""
mother: Member
Returns: Boolean, whether or not `mother` is the
parent of this Member
"""
return self.parent == mother
def add_child(self, child):
"""
child: Member
Adds another child Member node to this Member
"""
self.children.append(child)
def is_child(self, child):
"""
child: Member
Returns: Boolean, whether or not `child` is a
child of this Member
"""
return child in self.children
class Family(object):
def __init__(self, founder):
"""
Initialize with string of name of oldest ancestor
Keyword arguments:
founder -- string of name of oldest ancestor
"""
self.names_to_nodes = {}
self.root = Member(founder)
self.names_to_nodes[founder] = self.root
def set_children(self, mother, list_of_children):
"""
Set all children of the mother.
Keyword arguments:
mother -- mother's name as a string
list_of_children -- children names as strings
"""
# convert name to Member node (should check for validity)
mom_node = self.names_to_nodes[mother]
# add each child
for c in list_of_children:
# create Member node for a child
c_member = Member(c)
# remember its name to node mapping
self.names_to_nodes[c] = c_member
# set child's parent
c_member.add_parent(mom_node)
# set the parent's child
mom_node.add_child(c_member)
def is_parent(self, mother, kid):
"""
Returns True or False whether mother is parent of kid.
Keyword arguments:
mother -- string of mother's name
kid -- string of kid's name
"""
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return child_node.is_parent(mom_node)
def is_child(self, kid, mother):
"""
Returns True or False whether kid is child of mother.
Keyword arguments:
kid -- string of kid's name
mother -- string of mother's name
"""
mom_node = self.names_to_nodes[mother]
child_node = self.names_to_nodes[kid]
return mom_node.is_child(child_node)
def cousin(self, a, b):
"""
Returns a tuple of (the cousin type, degree removed)
Keyword arguments:
a -- string that is the name of node a
b -- string that is the name of node b
cousin type:
-1 if a and b are the same node.
-1 if either one is a direct descendant of the other
>=0 otherwise, it calculates the distance from
each node to the common ancestor. Then cousin type is
set to the smaller of the two distances, as described
in the exercises above
degrees removed:
>= 0
The absolute value of the difference between the
distance from each node to their common ancestor.
"""
## YOUR CODE HERE ####
cousin_type = 0
degree_removed = 0
first_node = self.names_to_nodes[a]
second_node = self.names_to_nodes[b]
if(first_node == second_node or first_node.is_parent(second_node) or first_node.is_child(second_node)):
cousin_type = -1
if first_node == second_node:
degree_removed = 0
else:
degree_removed = 1
else:
node_a = first_node.get_parent()
list_a = list()
while(node_a != None):
list_a.insert(0, node_a)
node_a = node_a.get_parent()
node_b = second_node.get_parent()
list_b = list()
while(node_b != None):
list_b.insert(0, node_b)
node_b = node_b.get_parent()
small_list = list_a if (len(list_a) < len(list_b)) else list_b
big_list = list_a if (len(list_a) >= len(list_b)) else list_b
count = 0
for node_a in small_list:
node_b = big_list[count]
if(node_a == node_b):
count += 1
else:
break
if first_node.get_parent() == None or second_node.get_parent() == None:
cousin_type = -1
else:
cousin_type = len(small_list) - count
degree_removed = len(big_list) - len(small_list)
return (cousin_type, degree_removed)
f = Family("a")
f.set_children("a", ["b", "c"])
f.set_children("b", ["d", "e"])
f.set_children("c", ["f", "g"])
f.set_children("d", ["h", "i"])
f.set_children("e", ["j", "k"])
f.set_children("f", ["l", "m"])
f.set_children("g", ["n", "o", "p", "q"])
words = ["zeroth", "first", "second", "third", "fourth", "fifth", "non"]
## These are your test cases.
## The first test case should print out:
## 'b' is a zeroth cousin 0 removed from 'c'
t, r = f.cousin("b", "c")
print "'b' is a", words[t],"cousin", r, "removed from 'c'"
## For the remaining test cases, use the graph to figure out what should
## be printed, and make sure that your code prints out the appropriate values.
t, r = f.cousin("d", "f")
print "'d' is a", words[t],"cousin", r, "removed from 'f'"
t, r = f.cousin("i", "n")
print "'i' is a", words[t],"cousin", r, "removed from 'n'"
t, r = f.cousin("q", "e")
print "'q' is a", words[t], "cousin", r, "removed from 'e'"
t, r = f.cousin("h", "c")
print "'h' is a", words[t], "cousin", r, "removed from 'c'"
t, r = f.cousin("h", "a")
print "'h' is a", words[t], "cousin", r, "removed from 'a'"
t, r = f.cousin("h", "h")
print "'h' is a", words[t], "cousin", r, "removed from 'h'"
t, r = f.cousin("a", "a")
print "'a' is a", words[t], "cousin", r, "removed from 'a'"