Assignment #3: Kevin Bacon Game

For a description of the Kevin Bacon game, follow this occasionally unreliable link or look at Exercise 14.23 in the text. Try the game a few times and see if you can find someone with a Bacon Number higher than 3. In this assignment, you will find all persons with a Bacon Number of 7 or higher. You will use the same data files as in Assignment #2. However, I do not want you to spend as much time reading these files as you did before so there will be an additional step. Also, you will need to write a recursive method at the end.

Strategy

This is basically a shortest path problem. After that is done, find the large Bacon numbers by scanning the bacon numbers and print out the high-numbered actors and their chains. To print out a high-numbered actor, you should use recursion. Specifically, if some actor x has a Bacon number of b, then you know that they must have been in a movie with someone, call them actor y with a Bacon number of b-1. To print out x's chain, you would print out y's chain (recursively) and then the movie that x and y had in common.

Extra I/O Step

As you debug your program, and it doesn’t work, you will find it very annoying to repeatedly spend significant time to read the data. So what you will do is after the data has been read once, and stored in your Database object (as mostly a few HashMaps), you will use serialization to dump the entire state of the Database object to disk. Note that the state of an object includes the object's instance data. It does not include static data, or local method data. If there is instance data that you do not want dumped, you should mark the instance field as transient. When you run the program a second time, you check to see if there is a dump of the database, and if so, you simply read it back in (otherwise, you go back to reading as in Assignment #2).

To use serialization, which is part of all current Java implementations, you will need to explicitly state that the objects that you are writing are Serializable. In the case of this assignment you will need to say:

class Database implements Serializable

{

   …

    private static final class Actor implements Serializable

    {

      …

    }

}

 

Serializable is an interface in package java.io, but it has no methods. It used to signal that serialization is allowed for objects of type Database and Actor. If you have a reference to a Database object, db, then you can dump the entire db object to a file name "db.ser" using code that mimics:

 

    ObjectOutputStream oo = new ObjectOutputStream( new BufferedOutputStream( new FileOutputStream( “db.ser” ) ) );

    oo.writeObject( db );

    oo.close();

 

In this code, ObjectOutputStream is also in package java.io, and I have made little attempt to show correct error handling, or use of finally blocks. The call to close is crucial.

 

This dump will take some time (but is only done once), and it will also require that you bump the VM up to 240 Mbytes, which will be tight on some systems. The result will be an output file that is about 48 to 55.5 Meg, depending on how you did things. Your AUL quotas have been increased to 75 Meg to allow this.

 

Later on, if you invoke your program a second time, you can read everything back, with code that mimics:

 

    ObjectInputStream ii = new ObjectInputStream( new BufferedInputStream( new FileInputStream( “db.ser” ) ) );

    db = (Database) ii.readObject( );

    ii.close();

 

This will run in only 160Mbytes, and should be faster than reading was before (how much faster depends on the CPU). You will need to deal with exceptions, and I would recommend that if an IOException occurs, you handle the error by reading the two files as in the last assignment. You will also have to catch ClassNotFoundException.

 

If you make a change that involves the adding or removing of members, or the changing of their modifiers (public, static, etc.) in between writing out the serialized data and reading it back in, you will get an exception when you try the read. Although there are ways of handling it, you should simply just let your code reload the database the old way and dump out a new version. You will not have this problem when you simply change the implementation of a method, or add local method variables.

What To Submit                                       

Submit complete source code and the actors/actresses with Bacon Numbers of 7 or higher. Include the complete paths for each of the actors/actresses (with shared movie titles). Also indicate how long your algorithm takes in the AUL. This means how long it takes to load, using the normal method, how long it takes to load from the serialized files, and also how long it takes to run the shortest path computation (not including the output of the answer). Also, insert code that tells me how large the VM is. The magic incantation can be seen by looking in StringMemoryDemo.java. Don't forget to write in the processor speed of the AUL computer you are using. If it's somewhat fast, or provably space-efficient, you can get extra credit. You cannot receive credit for a working program if your program fails to produce a large set of actors and actresses with Bacon Numbers of 7 or higher. Note: the data you will work on and the data the Oracle uses (and the IMDB data) are all slightly out of sync. So you might not be able to exactly reproduce the results, although I was able to when I ran my program on February 7, using the Jan 9 files. Finally, I am banning the use of Swing until further notice.

Notes About Assignment #2

If you did not get Assignment #2 to work, you will need to fix that first in order to begin this assignment. Also, in Assignment #2, the slow option was intern, so if you used it, you need to rewrite your code to use a third map.

Due Date

This program is due on Thursday, February 21.