Classificação topológica: exemplo de algoritmo Python, C++

O que é algoritmo de classificação topológica?

A classificação topológica também é conhecida como algoritmo de Kahn e é um algoritmo de classificação popular. Usando um gráfico direcionado como entrada, a classificação topológica classifica os nós para que cada um apareça antes daquele para o qual aponta.

Este algoritmo é aplicado em um DAG (Gráfico Acíclico Direcionado) para que cada nó apareça na matriz ordenada antes que todos os outros nós sejam apontados para ele. Este algoritmo segue algumas regras repetidamente até que a classificação seja concluída.

Para simplificar, veja o seguintewing exemplo:

Gráfico direcionado
Gráfico direcionado

Aqui, podemos ver que “A” não tem grau. Significa a aresta que aponta para um nó. “B” e “C” possuem um pré-requisito de “A”, então “E” possui um pré-requisito de nós “D” e “F”. Alguns dos nós dependem de outros nós.

Aqui está outra representação do gráfico acima:

Dependência de cada nó

Dependência de cada nó (ordenação linear)

Assim, ao passarmos o DAG (Directed Acíclico Graph) para a ordenação topológica, ele nos dará um array com ordenação linear, onde o primeiro elemento não possui dependência.

Algoritmo de classificação topológica

Este exemplo mostra um gráfico com um ciclo:

Aqui estão as etapas para fazer isso:

Passo 1) Encontre o nó com zero arestas de entrada, um nó com zero graus.

Passo 2) Armazena que zera o nó de grau em uma fila ou pilha e remove o nó do gráfico.

Passo 3) Em seguida, exclua a borda de saída desse nó.

Isso diminuirá a contagem de graus para o próximo nó.

A ordenação topológica exige que a estrutura de dados do gráfico não tenha nenhum ciclo.

Um gráfico será considerado um DAG se atender a estes requisitos:

  • Um ou mais nós com valor de indegree igual a zero.
  • O gráfico não contém nenhum ciclo

Contanto que haja nós no gráfico e o gráfico ainda seja DAG, executaremos as três etapas acima. Outrowise, o algoritmo cairá na dependência cíclica e o algoritmo de Kahn não será capaz de encontrar um nó com grau zero.

Como funciona a classificação topológica

Aqui, usaremos o “Algoritmo de Kahn” para a ordenação topológica. Digamos que temos o seguintewing Gráfico:

A classificação topológica funciona

Aqui estão as etapas para o algoritmo de Kahn:

Passo 1) Calcule o grau de entrada ou borda de entrada de todos os nós no gráfico.

Nota:

  • Indegree significa as arestas direcionadas apontando para o nó.
  • Outdegree significa as arestas direcionadas que vêm de um nó.

Aqui está o grau de entrada e saída do gráfico acima:

A classificação topológica funciona

Passo 2) Encontre o nó com zero graus de entrada ou zero arestas de entrada.

O nó com grau zero significa que nenhuma aresta está vindo em direção a esse nó. O nó “A” tem zero graus, o que significa que não há aresta apontando para o nó “A”.

Então, faremos o seguintewing ações:

  • Remova este nó e suas arestas de saída (arestas de saída)
  • Coloque o nó na fila para pedido.
  • Atualize a contagem em graus do nó vizinho de “A”.

A classificação topológica funciona

Passo 3) Precisamos encontrar um nó com valor de indegree igual a zero. Neste exemplo, “B” e “C” têm grau zero.

Aqui, podemos pegar qualquer um desses dois. Vamos pegar “B” e excluí-lo do gráfico.

Em seguida, atualize os valores de grau de outros nós.

Depois de realizar essas operações, nosso gráfico e fila ficarão parecidos com o seguintewing:

A classificação topológica funciona

Passo 4) O nó “C” não possui borda de entrada. Então, vamos remover o nó “C” do gráfico e colocá-lo na fila.

Também podemos deletar a aresta que sai de “C”.

Agora, nosso gráfico ficará assim:

A classificação topológica funciona

Passo 5) Podemos ver que os nós “D” e “F” têm grau de entrada zero. Pegaremos um nó e o colocaremos na fila.

Vamos retirar “D” primeiro. Então a contagem de graus para o nó “E” será 1. Agora, não haverá nenhum nó de D a E.

Precisamos fazer o mesmo para o nó “F”, nosso resultado será como o seguintewing:

A classificação topológica funciona

