cs215 ยป

CS215 Unit 5 Solutions

# CS215 Unit 5 Solutions: Least Obscure Path

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
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: