Ordenación topológica explicada: cómo funciona, código y complejidad

Qué problema resuelve la ordenación topológica

Muchas tareas reales tienen requisitos previos: un curso exige cursos anteriores, un archivo fuente debe compilarse después de los archivos que importa, un paquete debe instalarse después de sus dependencias, una celda de una hoja de cálculo debe calcularse después de las celdas a las que hace referencia. Dibuja cada tarea como un nodo y cada regla "debe ir antes" como una arista dirigida. Un orden topológico es cualquier secuencia de las tareas que respeta todas las aristas.

Existe un orden si y solo si el grafo no tiene ningún ciclo dirigido. Si A necesita a B y B necesita a A, no hay ningún orden válido, y una buena ordenación topológica lo informa en lugar de entrar en un bucle infinito. Un DAG suele tener muchos órdenes válidos; los algoritmos devuelven uno de ellos.

La idea en palabras sencillas

El algoritmo de Kahn (publicado por Arthur Kahn en 1962) trabaja desde el principio:

1. Cuenta las aristas entrantes (el grado de entrada) de cada nodo.
2. Pon en una cola cada nodo con grado de entrada 0: son tareas sin requisitos pendientes.
3. Toma un nodo de la cola y añádelo al resultado. Para cada una de sus aristas salientes, reduce en 1 el grado de entrada del destino; si llega a 0, añade el destino a la cola.
4. Cuando la cola esté vacía, si el resultado contiene todos los nodos, es un orden topológico. Si no, los nodos restantes forman parte de un ciclo.

El método DFS trabaja desde el final: un nodo solo termina después de que termine todo aquello a lo que apunta, así que listar los nodos en orden inverso de finalización coloca cada nodo antes de todos sus sucesores.

Ejemplo resuelto, paso a paso

Vestirse (los nombres de los nodos se dejan en inglés, igual que en el código): underwear → pants, pants → shoes, socks → shoes, pants → belt, shirt → belt, shirt → tie, tie → jacket, belt → jacket. Algoritmo de Kahn, tomando los nodos de la cola en orden primero en entrar, primero en salir:

Orden final: underwear, socks, shirt, pants, tie, shoes, belt, jacket. Los 8 nodos están colocados, así que no hay ningún ciclo.

Implementación en Python

El algoritmo de Kahn con una deque:

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

La versión DFS añade un nodo cuando todos sus sucesores han terminado y luego invierte la lista:

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

Ambas salidas son válidas. Desde Python 3.9, la biblioteca estándar también incluye graphlib.TopologicalSorter. Ten en cuenta que recibe un mapeo de cada nodo a sus predecesores, en dirección contraria a los diccionarios anteriores:

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

Complejidad temporal y espacial

Variantes y errores comunes

• Menor orden primero: sustituye la cola por un montículo de mínimos (heapq) para elegir siempre el menor nodo disponible. Así se obtiene el orden lexicográficamente menor en O((V + E) log V).
• Planificación en paralelo: ejecuta el algoritmo de Kahn por rondas, tomando de una vez todos los nodos con grado de entrada 0. Cada ronda es un lote de tareas que pueden ejecutarse a la vez; el número de rondas es la longitud de la cadena de dependencias más larga. graphlib.TopologicalSorter lo admite con get_ready() y done().
• Camino más largo o más corto en un DAG: relaja las aristas en orden topológico para obtener la respuesta en O(V + E), incluso con pesos negativos.
• Contar órdenes distintos es un problema mucho más difícil; no intentes listarlos todos en grafos grandes.

La versión recursiva con DFS tiene el mismo problema de límite de recursión que cualquier DFS recursivo en Python: para cadenas de miles de nodos, usa el algoritmo de Kahn.

Cuándo usarlo y usos en el mundo real

• Las herramientas de compilación como Make ordenan los objetivos según sus dependencias, y los gestores de paquetes ordenan las instalaciones según los grafos de dependencias.
• Las hojas de cálculo recalculan las celdas en orden de dependencia e informan de las referencias circulares.
• Los planificadores de tareas y los motores de flujos de trabajo, por ejemplo los pipelines de datos basados en DAG, ejecutan las tareas en orden topológico.
• Los compiladores ordenan declaraciones y evalúan grafos de expresiones; las bases de datos ordenan la creación o el borrado de claves foráneas.
• Problemas de entrevista: horario de cursos I y II, diccionario alienígena (orden de letras a partir de palabras ordenadas), cursos en paralelo, altura mínima de un plan de construcción.