The phrase six degrees of separation refers to the idea that, on average, everyone is about six steps away from knowing anyone else on earth. That is, any two people can be immediate friends (i.e., level-1 friends), or friends of friends (i.e., level-2 friends), or so on all the way to friends of friends of friends of friends of friends of friends (i.e., level-6 friends). [As a special case, a person is considered to be a level-0 friend of himself/herself.] This idea was first proposed in a 1929 story by Frigyes Karinthy, and later popularized in a play and major motion picture.

For this assignment, you will write a program that is able to store friend relationships and search for connections between people. Your program should read the network of friends from a file in which each line lists a person's name followed by all of his/her friends. You may assume that names do not contain white space. For example, the following file would describe a collection of five friends. Ann has two friends: Bob and Dave; Bob has two friends: Ann and Carol; Carol has only one friend: Erin; Dave has two friends: Ann and Bob; and Erin has one friend: Carol.

Note that friendship is not necessarily bidirectional. In the above network, Bob lists Carol as his friend, but Carol does not list Bob.

Your class, named Friendship, should have the following constructor and methods, each worth 25% of the total grade. In addition, you will need to write a driver to test your methods, but the driver will not be graded. Instead, the instructor will insert his own driver to test your code. For that reason, you must implement the constructor and methods exactly as described below. Misnaming the class or a method will result in a penalty.

public Friendship(String filename)

The constructor should read the friend data from the file with the specified name. If the file is not found, then an error message should be displayed and the underlying data structure should be initialized appropriately. Note: Regardless of whether the file was found or not, subsequent calls to the other methods should not result in crashes.

public Set<String> getFriends(String person)

This method takes a person's name and returns a set of all of that person's (immediate, or level-1) friends. For example, given an object named f that contains the above friend data, the call f.getFriends("Dave") should return the set {"Ann", "Bob"}. Note: if the specified person does not have any friends, the method should return an empty set (not null).

public Set<String> getCircle(String person, int level)

This method takes a person's name and a level number, and returns his/her circle of friends for that level. Note that a level-N circle of friends for a given person is the set of all his/her friends from level-1 up through level-N. For example, the call f.getCircle("Dave", 1) should return the set {"Ann", "Bob"} (Dave's level-1 friends), while f.getCircle("Dave", 2) should return the set {"Ann", "Bob", "Carol"} (Dave's level-1 + level-2 friends). Note: a person should not appear in his/her own circle of friends.

public int getLevel(String person1, String person2)

This method takes the names of two people and returns the smallest level of friendship that connects person1 to person2. For example, the call f.getLevel("Dave", "Ann") should return 1 (since Ann is in Dave's level-1 circle of friends), while f.getLevel("Dave", "Erin") should return 3 (since Erin is in Dave's level-3 circle of friends). Note: if the specified people are not connected by friendship, the method should return -1.