Anwenden des 4-Farben-Theorems auf die Liste der Nachbarpolygone in einem Graphenfeld

Question

Ich möchte die 4 color theorem IE anwenden. Jedes Nachbarpolygon auf einer Karte sollte eine andere Farbe haben. Der Satz besagt, dass nur 4 Farben für jede Art von Karte benötigt werden.

Als Eingabe habe ich ein Array von Polygon mit ID und Farbe ID und ein Diagramm Array von benachbarten Polygonen. Als Ausgabe möchte ich jedem Polygon eine Farb-ID zwischen 0-3 (oder maximal 0-4) zuordnen, um sicherzustellen, dass benachbarte Polygone unterschiedliche Farb-IDs haben.

Ich habe den folgenden Code (from this question), die eine andere Farbe ID für jeden neighboor gibt, aber es stellt nicht sicher, dass die minimale Anzahl von Farben verwendet wird.

#array of input polygon tuples (id, color_id) color_id is None at beginning 
input_polygons = [(0, None), (1, None), (2, None), (3, None), (4, None), (5, None), (6, None), (7, None), (8, None)] 

#graph array of neighbors ids 
adjacent_polygons_graph = [[0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [1, 0], [2, 0], [2, 3], [3, 0], [3, 2], [3, 6], [3, 8], [4, 0], [4, 5], [4, 6], [5, 0], [5, 4], [6, 3], [6, 4], [6, 7], [7, 6], [8, 3]] 

colored = [] 
for polygon in input_polygons: 
    nbrs = [second for first, second in adjacent_polygons_graph if first == polygon[0]] 
    used_colors = [] 
    for nbr in nbrs: 
     used_colors += [second for first, second in colored if first == nbr] 
    polygon[1]=[color for color in range(10) if color not in used_colors][0] 
    colored.append(polygon) 

würde ich das Skript bei maximaler wie die Anzahl der Farben (4 oder 5) unter Verwendung von Brute-Force-Schleife oder andere Verfahren zu verringern.

Answer 1

Hier ist der Graph Malcode aus dem Code in meinem math.stackexchange answer extrahiert. Dieser Code ist zugegebenermaßen etwas kompliziert, da er Knuths Algorithmus X für zwei Aufgaben verwendet: Lösen des Tromino-Packungsproblems und dann Lösen des Färbungsproblems für jede Lösung des Packungsproblems.

Dieser Code findet 24 3-Farben-Lösungen oder 756 4-Farben für Ihre Beispieldaten in weniger als 1 Sekunde. Es gibt tatsächlich mehr Lösungen, aber ich setze willkürlich die Farben für die ersten 2 Knoten, um die Gesamtzahl der Lösungen zu reduzieren und den Suchalgorithmus etwas zu beschleunigen.

''' Knuth's Algorithm X for the exact cover problem, 
    using dicts instead of doubly linked circular lists. 
    Written by Ali Assaf 

    From http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html 

    and http://www.cs.mcgill.ca/~aassaf9/python/sudoku.txt 

    Python 2/3 compatible 

    Graph colouring version 
''' 

from __future__ import print_function 
from itertools import product 

def solve(X, Y, solution=[]): 
    if not X: 
     yield list(solution) 
    else: 
     c = min(X, key=lambda c: len(X[c])) 
     Xc = list(X[c]) 

     for r in Xc: 
      solution.append(r) 
      cols = select(X, Y, r) 
      for s in solve(X, Y, solution): 
       yield s 
      deselect(X, Y, r, cols) 
      solution.pop() 

def select(X, Y, r): 
    cols = [] 
    for j in Y[r]: 
     for i in X[j]: 
      for k in Y[i]: 
       if k != j: 
        X[k].remove(i) 
     cols.append(X.pop(j)) 
    return cols 

def deselect(X, Y, r, cols): 
    for j in reversed(Y[r]): 
     X[j] = cols.pop() 
     for i in X[j]: 
      for k in Y[i]: 
       if k != j: 
        X[k].add(i) 

#Invert subset collection 
def exact_cover(X, Y): 
    newX = dict((j, set()) for j in X) 
    for i, row in Y.items(): 
     for j in row: 
      newX[j].add(i) 
    return newX 

def colour_map(nodes, edges, ncolours=4): 
    colours = range(ncolours) 

    #The edges that meet each node 
    node_edges = dict((n, set()) for n in nodes) 
    for e in edges: 
     n0, n1 = e 
     node_edges[n0].add(e) 
     node_edges[n1].add(e) 

    for n in nodes: 
     node_edges[n] = list(node_edges[n]) 

    #Set to cover 
    coloured_edges = list(product(colours, edges)) 
    X = nodes + coloured_edges 

    #Subsets to cover X with 
    Y = dict() 
    #Primary rows 
    for n in nodes: 
     ne = node_edges[n] 
     for c in colours: 
      Y[(n, c)] = [n] + [(c, e) for e in ne] 

    #Dummy rows 
    for i, ce in enumerate(coloured_edges): 
     Y[i] = [ce] 

    X = exact_cover(X, Y) 

    #Set first two nodes 
    partial = [(nodes[0], 0), (nodes[1], 1)] 
    for s in partial: 
     select(X, Y, s) 

    for s in solve(X, Y, []): 
     s = partial + [u for u in s if not isinstance(u, int)] 
     s.sort() 
     yield s 

# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

input_polygons = [ 
    (0, None), (1, None), (2, None), (3, None), (4, None), 
    (5, None), (6, None), (7, None), (8, None), 
] 

#graph array of neighbors ids 
adjacent_polygons_graph = [ 
    (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (2, 0), (2, 3), 
    (3, 0), (3, 2), (3, 6), (3, 8), (4, 0), (4, 5), (4, 6), 
    (5, 0), (5, 4), (6, 3), (6, 4), (6, 7), (7, 6), (8, 3), 
] 

# Extract the nodes list 
nodes = [t[0] for t in input_polygons] 

# Get an iterator of all solutions with 3 colours 
all_solutions = colour_map(nodes, adjacent_polygons_graph, ncolours=3) 

# Print all solutions 
for count, solution in enumerate(all_solutions, start=1): 
    print('%2d: %s' % (count, solution)) 

Ausgang

1: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 1), (7, 0), (8, 1)] 
2: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 1), (7, 0), (8, 0)] 
3: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 1), (7, 2), (8, 1)] 
4: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 1), (7, 2), (8, 0)] 
5: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 0), (7, 2), (8, 0)] 
6: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 0), (7, 1), (8, 0)] 
7: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 0), (7, 2), (8, 1)] 
8: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 2), (5, 1), (6, 0), (7, 1), (8, 1)] 
9: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 1), (5, 2), (6, 0), (7, 1), (8, 1)] 
10: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 1), (5, 2), (6, 0), (7, 1), (8, 0)] 
11: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 1), (5, 2), (6, 0), (7, 2), (8, 0)] 
12: [(0, 0), (1, 1), (2, 1), (3, 2), (4, 1), (5, 2), (6, 0), (7, 2), (8, 1)] 
13: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 2), (7, 0), (8, 0)] 
14: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 2), (5, 1), (6, 0), (7, 2), (8, 0)] 
15: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 0), (7, 2), (8, 0)] 
16: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 2), (5, 1), (6, 0), (7, 1), (8, 0)] 
17: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 0), (7, 1), (8, 0)] 
18: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 2), (7, 1), (8, 0)] 
19: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 2), (7, 1), (8, 2)] 
20: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 2), (7, 0), (8, 2)] 
21: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 2), (5, 1), (6, 0), (7, 2), (8, 2)] 
22: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 0), (7, 2), (8, 2)] 
23: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 2), (5, 1), (6, 0), (7, 1), (8, 2)] 
24: [(0, 0), (1, 1), (2, 2), (3, 1), (4, 1), (5, 2), (6, 0), (7, 1), (8, 2)] 

