GOAL: Find the degree of separation between 2 celebrities in a given data base
SYNPOSIS: Individual Project | Spring 2018 | Java
KEY SKILLS: Graph construction & analysis | Parsing a text file | Command-line interface
PLAY ME!
GAME INSTRUCTIONS:
| Command |
Example |
Description |
| p {celebrity-name} |
p Anne Hathaway |
display degree of separation from inputted celebrity to center celeb (center is initially Kevin Bacon) |
| u {celebrity-name} |
u Emma (II) Watson |
change the center celeb |
| i |
i |
list those infinitely separated from the center celeb |
| d {low-num} {high-num} |
d 80 81 |
list everybody separated by 1 degree from from X celebs, where X is in-between low & high num |
| q |
q |
quit game |
Key Process:
- Parse text files to build 3 maps. (1) movie ID -> movie name (2) actor ID -> actor name (3) movie -> all actors. Include try catch statements for parsing.
- Use the maps to build a graph w/ actors as vertices and the set of shared movies as edges.
- Run a BFS on the graph, starting from the center-of-the-universe actor, to construct a tree of shortest paths. The center-of-the-universe actor is the root, every other non-infinitely separated actor is a node.
- Backtrace shortest-path tree until root, storing edge data as you proceed, to find the numerical separation and path of separation
- Graph analysis: use recursion to find the average distance from root to node in the tree, a representation of the average separation from the center-of-universe actor.
- Graph analysis: compare number of nodes in graph to shortest-path tree, a representation of connectivity of center-of-universe actor.
- Use Scanner to create a command-line-interface, adding aditional features. Create series of try-catch & if statements to catch invalid user inputs.