biological family trees

代写完成–家族关系系统

Introduction

This project deals with biological family trees. A family tree is defined in this project as a set of individuals who are “connected” to each other by genetic relationships. You will write a Java program to solve the problem of determining how people are related to each other.

Problem Background

For this problem, you must design and write a Java program that will read an input stream that defines a family tree, and then answer questions about different specializations of “related” between people in the tree. There are two kinds of questions you will handle:

A) “IS-A” Questions: These are “Yes/No” questions about whether two people <A> and share the following relationships:
1. Is <A> a child of (order of names matters!)
2. Is <A> a sibling of
3. Is <A> an ancestor of
4. Is <A> a cousin of
5. Is <A> unrelated to
B) “WHO-IS-A” Questions: “Who are all the people who are A’s <relation>?” <Relation> can be any of the relationships listed for “IS-A” Questions.
Another way of looking at a family tree is to view it as a directed graph. The nodes represent individuals, connected by edges (arrows) that represent the “offspring” relationship. An edge from one node to another means that the latter node is an offspring of the former node. In general, we can say one node (individual A) is an direct ancestor of another node (individual B) if and only if (iff) there is a backward sequence of one or more edges from node B back to node A.

Nodes in a family tree have at most two edges in (one for each biological parent), and an arbitrary number of edges out (one for each offspring). Two people are related if they share a common ancestor OR if one is a direct ancestor of the other. Thus, if two people have no common ancestor AND neither is the direct ancestor of the other, then they are unrelated.

Defining the cousin relationship

Another way of looking at the cousin relationship is that it is the same as the first part of the related definition: two people are cousins iff they share a common ancestor, (but neither is a direct ancestor of the other). Thus, a parent and a child are not considered cousins, nor would grandparents and their grandchildren be considered cousins. Note that siblings are actually 0th cousins by this definition! An interesting element here is the category of “first/second/third/etc- cousin, once/twice/thrice/etc. removed.” To begin with, suppose the following facts:
A and B are siblings, C is a child of A,
D is a child of B,

Then C and D are first cousins. Proceeding logically, if C has a child X and D has a child Y, then X and Y are second cousins. However, what is the relationship between C and Y? Why, C and Y are first cousins, once removed! For our purposes in the current project, we’ll just assume that C and Y are simply first cousins.

Re-Marriages

A twist in this problem is that you’ll have to be careful of second, third, fourth, etc marriages – do not assume that a person can have at most one spouse. In the case of second marriages, technically the children from each spouse’s earlier marriage are NOT siblings, but new children produced after the marriage are (half-)siblings of the earlier marriages’ offspring. I n o u r project, however, we’ll have to recognize that there can be remarriages, BUT two people with only a single parent in common are still siblings.

Problem I/O Specification

The family tree will be supplied to your program via standard in. This means you should be sure to open a BufferedReader or Scanner on the System.in stream. You should also be printing all output to System.out.

NOTE: You must NOT write the program so that it always looks at some hard- coded data file name or so that you have to supply the name as a command line argument.
You can assume that there will be no formatting errors to check for. Each line in the family tree will have the form
E <name1> <name2> or E <name1> <name2> <name3>
which has the meaning “<name1> and <name2> are married” or “the married parents <name1> and <name2> produced a child <name3>.” Note that marriage events and birth events are listed chronologically, and that not all marriages produce children. Names have no spaces in them and contain no hyphens.

The family tree file will also have query lines (possibly interspersed with event lines). These will have the form
QUERY Meaning
X <name1> <relation> <name2> Is <name1> the <relation> of <name2>?
W <relation> <name1> List everyone who is the <relation> of <name1>.
<relation> can be child, sibling, ancestor, cousin, or unrelated.
Whenever the program encounters a query, it must answer according to the knowledge so far collected as events in the input file. Note that <relation> for cousin will be the word “cousin” followed by a number indicating the type of cousin.

No output is required when the program encounters an event line. When a query line is encountered, the program must print out a blank line, then print the query, then on the next line print out the response. The response to “X” queries must be either “Yes” or “No.” The response to “W” queries must be all the names, one per line, that correctly answer the question. The names must be sorted in alphabetical order.

Example I/O File Content:
E John Mary Bill
E John Mary Pete
E John Mary Fred
E John Jean Rebecca
E Rebecca Bill Andrew E Pete Carol Jim
W child John
X Bill sibling Pete
X Bill sibling Fred
X John unrelated Mary W ancestor Andrew
X Bill cousin Mary
Output:
W child John
Bill Fred Pete Rebecca
X Bill sibling Pete Yes
X Bill sibling Fred Yes
X John unrelated Mary Yes
W ancestor Andrew Bill
Jean
John
Mary Rebecca
X Bill cousin Mary No

效果

JAVA