title: Recursion: how to avoid Python set changed set during iteration RuntimeError
body: <h1>Background and Problem Description:</h1>
  
  <p>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:</p>
  
  <pre><code>  File "C:\Users\danisg\Desktop\coloring\Solver.py", 
    line 99, in solve
    for color in self.domains[var]:
    RuntimeError: Set changed size during iteration
  </code></pre>
  
  <p>Here, for each vertex, I keep a <code>set</code> of possible particular values for that particular vertex:</p>
  
  <pre><code>  self.domains = { var: set(self.colors) for var in self.vars }
  </code></pre>
  
  <p>After I make an assignment, I propagate this constraint to the neighboring domains, to limit the search space:</p>
  
  <pre><code>  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)
  </code></pre>
  
  <p>This isn't where the actual error is thrown (in my code, I indicate where the problem is in a <code>try-except</code> block), but may be the source of the problem. </p>
  
  <h1>My Question:</h1>
  
  <p>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 <code>domains</code> dictionary? Or could we make <code>domain</code> a property of each node in the graph? </p>
  
  <h1>My Code:</h1>
  
  <p>Here's the <code>solve</code> function where this code is called:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>My implementation uses a <code>Node</code> object:</p>
  
  <pre><code>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 }
  </code></pre>
  
  <p>Here are two other functions that are used/are helpful:</p>
  
  <pre><code>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
  </code></pre>
  
  <h1>Data and Example for which the Code is Failing:</h1>
  
  <p>The example graph I'm using can be found <a href="https://drive.google.com/file/d/0B1PjzDTxaswROWQwQ3ctSFhoUHc/edit?usp=sharing">here</a>.</p>
  
  <p>The function for reading the data:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>It should be called as follows:</p>
  
  <pre><code>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
  </code></pre>