Jack Ryan Jack Ryan - 8 days ago 5
Python Question

Dictionary size changed during iteration

I cannot, for the life of me, figure out how Python thinks my

dict
is changing size during iteration. I have tried reworking the code a few times, and cannot figure out where I would be modifying the dictionary.

Overview: I am working on a hierarchical clustering algorithm where I build an MST out of a graph I have created, and then remove edges that are weaker than a specified threshold. This all seems to work fine, but now when I am going through and computing the
clusters
(a list of lists), I run into this really odd error. Below is my code:

def compute_clusters(self):
""" wrapper function to compute clusters via DFS """
mst = self.mst
total_nodes = len(mst.keys())
visited = set()
for node in mst.keys():
if node not in visited:
self.clusters += self.cluster_dfs(mst, node, visited)

def cluster_dfs(self, mst, node, visited, cluster=[]):
""" creates clusters through dfs """
cluster.append(node)
if self.dfs_finished(mst, node, visited):
return cluster
for neighbor in self.mst[node].keys():
if neighbor not in visited:
visited.add(neighbor)
cluster.append(neighbor)
self.cluster_dfs(mst, neighbor, visited, cluster)

def dfs_finished(self, mst, node, visited):
for neighbor in self.mst[node].keys():
if neighbor not in visited:
return False
return True


Basically,
mst
is a copy of my MST (defaultdict(dict)), it maps all of the nodes to their neighbors:weights.

I figured an easy approach would be to perform a DFS from each node in the MST that has not been touched yet by the DFS. By this logic, the recursion would only return after all elements in that particular cluster have been visited. And then it goes to the next cluster and does a DFS.

My RunTime error is:

Traceback (most recent call last):
File "cluster.py", line 91, in <module>
cluster.build_clusters()
File "cluster.py", line 25, in build_clusters
self.compute_clusters() # compute final clusters
File "cluster.py", line 66, in compute_clusters
for node in mst.keys():
RuntimeError: dictionary changed size during iteration


Does anyone see a spot where I could maybe be accidentally modifying the
dict
? Apologies if it is a dumb mistake - I am a bit tired.

Answer

Does anyone see a spot where I could maybe be accidentally modifying the dict?

Given mst is a defaultdict, one possible suspect is:

for neighbor in self.mst[node].keys():

Since that could add node to self.mst. If this is the issue it leaves the question of how; for that more of the context / mst setup might help.


Seems like it does, accessing a non-existing key to a defaultdict will add the key. .... an mcve..

d = collections.defaultdict(int)
print(d)
keys = ['a','b','c']
for key in keys:
    print(key, hex(d[key]))
print(d)

>>> 
defaultdict(<class 'int'>, {})
a 0x0
b 0x0
c 0x0
defaultdict(<class 'int'>, {'a': 0, 'c': 0, 'b': 0})
>>>