Python, RuntimeError: dictionary changed size during iteration

Question

I'm trying to create a sort of residual network from a given network, for that I'm first creating the reverse edges that doesn't exist in the graph, but I keep getting the message

RuntimeError: dictionary changed size during iteration

First I was obviously iterating over an object that was being modified during the loop:

def Gf(Graph):    #residual graph
 for u in Graph:
    for v in Graph[u]:
        if u in Graph[v]: 
            pass
        else:
            Graph[v][u]=0 #create the edge with capacity 0
 return Graph

Where the graph Graph is an object of the form (I'm new to python so I don't know if this is the best way to do it)

defaultdict(lambda: defaultdict(lambda:0))

with values Graph[u][v] set to capacity of the edge u,v.

So I created a copy of Graph and tried to iterate over that object

def Gf(Graph):    #residual graph
 Graph_Copy=Graph.copy()
 for u in Graph_Copy:
    for v in Graph_Copy[u]:
        if u in Graph_Copy[v]: 
            pass
        else:
            Graph[v][u]=0 
 return Graph

But that didn't work. I tried some other ways (create a deepcopy; create an empty object Graph_Copy, iterate over Graph and then set adequate values to Graph_Copy) but no luck so far. What I'm doing wrong?

The variables `Gf`, `G`, `u`, `v`, and `Gr` do not have descriptive names. Give them names composed of actual words. The program will run just as fast, while being much easier to debug. — TigerhawkT3, May 12 '15 at 03:57
Thanks for the suggestion, I changed the code (Though I think that u,v are pretty straightforward variables while working on a graph, and Gf is the usual notation for the residual graph). — Raul, May 12 '15 at 04:02
Is there any reason why your are using a dictionary of dictionary, instead of a 2-dimensional array (i.e. a list of list)? The array would be much easier to iterate over, not to mention being the standard data structure for graphs. — oxymor0n, May 12 '15 at 04:08
Because I find it easier to set and get the capacity of the edge u,v, being simply Graph[u][v], but, like I said I'm really new to python, so maybe what you said it's a better option (How do I keep the capacities with a 2-dimensional array? with another array?) — Raul, May 12 '15 at 04:11
Hi, this is not related to the question exactly, but would highly recommend you to watch this video http://pyvideo.org/video/276/the-mighty-dictionary-55 , so that you have a better idea about dictionaries — Siddharth Srivastava, May 12 '15 at 04:30

score 2 · Accepted Answer · answered May 12 '15 at 05:07

Honestly, I don't know exactly what is causing your exception. What I do know, however, is that it is a bad idea to use nested dictionaries to represent graphs. They are harder to iterate over, as you have discovered, and have more overhead. Instead, you should use a nested list.

If I understand your current data structure correctly, it can be represented as followed:

graph = {
    u0: {v0: 0, v1: 0, ... },
    u1: {v0: 0, v1: 0, ... },
    ...
}  # the curly brackets denote dictionaries

The better representation would be:

graph = [
    [0, 0, 0, ...],
    [0, 0, 0, ...],
    ...
]  # the brackets denote lists

This is the default way to encode the distance matrix (http://en.wikipedia.org/wiki/Distance_matrix) representation of a graph. If you have coded in other languages like C/C++, then this is the equivalent of a 2-dimensional array.

Assuming that u & v are labels for your graph vertices, they can be represented as numerical values, i.e. 0 for the 1st node, 1 for the 2nd, and so on. Accessing the value of the edge u-v would be as simple as doing graph[u][v].

Now, let's assume that you have changed your code so that the graph G which has N vertices is represented as a nested list/2D array of size NxN, your function can be rewritten as followed:

def gf(g):  # python style guideline recommends lower case variable & function names
    vertices_count = len(g)  # get the size of the original graph
    gf = []   # initialize the new redidual graph
    for u in range(vertices_count):
        gf.append([0]*vertices_count)  # initialize the edges
        for v in range(vertices_count):
            if g[u][v] > 0:
                # do something here if the value of edge u-v is more than zero, e.g. gf[u][v] = some formula
            else:
                # do something here if the value of edge u-v is zero,, e.g. gf[u][v] = 0
    return gf

Jomel Imperio · Answer 2 · 2015-05-12T04:24:15.087

0

The error is because you're using defaultdict. So what can look like a read-only operation, e.g., Graph[u], can actually add a key and change the dictionary size.

EDIT: Removed suggestion to use copy or deepcopy.

edited May 12 '15 at 04:24

answered May 12 '15 at 03:47

Jomel Imperio

924
4
16

Thanks! I didn't know that, but I keep getting the error message. – Raul May 12 '15 at 03:52
.copy() only create a shallow copy (http://stackoverflow.com/questions/3975376/understanding-dict-copy-shallow-or-deep), i.e. a reference. You need to use deepcopy() instead (`from copy import deepcopy`) – oxymor0n May 12 '15 at 04:05
@oxymor0n Ah, you're right, in this case it's important because the values are `defaultdict` instances as well. I'll edit my answer. – Jomel Imperio May 12 '15 at 04:08
Thanks, but I already tried with a deepcopy(), I'm probably doing something else wrong. – Raul May 12 '15 at 04:15
I think you could probably go with a simpler data structure instead as @oxymor0n suggests. – Jomel Imperio May 12 '15 at 04:18

Python, RuntimeError: dictionary changed size during iteration

2 Answers2