Ordenación topológica usando el módulo graphlib Python

La clasificación topológica es una ordenación lineal de los vértices del gráfico acíclico dirigido. Para cada borde dirigido uv, el vértice u viene antes que v en la clasificación topológica.

El módulo graphlib de Python introducido en Python 3.9.0 proporciona la clasificación topológica de un gráfico, donde el gráfico se representa en un diccionario. Suponga que el gráfico no tiene bordes paralelos, el gráfico se puede representar mediante un diccionario con vértices como claves y los valores son los Nodes a los que están conectados.

Para instalar este módulo, ejecute este comando en su terminal.

pip install graphlib

Usaremos la clase graphlib. TopologicalSorter(graph= None) , y las siguientes funciones con la instancia de TopologicalSorter:

add(Node, *predecesores):

Agrega un nuevo Node y sus dependencias a un gráfico. Por ejemplo, ts.add(3, 2, 1) agrega el valor clave 3 y sus predecesores 2, 1 al gráfico.  

orden_estático():

Devuelve un iterable de Nodes en un orden topológico.

Verifique los programas a continuación para la clasificación topológica con graphlib.TopologicalSorter()

Ejemplo 1: Clasificación topológica utilizando TopologicalSorter con gráfico no inicializado.

# Python 3.9.0 program for
# topological sorting using
# graphlib module
from graphlib import TopologicalSorter
  
# creating an instance of TopologicalSorter
# initial graph is optional
ts = TopologicalSorter()
  
# adding vertex and it's nodes
ts.add(3, 2, 1)
# adding more node and predecessor
ts.add(1, 0)
  
# printing the topological order
# returned by static_order()
print([*ts.static_order()])

Producción:

[2, 0, 1, 3]

Ejemplo 2: Clasificación topológica usando TopologicalSorter usando un gráfico inicializado.

# Python program for topological sorting
# through graphlib module
  
from graphlib import TopologicalSorter
  
# making graph
graph = {2: {3}, 3: {1}, 4: {0, 1}, 5: {0, 2}}
  
# creating an instance of TopolocialSorter
# with initial graph(initial graph is optional)
ts = TopologicalSorter(graph)
  
# printing the topological order
# returned by static_order()
print([*ts.static_order()])

Producción:

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