Encontra e salva os ciclos de um digrafo usando uma busca em profundidade (complexidade nao piora, continua O(n+m))

encontrar_ciclos_digrafo.py

from copy import deepcopy

# coisos globais
valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
profundidades_entrada_saida = {}
pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
niveis = {} # nivel de cada vertice na arvore de busca em profundidade
# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
nao_visitados = set()
# lista de arvores (floresta) da busca em profundidade
floresta = []
lista_de_vertices = []
lista_de_arestas = []
# lista de ciclos do digrafo
ciclos = []

def cria_grafo(lista_de_vertices, lista_de_arestas):
    grafo = {}
    for vertice in lista_de_vertices:
        grafo[vertice] = []
    for aresta in lista_de_arestas:
        grafo[aresta[0]].append(aresta[1])
    return grafo

# funcao de chamada
def busca_em_profundidade(digrafo, vertice_do_digrafo):
    limpar_globais() # garantindo que para cada chamada dessa funcao, as variaveis globais vao estar limpinhas
    caminho = {} # vamos guardar o caminho percorrido para salva-lo como ciclo nos devidos casos
    # marcando todos como nao_visitados
    for vertice in digrafo:
        nao_visitados.add(vertice)

    pai[vertice_do_digrafo] = None # a raiz naum tem pai
    lista_de_vertices[:] = [vertice_do_digrafo]
    lista_de_arestas[:] = []
    floresta.append(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1, caminho))

    # para garantir que todos os vertices serao visitados, precisamos recomecar a busca de vertices que nunca entraram na pilha (caso ainda existam)
    while len(nao_visitados): # enquanto naum terminar de visitar todos os vertices precisamos repetir o processo...
        vertice_do_digrafo = nao_visitados.pop() # (**) ... com uma nova raiz que seja um vertice ainda nao visitado
        caminho.clear() # limpando o caminho antigo! vamos comecar um novo!
        pai[vertice_do_digrafo] = None
        lista_de_vertices[:] = [vertice_do_digrafo]
        lista_de_arestas[:] = []
        floresta.append(call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, 1, caminho))

# funcao recursiva
def call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, nivel, caminho):
    global valor_profundidade_entrada, valor_profundidade_saida
    valor_profundidade_entrada += 1 # atualizando o contador de profundidade de entrada
    profundidades_entrada_saida[vertice_do_digrafo] = [valor_profundidade_entrada, None] # anotando profundidade de entrada de vertice_do_digrafo
    niveis[vertice_do_digrafo] = nivel # anotando o nivel desse vertice_do_digrafo na arvore de busca em profundidade

    # como eh certo de que um vertice_do_digrafo que entra na pilha uma hora sairah dela, podemos jah marcar esse vertice_do_digrafo como visitado retirando do conjunto de nao_visitados
    nao_visitados.discard(vertice_do_digrafo) # usando o metodo discard para evitar problemas caso o pop jah tenha tirado o vertice_do_digrafo do conjunto a fim de selecionar uma nova raiz em (**)

    for vizinho in digrafo.get(vertice_do_digrafo): # percorrendo os vizinhos de vertice_do_digrafo
        caminho[vertice_do_digrafo] = vizinho # adiciona a aresta ao caminho! (SUJOU)
        # (descomente os codigos abaixo para ver a ordem em que as arestas sao visitadas e suas respectivas classificacoes)
        print('%s -> %s:' % (str(vertice_do_digrafo), str(vizinho)))
        # print('caminho: ' + str(caminho))
        if not profundidades_entrada_saida.get(vizinho): # testa se esse vizinho jah foi empilhado (chamado pela recursao)
            # se ainda naum foi empilhado, eh hora de...
            pai[vizinho] = vertice_do_digrafo # ... atualizar quem eh o pai dele na arvore de busca em profundidade e...
            lista_de_vertices.append(vizinho) # ... colocar o vizinho na lista de vertices dessa arvore
            # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE ARVORE
            aresta[(vertice_do_digrafo, vizinho)] = 'aresta de arvore'
            lista_de_arestas.append((vertice_do_digrafo, vizinho))
            print('aresta de arvore')
            # chamada de recursao escolhendo agora esse vizinho como raiz:
            call_to_busca_em_profundidade(digrafo, vizinho, nivel + 1, caminho) # o proximo vertice estarah um nivel abaixo desse na arvore de busca em profundidade
            del caminho[vertice_do_digrafo] # LIMPOU
        else: # caso o vizinho jah esteja na pilha (jah houve uma chamada de call_to_busca_em_profundidade com parametro vertice_do_digrafo=vizinho)
            # testa se esse vizinho jah foi desempilhado (terminou sua chamada de call_to_busca_em_profundidade)
            if not profundidades_entrada_saida[vizinho][1]:
                # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE RETORNO
                aresta[(vertice_do_digrafo, vizinho)] = 'aresta de retorno'
                lista_de_arestas.append((vertice_do_digrafo, vizinho))
                print('aresta de retorno')
                # ACHEI UM CICLO!
                salva_ciclo(caminho, vizinho) # guardo o caminho na lista de ciclos!
            else: # vizinho jah foi desempilhado
                if profundidades_entrada_saida[vertice_do_digrafo][0] < profundidades_entrada_saida[vizinho][0]: # testa quem foi empilhado primeiro
                    # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE AVANCO
                    aresta[(vertice_do_digrafo, vizinho)] = 'aresta de avanco'
                    lista_de_arestas.append((vertice_do_digrafo, vizinho))
                    print('aresta de avanco')
                    # POSSO TER ACHADO OUTRO CICLO!
                    testa_possivel_ciclo_de_avanco(vertice_do_digrafo, vizinho)
                else: # vizinho foi empilhado e desempilhado antes de vertice_do_digrafo ser empilhado
                    # MOMENTO PARA VISITAR vertice_do_digrafo -> vizinho COMO ARESTA DE CRUZAMENTO
                    aresta[(vertice_do_digrafo, vizinho)] = 'aresta de cruzamento'
                    print('aresta de cruzamento')
                    # POSSO TER ACHADO OUTRO CICLO!
                    testa_possivel_ciclo_de_cruzamento(caminho, vertice_do_digrafo, vizinho)
            del caminho[vertice_do_digrafo] # LIMPOU

    valor_profundidade_saida += 1 # atualizando o contador de profundidade de saida
    profundidades_entrada_saida[vertice_do_digrafo][1] = valor_profundidade_saida

    return cria_grafo(lista_de_vertices, lista_de_arestas)

