Getting KeyError : 3

Question

Getting KeyError: 3 when trying to do the following to find the topological sort:

def dfs_topsort(graph):         # recursive dfs with 
    L = []                      # additional list for order of nodes
    color = { u : "white" for u in graph }
    found_cycle = [False]
    for u in graph:
        if color[u] == "white":
            dfs_visited(graph, u, color, L, found_cycle)
        if found_cycle[0]:
            break

    if found_cycle[0]:           # if there is a cycle, 
        L = []                   # then return an empty list  

    L.reverse()                  # reverse the list
    return L                     # L contains the topological sort


def dfs_visited(graph, u, color, L, found_cycle):
    if found_cycle[0]:
        return
    color[u] = "gray"
    for v in graph[u]:
        if color[v] == "gray":
            found_cycle[0] = True
            return
        if color[v] == "white":
            dfs_visited(graph, v, color, L, found_cycle)
    color[u] = "black"      # when we're done with u,
    L.append(u)

graph_tasks = {1: [2,11],
    2: [3],
    11: [12],
    12: [13]
    }
order = dfs_topsort(graph_tasks)

for task in order:
    print(task)

I'm getting KeyError: 3 for the above example. Why is that so? How can it be fixed?

Answer 1

It seems that the dfs_topsort algorithm needs a key for every value that exists in the graph.

So we need to include keys for each of the values. The first one that's missing is 3, which caused the KeyError: 3, and also 13. If we include these keys and give them empty values (because they are not connected to any other nodes) then it fixes the error.

Also, the other example you gave in the comment works because every value (right-hand side) ( [2,3], [4, 5, 6], [4, 6], [5, 6], [6], [] ) is also in the Key values (left-hand side) [1, 2, 3, 4, 5, 6].

So using graph_tasks = { 1: [2, 11], 2: [3], 3: [], 11: [12], 12: [13], 13: [] } gives the output you may be expecting.

I hope this helps you.