Temporal Bacon Number

This assignment is a more advanced version of Bacon Number

Goals

The Bacon Number of an actor is the number of step it takes to go from an actor to Kevin Bacon by only going from an actor to an other one that played together in a movie.

Computing the Bacon number of an actor boils down to computing BFS in an Actor-Movie graph. However, the Bacon number of an actor decreases as time passes, since more movies are made. The purpose of this assignment is to track the Bacon number of some actors over time.

We will also study the time it takes to answer the question when the graph gets bigger as more movies are made.

Tasks

  1. Get the Movie Actor data for year interval from wikidata using the Bridges API: DataSource.getWikidataActorMovie()

  2. Construct a graph where vertices are Movie and Actors, and there is an edge between a movie and an actor if the actor played in the movie.

  3. Compute the BFS distance from Kevin Bacon to the rest of the graph.

  4. Plot over time the Bacon Number of a few actors, for instance Idris Elba and Demi Moore.

  5. Measure the time each of the BFS calculation takes. Use LineChart to show the time it takes to compute the BFSs as a function of the time range, the number of vertices in the graph, and the number of edges in the graph. You can use LineChart to plot some data.

Variants

We used a graph where the vertices are Movies and Actors, but one could directly build a graph of actors with an edge between them if they played in the same Movie. Would that be faster? Implement the problem using a graph of Actors (not including Movies) and confirm (or infirm) your intuition.

Help

For C++

Bridges documentation

LineChart documentation

For Java

Bridges documentation

LineChart documentation

For Python

Bridges documentation

LineChart documentation