6 3/10: Party invitations
Representing social networks
We’d like to experiment with a very simple social network: we have a group of people, whom we will assume all have distinct names, and each of whom has a list of friends. (You can reuse either the ConsLists or QuickLists from the last assignment, if you wish.)
Exercise 1. Design classes to represent the above information.
Before we can design any methods to analyze the social network, we need examples of data. Here are some examples to get started:
Ann is friends with Bob and Cole.
Bob is friends with Ann, Ed, and Hank.
Cole is friends with Dan.
Dan is friends with Cole.
Ed is friends with Fay.
Fay is friends with Ed and Gabi.
Gabi is friends with Ed and Fay.
Hank is friends with no one.
Jan is friends with Kim and Len.
Kim is friends with Jan and Len.
Len is friends with Jan and Kim.
Exercise 2. Draw a diagram of this social network.
Exercise 3. Define an ExampleFriends class, and try to define examples to represent these people. What goes wrong?
Exercise 4. Design the method addBuddy on class Person that modifies the person’s friend list by adding the given person to that friend list. Be careful to avoid duplicates!
This method should have the following purpose/effect statement and header:
// EFFECT: Changes this Person's friend list to
// include the given person
void addBuddy(Person buddy) { ... }
Add any additional helper methods you may need to make sure you can represent the friend network given above.
Who’s friends with whom?
Suppose someone is having an open-house party: all friends are welcome, and
friends-of-friends, and so on —
Exercise 5. Does this Person have another Person as a direct friend?
// Returns true if this Person has that Person as a direct friend
boolean hasDirectFriend(Person that) { ... }
Exercise 6. How many direct friends do two Persons have in common?
// Returns the number of people that are direct friends
// of both this and that
int countCommonFriends(Person that) { ... }
Exercise 7. Will the given Person be invited to a party hosted by this Person?
// Returns true if that Person is a distant buddy of this one
boolean hasDistantBuddy(Person that) { ... }
Exercise 8. How many people will come to a party?
// Returns the number of people who will come to this Person's party
int partyCount() { ... }
Clique it or ticket A clique of size N in a social network is a group of N people, all of whom are friends with everyone else in the group.
Exercise 9. Design a method in the Examples class that computes whether a given list of people forms a clique. Define whatever helper methods you might need. Find a clique of size 3 in the example graph.