Clasificación topológica: ejemplo de algoritmo de Python y C++

¿Qué es el algoritmo de clasificación topológica?

La clasificación topológica también se conoce como algoritmo de Kahn y es un algoritmo de clasificación popular. Utilizando un gráfico dirigido como entrada, Topological Sort ordena los nodos para que cada uno aparezca antes del que apunta.

Este algoritmo se aplica en un DAG (gráfico acíclico dirigido) para que cada nodo aparezca en la matriz ordenada antes de que todos los demás nodos apunten a él. Este algoritmo sigue algunas reglas repetidamente hasta que se completa la clasificación.

Para simplificar, mira lo siguiente.wing ejemplo:

Gráfico dirigido
Gráfico dirigido

Aquí podemos ver que "A" no tiene grado. Significa la arista que apunta a un nodo. "B" y "C" tienen un requisito previo de "A", luego "E" tiene un requisito previo de nodos "D" y "F". Algunos de los nodos dependen de otros nodos.

Aquí hay otra representación del gráfico anterior:

Dependencia de cada Nodo

Dependencia de cada nodo (Ordenamiento lineal)

Entonces, cuando pasamos el DAG (Gráfico acíclico dirigido) al ordenamiento topológico, nos dará una matriz con ordenamiento lineal, donde el primer elemento no tiene dependencia.

Algoritmo de clasificación topológica

Este ejemplo muestra un gráfico con un ciclo:

Estos son los pasos para hacer esto:

Paso 1) Encuentre el nodo con cero aristas entrantes, un nodo con cero grados.

Paso 2) Almacene ese nodo de grado a cero en una cola o pila y elimine el nodo del gráfico.

Paso 3) Luego elimine el borde saliente de ese nodo.

Esto disminuirá el recuento de grados para el siguiente nodo.

El orden topológico requiere que la estructura de datos del gráfico no tenga ningún ciclo.

Un gráfico se considerará DAG si cumple estos requisitos:

  • Uno o más nodos con un valor de grado cero.
  • El gráfico no contiene ningún ciclo.

As long as there’re nodes in the Graph and the Graph is still DAG, we will run the above three steps. Otherwise, the algorithm will fall into the cyclic dependency, and Kahn’s Algorithm won’t be able to find a node with zero in-degree.

Cómo funciona la clasificación topológica

Aquí usaremos el "algoritmo de Kahn" para la clasificación topológica. Digamos que tenemos el siguientewing Grafico:

Trabajos de clasificación topológica

Estos son los pasos para el algoritmo de Kahn:

Paso 1) Calcule el grado interno o el borde entrante de todos los nodos en el gráfico.

Nota:

  • Engrado significa los bordes dirigidos que apuntan al nodo.
  • Grado exterior significa los bordes dirigidos que provienen de un nodo.

Aquí está el grado de entrada y salida del gráfico anterior:

Trabajos de clasificación topológica

Paso 2) Encuentre el nodo con cero grados de entrada o cero aristas entrantes.

El nodo con cero grados significa que no hay bordes que se acerquen a ese nodo. El nodo "A" tiene cero grados, lo que significa que no hay ningún borde que apunte al nodo "A".

Entonces, haremos lo siguiente.wing comportamiento:

  • Elimine este nodo y sus bordes exteriores (bordes salientes)
  • Coloque el nodo en la cola para realizar pedidos.
  • Actualice el recuento de grados del nodo vecino de "A".

Trabajos de clasificación topológica

Paso 3) Necesitamos encontrar un nodo con un valor de grado cero. En este ejemplo, "B" y "C" tienen un grado de entrada cero.

Aquí podemos tomar cualquiera de estos dos. Tomemos "B" y eliminémoslo del gráfico.

Luego actualice los valores de grado de otros nodos.

Después de realizar estas operaciones, nuestro Gráfico y Cola se verán como siguewing:

Trabajos de clasificación topológica

Paso 4) El nodo "C" no tiene borde entrante. Entonces, eliminaremos el nodo "C" del gráfico y lo insertaremos en la cola.

También podemos eliminar el borde que sale de “C”.

Ahora, nuestro gráfico se verá así:

Trabajos de clasificación topológica

Paso 5) Podemos ver que los nodos "D" y "F" tienen el grado de cero. Tomaremos un nodo y lo pondremos en la cola.

Primero eliminemos "D". Entonces el recuento de grados para el nodo "E" será 1. Ahora, no habrá ningún nodo de D a E.

Necesitamos hacer lo mismo para el nodo "F", nuestro resultado será como el siguientewing:

Trabajos de clasificación topológica

Paso 6) El grado de entrada (bordes de entrada) y el grado de salida (bordes de salida) del nodo "E" se volvieron cero. Entonces, hemos cumplido todos los requisitos previos para el nodo "E".

Aquí, pondremos “E” al final de la cola. Entonces, no nos quedan nodos, por lo que el algoritmo termina aquí.

Trabajos de clasificación topológica

Pseudocódigo para clasificación topológica

Aquí está el pseudocódigo para la clasificación topológica utilizando el 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

