77 lines
1.9 KiB
Python
77 lines
1.9 KiB
Python
|
lines = [
|
||
|
|
['A','B'],
|
||
|
|
['A','C'],
|
||
|
|
['B', 'C'],
|
||
|
|
['D', 'C'],
|
||
|
|
['E','C'],
|
||
|
|
['E','F'],
|
||
|
|
['C', 'F'],
|
||
|
|
['F','G'],
|
||
|
|
['F','H'],
|
||
|
|
['G', 'H'],
|
||
|
|
]
|
||
|
|
|
||
|
|
'''the verteices of {'POINT', (ADAJACENT POINTS)}'''
|
||
|
|
vertex_and_adjs = dict()
|
||
|
|
|
||
|
|
class Vertex:
|
||
|
|
def __init__(self, name, adjacent):
|
||
|
|
self.color = None
|
||
|
|
self.name = name
|
||
|
|
self.adjacents = set(adjacent)
|
||
|
|
|
||
|
|
def add_adjacent(self, adj):
|
||
|
|
self.adjacents.add(adj)
|
||
|
|
def __repr__(self):
|
||
|
|
return '{' + f'{self.name} - color: {self.color}, adjs: {self.adjacents}' + '}'
|
||
|
|
|
||
|
|
|
||
|
|
def add_to_graph(vertexes, lines):
|
||
|
|
for line in lines:
|
||
|
|
point_a = line[0]
|
||
|
|
point_b = line[1]
|
||
|
|
|
||
|
|
if not point_a in vertexes:
|
||
|
|
vertexes[point_a] = Vertex(point_a, point_b)
|
||
|
|
else:
|
||
|
|
vertexes[point_a].add_adjacent(point_b)
|
||
|
|
|
||
|
|
if not point_b in vertexes.keys():
|
||
|
|
vertexes[point_b] = Vertex(point_b, point_a)
|
||
|
|
else:
|
||
|
|
vertexes[point_b].add_adjacent(point_a)
|
||
|
|
return vertexes
|
||
|
|
|
||
|
|
graph = add_to_graph(vertex_and_adjs, lines)
|
||
|
|
|
||
|
|
def is_available(graph, vertex, color):
|
||
|
|
adjacents_of_vertex = graph[vertex].adjacents
|
||
|
|
unavailable_colors = list(map(lambda x : graph[x].color, adjacents_of_vertex))
|
||
|
|
print("vertex", vertex)
|
||
|
|
print("color", color)
|
||
|
|
print("UN_COLORS", unavailable_colors)
|
||
|
|
print("==")
|
||
|
|
|
||
|
|
if color in unavailable_colors:
|
||
|
|
return False
|
||
|
|
else:
|
||
|
|
return True
|
||
|
|
|
||
|
|
colors = ['1','2','3','4']
|
||
|
|
|
||
|
|
def graph_add_color(graph, vertex_id, colors):
|
||
|
|
graph_len = len(graph)
|
||
|
|
graph_list = list(graph)
|
||
|
|
for color in colors:
|
||
|
|
if is_available(graph, graph_list[vertex_id], color):
|
||
|
|
graph[graph_list[vertex_id]].color = color
|
||
|
|
if vertex_id < graph_len-1 \
|
||
|
|
and graph_add_color(graph, vertex_id+1, colors):
|
||
|
|
return True
|
||
|
|
else:
|
||
|
|
continue
|
||
|
|
return False
|
||
|
|
|
||
|
|
res = graph_add_color(graph, 0, colors)
|
||
|
|
print(res)
|