Lekcja – Kolorowanie grafu
# graph = [
# [0,1,1,1,1],
# [1,0,1,0,1],
# [1,1,0,1,0],
# [1,0,1,0,1],
# [1,1,0,1,0]
# ]
# graph = [
# [0,1,1,1],
# [1,0,1,1],
# [1,1,0,1],
# [1,1,1,0]
# ]
graph = [
[0,1,1,0,0],
[1,0,1,1,0],
[1,1,0,1,0],
[0,1,1,0,1],
[0,0,0,1,0]
]
graph = [
[0,1,1,0,0],
[1,0,1,0,1],
[1,1,0,0,1],
[0,0,0,0,1],
[0,1,1,1,0]
]
color_names = ['red', 'green', 'blue', 'yellow', 'orange', 'black', 'white', 'gray']
number_of_colors = 3
colors = [None for i in range(len(graph))]
def is_no_conflict(graph, vertex_idx, colors, color):
for i in range(len(graph)):
if graph[vertex_idx][i] == 1 and colors[i] == color:
return False
return True
def try_paint(graph, number_of_colors, colors, vertex_idx):
if vertex_idx == len(graph):
return True
for color in range(number_of_colors):
if is_no_conflict(graph, vertex_idx, colors, color):
colors[vertex_idx] = color
if try_paint(graph, number_of_colors, colors, vertex_idx + 1):
return True
colors[vertex_idx] = None
return False
result = try_paint(graph, number_of_colors, colors, 0)
if result:
print(f"Solution found: {colors}")
print([color_names[i] for i in colors])
else:
print("Solution not found.")
Lab
family = {
'Ann' : ['John', 'Betty', 'Sophie'],
'Oliver' : ['Lucas','Sophie'],
'Sophie' : ['Ann', 'Oliver'],
'John' : ['Ann'],
'Betty' : ['Ann'],
'Lucas' : ['Oliver'],
'Emma' :[],
'Charlotte' : ['James'],
'James': ['Charlotte']
}
family = {
'Ann' : ['John', 'Betty', 'Sophie'],
'Oliver' : ['Lucas','Sophie'],
'Sophie' : ['Ann', 'Oliver'],
'John' : ['Ann', 'Betty'],
'Betty' : ['Ann','John'],
'Lucas' : ['Oliver'],
'Emma' :[],
'Charlotte' : ['James'],
'James': ['Charlotte']
}
number_of_tables = 3
assigments = {name: None for name in family.keys()}
def is_no_conflict(family, person, assigments, proposed_assigment):
for v,e in family.items():
if v in family[person] and proposed_assigment == assigments[v]:
return False
return True
def try_assign_tables(family, number_of_tables, assigments):
# get first unassigned person from the family
person = None
for p in assigments.keys():
if assigments[p] == None:
person = p
break
# if all persons have already table assigment
if person == None:
return True
# try assign to table just one after another
for table_no in range(number_of_tables):
# if there is no conflict with the new assigment
if is_no_conflict(family, person, assigments, table_no):
assigments[person] = table_no
# try to continue with next assigments (keep in mind, we can fail...)
if try_assign_tables(family, number_of_tables, assigments):
return True
# if we failed, the assigment was a bad one and we need to take step back
assigments[person] = None
return False
result = try_assign_tables(family, number_of_tables, assigments)
if result:
print(f"Solution found: {assigments}")
else:
print("Solution not found.")