Antecedentes y descripción del problema:

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.

Mi pregunta:

¿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?

Mi código:

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