Assignment 6 Solution

New concepts tested by this program

Implement Graph Interface

Use Graph to maintain a network of Actors

Shortest Path Algorithm implementation




Social networks are everywhere! They connect people with other people. There is an internet meme called “The Six Degrees of Kevin Bacon”, which describes how movie actors are connected, directly or indirectly, with Kevin Bacon. Surprisingly, very short chains exist between any pair of actors, even obscure ones. For more information, see Six Degrees of Kevin Bacon and The Oracle of Kevin Bacon.

A Graph is a set of Vertices and a Set of Edges. You will creating an ActorGraph that will be implementing a Graph interface with a set of Vertices of Actors and a set of Edges that identify the connection between two actors with a movie name. The header for your ActorGraph will be as follows: public class ActorGraph implements Graph<Actor, MovieEdge.

Within the Graph interface is a method dijkstraShortestPath. You will be coding the Dijkstra’s Shortest Path algorithm. You will then be able to find the connections between two actors through the movies that they have acted in.

For example, to connect Robin Williams to Charles Chaplin we might find:

 Robin Williams via “Dead Poets Society” to Norman Lloyd

Norman Lloyd via “Limelight” to Charles Chaplin.

The ShortestPath algorithm typically uses a weighted graph which means that the edges have a weight, and this is used to determine the shortest path. For this implementation, each weight will be 1, so that the shortest path is based on the number of movies in the path.

Data Element – Actor (Vertices)

You will be creating a class Actor which will hold all the information for an actor and implements Comparable. For simplicity sake, we will store the name in a single String in the following format: Last name, First name, so they can be sorted easily by last name. For the JUnit test, you will need a constructor of the Actor class that takes in a string, which is the name of the actor in the format: Last name, First name. You will also need a getName method to return the name of the actor in the format: Last name, First name. Follow the Javadoc for Actor.

Data Element – MovieEdge (Edges)

You will be creating a class MovieEdge which will hold all the information for an edge and implements Comparable. It contains a source and a destination, both are Actor objects, a weight (use 1 for the movie shortest path), and a String which holds the movie name that these two actors are connected by. It must have methods of getSource() and getDestination() which return the Actor objects and getMovieName() which returns a String with the movie name for the JUnit Tests. Follow the Javadoc html for MovieEdge.





Data Structure – ActorGraph

You will be creating a class ActorGraph which implements GraphInterface. The header for this class will be: public class ActorGraph implements GraphInterface<Actor, MovieEdge. Implement the methods. This is an undirected graph, which mean that an edge from Actor1 to Actor2 also means there is an edge created from Actor2 to Actor1.

Data Manager - ActorGraphManager

Implement the ActorGraphManagerInterface that holds an object of the ActorGraph data structure and has methods for maintaining the data structure. The ActorGraphManager takes input from the GUI and provides output to the GUI through methods such as addActor and addMovie.

GUI Driver

Create a GUI driver that will allow the user to read from a file to add Actors and Movies, or add Actors and Movies by typing in names. It will then display the connections between Actors. Use a FileChooser to allow the user to select a file to read from.

Beginning screen. First read a file.

Delimiter of “;”



Add a movie by entering the movie name and the actors:









Find a connection between actors. Select two actors and the path is displayed in the text area.









Deliverables:

Java files - The src folder with your data structure, data elements, data manager and Junit Test (.java) files

Javadoc files - The doc folder with your javadoc for student generated files

UML Class Diagram (an image, not the proprietary format, must be a .jpg or .pdf)

 

Deliverable format: The above deliverables will be packaged as follows. Two compressed files in the following formats:

LastNameFirstName_AssignmentX_Complete.zip [a compressed file containing the following]

                        UML.jpg

                        doc [a directory] include the entire student-generated javadoc folder

                                    file1.html (example)

                                    file2.html (example)

                        src [a directory] contains your .java and Junit Test (.java) files

                                    File1.java (example)

                                    File2.java (example)

                                    File_Test.java (example)

LastNameFirstName_AssignmentX_Moss.zip (a compressed file containing only the following: contains your .java files – NO FOLDERS!!)

                        File1.java (example)

                        File2.java (example)





Program Grade Sheet

Assignment #6

CMSC204





Name ____________________________ Blackboard Date/Time: _______________



DOCUMENTATION (20 pts)
CheckList for Assignment 6 is included and completed 1 pt _____
Javadoc generated for all student created classes: 4 pts _____
JUnit Test Class 6 pts _____

Implement the STUDENT methods of DataManagerTest

Create a JUnit test for your FriendGraph - FriendGraphTest

UML Diagram 4 pts _____

Lessons Learned 5 pt _____

In 3+ paragraphs, highlight your lessons learned and learning experience from working on this project.

How did you do? What have you learned? What did you struggle with? How will you approach your

next project differently?




PROGRAMMING (80 pts)
Programming Style and internal class documentation (within source code) 6 pts _____

Class description using Javadoc

Author’s Name, Class, Class Time, @author

Methods commented using Javadoc, @param, @return

Accuracy

Public tests 10 pts _____

Your tests (student tests) 8 pts _____

Private tests 10 pts _____

Program Details

Actor 8 pts _____

holds the name (LastName, FirstName)
implements the standard methods - constructors, getters/setters, toString, equals, etc.
implements the Comparable interface



MovieEdge 8 pt _____

implements Comparable
stores references to both Actor objects, weight (1) and movie name
implements the standard methods - constructors, getters/setters, toString, equals, etc
ActorGraph 10 pt _____

implements GraphInterface
use an adjacent matrix or adjacency list to store graph
ActorGraphManager 10 pt _____

Implements ActorGraphManagerInterface
Contains an ActorGraph
GUI details 10 pt _____

Use FileChooser to select file
User can add a movie or/and an actor.
User can choose from list of available actors (alpha order, no duplicates)
Actor list is updated when adding an actor



Total 100 pts _____