Project 4 — Family Trees solution

Description

Goal
Given a set of parents and children, determine how pairs of people are related, if at all.
Details
The input to the program consists of two parts. The first line consists of two integers ƒ and q, which
are the number of nuclear families and queries that follow. The next ƒ lines each describe one
nuclear family. These lines are of the form m ƒ ther mother chd1 chd2 . . . chdm, where m
is the number of children in the nuclear family and the remaining elements are names. The last q
lines are pairs of names.
A name is any sequence of non-space characters.
Some definitions for ascertaining relationships:
• p is a 0-descendent of q if p is a child of q.
• p is a k-descendent of q if p is a child of some person r and r is a (k − 1)-descendent of q.
• p is a 0-ancestor of q if p is a parent of q.
• p is a k-ancestor of q if p is a parent of some person r and r is a (k − 1)-ancestor of q.
If two people p and q are related, then they are related in one of the following manners:
• child
p is a child of q if p is a 0-descendent of q
• grandchild
p is a grandchild of q if p is a 1-descendent of q
• great great . . . great
| {z }
n times
grandchild
This is when p is an (n + 1)-descendent of q
• parent
p is a child of q if p is a 0-ancestor of q
• grandparent
p is a grandparent of q if p is a 1-ancestor of q
• great great . . . great
| {z }
n times
grandparent
This is when p is an (n + 1)-ancestor of q
Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034
• cousins and siblings
Let r be the closest common ancestor to p and q; that is, no descendent of r is also an
ancestor of both p and q. Suppose that p is an m-descendent of r and q is an n-descendent
of r. Let s = mn(m, n) and let t = |m − n|. Then, p and q are s-cousins t times removed.
0
th-cousins zero times removed are siblings.
For each query p q, output one of the following lines as appropriate:
• child, grandchild, great great . . . great grandchild
If p is a descendent of q
• parent, grandparent, great great . . . great grandparent
If p is an ancestor of q
• sibling
If p and q are 0-cousins zero times removed
• m-cousin
If p and q are m-cousins zero times removed
• m-cousin removed n
If p and q are m-cousins n times removed
• No relation
If p and q are not related
.Limitations
For any query, there will be at most two closest common ancestors; these will be spouses of each
other.
There will be at most 500 unique names.
What to turn in
Turn in your source code and Makefile. If you use Code::Blocks, turn in a tarball of your project
directory.
2 of 3
Data Structures and Objects Project 4 — Family Trees Fall 2017 — CRN 42034
Example Input
13 6
2 bill wilma brenda deb
3 bob.1 diana bob.2 kelly angela
4 mac pearl lloyd bill barb bob.1
2 kelly glenn hilary ashlee
2 bob.2 betty tony nick
1 bob.3 barb bob.4
9 joe.1 nettie ron.1 joe.2 jim.1 bob.3 carol georgia charlie mary.ellen lynette
4 jim.1 mary.ann jim.2 michael bradley brian
3 michael kris max madison mckenna
3 jim.2 connie alex kerri zack
2 ron.1 jackie ron.2 jacob
2 joe.3 helen joe.1 katherine
3 jim.3 emma joe.3 jim.4 george
alex emma
joe.3 ron.2
nick kelly
georgia charlie
deb jacob
tony ashlee
Sample Output
great great great grandchild
great grandparent
0 cousin 1 removed
sibling
no relation
1 cousin