Passo 6) O grau de entrada (bordas de entrada) e o grau de saída (bordas de saída) do nó “E” tornaram-se zero. Portanto, atendemos todos os pré-requisitos para o nó “E”.

Aqui, colocamos “E” no final da fila. Portanto, não temos mais nós, então o algoritmo termina aqui.

A classificação topológica funciona

Pseudocódigo para classificação topológica

Aqui está o pseudocódigo para a classificação topológica ao usar o algoritmo de Kahn.

function TopologicalSort( Graph G ):
  for each node in G:
    calculate the indegree
  start = Node with 0 indegree
  G.remove(start)
  topological_list = [start]
  While node with O indegree present:
    topological_list.append(node)
    G.remove(node)
    Update Indegree of present nodes
  Return topological_list

A classificação topológica também pode ser implementada usando o DFS (Profundidade primeira pesquisa) método. No entanto, essa abordagem é o método recursivo. O algoritmo de Kahn é mais eficiente que a abordagem DFS.

Implementação C++ de classificação topológica

#include<bits/stdc++.h>
using namespace std;
class graph{
  int vertices;
  list<int> *adjecentList;
public:
  graph(int vertices){
    this->vertices = vertices;
    adjecentList = new list<int>[vertices];
  }
  void createEdge(int u, int v){
    adjecentList[u].push_back(v);
  }
  void TopologicalSort(){
    // filling the vector with zero initially
    vector<int> indegree_count(vertices,0);

    for(int i=0;i<vertices;i++){
      list<int>::iterator itr;
      for(itr=adjecentList[i].begin(); itr!=adjecentList[i].end();itr++){
        indegree_count[*itr]++;
      }
    }
    queue<int> Q;
    for(int i=0; i<vertices;i++){
      if(indegree_count[i]==0){
        Q.push(i);
      }
    }
    int visited_node = 0;
    vector<int> order;
    while(!Q.empty()){
      int u = Q.front();
      Q.pop();
      order.push_back(u);

      list<int>::iterator itr;
      for(itr=adjecentList[u].begin(); itr!=adjecentList[u].end();itr++){
        if(--indegree_count[*itr]==0){
          Q.push(*itr);
        }
      }
      visited_node++;
    }
    if(visited_node!=vertices){
      cout<<"There's a cycle present in the Graph.\nGiven graph is not DAG"<<endl;
      return;
    }
    for(int i=0; i<order.size();i++){
      cout<<order[i]<<"\t";
    }
  }
};
int main(){
  graph G(6);
  G.createEdge(0,1);
  G.createEdge(0,2);
  G.createEdge(1,3);
  G.createEdge(1,5);
  G.createEdge(2,3);
  G.createEdge(2,5);
  G.createEdge(3,4);
  G.createEdge(5,4);
  G.TopologicalSort();
}

saída

0       1       2       3       5       4

Implementação Python de classificação topológica

from collections import defaultdict
class graph:
    def __init__(self, vertices):
        self.adjacencyList = defaultdict(list) 
        self.Vertices = vertices  # No. of vertices
    # function to add an edge to adjacencyList
    def createEdge(self, u, v):
        self.adjacencyList[u].append(v)
    # The function to do Topological Sort.
    def topologicalSort(self):
        total_indegree = [0]*(self.Vertices)
        for i in self.adjacencyList:
            for j in self.adjacencyList[i]:
                total_indegree[j] += 1
        queue = []
        for i in range(self.Vertices):
            if total_indegree[i] == 0:
                queue.append(i)
        visited_node = 0
        order = []
        while queue:
            u = queue.pop(0)
            order.append(u)
            for i in self.adjacencyList[u]:
                total_indegree[i] -= 1

                if total_indegree[i] == 0:
                    queue.append(i)
            visited_node += 1
        if visited_node != self.Vertices:
            print("There's a cycle present in the Graph.\nGiven graph is not DAG")
        else:
            print(order)
G = graph(6)
G.createEdge(0,1)
G.createEdge(0,2)
G.createEdge(1,3)
G.createEdge(1,5)
G.createEdge(2,3)
G.createEdge(2,5)
G.createEdge(3,4)
G.createEdge(5,4)
G.topologicalSort()

saída

[0, 1, 2, 3, 5, 4]

Gráficos cíclicos do algoritmo de classificação topológica

Um gráfico contendo um ciclo não pode ser ordenado topologicamente. Já o Gráfico cíclico tem a dependência de forma cíclica.

