Lekcja – Graf cykliczny
actions1 = {
'F1' : ['F2', 'F3'],
'F2' : ['F4'],
'F3' : ['F4'],
'F4' : []
}
actions2 = {
'F1' : ['F2', 'F3'],
'F2' : [],
'F3' : ['F4'],
'F4' : ['F1']
}
def get_path_between(V, source, dest):
list_to_check = [[source]]
list_visited = []
while list_to_check:
current_path = list_to_check.pop(0)
current_node = current_path[-1]
if current_node == dest:
return current_path
else:
if current_node not in list_visited:
list_visited.append(current_node)
for n in V[current_node]:
new_path = current_path.copy()
new_path.append(n)
list_to_check.append(new_path)
return []
def get_cycle(graph, node):
for neighbour in graph[node]:
path = get_path_between(graph, neighbour, node)
if path:
return path
return []
def is_cyclic(graph):
for node in graph:
if get_cycle(graph, node):
return True
return False
start = 'F1'
print(f'Path from {start} to {start} is {get_cycle(actions1, start)}')
print(f'Path from {start} to {start} is {get_cycle(actions2, start)}')
print(f'Graph 1 is cyclic: {is_cyclic(actions1)}')
print(f'Graph 2 is cyclic: {is_cyclic(actions2)}')
Lab
why_not = {
'no time' : ['classify priorities'],
'classify priorities' : [],
'no training' : ['attend training'],
'attend training': ['no time', 'no money motivation'],
'no expirience' : ['work on a project'],
'work on a project' : ['no time', 'no training', 'no expirience'],
'no money motivation' : ['work on a project']
}
def get_path_between(V, source, dest):
list_to_check = [[source]]
list_visited = []
while list_to_check:
current_path = list_to_check.pop(0)
current_node = current_path[-1]
if current_node == dest:
return current_path
else:
if current_node not in list_visited:
list_visited.append(current_node)
for n in V[current_node]:
new_path = current_path.copy()
new_path.append(n)
list_to_check.append(new_path)
return []
def get_cycle(graph, node):
for neighbour in graph[node]:
path = get_path_between(graph, neighbour, node)
if path:
return path
return []
def is_cyclic(graph):
for node in graph:
if get_cycle(graph, node):
return True
return False
for statement in why_not.keys():
print(f'Path from {statement} to {statement} is {get_cycle(why_not, statement)}')
print(f'The graph is cyclic: {is_cyclic(why_not)}')