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 1 Friends Given a command line like friends Adalrada the program should print all of Adalrada s friends 2 Orphans This command which takes no arguments should list all the people with no parents 3 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 4 Descendants Print all of a person s descendents labeled as children grandchildren great grandchildren etc 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 printout of your source code with the grading sheet other side stapled to it CS212 Program 4 Grading Sheet Name 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 Friends command 10 2 Orphans 10 3 Bingo finds and prints the shortest path of relationships between two people or says that they are unrelated 10 4 Descendants command with labeled output children grandchildren etc If the graph has a cycle it should say so and abort 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