def preprocess_constraints(ml, cl, n):
<EOL>ml_graph, cl_graph = {}, {}<EOL>for i in range(n):<EOL><INDENT>ml_graph[i] = set()<EOL>cl_graph[i] = set()<EOL><DEDENT>def add_both(d, i, j):<EOL><INDENT>d[i].add(j)<EOL>d[j].add(i)<EOL><DEDENT>for (i, j) in ml:<EOL><INDENT>ml_graph[i].add(j)<EOL>ml_graph[j].add(i)<EOL><DEDENT>for (i, j) in cl:<EOL><INDENT>cl_graph[i].add(j)<EOL>cl_graph[j].add(i)<EOL><DEDENT>def dfs(i, graph, visited, component):<EOL><INDENT>visited[i] = True<EOL>for j in graph[i]:<EOL><INDENT>if not visited[j]:<EOL><INDENT>dfs(j, graph, visited, component)<EOL><DEDENT><DEDENT>component.append(i)<EOL><DEDENT>visited = [False] * n<EOL>neighborhoods = []<EOL>for i in range(n):<EOL><INDENT>if not visited[i] and ml_graph[i]:<EOL><INDENT>component = []<EOL>dfs(i, ml_graph, visited, component)<EOL>for x1 in component:<EOL><INDENT>for x2 in component:<EOL><INDENT>if x1 != x2:<EOL><INDENT>ml_graph[x1].add(x2)<EOL><DEDENT><DEDENT><DEDENT>neighborhoods.append(component)<EOL><DEDENT><DEDENT>for (i, j) in cl:<EOL><INDENT>for x in ml_graph[i]:<EOL><INDENT>add_both(cl_graph, x, j)<EOL><DEDENT>for y in ml_graph[j]:<EOL><INDENT>add_both(cl_graph, i, y)<EOL><DEDENT>for x in ml_graph[i]:<EOL><INDENT>for y in ml_graph[j]:<EOL><INDENT>add_both(cl_graph, x, y)<EOL><DEDENT><DEDENT><DEDENT>for i in ml_graph:<EOL><INDENT>for j in ml_graph[i]:<EOL><INDENT>if j != i and j in cl_graph[i]:<EOL><INDENT>raise InconsistentConstraintsException('<STR_LIT>'.format(i, j))<EOL><DEDENT><DEDENT><DEDENT>return ml_graph, cl_graph, neighborhoods<EOL>
Create a graph of constraints for both must- and cannot-links