cs215 ยป

The main idea of this assignment was to create a graph that uses the obscurity scores of the movies to create a graph with edges between actors and then to modify Dijkstra's algorithm to run on the graph and minimize the obscurity score.

```
# First, I leave it up to you to take the given input data files and create
# the three data structures below below
# obscurity : a dictionary mapping a movie to its obscurity score
# G : a bipartite graph with actors in one group and movies in another
# an edge connects an actor with a movie if the actor appeared in the movie
# actors : a set containing all of the actors in G
# here is a version of make_link that updates the weight between
# two nodes only if its smaller then the existing weight
def make_link(G, n1, n2, weight):
if weight < G[n1][n2]:
G[n1][n2] = weight
G[n2][n1] = weight
def val(pair): return pair[0]
def id(pair): return pair[1]
def get_parent(pair): return pair[2]
# modified dijkstra to minimize
# the obsucurity instead of distance
import heapq
def dijkstra_min(G,v):
first_entry = [0, v, None]
heap = [first_entry]
obs_so_far = {v:first_entry}
final_obs = {}
while len(final_obs) < len(G):
# find the closest un-explored node
while True:
w = heapq.heappop(heap)
# grab the relevant parts of w
node = id(w)
obscurity = val(w)
parent = get_parent(w)
if node != 'REMOVED':
del obs_so_far[node]
break
# lock it down!
final_obs[node] = [obscurity, node, parent]
# look at its neighbors
for x in G[node]:
# but only those that haven't been locked down
if x not in final_obs:
# instead of adding obscurities, we set the new distance to the
# maximum obscurity seen so far
new_obscurity = max(obscurity, G[node][x])
new_entry = [new_obscurity, x, node]
if x not in obs_so_far:
# we haven't see this yet
# so add to the heap and the dictionary
obs_so_far[x] = new_entry
heapq.heappush(heap, new_entry)
elif new_obscurity < val(obs_so_far[x]):
# the new distance is less then the
# best known
# Instead of removing it from the heap
# which could be expensive, mark it
obs_so_far[x][1] = "REMOVED"
# and then add a new entry
# for this node
obs_so_far[x] = new_entry
heapq.heappush(heap, new_entry)
return final_obs
# returns the obscurity score of the
# least obscure score between two actors
def least_obscure(actor1, actor2):
all_obs = dijkstra_min(actorG, actor1)
return all_obs[actor2][0]
# this might be considered an abuse of defaultdict
#
# create a defaultdict, where the factory creates another
# defaultdict. The factor of this defaultdict creates entries
# with a MAX_WEIGHT value.
# This has the effect of giving every character to character mapping
# a default value of MAX_WEIGHT
from collections import defaultdict
MAX_WEIGHT = 1000
def new_entry():
return defaultdict(lambda:MAX_WEIGHT)
actorG = defaultdict(new_entry)
# create a graph with links between actors
# using the least obscure movie between the two of
# them as the weight between the two
done = set()
for actor1 in actors:
done.add(actor1)
for movie in G[actor1]:
obsc = obscurity[movie]
for actor2 in G[movie]:
if actor2 not in done:
make_link(actorG, actor1, actor2, obsc)
# And, finally, I leave it as an exercise for you to iterate through
# the actor pairs in the answer dictionary and then calculate the
# obscurity score of the path between the two actors
```