将 4 色定理应用于图形数组中存储的相邻多边形列表

Question

我想应用4颜色定理，即。地图上的每个相邻多边形应具有不同的颜色。该定理指出任何类型的地图只需要 4 种颜色。

作为输入，我有一个包含 id 和颜色 id 的多边形数组以及一个相邻多边形的图形数组。作为输出，我想将 0-3（或最大 0-4）之间的颜色 id 与每个多边形相关联，确保相邻的多边形具有不同的颜色 id。

我有以下代码（来自这个问题），它为每个邻居返回不同的颜色ID，但它不能确保使用最小数量的颜色。

#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)

我希望脚本使用强力循环或其他方法最多减少颜色数量（4 或 5）。

Answer 1

这是从我的 math.stackexchange 答案 中提取的图形着色代码。不可否认，该代码有点复杂，因为它使用 Knuth 算法 X 来完成两个任务：解决 tromino 打包问题，然后解决每个打包问题解决方案的着色问题。

此代码可在不到 1 秒的时间内为您的样本数据找到 24 个 3 色解决方案或 756 个 4 色。其实还有更多的解，但是我随意设置了前2个节点的颜色，以减少解的总数，并稍微加快搜索算法的速度。

''' 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))

输出

 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)]

如果您只想要一个解决方案，请将最后一个

for

循环替换为

output_polygons = next(all_solutions)
print(output_polygons)

---

FWIW，这里有一些代码可用于从图形数据创建图表。

# 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')

你可以这样称呼它：

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

它还可用于生成

input_polygons

的 DOT 文件。

要使用 Graphviz

neato

实用程序从 DOT 文件生成 PNG 图像文件，您可以执行此操作（在 Bash 中）。

neato -Tpng -ograph.png graph.dot

这是上面第一个解决方案的 DOT 文件：

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;
}

这是 PNG：

这是一个 live 版本，在 SageMathCell 服务器上运行。