The Oracle of Bacon Exercise

The Oracle of Bacon uses freely available database files from the Internet Movie Database's to handle 2 kinds of requests:

  1. Find the link from Actor A to Actor B.
  2. How good a "center" is a given actor?
  1. Why is there such a phenomenon surrounding Kevin Bacon? Would this kind of game work as well with other performers?
  2. Find someone who has a finite Bacon number that is ≥ 4. What characteristics would a person with a high Bacon number have?
  3. We would like to represent the connections between actors as a graph. Should the edges in an Oracle of Bacon graph have direction? Weight?
  4. The data linked below is taken from IMDB via the Sedgewick and Wayne book site, cleaned up slightly, and provided in the following format. Each line in the data file consists of a movie title, followed by a list of actors and actresses that appeared in that movie, delimited by /.

    FILE DESCRIPTION    MOVIES       ACTORS        EDGES    
    input8.txt movies released in 2006 8 15 27
    cast-06.txt movies released in 2006 8780 84236 103815
    cast-mpaa.txt movies rated by MPAA 21861 280624 627061
    cast-rated.txt popular movies 4527 122406 217603
    cast-all.txt over 250,000 movies 285462 933864 3317266
    Consider the file input8.txt: 

    Movie 0/Bacon, Kevin/A
Movie 1/A/B/C
Movie 2/D/E/A/B
Movie 3/E/F/G
Movie 4/F/G/H
Movie 5/H/I/J/K
Movie 6/J/L/M/N
Movie 7/A/B/C/D

    Three different versions of the graph constructed from this file are below.
    • Vertices: Actors or actresses
    • Edges: Two actors are adjacent if they appeared in the same movie
    Actor-Actor

    • Vertices: Movies
    • Edges: Two movies are adjacent if they share a cast member
    Movie-Movie Graph

    • Vertices: Actors, Actresses, and Movies
    • Edges: An Actor is connected to a Movie, if and only if he or she appeared in that movie
    Actor-Movie Graph

    Compare and contrast the three methods for structuring the information? Which graph will be have the most vertices or edges? Which one will be easiest to implement?
  5. Complete the createActorGraph, createActorMovieGraph, and createMovieGraph methods in the Bacon class to create the initialize myGraph (a Graph structure that will be used in traversal). You should use the already initialized myActors (maps from names to Actor) and myMovies (maps from movie name to Movie) objects. Time each one.
  6. Complete the traverse method in the Bacon class, so that it does a breadth-first traversal of the graphs and properly sets the distance and predecessor values of each vertex.
  7. Extra credit: complete the degreeCentrality, closenessCentrality, and betweennessCentrality methods in the Graph class. What is the big-Oh of each, in terms of V, the number of vertices, and E, the number of edges.