{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# [CptS 215 Introduction to Algorithmic Problem Solving](http://piazza.com/wsu/fall2017/cpts215/home)\n", "[Washington State University](https://wsu.edu)\n", "\n", "[Gina Sprint](http://eecs.wsu.edu/~gsprint/)\n", "## PA6 Graph Mining (100 pts)\n", "Due: \n", "\n", "### Learner Objectives\n", "At the conclusion of this programming assignment, participants should be able to:\n", "* Implement breadth first search for graphs\n", "* Visualize graph structures\n", "* Compute graph statistics\n", "\n", "### Prerequisites\n", "Before starting this programming assignment, participants should be able to:\n", "* Write object-oriented code in Python\n", "* Implement a graph ADT and common graph algorithms\n", "* Write Markdown and code cells in Jupyter Notebook\n", "* Create plots with `matplotlib`\n", "\n", "### Acknowledgments\n", "Content used in this assignment is based upon information in the following sources:\n", "* [Kevin Bacon number assignment from Dartmouth](http://www.cs.dartmouth.edu/~cbk/classes/10/14winter/hws.php?hw=PS-5)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Overview and Requirements\n", "For this programming assignment, we are going to tackle the important social network problem of finding an actor's [\"Bacon number\"](https://simple.wikipedia.org/wiki/Bacon_number): starting with an actor, see if they have been in a movie with someone who has been in a movie with someone who has been in a movie ... who has been in a movie with [Kevin Bacon](https://en.wikipedia.org/wiki/Kevin_Bacon). They're usually at most 6 steps away. \n", "\n", "There are plenty of other 6-degrees-of-separation phenomena in social networks. In a geekier version, the center of the universe is [Paul Erdos](https://en.wikipedia.org/wiki/Paul_Erd%C5%91s), a prolific author and coauthor, and people are characterized by their [Erdos numbers](https://en.wikipedia.org/wiki/Erd%C5%91s_number). The highest known finite Erdos number is 13. Remarkably, there are a number of people who have both small Erdos numbers and small Bacon numbers (number = steps away):\n", "* [Dan Kleitman](https://en.wikipedia.org/wiki/Daniel_Kleitman) has total Erdos-Bacon number of 3 (Erdos 1, Bacon 2), but the Bacon number is due to a role as an extra. \n", "* [Danica McKellar](https://en.wikipedia.org/wiki/Danica_McKellar) has an Erdos-Bacon number of 6, and is both a professional actress (The Wonder Years and West Wing) and wrote a published math paper as well as supplemental math texts designed for teenage girls (Math Doesn't Suck, Kiss My Math, and Hot X: Algebra Exposed).\n", "\n", "Note: for this assignment, code one Jupyter Notebook that tells the story of your data science endeavor. All auxiliary code (e.g. graph classes and functions) are to be in separate .py files and are imported into the notebook." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Program Details\n", "In this problem you will write a program to play the Kevin Bacon game. The vertices in this network graph are actors and the edge relationship is \"appeared together in a movie\". The goal is to find the shortest path between two actors. Traditionally the goal is to find the shortest path to Kevin Bacon. The following output from the sample solution shows how the game is played:\n", "\n", "```\n", "To quit the program, type return in answer to a question.\n", "Enter the name of an actor: Diane Keaton\n", "Diane Keaton's number is 2\n", "Diane Keaton appeared in Hanging Up (2000) with Meg Ryan\n", "Meg Ryan appeared in In the Cut (2003) with Kevin Bacon\n", "\n", "Enter the name of an actor: Buster Keaton\n", "Buster Keaton's number is 5\n", "Buster Keaton appeared in Limelight (1952) with Claire Bloom\n", "Claire Bloom appeared in Haunting, The (1963) with Julie Harris\n", "Julie Harris appeared in Requiem for a Heavyweight (1962) with Mickey Rooney\n", "Mickey Rooney appeared in Erik the Viking (1989) with Tim Robbins\n", "Tim Robbins appeared in Mystic River (2003) with Kevin Bacon\n", "\n", "Enter the name of an actor: \n", "```\n", "\n", "So based on the data set we supply for this problem, Diane Keaton's Bacon Number is two, and Buster Keaton's Bacon Number is five.\n", "\n", "#### Shortest Path Computation\n", "The easiest way to play the Kevin Bacon game is to do what is called breadth-first search (BFS) in the movie data graph. This builds a tree of shortest paths from every actor who can reach Kevin Bacon back to Kevin Bacon. Or more generally, given a root BFS builds a shortest-path tree from every vertex that can reach the root back to the root. It is a tree where every vertex points to its parent, and the parent is the next vertex in a shortest path to the root.\n", "\n", "Note: In class, we implemented a BFS to print out vertices in the graph. This BFS does not build a shortest-path tree. Later, we will implement Dijkstra's algorithm for a *weighted* graph. Dijkstra's algorithm does build a shortest-path tree. For this assignment, our graph structure is *unweighted*, so we can use either a BFS generated shortest-path tree or a modified version of Dijkstra's algorithm to generate the tree.\n", "\n", "To implement BFS we use a queue. We also need a graph, which is to be represented using your own implementation of a `Graph` class (see the lesson notes for how to do this). The result of our BFS is the shortest-path tree described above. \n", "\n", "The pseudocode describing BFS is:\n", "\n", "```\n", "insert root into an empty queue Q and into a new directed graph T\n", "\n", "until Q is empty\n", " dequeue Q to get next vertex V_des to process\n", " for each edge E that is incident to V_des in G\n", " let V_src be the other end of the edge\n", " if V_src is not in T\n", " add V_src to T and add an edge with the same label as E from V_src to V_des in T\n", " enqueue V_src in Q\n", "return T\n", "```\n", "\n", "When you are done, `T` holds a shortest-path or BFS tree. To find the Bacon number of an actor, look the actor up in `T`. If there is no vertex for that actor in `T`, then the actor is not connected to the root. If the actor is there, follow edges of `T` back to the root, printing movies (edge labels) and actors (vertices) along the way.\n", "\n", "\n", "#### Dataset\n", "Download [bacon.zip](https://github.com/srinibadri/cpts215/blob/fall2019/progassignments/files/bacon.zip) (thanks to Brad Miller at Luther College) and construct a graph from the datasets contained within the zip file. The three main files, actors.txt, movies.txt, and movie-actors.txt are large: 9,235 actors, 7,067 movies, and 21,370 movie-actor pairs, resulting in 32,337 edges. \n", "\n", "Note: while you are developing your program use smaller versions actorsTest.txt, moviesTest.txt, movie-actorsTest.txt, whose data represent the graph:\n", "\n", "```\n", "vertices:\n", " \"Kevin Bacon\", \"actor1\", \"actor2\", \"actor3\", \"actor4\", \"actor5\", \"actor6\"]\n", " \n", "edges:\n", " (\"Kevin Bacon\", \"actor1\", \"movie1\")\n", " (\"Kevin Bacon\", \"actor2\", \"movie1\")\n", " (\"actor1\", \"actor2\", \"movie1\") \n", " (\"actor1\", \"actor3\", \"movie2\") \n", " (\"actor3\", \"actor2\", \"movie3\") \n", " (\"actor3\", \"actor4\", \"movie4\")\n", " (\"actor5\", \"actor6\", \"movie5\")\n", "```\n", "\n", "The files are all formatted the same way. Each line has two quantities separated by a \"|\". In the actors file the quantities are actorID and actorName. In the movies file they are movieID and movieName. In the movies-actors file they are movieID and actorID, indicating that the actor associated with actorID appeared in the movie associated with movieID.\n", "\n", "Use the file contents to build a graph whose vertices are labeled with actor names (not IDs). Create an edge between two actors if they appeared in the same movie, and label that edge with the name of that movie. You should assume that no movie appears twice in the movies file and that no actor appears twice in the actors file. It is OK for there to be multiple edges between a pair of actors if they appeared together in multiple movies. You may find it useful to create maps (e.g. dictionaries) for mapping IDs to actor names and IDs to movie names. You can also use a map to figure out which actors appeared in each movie, and can use that information to add the appropriate edges to the graph. This may take a little thought, but try it by hand on the small data set given above.\n", "\n", "Note: When opening these files, you may need to specify the encoding so Python doesn't crash: `open(r\"actors.txt\", \"r\", encoding=\"latin-1\")`\n", "\n", "#### Bacon Game\n", "Implement the Bacon game. Perform BFS on the graph with \"Kevin Bacon\" as root and hold onto the BFS tree returned. Then ask for a series of actors. For each one, print out the path between that actor and the source, or say that none exists. This will require following a path from the chosen actor in the BFS tree back to the root (see above for an example of how this might be formatted). If the user gives a name that is not in the original graph (not the tree) say so and prompt again.\n", "\n", "Test your program on the movieTest.txt, actorTest.txt, and movie-actorTest.txt files. Make sure to demonstrate that your program works for boundary conditions. When you are sure that your program works on the test data, change it to use the movie.txt, actor.txt, and movie-actor.txt files. Demonstrate that your program works for these as well.\n", "\n", "#### Path Visualization\n", "Using a python library for visualization (such as `networkx`), visualize the path from the user-specified actor to Kevin Bacon. The vertices in the graph should be labeled with the actor's name and the edges should be labeled with the movie name. For example, a path from Owen Wilson to Kevin Bacon: \n", "\n", "\n", "\n", "#### Additional Functionality\n", "Compute *at least two* interesting statistics about this graph. Some possible examples: \n", "* Find an actor with the largest finite Bacon number for this data set. \n", "* Find the average Bacon number for those actors with finite Bacon numbers. \n", "* Find the destination actor that minimizes either longest path length or average path length from all other actors." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Bonus (5 pts)\n", "This movie data is a bit out of date now. Find a newer or more comprehensive dataset (perhaps by way of querying some web service). Or do a six-degree-of-separation game with a different social network." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Submitting Assignments\n", "1.\tUse the Blackboard tool https://learn.wsu.edu to submit your assignment. You will submit your code to the corresponding programming assignment under the \"Content\" tab. You must upload your solutions as `_pa6.zip` by the due date and time.\n", "2.\tYour .zip file should contain your .ipynb file, .py files (graph class code), and your .txt files used to test your program." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Grading Guidelines\n", "This assignment is worth 100 points + 5 points bonus. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria:\n", "* 5 pts for correctly reading in the data files\n", "* 5 pts for correctly cross-indexing IDs to names\n", "* 15 pts for correctly using your own `Graph` class and object to store the network\n", "* 10 pts for correctly looping over queue to visit nodes in BFS\n", "* 10 pts for correctly maintaining the shortest path tree in BFS\n", "* 10 pts for correct text-based path trace from actor back to Kevin Bacon\n", "* 15 pts for correctly visualizing the path trace from user-specified actor back to Kevin Bacon\n", "* 5 pts for implementing an interactive interface (read names, print results)\n", "* 10 pts for correctly computing at least two interesting statistics about the graph network\n", "* 5\tfor correctly handling boundary cases\n", "* 5 pts for class and function design\n", "* 5 pts for adherence to proper programming style and comments established for the class" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [Root]", "language": "python", "name": "Python [Root]" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.2" } }, "nbformat": 4, "nbformat_minor": 0 }