Classificando arestas da arvore de busca em profundidade feita em um digrafo com Python

classificacao_arestas_profundidade_digrafo.py

# 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 = []

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):
    # 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))

    # 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
        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))

# funcao recursiva
def call_to_busca_em_profundidade(digrafo, vertice_do_digrafo, nivel):
    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 um 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
        # (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)))
        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) # o proximo vertice estarah um nivel abaixo desse na arvore de busca em profundidade
        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')
            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')
                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')

    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)





digrafo = {
    'a': ['c', 'd', 'f'],
    'b': ['a'],
    'c': ['b'],
    'd': ['e', 'f'],
    'e': [],
    'f': ['e']
}

busca_em_profundidade(digrafo, 'a')