Python, RuntimeError: измененный размер слова во время итерации

Question

Я пытаюсь создать своего рода остаточную сеть из данной сети, для этого я сначала создаю обратные ребра, которые не существуют на графике, но я сохраняю получать сообщение

RuntimeError: dictionary changed size during iteration 

Сначала я был, очевидно, итерация над объектом, который вносятся изменения в течение цикла:

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 

Когда граф Graph является объектом вида (я новичок в Python поэтому я не знаю, если это лучший способ сделать это)

defaultdict(lambda: defaultdict(lambda:0))

со значениями График [u] [v] установлен на емкость ребра u, v.

Так что я создал копию графика и попытался перебрать этот объект

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 

Но это не сработало. Я пробовал другие способы (создаю глубокую копию, создаю пустой объект Graph_Copy, перебираем Graph и затем устанавливаем соответствующие значения Graph_Copy), но пока не повезло. Что я делаю неправильно?

Answer 1

Честно говоря, я точно не знаю, что вызывает ваше исключение. Однако я знаю, что это плохая идея использовать вложенные словари для представления графиков. Они сложнее перебирать, как вы обнаружили, и иметь больше накладных расходов. Вместо этого вы должны использовать вложенный список.

Если я правильно понимаю вашу текущую структуру данных правильно, она может быть представлена ​​как следует:

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

Чем лучше представление будет:

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

Это способ по умолчанию для кодирования матрицы расстояний (http://en.wikipedia.org/wiki/Distance_matrix) представление графика. Если вы закодированы на других языках, таких как C/C++, это эквивалентно двумерному массиву.

u Предполагая, что & v ярлыки для ваших вершин графа, они могут быть представлены в виде числовых значений, то есть 0 для 1-го узла, 1 для 2-го и так далее. Доступ к значению края u-v будет таким же простым, как и для graph[u][v].

Теперь, давайте предположим, что вы изменили код так, что граф G, который имеет N вершин представлен в виде вложенного списка/2D массив размером NxN, ваша функция может быть переписано как следует:

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 

Answer 2

Ошибка в том, что вы используете defaultdict. Итак, что может выглядеть как операция только для чтения, например, Graph[u], может фактически добавить ключ и изменить размер словаря.

EDIT: Убрано предложение использовать copy или deepcopy.