Graph_Coloring/graph_coloring.py at main · litsas7/Graph_Coloring · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 21 17:52:30 2022

@author: litsas7
"""


import sys
import argparse
import collections
import math

program = sys.argv[1]
colours = int(sys.argv[2])
first = int(sys.argv[3])
graph = sys.argv[4]
g = {}

with open(graph) as graph_input:
    for line in graph_input:
        nodes = [int(x) for x in line.split()]
        if len(nodes) != 2:
            g[nodes[0]] = []
            continue
        if nodes[0] not in g:
            g[nodes[0]] = []
        if nodes[1] not in g:
            g[nodes[1]] = []
        g[nodes[0]].append(nodes[1])
        g[nodes[1]].append(nodes[0])

grade = []
W = []
U = []
coloured = []
if program == "johnson":
    for i in range(len(g)):
        grade.append(len(g[i]))
        W.append(i)
        coloured.append(-1)
    n = max(grade) + 1
    i = 0
    grade1 = []
    while len(W) > 0:
        U = W.copy()
        while len(U) > 0:
            for a in range(len(U)):
                grade1.append(-1)
                grade1[a] = grade[U[a]]
            u = U[grade1.index(min(grade1))]
            grade[u] = n
            coloured[u] = i
            if u in U:
                U.remove(u)
            for j in range(len(g[u])):
                x = g[u][j]
                if x in U:
                    U.remove(x)
            if u in W:
                W.remove(u)
            grade1 = []
        i = i + 1
    for b in range(len(g)):
        print(b,':', coloured[b] + first)
    print(i)
else:
    for i in range(len(g)):
        coloured.append(-1)
    def Wigderson(G, k, i):
        for i in range(len(g)):
            grade.append(len(g[i]))
        D = max(grade)
        n = len(G)
        f = n ** (1 - (1/(k-1)))
        if k == 2:
            coloured[G[0]] = i
            coloured[G[1]] = i + 1
            same = False
            for q in range(len(g[G[1]])):
                if coloured[G[1]] == coloured[g[G[1]][q]]:
                    same = True
            if same == False:
                return 2
            if same == True:
                return -1
        if k >= math.log10(n):
            return n
        while D >= math.ceil(f):
            u = grade.index(D)
            H = G[u].copy()
            j = Wigderson(H, k-1, i)
            coloured[u] = i + j
            i = i + j
            del G[u]
            return coloured
    def first_available(coloured):
        color_set = set(coloured)
        count = 0
        while True:
            if count not in color_set:
                return count
            count += 1
    def greedy_color(G, order):
        color = dict()
        for node in order:
            used_neighbour_colors = [color[nbr] for nbr in G[node] if nbr in color]
            color[node] = first_available(used_neighbour_colors)
        return color

    w = Wigderson(g, colours, first)
    for e in range(len(g)):
        print(e,':',coloured[e])