Need Help figuring out the shortest_path() method implementation. Returns the shortest list of (movie_id, person_id) pairs that connect the source to the target.

[ninijoe]

I want to figure out the implementation to the problem. I have some code written down but im not sure..Its supposed to figure out the shortest path that connects two actors together in a list of actors. It has a utility class that creates a node object and also node functions. It also has an example text file for which you can test the implementation of the idea. I am meant to only implement the shortest_path function.

#degrees.py `import csv import sys

from util import Node, StackFrontier, QueueFrontier

Maps names to a set of corresponding person_ids

names = {}

Maps person_ids to a dictionary of: name, birth, movies (a set of movie_ids)

people = {}

Maps movie_ids to a dictionary of: title, year, stars (a set of person_ids)

movies = {}

def load_data(directory): """ Load data from CSV files into memory. """

Load people

with open(f"{directory}/people.csv", encoding="utf-8") as f:
    reader = csv.DictReader(f)
    for row in reader:
        people[row["id"]] = {
            "name": row["name"],
            "birth": row["birth"],
            "movies": set()
        }
        if row["name"].lower() not in names:
            names[row["name"].lower()] = {row["id"]}
        else:
            names[row["name"].lower()].add(row["id"])

# Load movies
with open(f"{directory}/movies.csv", encoding="utf-8") as f:
    reader = csv.DictReader(f)
    for row in reader:
        movies[row["id"]] = {
            "title": row["title"],
            "year": row["year"],
            "stars": set()
        }

# Load stars
with open(f"{directory}/stars.csv", encoding="utf-8") as f:
    reader = csv.DictReader(f)
    for row in reader:
        try:
            people[row["person_id"]]["movies"].add(row["movie_id"])
            movies[row["movie_id"]]["stars"].add(row["person_id"])
        except KeyError:
            pass

def main(): if len(sys.argv) > 2: sys.exit("Usage: python degrees.py [directory]") directory = sys.argv[1] if len(sys.argv) == 2 else "large"

# Load data from files into memory
print("Loading data...")
load_data(directory)
print("Data loaded.")

source = person_id_for_name(input("Name: "))
if source is None:
    sys.exit("Person not found.")
target = person_id_for_name(input("Name: "))
if target is None:
    sys.exit("Person not found.")

path = shortest_path(source, target)

if path is None:
    print("Not connected.")
else:
    degrees = len(path)
    print(f"{degrees} degrees of separation.")
    path = [(None, source)] + path
    for i in range(degrees):
        person1 = people[path[i][1]]["name"]
        person2 = people[path[i + 1][1]]["name"]
        movie = movies[path[i + 1][0]]["title"]
        print(f"{i + 1}: {person1} and {person2} starred in {movie}")

def shortest_path(source, target): """ Returns the shortest list of (movie_id, person_id) pairs that connect the source to the target.

If no possible path, returns None.
"""
self.num_explored=0
source = Node(state=self.source, parent=None, action=None)
frontier = QueueFrontier()
frontier.add(source)

self.explored =()

while true:
    if frontier.isempty():
        raise Exception("none")

    node = frontier.remove()
        self.num_explored += 1

    if node.state == self.target
        movie_id = []
        person_id = []
            while node.parent is not None:
                movie_id.append(node.action)
                person_id.append(node.state)
                node = node.parent
            movie_id.reverse()
            person_id.reverse()
            self.solution = (movie_id, person_id)
            return

    self.explored.add(node.state)        

    for movie, person in self.neighbors_for_person(node.state):
        if not frontier.contains_state(state) and state not in self.explored:
            child = Node(state=state, parent=node, action=action)
            frontier.add(child)

     # TODO
        raise NotImplementedError

def person_id_for_name(name): """ Returns the IMDB id for a person's name, resolving ambiguities as needed. """ person_ids = list(names.get(name.lower(), set())) if len(person_ids) == 0: return None elif len(person_ids) > 1: print(f"Which '{name}'?") for person_id in person_ids: person = people[person_id] name = person["name"] birth = person["birth"] print(f"ID: {person_id}, Name: {name}, Birth: {birth}") try: person_id = input("Intended Person ID: ") if person_id in person_ids: return person_id except ValueError: pass return None else: return person_ids[0]

def neighbors_for_person(person_id): """ Returns (movie_id, person_id) pairs for people who starred with a given person. """ movie_ids = people[person_id]["movies"] neighbors = set() for movie_id in movie_ids: for person_id in movies[movie_id]["stars"]: neighbors.add((movie_id, person_id)) return neighbors

if name == "main": main() **#util.py** class Node(): def init(self, state, parent, action): self.state = state self.parent = parent self.action = action

class StackFrontier(): def init(self): self.frontier = []

def add(self, node):
    self.frontier.append(node)

def contains_state(self, state):
    return any(node.state == state for node in self.frontier)

def empty(self):
    return len(self.frontier) == 0

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[-1]
        self.frontier = self.frontier[:-1]
        return node

class QueueFrontier(StackFrontier):

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[0]
        self.frontier = self.frontier[1:]
        return node

`

#stars.csv person_id,movie_id 102,104257 102,112384 129,104257 129,95953 144,93779 158,109830 158,112384 1597,93779 163,95953 1697,93779 193,104257 197,104257 200,112384 398,109830 420,95953 596520,95953 641,109830 641,112384 705,109830 705,93779