-
Notifications
You must be signed in to change notification settings - Fork 3
/
56_Google_Color_Adjacency_Matrix.py
executable file
·85 lines (56 loc) · 1.79 KB
/
56_Google_Color_Adjacency_Matrix.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
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
"""
This problem was asked by Google.
Given an undirected graph represented as an adjacency matrix and an integer k,
write a function to determine whether each vertex in the graph can be colored
such that no two adjacent vertices share the same color using at most k colors.
"""
# creates a 2 object list out of each and adds None to the place where we'll mark the color of the node
def get_nodes(adj_mat):
return [[i, None] for i in range(len(adj_mat))]
def check_nodes_filled(nodes):
# check if all nodes are filled
return all((val[1] for val in nodes))
def check_valid(curr_node, nodes, adj_mat):
for node,edge in enumerate(adj_mat[curr_node[0]]):
if edge == 1:
if nodes[node][1] == curr_node[1]:
return False
return True
def add_color(nodes, k):
# take the first node with None as the second attr
current_node = None
for n in nodes:
if n[1] is None:
current_node = n
break
# check if all nodes are colored
if current_node is None:
return nodes
# try to add color to the node:
for color in k:
current_node[1] = color
if check_valid(current_node, nodes,adjacency_mat):
# if True
result = add_color(nodes, k)
if check_nodes_filled(result):
return result
current_node[1] = None
return nodes
def solve(adj_mat, k):
result = add_color(get_nodes(adjacency_mat), k)
return result, check_nodes_filled(result)
if __name__ == '__main__':
"""
(a)---(b)
| \/
| /\
| / \
(c)---(d)
"""
adjacency_mat = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
print(solve(adjacency_mat, ['r', 'g', 'b']))