CS35 Lab11: Oracle of Bacon

Due by 11:59pm, Wednesday, 28 April 2011

A skeleton version of the programs will appear in your cs35/lab/11 directory when you run update35. The program handin35 will only submit files in this directory.

You are encouraged to work with a partner on this lab.

Expand your previous lab to find paths between two actors/actresses.

The Oracle of Bacon searches a movie database to link Kevin Bacon to other actors by a path of movies and co-stars that appeared in those movies. For example, if you wanted to link Kurt Russell with Kevin Bacon, the Oracle might report:

Kurt Russell was in Mean Season, The (1985) with Andy Garcia
Andy Garcia was in Air I Breathe, The (2007) with Kevin Bacon

Kurt Russell has a Kevin Bacon number of 2
This linking concept can be extended to any two actors. For example, if you wanted to link Reese Witherspoon with John Wayne, the Oracle might report:
Reese Witherspoon was in Rendition (2007) with Alan Arkin
Alan Arkin was in America at the Movies (1976) with John Wayne

Reese Witherspoon has a John Wayne number of 2

To implement the search for links between actors in the movie database you will use a number of the data structures and techniques that we've explored throughout this course, including lists, queues, dictionaries, and breadth-first search.


Your program should provide an interactive menu that allows the user to request the following information from the database:

  1. Given an actor's name, report all the movies that he or she appeared in.
  2. Given a movie title and year, report all the actors that appeared in the movie.
  3. Given two actor's names, report the shortest chain that links them. If no chain exists, then inform the user.
  4. Compute the average linkability of an Actor/Actress. This is done by accumulating the shortest distance from each Actor/Actress to a given source and then dividing by the total number of people in the connected component.
  5. Free memory using delete and have appropriate destructors.

Your program should handle incorrect information gracefully such as when the actor name or movie title entered is not in the database.

Additionally, you should implement DFS in the Graph class, even though it is not needed to implement the Oracle of Bacon.

Data Files

The data for this lab can be found in the directory /usr/local/doc/. The complete set of data is over 100MB. A number of trimmed down versions of the data are available. I strongly urge you to initially test your program on the smaller versions before attempting the larger ones. At a minimum your program should be able to handle the two links version of the data.

Getting Started
Use your files form lab 11a as a starting point.
Optional feature

If you'd like an additional challenge, try this optional feature. For a given actor, report another actor whose path is finite and maximal. In other words, given Kevin Bacon as a query, who is the least linkable to Kevin Bacon and how long is his/her path? Note the solution may not be unique. You just have to report one candidate.

Once you are satisfied with your code, hand it in by typing handin35. This will copy the code from your cs35/lab/10 to my grading directory. You may run handin35 as many times as you like, and only the most recent submission will be recorded. If you worked with a partner, only one of you needs to handin the code.