Jason Kim
CSE 680
SU 06

Kevin Bacon Lab

Language: Java

Source Files:

BaconNumbers.java
Graph.java
BFS.java

Bytecode:

BaconNumbers.class (executable)
BFS.class (BFS$Queue.class, BFS$Queue$Node.class, BFS$ST.class)
Graph.class (Graph$Linklist.class, Graph$LinkList$Node.class, Graph$ST.class)


Compile:

javac BaconNumbers.class

Run:

java BaconNumbers filet.txt

When it is run, it will output my name and class, then build the graph and ask the user to wait, 
then it will ask for input form the user in the form of an actor with Last Name, First Name. (ie- Hanks, Tom)
Names are also Case Sensitive.

Inputting Hanks, Tom will give the output of 

Hanks, Tom
stars in / also stars
Apollo 13 (1995)
stars in / also stars
Bacon, Kevin
Hanks, Tom's Bacon Number is: 1
Go Again? 1 for yes, 0 for no

and prompt the user if they want to find another actor's bacon number.

Report:

The Implementation of this is done using Java with a BFS search on a Graph created using Java Hash Map Linked List 

The purpose of this was to learn more about graphing algorithms, specifical Breadth First Search.  The "Six Degrees of Kevin Bacon" is where you can 
connect any actor to Kevin Bacon in under 6 steps, by linking an actor to another actor by if they starred in the same movie.

So basically in Graph Theory, an Actor is a node, and the movie they starred in is an Edge that connects them to any other Actor that they might have starred in together with.

The example given to us from http://www.cs.virginia.edu/oracle/ tells us that the Breadth First Search Algorithm is used to find the shortest path of an Actor on a graph to the goal node Kevin Bacon.


The Program itself takes generally a short amount of time to run the small movies file, and around 30 seconds to do the large mpaa movie file.

The Running time for the BFS algorithm for a graph G = (V,E) is O(V + E)  (or for n verticies, and m edges, O(n+m) )

The steps are fairly simple, the Program reads data from the file and builds the graph using java's hashmap and a custom link list class.
then it runs the BFS on the graph with Kevin Bacon as the Goal, then the user can query any actor name to find it's bacon number.

Error List:

Blank fields and Garbage/False Values will give a Bacon number of 0, instead of "This is not an actor" or "Actor cannot be linked"

An actor with no connection to Kevin Bacon will still return a number of 0.