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)}')