Ordenação Topológica

Ordenação topológica é uma das principais aplicações de busca em profundidade, portanto merece nossa atenção. Primeiro, explicaremos (por meio de exemplos) o que é o problema de ordenação topológica. Depois, definiremos mais formalmente o problema, e por fim mostraremos dois algoritmos para resolvê-lo.

O professor Donald Knuth apresenta um exemplo interessante de ordenação topológica. Nesse exemplo, imagine um grande glossário contendo definições de termos técnicos. O problema de ordenação topológica neste caso é encontrar uma forma de organizar as palavras no glossário de modo que nenhum termo seja usado antes de ser definido.

Pelo exemplo acima, vemos que ordenação topológica está relacionada com dependências entre entidades que desejamos representar: termos do glossário dependem de outros termos que tenham sido definidos anteriormente.

Seguindo essa mesma ideia de dependência, vejamos outro exemplo. Suponha que lhe seja fornecida uma lista de tarefas, na qual cada tarefa possui uma lista de outras tarefas que devem ser completadas antes dela. Seu objetivo é criar uma lista na qual as tarefas devem ser executadas obdecendo as dependências entre tarefas. Esse problema pode ser modelado como um grafo cujos vértices são as tarefas e cujas arestas são dependências entre tarefas. A solução do problema é a ordenação topológica do grafo.

Em outras palavras, a ordenação topológica é uma forma de listar os vértices de um grafo de modo que para cada aresta $(u, v)$ (ou seja, saindo de $u$ e chegando em $v$) do grafo, $u$ aparece antes de $v$ na lista. Um requisito básico da ordenação topológica é que o grafo não pode ter ciclos (uma tarefa A que depende de B que depende de A, por exemplo).

Ainda outro exemplo de ordenação topológica, encontrado no livro "Introduction to Algorithms", escrito por Cormem e outros, é o de como se vestir. Segundo esse exemplo, para nos vestirmos (corretamente) é preciso obedecer uma ordem entre peças de vestuário. Por exemplo, precisamos colocar as meias antes de colocar os sapatos, precisamos colocar a roupa de baixo (cueca ou calcinha) antes de vestir as calças, e assim por diante. Esse problema pode ser modelado como o problema de se encontrar a ordenação topológica do grafo cujos vértices são peças do vestuário e cujas arestas são dependências entre essas peças.

Analisando o exemplo anterior, é possível concluir que o Super-Homem não sabe fazer ordenação topológica, dado que ele veste a cueca por cima da calça!

Piadas à parte, vamos agora definir o problema mais precisamente e analisar o funcionamento de dois algoritmos de ordenação topológica.

O problema de ordenação topológica pode ser definido assim:

Definição: Dado um grafo acíclico direcionado $G(V, E)$ com $n$ vértices, atribua números de $0$ a $n - 1$ aos vértices de modo que, se $v$ receber o número $k$ então todos os vértices que podem ser alcançados a partir de $v$ recebem números maiores que $k$.

Implementação Baseada em Busca em Profundidade

Para os algoritmos abaixo, por questões de simplicidade, usaremos a representação do grafo como lista de listas (representação implícita), como mostrado abaixo:

grafo = [ [1],           # Vizinhos do vértice 0.
          [2, 3],        # Vizinhos do vértice 1.
          [1, 4],        # Vizinhos do vértice 2.
          [0],           # Vizinhos do vértice 3.
          [1]            # Vizinhos do vértice 4.
        ]

O algoritmo de ordenação topológica consiste de três passos principais:

Execute o algoritmo de busca em profundidade no grafo e mantenha registro dos tempos em que cada vértice terminou de ser processado.
No momento em que um vértice termina de ser processado (todos seus vizinhos já foram visitados), insira esse vértice no final de uma lista.
Retorne a lista em ordem reversa.

def ordenacao_topologica(grafo):
    """
    DFS modificada para retornar a ordenação topológica do grafo.
    Isso é feito por meio da lista com os tempos de término do processamento
    de cada vértice, que será a ordenação topológica reversa do grafo.
    """
    def dfs_recursiva(grafo, vertice):
        visitados.add(vertice)
        for vizinho in grafo[vertice]:
            if vizinho not in visitados:
                dfs_recursiva(grafo, vizinho)
        tempo += 1
        ordem_topologica[vertice] = tempo

    visitados = set()
    ordem_topologica = [0] * len(grafo)
    tempo = 0
    for vertice in grafo:
        if not vertice in visitados:
            dfs_recursiva(grafo, vertice)
    ordem_topologica.reverse()
    return ordem_topologica

# Ordenação topológica.
ordem = ordenacao_topologica(grafo)

Note que na definição do problema dissemos que cada vértice recebe um número de $0$ a $n - 1$, mas em nossa implementação retornamos uma lista com os identificadores dos vértices. Isso é mais conveniente em termos de implementação e uso da lista retornada. Entretanto, podemos pensar nos números de $0$ a $n - 1$ mencionados na definição como sendo os índices da lista retornada.

Implementação Baseada no Grau dos Vértices

Existe ainda um outro algoritmo de ordenação topológica cuja ideia central é remover do grafo vértices com grau de entrada igual a zero. Esse algoritmo é bastante elegante e nos ensina a raciocinar de forma indutiva a respeito do grafo. Vejamos como ele funciona.