Por exemplo, verifique este gráfico:

Gráficos cíclicos do algoritmo de classificação topológica

Este gráfico não é DAG (gráfico acíclico direcionado) porque A, B e C criam um ciclo. Se você notar, não há nenhum nó com valor de grau zero.

De acordo com o Algoritmo de Kahn, se analisarmos o gráfico acima:

  • Encontre um nó com zero graus de entrada (sem arestas de entrada).
  • Remova esse nó do gráfico e envie-o para a fila.
    Porém, no gráfico acima, não há nenhum nó com zero em graus. Cada nó tem um valor de grau maior que 0.
  • Retorna uma fila vazia, pois não foi possível encontrar nenhum nó com zero em graus.

Podemos detectar ciclos usando a ordenação topológica com o seguintewing passos:

Passo 1) Execute a classificação topológica.

Passo 2) Calcule o número total de elementos na lista ordenada topologicamente.

Passo 3) Se o número de elementos for igual ao número total de vértices, então não há ciclo.

Passo 4) Se não for igual ao número de vértices, então há pelo menos um ciclo na estrutura de dados do gráfico fornecida.

ComplexAnálise de qualidade de classificação topológica

Existem dois tipos de comunicaçãoplexcapacidade em algoritmos. Eles estão

  1. Hora Complexdade
  2. Espaço Complexdade

Estes complexentidades são representadas com uma função que fornece uma comunidade geralplexity.

Hora Complexidade: Todos os tempos complexA qualidade é a mesma para a classificação topológica. Existem cenários piores, médios e melhores para o tempo complexity.

A hora complexA capacidade para classificação topológica é O (E + V), aqui, E significa o número de arestas no gráfico e V significa o número de vértices no gráfico.

Vamos romper esse complexidade:

Passo 1) No início, calcularemos todos os graus. Para fazer isso, precisamos percorrer todas as arestas e, inicialmente, atribuiremos todos os graus dos vértices V a zero. Portanto, as etapas incrementais que completamos serão O(V+E).

Passo 2) Encontraremos o nó com valor de grau zero. Precisamos pesquisar a partir do número V do vértice. Assim, as etapas concluídas serão O (V).

Passo 3) Para cada nó com zero indegrees, removeremos esse nó e decrementaremos o indegree. Executar esta operação para todos os nós levará O(E).

Passo 4) Por fim, verificaremos se existe algum ciclo ou não. Verificaremos se o número total de elementos na matriz classificada é igual ao número total de nós. Vai levar O (1).

Então, esses foram os momentos individuaisplexcapacidade para cada etapa da classificação topológica ou ordenação topológica. Podemos dizer que chegou a horaplexa qualidade do cálculo acima será O( V + E ); aqui, O significa o complexfunção de cidade.

Espaço Complexidade: Precisávamos de espaços O(V) para executar o algoritmo de classificação topológica.

Aqui estão as etapas em que precisávamos de espaço para o programa:

  • Tivemos que calcular todos os graus de nós presentes no gráfico. Como o Grafo possui um total de V nós, precisamos criar um array de tamanho V. Portanto, o espaço necessário foi O (V).
  • Uma estrutura de dados Queue foi usada para armazenar o nó com grau zero. Removemos os nós com grau zero do gráfico original e os colocamos na fila. Para isso, o espaço necessário foi O (V).
  • A matriz é chamada de “ordem”. Isso armazenou os nós em ordem topológica. Isso também exigia O (V) espaços.

Estes eram o espaço individual complexcidade. Portanto, precisamos maximizar esses espaços no tempo de execução.

Espaço complexity significa O(V), onde V significa o número do vértice no gráfico.

Aplicação de classificação topológica

Há um grande uso para classificação topológica. Aqui estão alguns deles:

  • É usado quando Sistema operacional precisa realizar a alocação de recursos.
  • Encontrando um ciclo no gráfico. Podemos validar se o gráfico é DAG ou não com classificação topológica.
  • Ordenação de frases nos aplicativos de preenchimento automático.
  • É usado para detectar deadlocks.
  • Diferentes tipos de agendamento ou agendamento de curso usam a classificação topológica.
  • Resolvendo dependências. Por exemplo, se você tentar instalar um pacote, esse pacote também poderá precisar de outros pacotes. A ordenação topológica descobre todos os pacotes necessários para instalar o pacote atual.
  • Linux usa a classificação topológica no “apt” para verificar a dependência dos pacotes.