This lab has several important differences from the earlier labs:

1. It is due on a Monday night, not a Wednesday.
2. It is a multi-week lab that will require more effort than a typical single-week lab.
3. You may work with a partner on this lab. You and your partner should only submit one version of the assignment. (Be sure to put both your name and your partner's name on your lab work.)

The Oracle of Bacon searches a movie database to find a path between Kevin Bacon and other actors using a graph defined by the co-star relationship: two actors are connected by an edge if those two actors co-starred in a movie together. An actor's Bacon number is the length of the shortest path between that actor and Kevin Bacon. For example, the Oracle of Bacon might report that Kevin Bacon is connected to Kurt Russell with a length-2 path:

  Kurt Russell was in Mean Season, The (1985) with Andy Garcia
  Andy Garcia was in Air I Breathe, The (2007) with Kevin Bacon

  Kurt Russell has a Kevin Bacon number of 2

In this lab you will first implement several graph algorithms and then use the Graph and other data structures from this course to respond to queries about movies and actors.

As usual, you can get the initial files for this lab by running update35. The new files are listed here, and the files that you will need to edit are highlighted in red:

• graph.h: Defines a Graph class.
• graph.inl: Implements the Graph class.
• graph-algorithms.h: Defines functions for several graph algorithms.
• graph-algorithms.inl: Implements the graph algorithms.
• testGraph.cc: A program to test your implementation of the graph algorithms.
• oracle.cc: A program to respond to queries about movies and actors and actresses.

The remainder of this document describes your work to complete this lab.

You may work with a partner for this lab, but if you work with a partner you and your partner must work together using pair programming.

The basic idea of pair programming is simple: both you and your partner must always be present while working on the lab, with one of you typing and the other watching and helping. To pair program you and your partner must contribute equally, switching roles frequently so that you and your partner both implement similar fractions of the lab.

We will not accept "partner" work for which one partner was not present or did not make a substantial contribution; if you work with a partner, never code alone. Before starting to work with a partner, please ensure that you and your partner have compatible work schedules with adequate available time to meet and complete the lab.

You should start by reviewing our implementation of the Graph class. Our Graph uses an edge-list representation: for each vertex we store a list (an STL vector, actually) of the outgoing edges from that vertex. The edge-list data for all vertices is stored in a single HashTable, using vertices as the keys and their edge-lists as the values.

Please complete each function marked with a TODO comment in graph-algorithms.inl. You must test each function you implement using the testGraph program.

Your main work for this lab is to implement oracle.cc. This program should first read a movie database file, then provide an interactive menu that allows the user to request information from your movie database. Specifically, your program should support the following queries:

1. Given an actor's name, report all the movies he or she appeared in.
2. Given a movie title and year, report all the actors that appeared in that movie.
3. Given two actor's names, report the shortest path between them using the graph defined by the co-star relationship. If no path exists, report that fact to the user.
4. Given an actor's name, compute the average distance between that actor and every other actor in the given actor's connected component, using the graph defined by the co-star relationship.

Your program should allow the user to repeatedly select a menu option until they select a "Quit" option or type CTRL-D. When possible, you should gracefully handle incorrect input such as when the user enters an actor or movie name not in the database.

The data files for this lab are in the /usr/local/doc directory, accessible from the CS lab computers. Some of these files are moderately large. We strongly urge you to test your program using the smaller files, and only use the larger files when you are confident that your program works. The files are:

• Bacon0Links.txt: All records for only the movies that Kevin Bacon appeared in (68 records, 2.1KB)
• Bacon1Links.txt: All records for Kevin Bacon and his co-stars (38307 records, 1.3MB)
• BaconModernPopLinks.txt: All records for actors that have appeared in at least 10 movies since 1970 (995894 records, 36MB)
• Bacon2Links.txt: All records for Kevin Bacon, his co-stars, and his co-stars' co-stars (1693497 records, 62MB)
• BaconAllLinks.txt: All records except for TV show appearances or direct release to video (4074807 records, 145MB)

You might find the following hints more or less helpful:

• Reading large data files can be slow. Make sure you only read the data file once to build your data structures, and then pass pointers to your data structures if you need to use them in other functions.
• To compute the path between two vertices in the graph, you should use auxiliary data much like computing the maze path in Lab 05.
• An intuitive but bad way to compute the average distance between a vertex v and each other vertex in v's component is:

    totalDistance = 0.0
    numVertices = 0.0
    component = Use BFS to find all vertices in v's component
    For each vertex u in component:
        totalDistance += distance(v, u)
        numVertices += 1
    return totalDistance / numVertices
  

  This is needlessly inefficient because many computations of distance(v,u) might each search O(n) other vertices. (Given that, what is the total running time of this pseudocode?) Instead, you should directly compute the distance between v and each other vertex during a single breadth-first search of the graph.

Optionally, implement Djikstra's algorithm as a W getDistance(V src, V dest, Graph* g) function inside graph-algorithms.h and graph-algorithms.inl. To test your implementation, use a variant of the Bacon co-star graph where an edge weight is 2011-y with y being the most-recent year for a movie that two actors co-starred in together.

Once you are satisfied with your program, hand it in by typing handin35 at the unix prompt. You and your partner should handin just one copy of your lab.

You may run handin35 as many times as you like, and only the most recent submission will be recorded. This is useful if you realize after handing in some programs that you'd like to make a few more changes to them.