Graph Six Degrees of Kevin Bacon

Ever heard of the game Six Degrees of Kevin Bacon? (Play the game online; it's fun and counts as serious academic work.) Your program will play the game, too: it will accept queries in the form of the names of two actors, and then it will output (1) the "costar distance" and (2) a shortest path to get from the first actor to the second.

Your program can run in two modes:

• Interactive. Run with command ./sixdegrees. Input is from stdin (typed on the command line by the user) and printed to stdout (printed to the terminal).
• File-based. Run with ./sixdegrees [inputfile]. Input is accepted from the given input file, and output is printed to stdout.

The starter code includes ADTs for several auxiliary data structures: Queue, Stack, and Linked List.

Graph Class

The Six Degrees program relies on an undirected, unweighted graph whose vertices are Actor objects and edges are strings. Every actor from the input file actors.txt becomes a vertex of the graph. If two actors have appeared in a movie together, they are connected by an edge whose value is the name of the movie.

A snapshot of the undirected, unweighted graph that connects actors and movies. see image.

There is an edge between two actors if they've been in a movie together. If the actors have appeared in multiple movies together, only one edge exists, and it doesnt matter which movie is represented on the edge.

Make all adjustments you need to the existing starter code for this to work with our setup.

You'll also need to write the following Graph functions:

• Copy constructor
• Assignment operator
• Destructor
• A function called something like get_edge that returns the string associated with a given edge (in lab 6, we had a get_weight function which returned an int, but that doesn't make as much sense for these edges).

And modify the Graph function report_path.

• This function currently prints each vertex along a path from source to destination, but now we want it to print the edges along the way as well as the vertices.
• This function should first print the "costar distance", the number of edges on the path from source to destination.
• The print format should be: [Vertex] was in [Edge] with [Vertex]
  • For example: Jeff Bridges was in The Big Lebowski with John Goodman

You can add or modify any other functions or attributes to the Graph class that you need. Any functions that do not modify attributes of the class should be const.

Actor

You'll also write a simple Actor class. It has two attributes:

• Name of the actor, a string.
• Movies the actor has been in, a Linked List of strings.

Write the following member functions for the Actor class:

• Constructor (default and/or parameterized; whatever you need for the rest of your solution).
• A function to take in the name of a movie and insert it into the Actor's movies list.
• A function to determine if the actor was in a given movie. This function takes in the name of a movie and returns true if the Actor was in that movie, false otherwise.
• string connect(Actor) takes in an Actor as a parameter. It returns the name of a movie in which the Actor object and Actor argument have appeared. If the Actors have no movies in common, returns an empty string.
  • For example, say I have two actor objects, Swayze and Reeves. I can call Swayze.connect(Reeves), and the function should return "Point Break".

Overload the following operators:

• == Returns true if two actors' names are identical, false otherwise.
• != Returns true if two actors' names are not identical, false otherwise.
• << Prints the name of the actor.

You can add any other functions or attributes to the Actor class that you need. Any functions that do not modify attributes of the class should be const. If your Actor class uses dynamic memory allocation, then also include a copy constructor, assignment operator, and destructor.

SixDegrees Class

This class is responsible for the Graph itself, and for interacting with the user. It should have a Graph of Actor objects as its only attribute.

The Graph's default constructor doesnt do much, so youll need to have the SixDegrees class call the initialize_graph() function before it begins populating vertices and edges.

You'll need to write the following functions:

• A function to populate the graph from the input file actors.txt. The format of this file is explained below.
  • An edge exists between two actors if they appeared in a movie together.
  • Only one edge (one movie) exists between two actors.
  • The name of the input file actors.txt should be hard-coded, it will not be provided on the command line.
• void run(istream &in, ostream &out). This function is called from the driver. It should continually prompt for the names of two actors, separated by a newline. It should call the BFS function, described below. The input comes from the istream indicated by in, and the output is printed to the ostream indicated by out.
  • If either actor is not found in the graph, print "Sorry, [actor name] is not in the list"
  • Case matters. If the user queries "uma thurman", she would not be found because the file contains Uma Thurman.
• void BFS(Actor a, Actor B, ostream &out). Uses Breadth-First Search to find and print a path from a to b. You should print the "costar distance" -- the number of edges joining the two actors and the edges/vertices along the path. See Breadth-First Search Attachment
  • BFS finds a shortest path in an unweighted graph. For example, if I enter "Minnie Driver" and Matt Damon you should find a costar distance of 1 because they were in Good Will Hunting Together. You should NOT report a longer distance of 7 or 8 or 9 because you can get from Minnie Driver to John Cusack to Samuel L. Jackson to...
  • There could be multiple shortest paths, depending on how you read in from the actors.txt file. For example, Stanley Tucci and Meryl Streep were in two movies together. A valid one-edge path could be "Julie & Julia" or The Devil Wears Prada -- either path is fine.
  • If no path is found, print: "[a] to [b]: No connection"

Input Files

The input file actors.txt has the following format:

Actor name
Movie
Movie
Movie
*
Actor name
Movie
Movie
*

You do not know in advance how many movies a given actor has appeared in. Instead, use the delimiter '*' to distinguish between one actor and the next. Youll want to use getline for reading from this file, because actors and movies have varying-length names.

If the user runs in interactive mode, i.e., they provide no command-line arguments other than the name of the executable, then the names of two actors to look for comes via stdin:

Enter two actor names separated by a new line.
Press ctrl-D to quit
John Goodman
Meryl Streep
John Goodman and Meryl Streep have a costar distance of 4
John Goodman was in The Big Lebowski with Sam Elliott
Sam Elliott was in Ghost Rider with Wes Bentley
Wes Bentley was in The Hunger Games with Stanley Tucci
Stanley Tucci was in Julie & Julia with Meryl Streep

If the user provides one command-line argument in addition to the name of the executable, then that is an input file of queries. Your program should still print its results to standard out. We've provided one such file, test_input.txt. It contains several pairs of actors, which are consumed by the run function in SixDegrees.cpp.

When you run your program against this input file, you can redirect the output from standard out to your own output file, like this:

./sixdegrees test_input.txt > myoutput.txt

The output file here might match our expected_output.txt file that was included in the starter code. But remember -- that file is only one possible output sequence. It's most important that the "costar distances" in your output and our output are the same. If the actual sequence of movies varies, thats totally OK as long as its valid.

Modifying the Driver (Command Line Arguments Attachment)

We've provided a simple driver that creates an instance of the SixDegrees class and calls its run function with cin and cout as arguments. For this assignment, well ask you to modify the provided driver to accept 0 or 1 command line arguments in addition to the name of the executable.

• If 0 command line arguments are provided, we read from cin and write to cout.
• If 1 command line argument is provided, it is the name of a file to read input from. Call run with an ifstream that reads from that file (doing the usual error checks), and write to cout.

Writing (and Providing) Unit Tests

As part of your grade for this assignment, you'll write and submit unit tests for the Graph class. Since the Graph data structure is templated, you can test your Graph with ints, chars, Actors, or strings.

The most challenging functions, and thus the most important to test, are (1) populating the graph from the input file, and (2) Breadth-First Search. You should test both of these with really, really small input files before you use actors.txt.

Write your own testing main called test-graph.cpp that tests each function and writes reasonable output about success or failure of tests to standard out. Look at the linked handout on testing for inspiration! As an example, consider the bfs function. To make sure this function works, you'll want to test its behavior if:

• The items you're searching for are in the graph
• The items you're searching for are not in the graph
• There is no valid path from start to end
• There is only one valid path from start to end
• There are multiple valid paths from start to end -- do you find the shortest one?

Make sure to think carefully about the expected behavior for each test case!

Another important function to test is the copy constructor (and assignment operator). It should work on an empty Graph, a Graph with some vertices, a Graph with a lot of edges, etc.

Your Makefile should be set up so that make graphtest compiles your Graph with your Graph tests to produce an executable called graphtest.

README

• Give an overview of the classes/modules you use and how they interact.
• Describe the ADTs you used in your program, as well as any key algorithms (in particular, we're looking for an understanding of the graph data structure, and a high-level explanation of BFS)
• What did you find challenging in this assignment? Which parts of your work are you most proud of, and which would you improve if you had more time?
• Did you complete all parts of the assignment successfully? If not, please indicate which parts may be incomplete, and explain how you would solve them. Are you aware of any edge cases that your program does not handle?
• Describe how you tested your code. Refer to any relevant test code.