A ideia deste algoritmo é a seguinte:

Encontre um vértice com grau de entrada zero.
Atribua a esse vértice o menor número disponível (ou coloque-o ao final de uma lista, como iremos fazer) ainda não utilizado.
Remova o vértice do grafo e atualize o grau de entrada de todos os vizinhos do vértice removido.
Repita os passos acima até que todos os vértices do grafo tenham sido numerados (colocados na lista).

Os maiores desafios do algoritmo acima são os passos 1 e 3. Antes de partirmos para a implementação do algoritmo, é importante discutir esses desafios.

A primeira pergunta interessante com relação ao passo 1 é a seguinte: É sempre possível encontrar um vértice com grau de entrada zero?

Um outro jeito de responder a pergunta anterior é dizer que todo grafo acíclico direcionado (DAG) tem um vértice de origem (um vértice com grau de entrada zero). O raciocínio por trás dessa afirmação é que, dado um vértice qualquer, se você seguir cada aresta de entrada dele em ordem reversa, você eventualmente alcançará o vértice de origem. Caso contrário, você voltaria ao vértice do qual você partiu, ou seja, você encontraria um ciclo no grafo, o que é impossível, dado que o grafo é um DAG.

A segunda pergunta interessante é: Como calcular o grau de entrada dos vértices? Para fazer isso, podemos percorrer cada vértice do grafo (de forma parecida com uma busca em profundidade ou com uma busca em largura) e atualizar o grau de entrada dos vizinhos do vértice em questão. Por exemplo, podemos fazer isso como mostrado abaixo:

    graus_entrada = [0 for _ in range(len(grafo))]
    for vertice in grafo:
        for vizinho in grafo[vertice]:
            graus_entrada[vizinho] += 1

Existem também alguns aspectos interessantes com relação ao passo 3. Esse passo nos pede para remover o vértice do grafo e atualizar o grau de entrada dos vizinhos desse vértice. Como acontece com frequência ao implementarmos algoritmos, por questões de eficiência, não nos preocuparemos em reproduzir exatamente o que foi dito nesse passo, mas encontraremos uma forma alternativa de implementar a ideia que ele transmite.

Essa forma alternativa é a seguinte. Manteremos uma fila de vértices com grau de entrada igual a zero. Com isso, em vez de removermos o vértice do grafo, simplesmente o removeremos dessa fila e, ao fazer isso, atualizaremos o grau de entrada de seus vizinhos (basta decrementar de uma unidade o grau de entrada de todos os vizinhos do vértice). O algoritmo executará enquanto houver vértices nessa fila (o passo 4 muda um pouco também).

Com essas discussões, podemos refinar um pouco a ideia do algoritmo:

Calcule o grau de entrada de todos os vértices do grafo e armazene esses graus de entrada em uma lista.
Percorra a lista e insira em uma fila todos os vértices com grau de entrada igual a zero (conforme vimos, haverá pelos menos um vértice com essa propriedade).
Remova o primeiro vértice da fila, insira-o em uma lista que armazena a ordem topológica do grafo e atualize o grau de entrada de seus vizinhos. Se nesse momento o grau de entrada de algum dos vizinhos do vértice em questão se tornar zero, insira esse vizinho na fila.
Repita os passos acima enquanto houver vértices na fila.

Agora estamos prontos para implementar o algoritmo.

def ordenacao_topologica(grafo):
    """
    Ordenação topológica baseada no grau de entrada dos vértices.
    """
    ordem_topologica = []
    # Calcula graus de entrada.
    graus_entrada = [0 for _ in range(len(grafo))]
    for vertice in grafo:
        for vizinho in grafo[vertice]:
            graus_entrada[vizinho] += 1
    # Cria uma fila de vértices com grau de entrada zero.
    fila = [v for v in range(len(grafo)) if graus_entrada[v] == 0]
    while fila:
        vertice = fila.pop()
        ordem_topologica.append(vertice)
        # Atualiza o grau de entrada dos vizinhos.
        for vizinho in grafo[vertice]:
            graus_entrada[vizinho] -= 1
            # Algum dos vizinhos passou a ter grau de entrada zero.
            if graus_entrada[vizinho] == 0:
                fila.append(vizinho)
    return ordem_topologica

Exercícios

Escreva uma função que verifica se uma ordenação topológica é válida.

Clique para ver a solução

Incluímos abaixo uma sugestão de solução. Nela, fazemos algumas verificações de consistência: vemos se algum vértice está na ordenação topológica mas não no grafo e vice-versa. Depois, verificamos a ordem dos vértices propriamente dita.

def verifica_ordenacao_topologica(grafo, ordem_topologica):
    """
    Verifica se uma ordenação topológica é válida.
    """
    vnum = {}
    for i in range(len(ordem_topologica)):
        if ordem_topologica[i] not in grafo:
            return False
        vnum[ordem_topologica[i]] = i

    for v in grafo:
        if v not in vnum:
            return False
        for w in grafo[v]:
            if w not in vnum or vnum[w] <= vnum[v]:
                return False
    return True

Playground


			
				# Use este espaço para praticar o que você aprendeu nesta seção.
				
				# Basta digitar o código no espaço abaixo e clicar 'run'.