Recursion: how to avoid Python set changed set during iteration RuntimeError
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 == var
when 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
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.
rookie
Updated on April 04, 2020Comments
-
rookie about 4 years
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
set
of possible particular values for that particular vertex: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-except
block), but may be the source of the problem.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
domains
dictionary? Or could we makedomain
a property of each node in the graph?My Code:
Here's the
solve
function where this code is called: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
Node
object: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
-
rookie about 10 yearsThough this is a good suggestion, this doesn't actually happen in the code supplied (just verified). The mapping for domains is also
{var: possible_colors}
. Can you please explain wherefor color in self.domains[var].keys():
should be put? -
dano about 10 yearsMy suggestion was to replace
for color in self.domains[var]:
, which is in the solve() method, withfor color in self.domains[var].keys():
. That should eliminate the backtrace you posted. -
rookie about 10 years
self.domains[var].keys()
produces the following:for color in self.domains[var].keys(): AttributeError: 'set' object has no attribute 'keys'
-
dano about 10 yearsAh, sorry about that, I was thinking it was a dict. You can use .copy(), instead.
-
dano about 10 yearsI've edited my original answer to use .copy() instead of .keys().
-
rookie about 10 yearsThis works...but why?! I put in some code to check if
var == key
, and the execution never hit this line. Can you say a little more about why this works? Is it the conflict happening somewhere deeper in the recursion? Please let me know if this check is invalid:for key in node.neighbors: if key == var: print('dano found the error!')
-
dano about 10 yearsI think it's probably the recursive nature of solve(). Say the first time you enter solve(), var == 1. key may never == 1 in that stack frame, but then you recursively call solve() again later in the for loop. If you end up removing a color from self.domains[1] in that lower stack frame (or any subsequent stack frame while recursing), you've blown up the top stack frame. So once you make it back to the original stack frame, the size of the set it's iterating over has changed, and it throws an exception.
-
rookie about 10 yearsexactly what I was thinking, but much better explained. Thank you so much!!
-
JGFMK almost 3 yearsCan you not do something with iterators instead in Python too in a similar way to what Java allows? Is yield the same in Python perhaps? realpython.com/introduction-to-python-generators