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.

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.

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.

You will use integers 0, 1,2,3,.., etc for labeling the vertices of the movie graph.

Do not add any code to the Graph class with regard to movie text file information.

graph.java

import java.util.*;

public class Graph

{

int numVertex;

int numEdge;

ArrayList> graph;

public Graph(){

numEdge=0;

graph = new ArrayList>();

// for (int i=0;i

//graph.add(new ArrayList());

}

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);

}

}

movies.txt

'Breaker' Morant (1980)/Brown, Bryan (I)/Henderson, Dick (II)/Gray, Ian (I)/Woodward, Edward/Thompson, Jack (I)/Procanin, Michael/Bernard, Hank/Nicholls, Jon/Knez, Bruno/Steele, Rob (I)/Lovett, Alan/Mullinar, Rod/Ball, Ray (I)/Rodger, Ron/Mann, Trevor (I)/Smith, Chris (I)/Cisse, Halifa/Cassell, Alan (I)/Osborn, Peter/Pfitzner, John/Waters, John (III)/Tingwell, Charles 'Bud'/Kiefel, Russell/Ball, Vincent (I)/Donovan, Terence (I)/Fitz-Gerald, Lewis/Currer, Norman/Meagher, Ray/Wilson, Frank (II)/Bell, Wayne (I)/Haywood, Chris (I)/Quin, Don/Peterson, Ron/Seidel, Nellie/West, Barbara/Reed, Maria/Horseman, Sylvia/Dick, Judy/Radford, Elspeth/Walton, Laurie (I)/Cornish, Bridget/Erskine, Ria

'burbs, The (1989)/Jayne, Billy/Howard, Rance/Ducommun, Rick/Drier, Moosie/Dern, Bruce/Kramer, Jeffrey (I)/Gordon, Gale/Theodore, Brother/Hays, Gary/Hahn, Archie/Gibson, Henry (I)/Olsen, Dana (I)/Ajaye, Franklyn/Katt, Nicky/Danziger, Cory/Hanks, Tom/Scott, Carey/Gains, Courtney/Feldman, Corey/Stevenson, Bill (I)/Picardo, Robert/Gage, Kevin/Miller, Dick (I)/Turner, Arnold F./Davis, Sonny Carl/Haase, Heather (I)/Katz, Phyllis/Benner, Brenda/Fisher, Carrie/Stewart, Lynne Marie/Darbo, Patrika/Vorgan, Gigi/Schaal, Wendy/Newman, Tracy (I)/French, Leigh

'Crocodile' Dundee II (1988)/Jbara, Gregory/Holt, Jim (I)/Soriero, Jim/Arvanites, Steven/Arriaga, Luis/Mercurio, Gus/Asai, Hisayo/Shams, Homay/Quinn, Colin/Folger, Mark/Rackman, Steve/Skilton, Gerry/Welsh, Kenneth/Saunders, Mark (I)/Krivak, Bryan/Dutton, Charles S./Cooper, Jim (I)/Ruiz, Anthony/Jerosa, Vincent/Batten, Tom (I)/Serbagi, Roger/Skinner, Doug/Maldonado, Edwin/Sandy, Bill/Hogan, Paul (I)/Dingo, Ernie/Cooper, Sam (I)/Root, Stephen (I)/Andrews, Jose/Guzmn, Luis (I)/Creighton, Rhett/Segura, Fernando/Meillon, John/Carrasco, Carlos/Spindell, Ahvi/Vasquez, Alberto (I)/Boutsikaris, Dennis/Alexander, Jace/Ramsey, John (I)/Fernndez, Juan (I)/Rios, Julio/Yasuda, Doug/Crivello, Anthony (I)/Ubarry, Hechter/Cerullo, Al/Yamamoto, Ronald/Wilson, Alec/Bobbit, Betty/Castle, Angela/Kozlowski, Linda/Cox, Hannah/Essman, Susie/Rogers, Maria Antoinette/Ali, Tatyana/Rockafellow, Stacey/Blinco, Maggie/Sokol, Marilyn/Lane, Rita/Crittenden, Dianne

