Created
September 4, 2022 10:47
-
-
Save AsyaMatveeva/b9210e53c9d17b942faa97d524943f02 to your computer and use it in GitHub Desktop.
Linear algorithm for coloring a planar graph in 5 colors.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
G = {0:{1:[3, 5], 3:[4, 1], 4:[5, 3], 5:[1, 4]}, | |
1:{0:[2, 5], 2:[6, 0], 5:[1, 4], 6:[5, 2]}, | |
2:{1:[3, 6], 3:[7, 1], 6:[1, 7], 7:[6, 3]}, | |
3:{0:[4, 2], 2:[0, 7], 4:[7, 0], 7:[2, 4]}, | |
4:{0:[3, 5], 3:[7, 0], 5:[0, 6], 6:[5, 7], 7:[6, 3]}, | |
5:{0:[4, 1], 1:[0, 6], 4:[6, 0], 6:[1, 4]}, | |
6:{1:[2, 5], 2:[7, 1], 4:[5, 7], 5:[1, 4], 7:[4, 2]}, | |
7:{2:[6, 3], 3:[2, 4], 4:[3, 6], 6:[4, 2]} | |
} | |
L = len(G) | |
flag = [False] * L | |
count = [0] * L | |
deg = [len(G[i]) for i in range(L)] | |
dp = [False] * L | |
Q = [[], [], []] | |
for v in G.keys():#формируем три очереди | |
if len(G[v]) <= 4: | |
Q[0].append(v) | |
elif len(G[v]) == 5: | |
Q[1].append(v) | |
elif len(G[v]) == 6: | |
Q[2].append(v) | |
def delete(G, v): #операция удаления вершины | |
global flag, count, deg, dp, Q | |
for key in G[v].keys(): #удаляем связи v с другими вершинами, обновляем deg и count | |
left = G[key][v][0] | |
right = G[key][v][1] | |
G[key][left][1] = right | |
G[key][right][0] = left | |
del G[key][v] | |
deg[key] -= 1 | |
count[key] -= flag[v] | |
if key in Q[1]: #обновляем Q | |
Q[1].remove(key) | |
Q[0].append(key) | |
elif key in Q[2]: | |
Q[2].remove(key) | |
Q[1].append(key) | |
del G[v] | |
for i in range(3): #обновляем Q | |
if v in Q[i]: | |
Q[i].remove(v) | |
def identify(G, x, y): #операция слияния двух вершин | |
global flag, count, deg, dp, Q | |
flag[y] = True | |
for key in G[y].keys(): #заменяем связи y на связи x, обновялем deg и count | |
сount[key] += 1 | |
if key not in G[x]: | |
x1 = list(G[x].keys())[0] | |
x2 = G[x][x1][0] | |
G[x][key] = [x2, x1] | |
G[x][x1][0] = key | |
G[x][x2][1] = key | |
k1 = list(G[key].keys())[0] | |
k2 = G[key][k1][0] | |
G[key][x] = [k2, k1] | |
G[key][k1][0] = key | |
G[key][k2][1] = key | |
deg[x] += 1 | |
count[x] += flag[key] | |
if x in Q[2]: | |
Q[2].remove(x) #обновляем Q | |
elif x in Q[1]: | |
Q[1].remove(x) | |
if count[x] == 0: | |
Q[2].append(x) | |
elif x in Q[0]: | |
Q[0].remove(x) | |
if count[x] <= 1: | |
Q[1].append(x) | |
else: | |
deg[key] -= 1 | |
if key in Q[1]: #обновляем Q | |
if deg[v] < 5: | |
Q[1].remove(key) | |
Q[0].append(key) | |
elif count[key] > 1: | |
Q[1].remove(key) | |
elif key in Q[2]: | |
if deg[key] < 6: | |
Q[2].remove(key) | |
Q[1].append(key) | |
elif count[key] > 0: | |
Q[2].remove(key) | |
left = G[key][y][0] | |
right = G[key][y][1] | |
G[key][left][1] = right | |
G[key][right][0] = left | |
del G[key][y] | |
del G[y] | |
for i in range(3): #обновляем Q | |
if y in Q[i]: | |
Q[i].remove(y) | |
def graph_5_coloring(G): | |
global flag, count, deg, Q, L | |
if len(G) <= 5: #если вершин не больше пяти, то для покраски n вершин используем n цветов | |
coloring = {} | |
color = 0 | |
for key in G.keys(): | |
coloring[key] = color | |
color += 1 | |
return coloring | |
else: | |
identified = {} | |
if len(Q[0]) != 0: | |
v = Q[0][0] | |
adjacent = G[v] | |
delete(G, v) | |
elif len(Q[1]) != 0: | |
v = Q[1][0] | |
x = G[v][list(G[v].keys())[0]] | |
left = str(G[v][x][0]) | |
y = str(G[v][left][0]) | |
if x in G[y].keys(): | |
x = left | |
y = G[v][y][0] | |
adjacent = G[v] | |
delete(G, v) | |
identify(G, v1, v2) | |
identified[v2] = v1 | |
elif len(Q[2]) != 0: | |
v = Q[2][0] | |
first = G[v][list(G[v].keys())[0]] #пронумеруем вершины против часовой стрелки | |
second = G[v][first][0] | |
third = G[v][second][0] | |
fourth = G[v][third][0] | |
fifth = G[v][fourth][0] | |
sixth = G[v][fifth][0] | |
v4 = "" | |
if first in G[third].keys(): | |
if fourth in G[sixth].keys(): | |
v1, v2, v3, v4 = first, fifth, second, fourth | |
three = False | |
else: | |
v1, v2, v3 = second, fourth, sixth | |
else: | |
if fourth in G[sixth].keys(): | |
v1, v2, v3 = first, third, fifth | |
else: | |
v1, v2, v3, v4 = first, third, fourth, sixth | |
adjacent = G[v] | |
delete(G, v) | |
if v4 == "": #три попарно не соединённые вершины | |
identify(G, v1, v2) | |
identify(G, v1, v3) | |
identified[v2] = v1 | |
identified[v3] = v1 | |
else: #две пары не соединённых вершин | |
identify(G, v1, v2) | |
identify(G, v3, v4) | |
identified[v2] = v1 | |
identified[v3] = v4 | |
flag = [False] * L | |
count = [0] * L | |
coloring = graph_5_coloring(G) | |
G[v] = adjacent | |
for key, val in identified.items(): | |
coloring[key] = coloring[val] | |
colors = [coloring[c] for c in G[v].keys()] | |
coloring[v] = 0 | |
while coloring[v] in colors: | |
coloring[v] += 1 | |
return coloring | |
coloring = graph_5_coloring(G) | |
print(coloring) | |
#Проверяем: | |
correct_coloring = True | |
for key, val in G.items(): | |
for v in val.keys(): | |
if coloring[key] == coloring[v]: | |
correct_coloring = False | |
break | |
print("Coloring is correct:", correct_coloring) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment