Java代写:CMSC132 Six Degrees of Kevin Bacon

Introduction

这次需要代写的Java编程作业,考察Graph的知识点,读文件构造Graph,然后按条件用BFS搜索,并最终输出结果。

Problem

In this project, you write a program that will help you play the “Six Degrees of Kevin Bacon” game. This game is played on a graph of movies and actors/actresses who starred in them. The Bacon Number is defined as follows: Kevin Bacon has a Bacon Number of 0; people who co-starred in a movie with Kevin Bacon have a Bacon Number of 1; people who co-starred in a movie with someone who has a Bacon Number of 1 in turn have a Bacon Number of 2; and so on. Given any actor/actress, the goal of the game is to establish their Bacon Number by a sequence of movies and co-stars. As shown in Figure 1, Bill Murray has a Kevin Bacon number of 1, because co-starred in “Wild Things”, while Cameron Diaz has a Kevin Bacon Number of 2, because she she co-starred with Bill Murray in “Charlie’s Angels”.
For example, using the “action” data set given below, we can show that “Al Pacino” has a Bacon Number
of 3 as follows:

Pacino, Al
   Heat (1995)
Rosales Jr., Thomas
   Lost World: Jurassic Park, The (1997)
Richards, Ariana
   Tremors (1990)
Bacon, Kevin

Kevin Bacon (0) starred in Tremors with Richards, Ariana (1) who starred in Lost World: Jurassic Park, The (1997) with Rosales Jr., Thomas (2) who starred in Heat (1995) with Pacino, Al (3). If we use the “all cast” data set given below, we can show that “Al Pacino” has a Bacon Number of 1 as follows:

Pacino, Al
   Boffo! Tinseltown's Bombs and Blockbusters (2006)
Bacon, Kevin

Kevin Bacon (0) starred in Boffo! Tinseltown’s Bombs and Blockbusters (2006) with Pacino, Al (1). Inter- estingly this works way in the past as well:

De Rosselli, Rex
   Lion's Claws, The (1918)
Brinley, Charles
   Adventure in Sahara (1938)
Lawrence, Marc (I)
   Big Easy, The (1987)
Goodman, John (I)
   Death Sentence (2007)
Bacon, Kevin

Turns out that Rex De Rosselli died in 1941 and yet he has a Bacon Number of just 4. Actually Rex really has a Bacon Number of 3 but we need to use a much bigger data set “cast.all.txt” to show this:

De Rosselli, Rex
   Dangerous Adventure, A (1922)
McCullough, Philo
   Chamber of Horrors (1966)
Danova, Cesare
   Animal House (1978)
Bacon, Kevin

We have included two data sets suitable for the program in the archive above (the data sets are courtesy of Robert Sedgewick):

action06.txt (4.4 MB, only action movies)
cast.all.txt (64 MB, all movies from the 2014 IMDB)

The format of these data sets is rather simple: Each line is a movie, and each movie consists of several fields separated by the “/“ character. The first field is the name of the movie itself, all the following fields are the names of actors and actresses starring in the movie. For example:

Heat (1995)/Daniels, Max/Perry, Manny/Marzan, Rick/Pacino, Al, ...
Heat After Dark (1996)/Kitami, Toshiyuki/Sugata,...
Heated Vengeance (1985)/Dye, Cameron/Walker, Robert (III), ...

Reading this data is not complicated, but we hand you the parsing code anyway so you can focus on the search algorithm instead.
In order to find the smallest Bacon Number for an actor we proceed as follows: First we identify the vertices for both Kevin Bacon and the actor in question (you already have that code). Then we start a breadth-first search at the vertex for Kevin Bacon; as we do this we keep track of the “previous vertex” that got us to the one we’re currently investigating. Once we find the vertex for the other actor, we are done: We just have to print out the path that got us here. This implementation of BFS is the only thing you have to write for this problem!
You will implement following functions in the given project:

1.Degree of separation from Kevin Bacon:
2.Degree of separation between any two actors/actresses:
3.Search actor/actress/movie:
4.List cast of a movie or movies of an actor/actress:
5.Exit
Select:

Here is what each menu item does:

  1. Finds the Kevin Bacon number of an actor/actress
  2. Find the shortest distance between any two actors/actresses.
  3. Actors with same name has a Roman number after their names. You can enter the name and search the exact name in the database. For example, Emma Watson’s name appeared as “Watson, Emma (II)” in the movie database.
  4. If input is a movies, it lists all the case. If the input is an actor/actress, it lists all the movies he/she
    starred in.
  5. terminate the program.

The “Graph” class, “Bag” class are fully implemented for you. The Graph class represents an undirected graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the graph, iterate over all of the vertices adjacent to a vertex. It also provides methods for returning the number of vertices V and the number of edges E. Parallel edges and self-loops are permitted. This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent to a given vertex, which takes time proportional to the number of such vertices.
You will have add the mapping relationships between vertex symbols (name of a movie, actor, acres) and vertex number in “SymbolGraph” class. For example: in Graph 2, vertex 0 and vertex 5 can represent movies and other vertices represent actors/actresses. You also have to implement to methods to find the shortest path between two given vertices. All edges have the weight of 1. Therefore, you can also use BFS to find the shortest distance between two vertices.
Before you are sure your program is running correctly, test your code with a smaller database base. Start with a file that only has 5-10 movies and actors/actresses. If you think your program is working, then try with “action06.txt”, (4.4 MB, only action movies). To try “cast.all.txt”, 64 MB, all movies from the 2014 IMDB, 300,000 movies, 900,000 actors/actresses, you have to allocate larger memory for your project. Google it for instructions to do that. If you run your program from coo and line you specify memory size in your command line. Following command allocate 2gb memory for JVM to run KevinBacon.

java -Xmx2g KevinBacom