-
Notifications
You must be signed in to change notification settings - Fork 0
/
tricoloring.py
35 lines (29 loc) · 1.09 KB
/
tricoloring.py
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
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
# check if the current color assignment is safe for vertex v
def isSafe(self, v, colour, c):
for i in range(self.V):
if self.graph[v][i] == 1 and colour[i] == c:
return False
return True
# recursive function to solve m coloring problem
def graphColourUtil(self, m, colour, v):
if v == self.V:
return True
for c in range(1, m+1):
if self.isSafe(v, colour, c) == True:
colour[v] = c
if self.graphColourUtil(m, colour, v+1) == True:
return True
colour[v] = 0
def graphColouring(self, m):
colour = [0] * self.V
if self.graphColourUtil(m, colour, 0) == False:
return False
#answer
color_array = []
for c in colour: color_array.append(c)
return color_array