Program 4: Dutch Bingo

CPSC 212: Data Structures and Algorithms
Program 4: Dutch Bingo
In this exercise you’ll write a C# program to read a list of people and relationships such as friend, parent,
or child and build a labeled graph to represent the information. Then the program should answer questions
about people such as “Who are Aachie’s descendants?,” “List Abeltje’s second-cousins-once-removed,”
or “Find a chain of relationships connecting Adalind and Adaluuidis” using a syntax described below.
The latter is called “Dutch Bingo.”
This assignment requires that the graph be directed (if Aachie is a parent of Aalberts, it doesn’t follow
that Aalberts is a parent of Aachie) and labeled (Aafke may be a friend of Aaltie but not a parent). Using a
nice graph library that supports labeled directed graphs would make the program easier, but I was unable
to find one, so I wrote a simple one. You will add capabilities for the program below.
I have provided starter code that reads a file of relationships and build a directed, labeled graph and
implements some basic commands such as printing the relationships a person participates in and printing
a representation of the whole graph. For simplicity it’s a console application. You should add support for
the following commands. Each is worth 10 points. The total possible score is 110, with 10 points of extra
credit available.
To build the starter project, start a new console project, remove the Program.cs file and add all the starter
.cs files with the Project -> Add existing file option.
1. Orphans. This command, which takes no arguments, should list all the people with no parents.
2. Siblings. Given a command line like “siblings Adalrada,” the program should print all of Adalrada’s
brothers and sisters.
3. Descendants. Print all of a person’s descendents, labeled as children, grandchildren, great
grandchildren, etc.
4. Bingo. The command “bingo Aaf Adalmut” should find a shortest chain of relationships between Aaf
and Adalmut. For example, it might report that
Aaf is a parent of Aardina
Aardina is a friend of Aagtje
Aagtje is a child of Adalmut
5. Cousins n k. This command should print all of a person’s nth-cousins k times removed where n and k
are nonnegative integers. For example, “cousins Adaja 1 0” would report first cousins, “cousins Abigail 2
1” would list second cousins once removed, and “cousins Aartje 0 1” would list nieces, nephews, uncles,
and aunts. (Cousin relationships are symmetric: if A is B’s zeroeth cousin once removed, then B is A’s as
well.) Note that if someone is a sibling, that person is not also a cousin, second cousin, etc.
Submit your zipped project directory through moodle. Also turn in a grading sheet.
CS212 Program 4 – Grading Sheet
Name:_________________________ Section ___ Date/time: _______ Is this program late? ______
Parts of the program I didn't get to work correctly:
Comments:
____________________[below the line for instructor use only]_______________________
Submit a program that compiles and runs (50%) ________
1. Orphans (10%) ________
2. Siblings command (10%) ________
3. Descendants command, with output labeled (child, grandchild, ________
great grandchild, etc.) (10%)
4. Bingo finds and prints the shortest path of relationships between two people—
or says that they are unrelated (10%) ________
5. Cousins n k. Relationships don’t apply if there is a closer relationship,
e.g. a sibling is not a cousin (10%) ________
Style and mechanics of submission (10%) ________
Total: ________