Recitation 9: Working with Cyclic Data🔗

Circularly Referential Data🔗

In this lab, we’ll look at how circular data naturally appears in lists of friends, or ‘buddy lists.’ These buddy lists could be IM buddy lists, Twitter followers, or lists of friends on social networks. Intuitively, a buddy list is just a username and a list of other buddies. If two people are on each other’s buddy lists, we immediately get circularity.

Download the Buddies.zip file above. It contains the files:

• Person.java

• ILoBuddy.java

• MTLoBuddy.java

• ConsLoBuddy.java

• ExamplesBuddies.java

(NOTE: We’re using non-generic lists in the lab deliberately, so we can add whatever helper methods we need. Really, these lists are being used as part of a graph, and so they might deserve to have some special-purpose methods.)

Create a project Lab9-Buddies and import the five files listed above into the default package. Add the tester.jar library to the project as you have done before.

All errors should have disappeared and you should be able to run the project.

• Before we can design any methods for the lists of buddies, we need to be able to make examples of buddy lists.

  We would like to make examples of the following circle of buddies:

  Ann's buddies are Bob and Cole

  Bob's buddies are Ann and Ed and Hank

  Cole's buddy is Dan

  Dan's buddy is Cole

  Ed's buddy is Fay

  Fay's buddies are Ed and Gabi

  Gabi's buddies are Ed and Fay

  Hank does not have any buddies

  Jan's buddies are Kim and Len

  Kim's buddies are Jan and Len

  Len's buddies are Jan and Kim

  Trying to make such examples directly, via simple variable declarations like Person ann = ...; Person bob = ...; will not work, for the same reason we couldn’t directly create Books and Authors that referred to each other. Where does the data break down?

• Design the method addBuddy that modifies the person’s buddy list by adding the given person to one person’s buddy list.

  This method should be defined in the class Person and have the following purpose/effect statement and header:

  // EFFECT: // Change this person's buddy list so that it includes the given person void addBuddy(Person buddy){...}

  Add any additional methods you may need to make sure you can represent the circle of buddies given above.

If someone wants to invite a lot of friends to a party, he or she calls all people on his or her list of buddies, and asks them to invite their friends (buddies) as well, and ask their friends to invite any of their friends as well (and ask them to invite their friends in turn...), eventually inviting anyone that can be reached through this network of friends.

We call those on the person’s buddy list the direct buddies and the others that will also be invited to the party the indirect buddies. (Note: some people technically qualify as both direct and indirect buddies; find an example of such a pair in the examples above.) We call the set of direct and indirect buddies the extended buddies of a person.

Now we would like to ask some pretty common questions. For each question design the method that will find the answer. As always, follow the Design Recipe! The purpose/effect statements and the headers for the methods are already given:

• Does this person have another person as a direct friend?

  // returns true if this Person has that as a direct buddy boolean hasDirectBuddy(Person that)

• How many direct buddies do the two persons have in common?

  // returns the number of people that are direct buddies // of both this and that person int countCommonBuddies(Person that)

• Will the given person be invited to a party organized by someone?

  // will the given person be (directly or indirectly) invited to a party // organized by this person? boolean hasExtendedBuddy(Person that)

• How many people will be at the party if all those a person invites (directly or indirectly) show up?

  // returns the number of people who will show up at the party // given by this person int partyCount()

HINT: some of these methods will benefit greatly from designing a helper method first, that can be reused to help solve more than one of the questions above. You are encouraged to make a work-list for each problem, to figure out what the high-level steps are first, before diving into writing code without a plan.

Game of telephone🔗

Kids often played a game of telephone, where they sat in a circle and one person whispers a secret message to the next person, who whispers whatever they heard to the next person, and so on, until the last person in the circle announces whatever final message they received...which is often hilariously garbled from the original message.

Now that they’re older (and coincidentally all taking Fundies 2 together) they’ve decided to see how often they can “win” at the game, to see how likely they can convey a message without garbling. So:

• Each Person has a diction score, between 0 and 1, that represents how likely it is that a Person with perfect hearing will hear their whispered message correctly.

• Each Person has a hearing score, between 0 and 1, that represents how likely it is that they understand a Person with perfect diction.

The likelihood of person A being understood by person B is therefore the product of person A’s diction with person B’s hearing.

By the rules of the game, each Person will only ever whisper their message to their buddies. Your task is to compute the maximum likelihood that person X can convey a message correctly to person Y.

You do not need to compute the actual path the message needs to take (though that would be an interesting and not-too-difficult extension), you just need to compute the maximum likelihood that the message will be received correctly.

Discussion🔗

The party methods earlier, and the game of telephone problem above, form two common styles of problem encountered while processing cyclic graphs. The hint in the first problem suggests that there might be some common abstraction you might use to help solve those first tasks. The telephone problem has a similar feel. Brainstorm a little bit: if you had to compare the kinds of computation needed in these problems to a list-processing function, which would it be most like: map, foldr, foldl, filter...? Make some suggestions for what an appropriate abstraction might be for these graph-processing problems.