Java. Program -must- have a run-time of one second or less.

The goal of this assignment is to take a file (movies.txt), and paired with the following code meant for representing, building, and querying an undirected graph, implement the following features into one piece of code:

//HELPER CODE BEGINS HERE:

import java.util.*; public class Graph { int numVertex; int numEdge; ArrayList> graph; public Graph(){ numEdge=0; graph = new ArrayList>(); // for (int i=0;i()); } public void addEdge (int i, int j) { // get the horizontal arraylist at location i // then add j to it // repeat for location j ArrayList temp1 = graph.get(i); temp1.add(j); ArrayList temp2 = graph.get(j); temp2.add(i); numEdge++; } public void addVertex(int i) { graph.add(i,new ArrayList()); numVertex++; } public boolean checkEdge(int i, int j) { // first get the horizontal arraylist at location i // check if the arraylist contains j return(graph.get(i).contains(j)); } public int degree (int i) { return (graph.get(i).size()); } public void createGraph() { addEdge(0,1); addEdge(1,2); addEdge(0,3); // for each edge in the file // get the i and j // and call addEdge (i,j); } }

//HELPER CODE ENDS HERE

//movies.txt can be found here:

https://github.com/taolin204/algorithm/blob/master/src/com/tsy/algorithm/chapter04/graph/data/movies.txt

//

1. The vertex set will consist of all people (names) who are featured in the movies (the cast ) and the names of the movies (with the year). The edges will go between the cast members and the movies in the sense that if a person (actor ) is featured in a movie then there is an edge between the two. Obviously therefore, there will not be any edge present between the actors OR between the movies.

2. Each line of the text file (saved in UTF8 format) is to be read as a String with nextLine() and then separated out using the split(/) method. The first one in the separated out array is always the movie name and the rest are all people names.

3. It is recommended that as you read the movies file into memory, you will generate for each line of the file, the vertices and the edges for that line right away. Basically, you will first call addVertex() before calling addEdge() between a pair of previously created vertices.

4. You will use integers 0, 1,2,3,.., etc for labeling the vertices of the movie graph. Now, you need a way to go between these integer labels and the actual movie descriptors. In other words, for every vertex j (integer) you should be able to determine if it corresponds to a movie or a actors name quickly and probably vice versa and then be able to produce the movie name or the actors name. Hash structures are good for this.

5. It is a good idea to find and use a mechanism (some data structure or attributes) to distinguish the two types of vertices in the graph, the movies vs the cast.

6. Do not add any code to the Graph class with regard to movie text file information. The Graph class is a general purpose utility that can used to build a graph for any type of appropriate data. This means that you will create separate Java class file(s) for doing this assignment.

7. Feel free to use as many data structures as needed (subject to your computers memory limits) to make the code time-efficient.

8. The first goal is to build the graph of movies and cast members featured in the movie. And in that process, build auxiliary data structures to answer questions efficiently.

9. You will then build code to answer the following questions (via suitable methods).

10. How many unique movies are there?

11. How many unique cast members are there? You can assume that two people with identical names are the same people which we will agree as a bit of oversimplification.

12. How many edges are there?

13. Given a cast member, print the list of movies in which the cast member is featured in.

14. Write a method public void coCast (int minMovies) that when provided with a threshold minimum number of movies, lists all pairs of cast members that are featured together in at least minMovies along with the titles of such movies. For instance, coCast(5) will produce a list of pairs of cast members which are featured together in at least 5 movies.

15. In particular, run the method for minMovies =13 and produce the listing. It should give you nine pairs of cast members. Your method should not take more than 2 to 3 minutes to run. You must meet the runtime performance.

16. Also find the pair of cast members who have featured in the most number of movies together. Yes, there is only one and produce the movie title along with the names of the two cast members. Of course, if you solved question 15 above, you got this one as well.

//Thank you for your time. Any response will be thumbed up immediately.