linear_5_coloring.py

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]}
} #example graph. Adjacency-lists are modeled with hashmap, planar embedding information is stored here.

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():#form three queues
    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): #delete vertex operation
    global flag, count, deg, dp, Q
    for key in G[v].keys(): #remove links from v to neighbors, update deg and 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]: #update 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): #update Q
        if v in Q[i]:
            Q[i].remove(v)
            
             
def identify(G, x, y): #merging operation
    global flag, count, deg, dp, Q
    flag[y] = True
    for key in G[y].keys(): #change links of y to links of x, update 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) #update 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]: #update 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): #update 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: #vertices <= 5, use 5 colors
        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]] #number vertices counter-clockwise
            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 == "": #three not-interconntected vertices
                identify(G, v1, v2)
                identify(G, v1, v3)
                identified[v2] = v1
                identified[v3] = v1
            else: #two pairs of not connected vertices
                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)  

#Check the correctness:
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)