La clasificación topológica también se puede implementar utilizando DFS (Primera búsqueda en profundidad) método. Sin embargo, ese enfoque es el método recursivo. El algoritmo de Kahn es más eficiente que el enfoque DFS.

Implementación en C++ de clasificación 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();
}

Salida

0       1       2       3       5       4

Implementación de Python de clasificación 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()

Salida

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

Gráficos cíclicos del algoritmo de clasificación topológica

Un gráfico que contiene un ciclo no se puede ordenar topológicamente. Como el gráfico cíclico tiene la dependencia de forma cíclica.

Por ejemplo, consulte este gráfico:

Gráficos cíclicos del algoritmo de clasificación topológica

Este gráfico no es DAG (gráfico acíclico dirigido) porque A, B y C crean un ciclo. Si te fijas, no hay ningún nodo con valor de grado cero.

Según el algoritmo de Kahn, si analizamos el gráfico anterior:

  • Encuentre un nodo con cero grados (sin aristas entrantes).
  • Elimine ese nodo del gráfico y empújelo a la cola.
    Sin embargo, en el gráfico anterior, no hay ningún nodo con cero en grados. Cada nodo tiene un valor de grado de entrada mayor que 0.
  • Devuelve una cola vacía, ya que no pudo encontrar ningún nodo con cero en grados.

Podemos detectar ciclos usando el ordenamiento topológico con el siguientewing pasos:

Paso 1) Realizar clasificación topológica.

Paso 2) Calcule el número total de elementos en la lista ordenada topológicamente.

Paso 3) Si el número de elementos es igual al número total de vértices, entonces no hay ciclo.

Paso 4) Si no es igual al número de vértices, entonces hay al menos un ciclo en la estructura de datos del gráfico dada.

¿CómoplexAnálisis de calidad de ordenación topológica

Hay dos tipos de complexidad en los algoritmos. Ellos son

  1. Tiempo Complexdad
  2. Espacio Complexdad

Estos complexLas ciudades se representan con una función que proporciona una comunidad general.plexity.

Tiempo Complexidad: com de todos los tiemposplexLa ciudad es la misma para la clasificación topológica. Hay escenarios peores, promedio y mejores para el tiempo.plexity.

el tiempo complexLa calidad para la clasificación topológica es O (E + V), aquí, E significa el número de aristas en el gráfico y V significa el número de vértices en el gráfico.

Rompamos esta comunicaciónplexidad:

Paso 1) Al principio calcularemos todos los grados. Para hacer eso, necesitamos pasar por todos los bordes e inicialmente, asignaremos todos los grados de los vértices V a cero. Entonces, los pasos incrementales que completemos serán O (V + E).

Paso 2) Encontraremos el nodo con valor de grado cero. Necesitamos buscar desde el número V del vértice. Entonces, los pasos completados serán O (V).

Paso 3) Para cada nodo con cero grados, eliminaremos ese nodo y disminuiremos el grado. Realizar esta operación para todos los nodos tomará O(E).

Paso 4) Finalmente comprobaremos si hay algún ciclo o no. Comprobaremos si el número total de elementos en la matriz ordenada es igual al número total de nodos. Tomará O (1).

Entonces, estos fueron los tiempos individuales complexidad para cada paso de la clasificación topológica u ordenamiento topológico. Podemos decir que el tiempo complexLa calidad del cálculo anterior será O (V + E); aquí, O significa la complexfunción de idad.

Espacio Complexidad: Necesitábamos espacios O(V) para ejecutar el algoritmo de clasificación topológica.

Estos son los pasos donde necesitábamos espacio para el programa:

  • Tuvimos que calcular todos los grados de los nodos presentes en el gráfico. Como el gráfico tiene un total de V nodos, necesitamos crear una matriz de tamaño V. Entonces, el espacio requerido fue O (V).
  • Se utilizó una estructura de datos de cola para almacenar el nodo con grado cero. Eliminamos los nodos con grado cero del gráfico original y los colocamos en la cola. Para ello se preparó el espacio necesario O (V).
  • La matriz se denomina "orden". Eso almacenó los nodos en orden topológico. Eso también requirió O (V) espacios

Estos fueron los espacios individuales complexidad. Entonces, necesitamos maximizar estos espacios en el tiempo de ejecución.

comunicación espacialplexity representa O(V), donde V significa el número del vértice en el gráfico.

Aplicación de ordenación topológica

La clasificación topológica tiene un gran uso. Éstos son algunos de ellos:

  • Se utiliza cuando Sistema operativo necesita realizar la asignación de recursos.
  • Encontrar un ciclo en el gráfico. Podemos validar si el Gráfico es DAG o no con ordenación topológica.
  • Orden de oraciones en las aplicaciones de autocompletar.
  • Se utiliza para detectar deadlocks.
  • Diferentes tipos de programación o programación de cursos utilizan el tipo topológico.
  • Resolviendo dependencias. Por ejemplo, si intenta instalar un paquete, es posible que ese paquete también necesite otros paquetes. El ordenamiento topológico descubre todos los paquetes necesarios para instalar el paquete actual.
  • Linux utiliza la clasificación topológica en "apt" para verificar la dependencia de los paquetes.