Classificação topológica

Em teoria de grafos , e mais especificamente em algoritmos de grafos, uma classificação topológica de um gráfico acíclico direcionado (ou dag , do gráfico acíclico direcionado do inglês ) é uma ordem total no conjunto de vértices, em que s precede t para qualquer arco de um vértice s para um vértice t.

Em outras palavras, uma classificação topológica é uma extensão linear da ordem parcial nos vértices determinados pelos arcos.

Deixe ser um gráfico direcionado com e . $G = (S, A)$ ${\ displaystyle S = \ {1,2,3,4,5,6,7,8,9 \}}$ ${\ displaystyle A = \ {(1,2), (1,8), (2,8), (2,3), (3,6), (4,3), (4,5), (5,6), (9,8) \}}$

Uma ordem topológica neste gráfico pode dar, por exemplo, a sucessão dos vértices 7, 1, 2, 9, 8, 4, 3, 5, 6. Na verdade, cada vértice aparece bem antes de seus sucessores. Não há exclusividade no pedido.

Algoritmo

Para um grafo representado na memória de uma forma fácil de navegar, por exemplo por listas de adjacência , o cálculo de uma classificação topológica é simples. É suficiente realizar uma navegação em profundidade no gráfico, durante a qual empilham cada vértice uma vez que seus sucessores tenham sido visitados. Ao desempilhar, obtemos uma classificação topológica.

Sem dedicar um procedimento para este processamento (gráficos grandes), podemos reutilizar uma jornada em profundidade já realizada para determinar diretamente uma ordem topológica. Na verdade, a leitura dos vértices na ordem inversa da numeração pós-fixada da rota em profundidade é uma ordem topológica.

Outra forma de proceder é encontrar uma raiz (vértice sem predecessor), removê-la e repetir a operação quantas vezes forem necessárias. Isso é fácil se pudermos calcular facilmente o número de predecessores de um vértice; na verdade, as raízes de uma iteração estão entre as sucessoras das raízes da iteração anterior, e um contador das predecessoras torna possível reconhecê-las.

O algoritmo de classificação topológica de um gráfico funciona no mesmo princípio que o algoritmo de pesquisa em profundidade , adicionando uma noção de data de início e data de término. A ordem topológica no final será os vértices na ordem da matriz de data de término. Começamos com um determinado vértice, então, enquanto possível, “ descemos ” de nível seguindo os arcos orientados, incrementando a data de início a cada passo, até chegar a um vértice a partir do qual nenhum arco começa. Em seguida, inserimos nossa primeira data de término. Em seguida, " voltamos " pelo pai de onde veio e visitamos outros arcos que ainda não foram processados. E repetimos a operação.

Para determinar se um cume foi visto ou não, usando um esquema de cores: branco para " Não processado ", cinza para " Em tratamento " e preto para " Tratado ".

"Não processado " corresponde aos vértices que não têm data de início nem data de término.
"Em processamento" corresponde aos vértices que possuem apenas uma data de início e ainda não uma data de término.
"Tratado" corresponde aos vértices que possuem ambos.

Por exemplo, com o gráfico acima (escrevemos o par startDate / EndDate da seguinte forma: (startDate, endDate)):

