I am getting "RuntimeError: dictionary changed size during iteration" despite not making any changes to the dictionary. How do i resolve this?

Question

I am trying to implement Topological Sort in Python 3.7 but am getting the following error message:

Traceback (most recent call last):
  File "D:/pythonchallenge/topological_sort.py", line 42, in <module>
    graph_.Topological_Sort()
  File "D:/pythonchallenge/topological_sort.py", line 28, in Topological_Sort
    for node in self.adj_list:
RuntimeError: dictionary changed size during iteration

Here is my code:

# Topological Sort
# Algorithm - https://www.geeksforgeeks.org/topological-sorting/

from collections import defaultdict


class Graph:
    def __init__(self, size):
        self.adj_list = defaultdict(list)
        self.visited = []
        self.size = size

    def Insert_Node(self, u, v):
        self.adj_list[u].append(v)

    def Topological_Sort_Util(self, input_node, input_stack):
        self.visited[input_node] = True

        for child in self.adj_list[input_node]:
            if not self.visited[child]:
                self.Topological_Sort_Util(child, input_stack)

        input_stack.append(input_node)

    def Topological_Sort(self):
        self.visited = [False] * self.size
        stack_ = []
        for node in self.adj_list:
            if not self.visited[node]:
                self.Topological_Sort_Util(node, stack_)

        while len(stack_) != 0:
            print(stack_.pop(-1), end=" ")


if __name__ == '__main__':
    graph_ = Graph(4)
    graph_.Insert_Node(1, 3)
    graph_.Insert_Node(2, 1)
    graph_.Insert_Node(4, 2)
    graph_.Insert_Node(4, 3)
    graph_.Topological_Sort()

Can anyone explain why I am getting this error despite me not making any modifications to the dictionary?

Answer 1

In short: You are changing the size of the defaultdict by accessing a non-existing member.

You are doing the following:

1. Loop over self.adj_list, which is (despite the name) a defaultdict

2. Call Topological_Sort_Util with a node from self.adj_list (so far so good)

3. Loop over the children in self.adj_list[input_node]

4. Call Topological_Sort_Util recursively with the children of the node

The last step is where things go wrong in your example. Node 1 has node 3 as the only child, but you never add node 3 to adj_list. Because adj_list is a defaultdict, the line

for child in self.adj_list[input_node]:

will add a new key for input_node to adj_list if it doesn't exist yet. This changes the size of the dictionary, and an exception is thrown.

You can see this by printing adj_list before and after the call to Topological_Sort_Util:

defaultdict(<class 'list'>, {1: [3], 2: [1], 4: [2, 3]})  # before
defaultdict(<class 'list'>, {1: [3], 2: [1], 4: [2, 3], 3: []})  # after

You can fix it by making sure the child node exists in Insert_Node:

def Insert_Node(self, u, v):
    self.adj_list[u].append(v)
    self.adj_list[v]

Another problem

Your visited attribute is a list, which uses 0-based indexing, but you start numbering your nodes from 1. So, when you do

self.visited[input_node] = True

it will fail for node 4, because your list only has size 4 (last index is 3).

So you either need to

• Convert visited to a dict with arbitrary keys or
• Make sure to make visited big enough to index into all of your nodes or
• Start numbering nodes from 0