CSCI 151 - Lab 10 - Spring 2008 Center of the Hollywood Universe

11:59.59pm, Sunday, May 4

You may work with one partner on this assignment.

Introduction

In class, we have been discussing how Graph structures might can be used to represent relationships between groups of objects. For this assignment, you will be writing a program that allows you to play the "Kevin Bacon Game". A person's "Bacon Number" is computed based on the number of movies of separation between that person and the actor Kevin Bacon. For example, if you are Kevin Bacon, then your Bacon Number is 0. If you were in a movie with Kevin Bacon, your number would be 1. If you weren't in a movie with Kevin Bacon, but were in a movie with someone who was, your Bacon Number would be 2. In short, your Bacon Number is one greater than the smallest Bacon Number of any of your co-stars.

Note that this is a take off of Erdos numbers (mine's 3), and the two can be combined to form the more elusive Erdos-Bacon number.

For fun and some additional background, you can try out the Oracle of Bacon at the University of Virginia.

Program Details

You will be writing a class called BaconNumber that will read a data file and allow you to interactively query the system for the Bacon Number and path for any actor in the database. The program should require a single argument which is the filename containing the information on people and the roles they played in a movie. On optional second argument can be used to specify the initial center. After reading in the data, the program should then prompt the user for commands until an end-of-file (CTRL-D) is reached (hasNextLine() will return false).

Similar to what you did in past labs, if the filename argument begins with "http:" you should treat it as an URL and read the file from the network. This will enable you to play the game without having to download the entire file. To open a Scanner from an URL, you just need to do something similar to the following:

Scanner s = new Scanner(new URL("http://www.cs.oberlin.edu/").openStream());

Sample command line usage

% java -Xmx2g BaconNumber imdb.full.txt 
        
    # plays the game with the full data set centered at "Kevin Bacon"

% java -Xmx2g BaconNumber imdb.pre1950.txt "Bela Lugosi" 

    # plays the game with the center set to "Bela Lugosi"

% java -Xmx2g BaconNumber http://www.cs.oberlin.edu/~kuperman/csci151/labs/imdb.no-tv-v.txt 
        
    # plays the game with the no TV/V data set centered at "Kevin Bacon" 

File Format

The movie data file contains information on what movies a performer appears in. Every line contains information on one person appearing in one movie. The lines are formatted as follows:

    <performer name>|<movie title>

The vertical pipe character '|' can be used to determine where the name ends and the title begins. There will only be one '|' on a line and there are no empty names or titles. java.lang.String has a number of methods that can be used to divide up the line. (e.g., split("\\|"))

I have supplied several data files of varying sizes for you to work with.

• imdb.small.txt - a 1817 line file with just a handful of performers (161), fully connected
• imdb.top250.txt - a 13032 line file listing just the top 250 movies on IMDB. (Two disconnected groups for the movies Oldboy and Nosferatu Disconnected groups of foreign films.)
• imdb.pre1950.txt - a 911175 line file with movies made before 1950
• imdb.1950+.txt - a 3888287 line file with the movies made after 1950
• imdb.only-tv-v.txt - a 1209414 line file with only made for TV and direct to video movies
• imdb.no-tv-v.txt - a 3590048 line file without the made for TV and direct to video movies (best for the canonical Kevin Bacon game)
• imdb.full.txt - all 4799462 lines of IMDB for you to search through

Rather than cluttering up your account with these files, you can either use the links above for URLs. Also, once you have your lab folder created, you can run 151lab10setup from a lab machine and you'll get symbolic links to the files in the current directory.

Other than the small database, you'll almost certainly need to increase the amount of memory allowed via the -Xmx argument.

Commands to be supported

Your program should read in the specified file and in the default case, choose "Kevin Bacon" as the initial center. There are a number of commands you are to support in order query the database and change the center.

Additional commands

You may opt to include additional other commands for consideration towards extra credit. For any additional commands you implement, you should document them in the README file. Be sure to explain what it does and how someone could use it.

Here are some suggestions

1. table - print out a table of the counts of bacon numbers for the given center from 0 up to the longest
2. longest - print out one of the longest paths to the center
3. movies <name> - list all outbound edges from a given name
4. Saving and restoring state via a serializable object

Notes

The longest Bacon Number I found in the 'imdb.no-tv-v.txt' dataset for Kevin Bacon was 8 ("Jessica Drizd" and others). "Kevin Bacon" has a center value of ~2.937 while "Sean Connery" has ~2.803 indicating that he is a better center than Kevin Bacon. The Oracle of Bacon has a top 1000 list of centers which could be used to search for better values.

Programming Tips

As we have been discussing graphs, It should be no surprise that a good way to represent these acting relationships would be through a graph. There are a number of ways in which this can be done, however, if you want to maintain a simple graph you might want to have both movies and actors be vertices and the edges simply being relationships between them.

While an undirected graph could be used, the resulting path length will be double the Bacon Number. You would need to divide the path length by 2 or use weights of 0.5 for the edges. Another technique would be to create a directed graph and weight the paths from actors to movies as 0 and movies to actors as 1. Then, using Dijkstra's algorithm, you can find the shortest path where all actors and actresses that are listed for a movie can be consider equally.

Remember that it is best to build and test your program incrementally. Construct your Graph class and be sure to include test cases in the main method.

If you decide to either use or model part of your implementation off of what is in the book, be sure to give proper credit in the methods or comments at the start of the file.

What to Hand In

Use handin to submit the following files:

1. All .java files necessary for compiling your code
2. A README file with:
   1. Your name (and your partner's name if you had one)
   2. Any known problems or interesting design decisions that you made
   3. Anything implemented for extra credit

   4. If you adhered to the honor code in this assignment, add the following statement to your README file:

      I affirm that I have adhered to the Honor Code in this assignment.

If you work with a partner, just submit one solution per team.

Acknowledgments

Information courtesy of The Internet Movie Database (http://www.imdb.com/). Used with permission. The data should only be used for personal and non-commercial purposes.

Last Modified: May 02, 2008 - Benjamin A. Kuperman