Recursión: cómo evitar que el conjunto de Python cambie el conjunto durante la iteración RuntimeError
Tengo un código que resuelve el problema de coloración del gráfico (ampliamente definido como el problema de asignar "colores" a un gráfico no dirigido, asegurándose de que no haya dos vértices conectados por un borde que tengan el mismo color). Estoy tratando de implementar una solución usando la propagación de restricciones para mejorar la eficiencia de un algoritmo de retroceso recursivo estándar, pero me encuentro con el siguiente 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
Aquí, para cada vértice, mantengo unset
de posibles valores particulares para ese vértice particular:
self.domains = { var: set(self.colors) for var in self.vars }
Después de realizar una asignación, propago esta restricción a los dominios vecinos para limitar el espacio de búsqueda:
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)
Aquí no es donde se arroja el error real (en mi código, indico dónde está el problema en untry-except
bloque), pero puede ser la fuente del problema.
¿Tengo la idea correcta, aquí, si no es la implementación correcta? Más al punto, ¿cómo puedo solucionar esto? Además, ¿es necesario mantener undomains
¿diccionario? O podríamos hacerdomain
una propiedad de cada nodo en el gráfico?
Aquí esta lasolve
función donde se llama este código:
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
Mi implementación utiliza unNode
objeto:
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 }
Aquí hay otras dos funciones que se utilizan / son útiles:
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
Datos y ejemplo para los que falla el código:El gráfico de ejemplo que estoy usando se puede encontraraquí.
La función para leer los datos:
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
Debe llamarse de la siguiente manera:
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