Hintergrund und Problembeschreibung:

Ich habe einen Code, der das Problem der Diagrammfärbung löst (allgemein definiert als das Problem der Zuweisung von "Farben" zu einem ungerichteten Diagramm, wobei sichergestellt wird, dass keine zwei durch eine Kante verbundenen Scheitelpunkte dieselbe Farbe haben). Ich versuche, eine Lösung mit der Weitergabe von Einschränkungen zu implementieren, um die Effizienz eines standardmäßigen rekursiven Backtracking-Algorithmus zu verbessern. Dabei tritt jedoch der folgende Fehler auf:

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

Hier behalte ich für jeden Eckpunkt einset von möglichen bestimmten Werten für diesen bestimmten Scheitelpunkt:

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

Nachdem ich eine Zuordnung vorgenommen habe, gebe ich diese Einschränkung an die benachbarten Domänen weiter, um den Suchbereich zu begrenzen:

  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)

Hier wird nicht der eigentliche Fehler ausgelöst (in meinem Code gebe ich an, wo sich das Problem in einem befindettry-except Block), kann aber die Ursache des Problems sein.

Meine Frage:

Habe ich hier die richtige Idee, wenn nicht die richtige Implementierung? Genauer gesagt, wie kann ich das beheben? Auch ist es notwendig, eine separate zu haltendomains Wörterbuch? Oder könnten wir machendomain eine Eigenschaft jedes Knotens im Graphen?

Mein Code:

Hier ist diesolve Funktion, in der dieser Code aufgerufen wird:

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

Meine Implementierung verwendet aNode Objekt:

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 }

Hier sind zwei weitere Funktionen, die verwendet werden / hilfreich sind:

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

Daten und Beispiel, für die der Code fehlschlägt:

Das Beispieldiagramm, das ich verwende, kann gefunden werdenHier.

Die Funktion zum Lesen der Daten:

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

Es sollte wie folgt aufgerufen werden:

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