CSc 120 Genealogy

Background

At a wedding reception, you find yourself sitting next to someone whose mother's aunt is your father's grandmother. How are you two related? This problem aims to write a program to figure that out.

This assignment focuses on trees and recursion, but also gives you an opportunity to make many of your design decisions for yourself. Conceptually, it has some similarities with the BST problem in Assignment 9 (so you will have encountered some aspects of the problem previously) but also some important differences (so it will need some thoughtful problem-solving).

Program behavior

In a file genealogy.py (plus any additional files you may use for defining your classes) write a Python program that implements the following functionality:

1. a function build_family_tree(rels ) where rels is a list of parent-child relationships, where each parent-child relationship is a tuple (parent, child). It returns a tuple (lookup_tree , family_tree ) where:

• lookup_tree is (a pointer to the root of) the BST used to map names to family tree nodes, as described in "2. The BST" under Data Structures below.
• family_tree is (a pointer to the root of) the family tree corresponding to the parent-child relationships provided (see Data Structures below); and

2. a function get_relationship(family_tree , name1 , name2 ) where family_tree is a tree built using the function build_family_tree() and name1 and name2 are strings. It returns a pair (path1 , path2 ) that are defined as follows: let node1 and node2 be the nodes in family_tree corresponding to name1 and name2 respectively, and let lca_node be their lowest common ancestor. Then path1 is a Python list (i.e., array) of strings giving the path from lca_node to node1 and path2 is a list of strings giving the path from lca_node to node2

Data Structures

1. Family Tree

A family tree is a tree where: (1) each node corresponds to a person; and (2) if person X is a parent of a person Y, then the node in the family tree corresponding to X is the parent of the node corresponding to node Y. For example, the following is part of William Shakespeare's family tree ( click on the image for a larger 1 picture): see image.

Notice that the tree shown above is not a binary tree: some nodes have more than two children. Also, notice that (because this is a tree) we can represent only one of the parents of each person.

You should define a class Person such that each node in the family tree is a Person object. A node in the family tree corresponding to a name X should have pointers to the family tree nodes corresponding to the children of X (as specified by the parent-child relationship tuples).

Required methods: None. The correctness of your family tree will be tested using the paths computed by the get_relationship() function.

2. The BST

The argument rels passed to your build_family_tree(rels ) function is a list of tuples where each tuple (X, Y) specifies that X is the parent of Y. For example, the input corresponding to Shakespeare's family tree shown above is:

[ (Susana_Shakespeare, Elizabeth_Hall),
(William_Shakespeare, Hamnet_Shakespeare),
(William_Shakespeare, Judith_Shakespeare),
(William_Shakespeare, Susana_Shakespeare) ]

However, there is no particular pre-defined order to the elements of this list. For example, in the example 2 shown above, the root of Shakespeare's family tree is William_Shakespeare but the names Susana_Shakespeare and Elizabeth_Hall may be encountered before the name William_Shakespeare is encountered. Because each element of this list is a tuple, the order of values inside the tuple is important. For example, the first tuple shown above states that Susana_Shakespeare was Elizabeth_Hall's parent, not vice versa.

This lack of any pre-defined order between elements of the list means that we have to deal with two problems when we process parent-child relationships:

1. When we process a name (as part of a parent-child relationship pair), we don't know whether (a) this is the first time we're seeing the name, in which case we have to create a node for it in the family tree; or (b) whether we've seen the name before, in which case there is already a node for it in the family tree. So we have to do some book-keeping to keep track of which names we've seen already, and which family tree node each such name corresponds to.

2. Unfortunately, we can't simply search our partially-constructed family tree to see if (the node corresponding to) a name is in the tree. The reason is that the lack of order among the parent-child relationship tuples means that our partially-constructed family tree may not be traversable. For example, consider the first two tuples shown above for Shakespeare's family tree:

{(Susana_Shakespeare, Elizabeth_Hall),
(William_Shakespeare, Hamnet_Shakespeare), ... }

There is no parent-child relationship that connects all of these nodes, so when we encounter the name Judith_Shakespeare in the third tuple we don't really have a tree that we can traverse to see whether we've seen that name already.

To deal with these problems, we need a separate data structure that keeps track of all the names we've seen so far, and maps each such name to the corresponding node in the family tree. This assignment requires that this data structure be a binary search tree:

• the keys for this BST are the names of the people mentioned in the family tree;
• the keys are inserted into the BST in the order in which names are encountered for the first time in the input list; and
• each node in the BST points to the node with the same name in the family tree.

For example, suppose that the sequence of parent-child relationship tuples for Shakespeare's family tree are encountered in the order shown above. Then the order in which names are encountered for the first time, and the resulting binary search tree, is as follows: see image.

A picture showing the mapping from nodes of the bookkeeping BST shown above to those of the family tree shown previously can be found here.

Required methods: Your BST should implement a method path_strings(name), where name is a string, such that for any BST object from_node, the value of from_node.path_strings(name) is the list of strings corresponding to the names of the nodes on the path from from_node to the node corresponding to name; None if there is no such path.

Algorithm

Your program must accomplish the following tasks. The exact algorithm by which it does so is up to you, as long as you meet the Programming Requirements listed below.

1. Given a collection of parent-child relationship tuples rels , the function build_family_tree(rels ) should construct and return a tuple (lookup_tree, family_tree) as discussed above. Sub-tasks here include the following:

• Constructing the family tree by (1) creating Person objects for names (when a name is first encountered); and (2) using the parent-child relationship tuples to add pointers from the object for a given name to the objects for its children.
• Using a BST to implement a mapping from names (strings) to the corresponding nodes in the family tree.
• Figuring out which node is the root of the family tree so that build_family_tree() can return a pointer to it. The root node is one that is not the child of any other node; we will make sure that your input data will be such that each family tree has exactly one root node. It is possible to find the root node by making a single pass over the list of parent-child relationship tuples.

2. Given a family tree family_tree constructed by your build_family_tree() function, and strings name1 and name2 , return a pair (path1 , path2 ) that are defined as follows:

• let node1 be the node in family_tree corresponding to name1 , and node2 the node corresponding to name2 ;
• let lca_node be the lowest common ancestor of node1 and node2 ;
• then path1 is a Python list of strings giving the names of the nodes on the path from lca_node to node1 ; path2 is similar, but for the path from lca_node to node2

Programming Requirements

• The "book-keeping data structure" that maps names to their family tree nodes should be a BST.
  • It should implement a method path_strings() as described above.
• The family tree should be a tree.
• The construction of the book-keeping BST should be done recursively using a recursive insert() method. Tree traversals (both the BST and the family tree) must be done recursively.
• For each node in the family tree, the collection of (pointers to) its children can be any appropriate Python data structure. This collection can be processed either iteratively (using a loop) or recursively.

Examples: see image.

Postscript

In reality, of course, we don't specify our relationships with family members by specifying how to navigate around the family tree (e.g., using the paths from the lowest common ancestor computed in this assignment). Rather, we give names to these relationships: sibling , uncle , great-grandfather , etc.

Suppose that the distance from name1 to its lowest common ancestor is Up and the distancefrom the lowest common ancestor to name2 is Dn . It turns out that it isn't all that difficult to implement a mapping from our Up/Dn values to these relationship namesyou aren't required to do this for this assignment, but if you want you can try to puzzle out how to go from Up/Dn values to relationship names. For example: see image.

Remember your neighbor from the wedding reception whose mother's aunt was your father's grandmother? It turns out that in this case Up = 3 and Dn = 4, making her your second cousin once removed.