def salva_ciclo(caminho, vertice_inicial):
    novo_ciclo = caminho.copy()
    proximo_vertice_fora_do_ciclo = None
    vertice_fora_do_ciclo = pai[vertice_inicial]
    while vertice_fora_do_ciclo:
        # print('O vertice %s estah fora do novo ciclo' % str(vertice_fora_do_ciclo))
        # print novo_ciclo
        proximo_vertice_fora_do_ciclo = pai[vertice_fora_do_ciclo]
        del novo_ciclo[vertice_fora_do_ciclo]
        # print('O vertice %s foi removido do ciclo' % str(vertice_fora_do_ciclo))
        # print novo_ciclo
        vertice_fora_do_ciclo = proximo_vertice_fora_do_ciclo
    print('Achei esse ciclo quando detectei uma aresta de retorno: ' + str(novo_ciclo))
    # print('ciclos antes: ' + str(ciclos))
    ciclos.append(novo_ciclo)
    # print('ciclos depois: ' + str(ciclos))

def testa_possivel_ciclo_de_avanco(vertice_avancando, vertice_atingido):
    ciclos_antigos = deepcopy(ciclos)
    for ciclo in ciclos_antigos:
        if (ciclo.get(vertice_atingido) is not None) and (ciclo.get(vertice_avancando) is not None):
            proximo_vertice_fora_do_ciclo = None
            vertice_fora_do_ciclo = ciclo[vertice_avancando]
            ciclo[vertice_avancando] = vertice_atingido
            while vertice_fora_do_ciclo != vertice_atingido:
                proximo_vertice_fora_do_ciclo = ciclo[vertice_fora_do_ciclo]
                del ciclo[vertice_fora_do_ciclo]
                vertice_fora_do_ciclo = proximo_vertice_fora_do_ciclo
            print('Achei esse ciclo quando detectei uma aresta de avanco: ' + str(ciclo))
            # print('ciclos antes: ' + str(ciclos))
            ciclos.append(ciclo)
            # print('ciclos depois: ' + str(ciclos))

def testa_possivel_ciclo_de_cruzamento(caminho, vertice_cruzando, vertice_atingido):
    ciclos_antigos = deepcopy(ciclos)
    for ciclo in ciclos_antigos:
        if ciclo.get(vertice_atingido):
            vertice_no_caminho = pai[vertice_cruzando]
            while vertice_no_caminho not in ciclo.keys() and vertice_no_caminho is not None:
                vertice_no_caminho = pai[vertice_no_caminho]
            if vertice_no_caminho:
                parte_do_novo_ciclo = caminho.copy()
                proximo_vertice_fora_do_ciclo = None
                vertice_fora_do_ciclo = ciclo[vertice_no_caminho]
                ciclo[vertice_no_caminho] = parte_do_novo_ciclo[vertice_no_caminho]
                while vertice_fora_do_ciclo != vertice_atingido:
                    proximo_vertice_fora_do_ciclo = ciclo[vertice_fora_do_ciclo]
                    del ciclo[vertice_fora_do_ciclo]
                    vertice_fora_do_ciclo = proximo_vertice_fora_do_ciclo
                novo_vertice_do_ciclo = ciclo[vertice_no_caminho]
                while novo_vertice_do_ciclo != vertice_atingido:
                    ciclo[novo_vertice_do_ciclo] = parte_do_novo_ciclo[novo_vertice_do_ciclo]
                    novo_vertice_do_ciclo = parte_do_novo_ciclo[novo_vertice_do_ciclo]
                print('Achei esse ciclo quando detectei uma aresta de cruzamento: ' + str(ciclo))
                # print('ciclos antes: ' + str(ciclos))
                ciclos.append(ciclo)
                # print('ciclos depois: ' + str(ciclos))

def limpar_globais():
    global valor_profundidade_entrada, valor_profundidade_saida
    valor_profundidade_entrada = 0
    valor_profundidade_saida = 0
    profundidades_entrada_saida.clear()
    pai.clear()
    aresta.clear()
    niveis.clear()
    nao_visitados.clear()
    floresta[:] = []
    lista_de_vertices[:] = []
    lista_de_arestas[:] = []
    ciclos[:] = []

def encontra_ciclos(digrafo, vertice_inicial):
    busca_em_profundidade(digrafo, vertice_inicial)
    if len(ciclos) > 0:
        print('O digrafo tem %d ciclos, sao eles:' % len(ciclos))
        print ciclos
    else:
        print('O digrafo nao tem ciclos')






digrafo = {
    1: [2],
    2: [3, 15],
    3: [4, 9],
    4: [5, 7],
    5: [2, 6],
    6: [],
    7: [8],
    8: [6],
    9: [10, 11],
    10: [3],
    11: [12, 13],
    12: [10],
    13: [14],
    14: [12],
    15: [16],
    16: [17,18],
    17: [9],
    18: [],
}
encontra_ciclos(digrafo, 1)