Começamos com o vértice 1, então temos para este ponto a data de início: (1,), a data de término ainda não é conhecida. Temos então a escolha de continuar em direção a 2 ou em direção a 8. Suponha que vamos para 2. Teremos então para 2 (2,), então em 3 com (3,) e finalmente em 6 com (4,).
Aqui, 6 é um vértice do qual nenhum arco começa. Portanto, é impossível descer mais. Portanto, marcamos nossa primeira data de término em 6: (4, 5). Então nós "subimos" através do pai de onde viemos, isto é, 3.
Como não há outro arco começando no vértice 3, marcamos nossa segunda data de término para 3: (3, 6) então “voltamos” novamente pelo pai de onde viemos, c 'isto é, 2.
Do cume 2, continue seguindo o arco que ainda não foi visitado (em direção ao 8), do qual é impossível descer mais. Então, temos para 8: (7, 8), então voltamos para os 2 primeiros.
Desta vez, todos os arcos a partir do vértice 2 foram processados, então marcamos a data final para 2: (2, 9) e voltamos ao vértice 1, que está na mesma situação, então 1: (1, 10 )
Em seguida, repetimos essas operações começando com um vértice que ainda não foi visitado, por exemplo 4: (11,) do qual podemos descer para 5: (12,), mas não mais porque 6 já foi visitado. Então temos para 5: (12, 13), depois voltar para 4: (11, 14) porque todos os seus vizinhos foram visitados.
Começamos novamente com 7: (15, 16) e 9: (17, 18), que não têm vizinhos não tratados.
Por fim, classificamos os vértices diminuindo a data de término para obter a seguinte ordem: 9, 7, 4, 5, 1, 2, 8, 3, 6.

Existem várias rotas topológicas para um gráfico, bem como para uma rota de profundidade, que variam de acordo com a direção tomada. No algoritmo a seguir, tratamos os vértices na ordem da lista de filhos de um vértice, ou seja, sempre começando com o elemento à esquerda, mas isso não é obrigatório.

Pseudo-código

Ele se divide em 2 funções:

Algorithme tri_topo (Graphe g) Entrée : Un graphe G =(V,E) orienté non cyclique. Sortie : La liste des sommets dans l'ordre topologique. Variables : listeSommets = [] t = 0 //C'est la variable qui établira les dates d'entrées et sorties. tabCouleur = [] //Le tableau qui indiquera la couleur et donc le traitement d'un sommet. Exécution : Pour i allant de 1 à nbSommets : ajouter(tabCouleur, 0) //On initialise tous les sommets à blancs, soit non traité. Fin Pour; Pour chaque x appartenant à V Faire : Si couleur(x) = Blanc alors : Parcours_Profondeur_Topo(G, listeSommets, x, t) Fin Pour; Afficher(listeSommets) et/ou Retourner(listeSommets) Fin Exécution;

O algoritmo Topo_Depth_Path_Topo (G, verticeslist, x, t):

Algorithme Parcours_Profondeur_Topo(G, listeSommets, x, t) Entrée : Un graphe G =(V,E) orienté non cyclique. La liste des sommets. Le sommet en traitement. La date. Sortie : Les sommets empilés dans l'ordre topologique dans listeSommets. Exécution : couleur(x) = Gris t = t + 1 dateDébut(x) = t Pour chaque y appartenant à Γ+ (x) Faire : //Γ+ (x) est l'ensemble des voisins de x. Si couleur(y) == Blanc alors : Parcours_Profondeur_Topo(G, listeSommets, y, t) Fin Si; Fin Pour; couleur(x) = Noir t = t + 1 dateFin(x) = t //Les dates ne sont pas nécessaires à l'algorithme mais pourraient être utilisées à d'autre fins. empiler(x, listeSommets) Fin Exécution;

Exemplo de código em Python

No código ao lado, as datas de início e término (correspondendo a t acima) não foram implementadas:

O código escrito aqui está em Python, mas usa funções SageMath que permitem modelar gráficos e métodos neles.

Aqui: G.vertices () retorna a lista de vértices do Gráfico G.

e G.neighbours (x) retorna a lista de vértices adjacentes a x.

O Sage também contém outros métodos que podem ser úteis dependendo se o gráfico é orientado ou não, como is_eulerian que determina se um gráfico é euleriano ou não.

Ou is_connected que retorna se um gráfico está conectado ou não.

Exemplo de uso

O software Make .
A ordenação topológica é um pré-processamento que torna possível calcular as distâncias dos caminhos mais curtos em um gráfico linear acíclico ponderado no tempo no tamanho do gráfico.

Link externo

"Ordenação sequencial: ordenação topológica" (versão de 3 de março de 2016 no Internet Archive )