I had two students who returned valid shortest path lists that did not match what the auto grader was expecting. Below you will find their code and feedback.

----------Student 1---------- CODE: if source not in self.d.keys(): raise KeyError("source node not in graph")

    # initialize list
    V = [] 
    # initialize deque
    Q = deque(source)
    # initialize set
    M = set(source)

    #traverse through graph step

    while set(V) != set(self.d.keys()): # until traversed graph
        diff = self.d[source].difference(M)

        M = M.union(self.d[source]) # update
        for x in diff:

            Q.append(x)

        source = Q.popleft()

        V.append(source) #append visited nodes
    return V

FEEDBACK: Problem 2 (10 points): Graph.traverse('A') failed Graph: {'A': {'C', 'B'}, 'B': {'D', 'E', 'A'}, 'C': {'F', 'G', 'A'}, 'D': {'H', 'I', 'B'}, 'E': {'K', 'J', 'B'}, 'F': {'M', 'L', 'C'}, 'G': {'N', 'O', 'C'}, 'H': {'D'}, 'I': {'D'}, 'J': {'E'}, 'K': {'E'}, 'L': {'F'}, 'M': {'F'}, 'N': {'G'}, 'O': {'G'}} Correct response: "['A', 'C', 'B', 'F', 'G', 'D', 'E', 'M', 'L', 'N', 'O', 'H', 'I', 'K', 'J']" Student response: "['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'K', 'J', 'M', 'L', 'N', 'O']" Score += 8

----------Student 2---------- CODE:

raise NotImplementedError("Problem 2 Incomplete")

    V = []          # .append 
    Q = deque()      #.append    #pop(0)
    M = set()      #use .add

    M.add(source)                    #append the fist one
    Q.append(source)

    while len(Q) != 0:
        current_node = Q.popleft()          #pop the first one and call it current node
        V.append(current_node)           #append it to V
        for x in self.d[current_node]-M:       #for loop so we add each individually, and subtract M so we dont re-add stuff
            M.add(x)                                            #self.d[current_node] is the neighbors
            Q.append(x)

    return V

Foundations-of-Applied-Mathematics / Labs

Breadth First Search - PDF #24

raise NotImplementedError("Problem 2 Incomplete")