Lekcja – Drzewa
mission_control = {
'FC' : ['Engine','Weather','Crew'],
'Engine': ['Engine Temp','Fuel'],
'Engine Temp': [],
'Fuel' : [],
'Weather' : ['Wind', 'Air Temp', 'Clouds'],
'Wind' : [],
'Air Temp' : [],
'Clouds':[],
'Crew': ['Health','Communication'],
'Communication': [],
'Health': []
}
status = {
'Engine Temp': True,
'Fuel': True,
'Wind': True,
'Air Temp': True,
'Clouds': True,
'Communication': True,
'Health': True
}
def can_start(graph, status, start_node):
if graph[start_node]:
for node in graph[start_node]:
if not can_start(graph, status, node):
print(f'{start_node} - False')
return False
print(f'{start_node} - True')
return True
else:
print(f'{start_node} {status[start_node]}')
return status[start_node]
print(f'Can we start? {can_start(mission_control, status, "FC")}')
Lab
names = ['1 CEO', '2 Cognitive', '2 Systems', '2 Operations','3 Healthcare',
'3 Cloud', '3 Research', '3Security', '3 Storage']
structure1 = [
[0,1,1,1,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]
structure2 = [
[0,1,1,1,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,1,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]
structure3 = [
[0,1,1,0,0,0,0,0,0],
[0,0,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]
# only one starting node
def get_root(structure):
the_root = None
#review all columns
for c in range(len(structure)):
#chek how many parents the node has
number_of_parents = 0
for r in range(len(structure)):
number_of_parents += structure[r][c]
#if the node hasn't parents, it is the root
if number_of_parents == 0:
the_root = c
break
#return found root or none
return the_root
def is_tree(structure):
# get the root, if there is no root, it is not a tree
the_root = get_root(structure)
if the_root == None:
return False
#visit all nodes, each node should be visited exactly one time
list_visited = []
list_to_visit = [the_root]
while list_to_visit:
current = list_to_visit.pop(0)
#if the node was already visited it is not a tree
if current in list_visited:
return False
list_visited.append(current)
#add neighbours of current node
for x in range(len(structure)):
if structure[current][x] == 1:
list_to_visit.append(x)
#if we visited all nodes it is a tree
return len(list_visited) == len(structure)
print('Structure 1:', is_tree(structure1))
print('Structure 2:', is_tree(structure2))
print('Structure 3:', is_tree(structure3))