Please implement in JAVA.

In The Small-World Phenomenon: An Algorithmic Perspective, Jon Kleinberg writes:

Long a matter of folklore, the small-world phenomenon -- the principle that we are all linked by short chains of acquaintances -- was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960's. This work was among the first to make the phenomenon quantitative, allowing people to speak of the six degrees of separation between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web.

In this assignment you will investigate the six degrees of Kevin Bacon. Check out the Wiki page on the six degrees of Kevin Bacon. And check out an online version of this game, The Oracle of Bacon.

Two actors or actresses are linked if they appeared in a movie together. The Kevin Bacon number of an actor is the shortest chain of links that leads to Kevin Bacon. For example, Robert De Niro has a Kevin Bacon number of 1 because he appeared in Sleepers with Kevin Bacon. Elvis Presley's number is 2: although Elvis did not appear in any movie with Kevin Bacon, he was in Change of Habit with Edward Asner, and Asner appeared in JFK with Kevin Bacon.

Your task is to read in a file containing a list of movies and the actors that appeared in them and compute the Kevin Bacon numbers for each actor. You will then read in a list of actors from standard input and print out a shortest chain of movies that leads each actor back to Kevin Bacon.

Input format. In addition to the massive list of movies and casts from the Internet Movie Database, included some smaller data files that include only a specific subset of movies, e.g., all movies released in 2006. 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 the character '/'. Here is an abbreviated example:

Picture Perfect (1997)/Aniston, Jennifer/Bacon, Kevin/Dukakis, Olympia/Mohr, Jay Planes, Trains & Automobiles (1987)/Bacon, Kevin/Candy, John/Martin, Steve/Robins, Laila Beach, The (2000)/DiCaprio, Leonardo/York, Daniel/Patarakijjanon, Patcharawan

Reading and representing the data: Your first task will be to read and load the data in memory into an appropriate data structure. Essentially, you'll need to store:

for each movie, all the actors in that movie

for each actor, all the movies the actor played in

Actor-movie relationships as a graph: We can think of the actor-movie relationship as forming a graph: the vertices in the graph are all actors and movies, and the edges are the relationships between them. That is, there is an edge between every movie and every actor who played in that movie.

Computing Kevin-Bacon numbers. More generally, computing Actor-A-numbers: Given two vertices in a graph, a path is a sequence of edges connecting them. There may be more than one path in a graph connecting two vertices. A shortest path is a path with minimum length among all paths between two vertices; here the length of a path is the number of edges on the path.

Let's phrase the KB problem in terms of paths in the graph: To find the Kevin-Bacon-number of an actor X, we need to find the shortest path connecting X to Kevin Bacon. Generally speaking, for an arbitrary actor A, we need to find the shortest path connecting X to A.

Your goal is to write a method that takes two actor names A and B, finds the A-number of B (that is, a shortest path from A to B) and displays nicely the movie-actor chain to A. Shortest paths are not necessarily unique; that is, there may be several paths of the same minimum length connecting A to X. In this case, we just want to compute one of them (does not matter which one).

It turns out that you can compute shortest paths in a graph using a strategy that you have seen while searching: breadth-first search (BFS). Start from the vertex representing the source (actor A); add all its neighbors to a queue. These are all the actors with an A-number of 1. Then add to the queue all neighbors of these neighbors, and so on. It is not hard to see (and we'll argue this in class) that using breadth-first search from A you find the shortest paths from A to all other vertices (that are connected to A).

Note that there is nothing special about Kevin Bacon, and that the same approach can be computed to compute shortest paths between any two actors in Holywood. It would be nice if you make your methods general enough, not customized for Kevin Bacon.

The sample files are at https://drive.google.com/open?id=0B7bGf7KYiOUheUE3SWJiOTVlZFk

cast.06.txt: movies released in 2006 [movies=8780, actors=84236] (note: 8779 distinct movies)

cast.00-06.txt: movies released 2000-06 [movies=52195, actors=348497]

cast.all.txt: movies [movies=285462, actors=933874]

cast.action.txt: action movies [movies=14938, actors=139861]

cast.rated.txt: popular movies [movies=4527, actors=122406]

Test8.txt: for testing only. [movies=8]

Submission: Submit a zip file containing the java file and a README with names of the team members, a verbal explanation of your data structure and the approach you took to solve the problem.

Use a command-line parameter to enter the name of the movie database file. You will also read in a list of actors from standard input, one per line. The first output is the Bacon Numbers Frequency Table.

Sample run:

$> java BaconNumbers cast-2000.txt

Bacon number Frequency ------------------------- 0 1 1 1494 2 127791 3 239671 4 36475 5 2965 6 275 7 39 8 47 9 99 10 15 11 2 infinity 9703

Enter the name of the actor: Dane, Cynthia Dane, Cynthia has a Bacon number of 3 Dane, Cynthia was in "Solstice (1994)" with Scott, Dennis Scott, Dennis was in "What About Bob? (1991)" with Murray, Bill Murray, Bill was in "Wild Things (1998)" with Bacon, Kevin