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?
The following questions are designed to lead you to building your own version of the Oracle.

Questions

  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?

    

    
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


    


    

    

  4.  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

    

    

    
 Who has the highest Bacon Degree in the file above?

    


    

Three different versions of the graph constructed from input8.txt 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

    

    

    

  5.  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?

    

  6.  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.

    

  7.  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.

    

  8.  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.

    

  9.  

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.

    

  10.  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.