递归：如何避免 Python 集在迭代期间更改集 RuntimeError

Recursion: how to avoid Python set changed set during iteration RuntimeError

提问by rookie

Background and Problem Description:

背景和问题描述：

I have some code that solves the graph coloring problem (broadly defined as the problem of assigning "colors" to an undirected graph, making sure that no two vertices connected by an edge have the same color). I'm trying to implement a solution using constraint propagation to improve on the efficiency of a standard recursive backtracking algorithm, but am running into the following error:

我有一些代码可以解决图着色问题（广义上定义为将“颜色”分配给无向图的问题，确保没有边连接的两个顶点具有相同的颜色）。我正在尝试使用约束传播来实现一个解决方案，以提高标准递归回溯算法的效率，但遇到以下错误：

  File "C:\Users\danisg\Desktop\coloring\Solver.py", 
  line 99, in solve
  for color in self.domains[var]:
  RuntimeError: Set changed size during iteration

Here, for each vertex, I keep a setof possible particular values for that particular vertex:

在这里，对于每个顶点，我set为该特定顶点保留了一个可能的特定值：

  self.domains = { var: set(self.colors) for var in self.vars }

After I make an assignment, I propagate this constraint to the neighboring domains, to limit the search space:

完成分配后，我将此约束传播到相邻域，以限制搜索空间：

  for key in node.neighbors:          # list of keys corresponding to adjacent vertices
      if color in self.domains[key]:  # remove now to prune possible choices
          self.domains[key].remove(color)

This isn't where the actual error is thrown (in my code, I indicate where the problem is in a try-exceptblock), but may be the source of the problem.

这不是引发实际错误的地方（在我的代码中，我指出问题在try-except块中的哪个位置），但可能是问题的根源。

My Question:

我的问题：

Do I have the right idea, here, if not the right implementation? More to the point, how can I fix this? Also, is it necessary to keep a separate domainsdictionary? Or could we make domaina property of each node in the graph?

如果不是正确的实施，我是否有正确的想法？更重要的是，我该如何解决这个问题？另外，是否有必要保留一本单独的domains字典？或者我们可以domain为图中的每个节点设置一个属性吗？

My Code:

我的代码：

Here's the solvefunction where this code is called:

这solve是调用此代码的函数：

def solve(self):

    uncolored = [var for var in self.vars if self.map[var].color == None]
    if len(uncolored) == 0:
        return True

    var  = min(uncolored, key = lambda x: len(self.domains[var]))
    node = self.map[var]
    old  = { var: set(self.domains[var]) for var in self.vars }

    for color in self.domains[var]:

        if not self._valid(var, color):
            continue


        self.map[var].color = color
        for key in node.neighbors:

            if color in self.domains[key]:
                self.domains[key].remove(color)

        try:
            if self.solve():
                return True
        except:
            print('happening now')


        self.map[var].color = None
        self.domains = old


    return False

My implementation uses a Nodeobject:

我的实现使用一个Node对象：

class Solver:

    class Node:

        def __init__(self, var, neighbors, color = None, domain = set()):

            self.var       = var
            self.neighbors = neighbors
            self.color     = color
            self.domain    = domain

        def __str__(self):
            return str((self.var, self.color))



    def __init__(self, graph, K):

        self.vars    = sorted( graph.keys(), key = lambda x: len(graph[x]), reverse = True )  # sort by number of links; start with most constrained
        self.colors  = range(K)
        self.map     = { var: self.Node(var, graph[var]) for var in self.vars }
        self.domains = { var: set(self.colors)           for var in self.vars }

Here are two other functions that are used/are helpful:

以下是使用/有用的另外两个功能：

def validate(self):

    for var in self.vars:
        node = self.map[var]

        for key in node.neighbors:
            if node.color == self.map[key].color:
                return False

    return True

def _valid(self, var, color):

    node = self.map[var]

    for key in node.neighbors:

        if self.map[key].color == None:
            continue

        if self.map[key].color == color:
            return False

    return True

Data and Example for which the Code is Failing:

代码失败的数据和示例：

The example graph I'm using can be found here.

我正在使用的示例图可以在这里找到。

The function for reading the data:

读取数据的函数：

def read_and_make_graph(input_data):

    lines = input_data.split('\n')

    first_line = lines[0].split()
    node_count = int(first_line[0])
    edge_count = int(first_line[1])

    graph = {}
    for i in range(1, edge_count + 1):
        line  = lines[i]
        parts = line.split()
        node, edge = int(parts[0]), int(parts[1])

        if node in graph:
            graph[node].add(edge)

        if edge in graph:
            graph[edge].add(node)

        if node not in graph:
            graph[node] = {edge}

        if edge not in graph:
            graph[edge] = {node}

    return graph

It should be called as follows:

它应该被称为如下：

file_location = 'C:\Users\danisg\Desktop\coloring\data\gc_50_3'
input_data_file = open(file_location, 'r')
input_data = ''.join(input_data_file.readlines())
input_data_file.close()

graph  = read_and_make_graph(input_data)
solver = Solver(graph, 6)  # a 6 coloring IS possible

print(solver.solve())      # True if we solved; False if we didn't

采纳答案by dano

I think the problem is here:

我认为问题出在这里：

for color in self.domains[var]:

    if not self._valid(var, color):
        continue

    self.map[var].color = color
    for key in node.neighbors:

        if color in self.domains[key]:
            self.domains[key].remove(color)  # This is potentially bad.

if key == varwhen self.domains[key].remove(color)is called, you change the size of the set you're currently iterating over. You can avoid this by using

如果调用key == varwhen ，self.domains[key].remove(color)则更改当前正在迭代的集合的大小。您可以通过使用来避免这种情况

for color in self.domains[var].copy():

Using copy() will allow you to iterate over a copy of the set, while removing items from the original.

使用 copy() 将允许您迭代集合的副本，同时从原始集合中删除项目。