*batteries not included (1987)/Aldredge, Tom/Boutsikaris, Dennis/Pankow, John/Dixon, MacIntyre/Vasquez, David (I)/Arceri, John/Hamer, Joe/Cronyn, Hume/DiSanti, John/Kurtz, Shelly (I)/McRae, Frank/LeGros, James/Raymond, Charles (II)/Greene, Michael (I)/Guzmn, Luis (I)/Imparato, Jon/Carmine, Michael (II)/Dear, H. Clay/Colon, Riki/Santana, Jos Angel/Renensland, Howard/Martinsen, Dick/Schwary, Ronald L./Schaal, Wendy/Belack, Doris/Hoffman, Jane (I)/Shoffner, Susan/Tandy, Jessica/Pea, Elizabeth/Grafe, Judy/Beardsley, Alice

...And Justice for All (1979)/Williams, Jonathan (XI)/Patterson, Kenneth (I)/Clute, Sidney/Dunbar, Julius/Arnold, Victor (II)/North, Alan/Blackmore, Stephen/Chianese, Dominic/Nelson, Craig T./Zwerling, Darrell/Siebert, Charles (I)/Saiontz, Donald/Duncan, Angus/Tambor, Jeffrey/Aquino, John (I)/Christian, Robert/Andes, Keith/Davy, Walter (II)/Strasberg, Lee/Sliwka, Frank/Bogazianos, Vasili/Forsythe, John (I)/Morton, Joe/Scott, Newton/Currier, Terrence/Hollander, Jack/Gorrin, Michael/Levene, Sam (I)/Hertzler, J.G./Bryggman, Larry/Haymer, Johnny/Beck, Vincent/Pistilli, Carl/Polk, Bill (I)/Hawkins, McLindsey/Warden, Jack/Symonds, Robert/Waites, Thomas G./Harris, Baxter/Pacino, Al/Quinn, Tom (II)/Sanders, Beverly/Schurr, Cathleen/Council, Allisha/Wooten, Terri/Sawyer, Connie (I)/Lahti, Christine/Fredricks, Rita/Forbes, Angelyn/Cartwright, Bonita/Kohler, Molly

10 (1979)/Alton, Walter George/Moore, Dudley/Jones, Sam J. (I)/Kassul, Art/Webber, Robert (I)/Rosenberg, Arthur/Colombatto, S. (I)/Hawker, John (I)/Sheehan, Doug/Calfa, Don/Linton, Jon/Tanney, Herb/Byrnes, Burke/Dennehy, Brian/Sullivan, Owen (I)/Goldman, Lorry/Showalter, Max/Champion, Michael/Hancock, John (I)/Lucking, William/Chappell, John (I)/Carr, Laurence/Anderson, Adam (I)/Daly, Rad/Noble, James (I)/Lpez, J. Vctor/Chase, Gregory/Farren, Vivian/Money, Constance/Serena (I)/Galardo, Yolanda/Ashland, Camila/Hanson, Marcy/Royale, Candida/Arnette, Jeanetta/Andrews, Julie (I)/Chess, Lisa/Rush, Deborah/DeCarlo, Kitty/Bowman, Gail/Aron, Adrian/Derek, Bo/Wallace, Dee (II)/Crosby, Denise/White, Debbie (I)/Alter, Julie/Haven, Annette/Kiser, Virginia/Ellis, Antonia (I)/Clark, Ellen/Gorman, Mari/Farrell, Lynn/Cassidy, Sheila/Le May, Dorothy/Zak, Sherri/Volz, Nedra

10 Things I Hate About You (1999)/Jackson, Greg (II)/Johnson, J.R./Dyer, Jesse/Mitchell, Daryl/Bennett, Tim (III)/Lacamara, Carlos/Hood, Brian/Houston, Tarance/Krumholtz, David/Kimbrough, Demegio/Therol, Aaron/Kountz, Daniel/Junger, Gil/Gordon-Levitt, Joseph/Leisure, David/Kennedy, Aidan/Muller, Travis/Mosley, Dennis/Riedmann, Eric (I)/Fraser, Cameron (I)/Maixner, Quinn/Karczag, Ari/Inglis, Joster/Brown, Nick (IV)/Laurance, Benjamin/Cease, Kyle/Keegan, Andrew/Eisenstein, Michael (II)/Thorpe, Joshua/Ledger, Heath/Mashburn, Brian/Miller, Larry (I)/Butler, Todd/Vukelic, Nick/Janney, Allison/Matthews, Amber/Powell, Monique/Hanley, Kay/Kajlich, Bianca/Evans, Alice (II)/Oleynik, Larisa/Union, Gabrielle/O'Neill, Bridget (III)/Mackay, Alisa/Gottlieb, Wendy/Taylor, Heather (I)/Quinn, Jelani/Stiles, Julia/Pratt, Susan May/Kenny, Laura