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