"His sisters and his cousins, whom he reckons up by dozens, and his aunts!" H.M.S. Pinafore, Gilbert and Sullivan
First Due Date Section 2: Monday, April 27. Section 1: Tuesday, April 28.
For the first due date, you must submit the code for the relational database module (see below) electronically only. However, we recommend you finish this part even earlier than this first due date in order to more evenly distribute your workload.
Overall Due Date Section 2: Monday, May 4. Section 1: Tuesday, May 5.
Hardcopy submission, which must be identical to electronic submission, may only be handed in at class on the due date, or directly to your TA, or placed in the folder between 3:00pm and 5:00pm (only) on the due date. Please be careful not to let other people see your solution.
Reading: Chapters 9, 13, 14 and sections 12.2, 16.4, 16.5, 16.6, 17.2, 17.3. These are all parts of the book you have not read so far, except chapter 15 on reading and writing to files (technical details you may need to familiarize yourself with if and when you take the data structures course).
Your Mission: Create a program that processes data about family relationships in the following dialogue format. User input is typed after the ">", and the resulting computer output is shown.
> eric has parent andrew
> rachel has parent andrew
> lisa has child eric
> lisa has child rachel
> who has sibling eric
rachel has sibling eric
> who has child eric
andrew has child eric
lisa has child eric
> ira has child jay
> lisa has parent ira
> franma has child lisa
> jay has parent franma
> sam has parent jay
> isaac has parent jay
> frances has parent jay
> who has cousin rachel
sam has cousin rachel
isaac has cousin rachel
frances has cousin rachel
> who has descendant sam
jay has descendant sam
ira has descendant sam
franma has descendant sam
> family tree franma
franma
jay
sam
isaac
frances
lisa
eric
rachel
> andrew has spouse ene
> ene has child aili
> ene has child marika
> who has stepsibling marika
eric has stepsibling marika
rachel has stepsibling marika
> who has stepparent andrew
aili has stepparent andrew
marika has stepparent andrew
> how do you feel
i feel good
Primitive relationships
As input, the user can specify only the following basic, primitive
relationships between people: spouse, parent and child. All
relationships are gender-blind.
Deducing relationships In addition to these relationships, the computer also handles sibling, cousin, descendant, ascendant, stepsibling, stepchild and stepparent relationships. These relationships must be deduced automatically by the computer.
Spouse relationships are reflexive, so the computer automatically deduces, for example, that Andy is Ene's spouse, if told that Ene is Andy's spouse. Likewise, parent and child relationships are mutually inferred from one another. Furthermore, two people with the same pair of parents are siblings with one another. Given two people who are not siblings, if a parent of one is a spouse of a parent of the other, they are stepsiblings. A spouse of a parent that is not known to be a parent is a stepparent, and the stepchild relationship is similarly inferred. Note that spouse relationships have no effect on sibling relationships (i.e., your parents do not have to be married), but stepsibling relationships do depend on spouse relationships. Additionally, descendant, ascendant, and cousin (first cousins only) relationships are automatically inferred.
It is necessary to infer some of these relationships only on demand (e.g., only discover all the cousins if and when the user asks about cousins). However, other relationships can and must be deduced immediately.
Reasonable input. You can assume input to the system is reasonable, and therefore it is not necessary to check for illegal family situations. For example, no need to check for multiple spouses, more than two parents, or being one's own grandparent. Your system only needs to work for reasonable input.
User queries: The user can ask a who-question (see examples in dialogue above) regarding any of the 10 types of relationships.
User inputs. There are three types of user input:
Relational database module. To store all the people and their relationships you will create and use a general relational database (rdb) module. This module will have its own separate source code file (.c file), and will have an interface/header file (.h file).
A relational database maintains a set of entities (such as family members), and relationships between these entities (such as sibling, parent and spouse relationships). To implement this, you should store the entities in an array of structures. Each entity has a name (a string), and a set of relationships with other entities. There can be more than one entity related by each type of relationship. For example, an individual entity can have more than one cousin.
The following functions should be declared for this database. The prototypes and definitions here belong in the interface/header file:
struct entity_struct {
string name;
/* put other members here to handle relationships */
};
/* For the interface, "entity" is defined (as a pointer to an
* entity_structure). This way, the rdb module can be used in a way that is
* independent of how entities are represented. */
typedef struct entity_struct *entity;
/* Find a named entity and return it, or return NULL if not found */
entity FindEntity(string name);
/* Return the name of an entity */
string EntityName(entity e);
/* Add an entity to the database */
entity CreatNewEntity(string name);
/* Assert that entities e1 and e2 are related according to relationship
number r */
void AddRelationship(entity e1, entity e2, int r);
/* Each relationship can have multiple entries. This function returns the
* nth entity that is related to e by way of relationship r. NULL is
* returned if there is no such entity. */
entity NthRelatedEntity(entity e, int r, int n);
Each relationship can have multiple entries. For example, a person can have more than one sibling.
The relational database is a general concept and should be programmed as such. In principle, it can be used for many things besides family relationships. For example, employee entities and relationships such as boss, secretary-for, or city entities and relationships between cities that are connected by a direct air flights. Therefore, the relational database module does not deduce any family relationships. Rather, it simply stores the relationships it is told. Your main program (which uses the relational database) will perform all inductions, and update the database accordingly.
For example, the relational database could be used as follows:
...
#include "rdb.h" /* Make sure to include the interface file */
...
/* This defines an integer constant for each family_relationship. Do not
* confuse family_relationship, which is now a special variable type (one of
* these 10 (integer) values only) with the more general concept of
* relationships implemented by the relational database. */
typedef enum {sibling, parent, child, spouse, cousin, ascendant,
descendant, stepsibling, stepparent, stepchild} family_relationship;
...
/* This main function uses the relational database to demonstrate how
it can be used, but your main function will look very different */
main() {
family_relationship r;
entity p1, p2, p3;
p1 = CreateNewEntity("eric");
p2 = CreateNewEntity("rachel");
r = sibling;
AddRelationship(p1, p2, r);
AddRelationship(p2, p1, r); /* (not automatically inferred by the rdb) */
p3 = NthRelatedEntity(p1, r, 0);
/* p3 should be the same as p2 */
}
The rdb module should be used in a way that is independent of how entities and relationships are implemented. For example, do not access the contents of a structure that is being pointed to by a variable of type entity (except within the rdb module). Rather, ask a function from the database module for the information you want. This is modular programming at its best. This way, if you ever wanted to change how the rdb is represented, you could do so without needing to change any programs that use it. Furthermore, a programmer could use this module without needing to know how it was written.
Several files Create a separate directory for this assignment. This directory will have the main source code (family.c) that makes use of the rdb, processes family relationships, infers new relationships, prints family trees, etc. It will also have the main and header file for the rdb source code, and the main and header file for the scanner source code files (from the piglatin example in our text book). And it will have a Makefile that is used to compile each of these files, and link them together to create the final executable. Copy all the files from ~es66/lib/programs/family/ to get started.
Family trees. Your function to print all the descendants of someone (i.e., a family tree) by following child relationships must be recursive. It should indent the output as shown in the above example. Note that there is no tree explicitly stored in the computer's memory other than that implicitly encoded by child relationships.
Scanning user input Instead of the ithword function you have used for two previous assignments, you will use the token scanner described in the text that is used to implement Pig Latin. See the scanner.h file mentioned above for a description on how to use it.
Testing your program: ~es66/lib/programs/family/testdata is example input to try your program on (to "pipe" it in, type "cat testdata | familyprogram"). Your program should produce output very very similar to that shown above. That is, it should give the same answers. Some differences are OK, such as listing siblings or cousins in different orders. You will also need to create your own data to completely test your program. Feel free to post your personal testdata (no code, though!) to the class newsgroup for others to try their program on. For grading, we will test your program on another set of data that you do not get to see before-hand!
Hint: To process a line of input that asserts a relationship (such as "eric has sibling rachel"), first use FindEntity to find each person. If someone is not found, use CreateEntity to add her or him to the rdb. Then use AddRelationship to add the asserted relationship. Finally, add other relationships that can be deduced at this time.
Extra Credit: Extra credit is available for added features or a graphical interface. Examples of added features could include additional inferences about relationships (e.g., secondcousin), or incorporating additional data about each family member, such as their age, birthdate, or favorite kind of cheese. A graphic interface could include drawing a family tree.