Wenn Sie nur eine einzige Lösung wollen, ersetzen Sie die letzte for Schleife mit

output_polygons = next(all_solutions) 
print(output_polygons) 

---

FWIW, hier einige Code, der verwendet werden kann, um ein Diagramm aus den Diagrammdaten zu erstellen.

# Create a Graphviz DOT file from graph data 
colors = { 
    None: 'white', 
    0: 'red', 1: 'yellow', 
    2: 'green', 3: 'blue' 
} 

def graph_to_dot(nodes, edges, outfile=sys.stdout): 
    outfile.write('strict graph test{\n') 
    outfile.write(' node [style=filled];\n') 

    for n, v in nodes: 
     outfile.write(' {} [fillcolor={}];\n'.format(n, colors[v])) 
    outfile.write('\n') 

    for u, v in edges: 
     outfile.write(' {} -- {};\n'.format(u, v)) 
    outfile.write('}\n') 

Sie können es so nennen:

# Produce a DOT file of the colored graph 
with open('graph.dot', 'w') as f: 
    graph_to_dot(output_polygons, adjacent_polygons_graph, f) 

Es kann auch eine DOT-Datei des input_polygons zu produzieren verwendet werden.

Um eine PNG-Bilddatei aus der DOT-Datei mit dem Graphvizneato Dienstprogramm zu generieren, können Sie dies (in Bash) tun.

neato -Tpng -ograph.png graph.dot 

Hier ist die DOT-Datei für die erste Lösung oben:

strict graph test{ 
    node [style=filled]; 
    0 [fillcolor=red]; 
    1 [fillcolor=yellow]; 
    2 [fillcolor=yellow]; 
    3 [fillcolor=green]; 
    4 [fillcolor=green]; 
    5 [fillcolor=yellow]; 
    6 [fillcolor=yellow]; 
    7 [fillcolor=red]; 
    8 [fillcolor=yellow]; 

    0 -- 1; 
    0 -- 2; 
    0 -- 3; 
    0 -- 4; 
    0 -- 5; 
    1 -- 0; 
    2 -- 0; 
    2 -- 3; 
    3 -- 0; 
    3 -- 2; 
    3 -- 6; 
    3 -- 8; 
    4 -- 0; 
    4 -- 5; 
    4 -- 6; 
    5 -- 0; 
    5 -- 4; 
    6 -- 3; 
    6 -- 4; 
    6 -- 7; 
    7 -- 6; 
    8 -- 3; 
} 

Und hier ist das PNG: