Clasificación topológica de Python

1. Algoritmo de clasificación topológica en Python
2. Implementar el algoritmo de clasificación topológica en Python

Este tutorial mostrará la implementación del algoritmo de clasificación topológica en Python.

Algoritmo de clasificación topológica en Python

El algoritmo de clasificación topológica clasifica los gráficos acíclicos dirigidos (DAG). Un gráfico acíclico dirigido (DAG) es un gráfico con bordes dirigidos de un nodo a otro pero sin ciclos.

La ordenación topológica es un algoritmo que acepta un DAG como entrada y devuelve una matriz en la que cada nodo aparece antes que los nodos a los que apunta.

No se puede aplicar a ningún gráfico que no sea DAG porque, en la ordenación topológica, el orden depende completamente de la dirección de los bordes entre los nodos, y si hay ciclos dentro de un gráfico, puede haber varios arreglos para él.

Como resultado, podemos afirmar que una ordenación topológica de los nodos de un grafo acíclico dirigido es la acción de disponer los nodos en el orden tal que si existe una arista (i,j), i precede a j en las listas.

Una clasificación topológica proporciona esencialmente una secuencia en la que debemos realizar la tarea y nos ayuda a determinar si el gráfico tiene un ciclo o no.

Cada gráfico puede soportar más de 1 ordenamiento topológico. El grado de entrada del nodo en el gráfico lo determina.

Además, el ordenamiento topológico de la red comienza con el nodo con grado de entrada 0, es decir, un nodo sin bordes entrantes.

Veamos un ejemplo para comprender mejor lo que sucede en la clasificación topológica.

Entrada DAG:

Primera iteración: []

Segunda Iteración: [B]

Tercera iteración: [B, E]

Cuarta Iteración: [B, E, A]

Quinta Iteración: [B, E, A, F]

Salida final: [B, E, A, F, C, D]

En el ejemplo anterior, eliminamos iterativamente el nodo sin bordes de entrada de nuestro gráfico y lo colocamos en nuestra matriz. Repetimos este proceso hasta que solo quede un nodo en nuestro gráfico.

Al final, agregamos este nodo final al final de nuestra matriz.

Implementar el algoritmo de clasificación topológica en Python

Podemos implementar la misma lógica discutida anteriormente para crear un programa de clasificación topológica en Python. Los pasos para implementar este algoritmo en nuestro código se dan a continuación.

1. Identifique el nodo que no tiene bordes entrantes.
2. Elimine este nodo y sus bordes correspondientes del gráfico.
3. Actualice el grado de entrada de los nodos adyacentes.
4. Repita los pasos 1 a 3 hasta que el gráfico esté vacío.

Está claro a partir de estos 4 pasos que tenemos que crear un gráfico para la ordenación topológica. Esto se puede hacer de varias maneras, pero el método más conveniente es crear una clase de gráfico que contenga métodos para insertar nodos y bordes en nuestro gráfico.

El siguiente fragmento de código muestra una clase de gráfico con un constructor y un método para agregar más bordes a nuestro gráfico.

from collections import defaultdict


class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

Ahora, tenemos una clase llamada graph que puede inicializar un gráfico dirigido o no dirigido y un método addEdge() que puede usarse para agregar más bordes a nuestro gráfico.

Todo lo que necesitamos ahora es un mecanismo para implementar el algoritmo de clasificación topológica. Necesitamos crear una función que visite un nodo, verifique si no hay bordes entrantes y elimine ese nodo si no hay bordes entrantes.

Este tipo de función se muestra en el siguiente fragmento de código.

def visitNode(self, s, visited, sortlist):
    visited[s] = True
    for i in self.graph[s]:
        if not visited[i]:
            self.visitNode(i, visited, sortlist)
    sortlist.insert(0, s)

La función anterior toma el índice del nodo actual s; una lista booleana visited que contiene información sobre si un nodo ya ha sido visitado o no, y una sortlist que usaremos para almacenar los nodos eliminados del gráfico.

Necesitamos crear otra función auxiliar que llame de forma incremental a este visitNode() para todos los nodos de nuestro gráfico e imprima los valores de la lista ordenada al final. El siguiente fragmento de código muestra una función similar implementada en Python.

def topologicalSort(self):
    visited = {i: False for i in self.graph}
    sortlist = []

    for v in self.graph:
        if not visited[v]:
            self.visitNode(v, visited, sortlist)
    print(sortlist)

Ahora, nuestra implementación de la clase graph está completa. Ahora necesitamos crear un gráfico y llamar a la función topologicalSort() para ordenar nuestra lista.

Este proceso se ha implementado en el siguiente código.

if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Producción :

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

El gráfico que creamos en este código corresponde al diagrama de los diagramas anteriores. Aquí, los índices 1 a 6 se refieren a los nodos A a F.

Como hemos visto, la lista ordenada final fue [B, E, A, F, C, D], que es la misma que nuestra salida en el código.

Ahora, veamos nuestro código anterior combinado en un bloque de código.

from collections import defaultdict


class Graph:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed

    def addEdge(self, frm, to):
        self.graph[frm].append(to)
        if self.directed is False:
            self.graph[to].append(frm)
        else:
            self.graph[to] = self.graph[to]

    def visitNode(self, s, visited, sortlist):
        visited[s] = True
        for i in self.graph[s]:
            if not visited[i]:
                self.visitNode(i, visited, sortlist)
        sortlist.insert(0, s)

    def topologicalSort(self):
        visited = {i: False for i in self.graph}
        sortlist = []

        for v in self.graph:
            if not visited[v]:
                self.visitNode(v, visited, sortlist)
        print(sortlist)


if __name__ == "__main__":

    graph = Graph(directed=True)
    graph.addEdge(1, 6)
    graph.addEdge(1, 3)
    graph.addEdge(2, 1)
    graph.addEdge(2, 5)
    graph.addEdge(3, 4)
    graph.addEdge(5, 1)
    graph.addEdge(5, 6)
    graph.addEdge(5, 6)
    graph.addEdge(6, 3)
    graph.addEdge(6, 4)

    print("Topological Sort Algorithm:")
    graph.topologicalSort()

Producción :

Topological Sort Algorithm:
[2, 5, 1, 6, 3, 4] #[B, E, A, F, C, D] in terms of previous example

Esto concluye nuestro tutorial. Ahora, puede implementar la ordenación topológica con una comprensión completa de cómo funciona.