Ordenamiento topológico

Lo que cubre este capítulo

El ordenamiento topológico responde la pregunta más común que le puedes hacer a un grafo de dependencias: dado un montón de tareas donde algunas deben ocurrir antes que otras, ¿cuál es un orden válido para hacerlas todas? Si tu build system tiene que compilar una librería antes que el programa que la enlaza, si un curso tiene prerrequisitos, si una celda de hoja de cálculo depende de otras celdas, entonces tienes un grafo dirigido y necesitas un orden donde toda flecha apunte hacia adelante: cada prerrequisito antes de lo que lo necesita. Ese orden es un ordenamiento topológico, y existe exactamente cuando el grafo no tiene ciclos (nada puede ir primero si dos tareas se esperan mutuamente). Este capítulo construye los dos algoritmos clásicos —uno nacido de BFS, otro de DFS—, muestra que ambos son los dos capítulos anteriores con sombrero nuevo, y mide qué tan difícil es resolver el problema adivinando: con una docena de dependencias, apenas uno de cada setecientos órdenes aleatorios es válido.

Un poco de historia

El problema es antiquísimo en espíritu —ordenar tareas por dependencia es tan viejo como la planeación de proyectos—, pero los dos algoritmos tienen origen claro. En 1962 Arthur Kahn publicó el método de pelar in-degrees en un artículo sobre cómo organizar los términos de un programa grande de computadora para que cada uno quedara definido antes de usarse; es el algoritmo de "quita lo que ya no tenga prerrequisitos pendientes y repite", y hasta hoy se le llama algoritmo de Kahn. La versión depth-first salió del trabajo de Robert Tarjan a principios de los setenta sobre algoritmos de grafos basados en DFS, donde observó que el orden en el que DFS termina los nodos, invertido, es un orden topológico: dos líneas añadidas al depth-first search del capítulo pasado. Donald Knuth también trató el problema a detalle en The Art of Computer Programming, ligándolo a la teoría de órdenes parciales: un ordenamiento topológico es exactamente una extensión lineal de un orden parcial, una forma de aplanar "algunas cosas van antes que otras" en "aquí tienes una secuencia completa". Ambos algoritmos son lineales, ambos siguen siendo estándar, y cuál usa una librería es más que nada cuestión de gusto — el graphlib de Python usa el enfoque DFS.

La intuición

El algoritmo de Kahn piensa como project manager. Mira todas las tareas y encuentra las que no tienen prerrequisitos pendientes: en términos de grafos, los nodos con in-degree cero, sin flechas apuntándoles. Cualquiera de esas puede ir primero, así que escoges una, la marcas como hecha y la tachas como prerrequisito en todas partes: cada tarea que la estaba esperando ahora necesita una cosa menos, y algunas pueden caer a cero prerrequisitos pendientes y volverse disponibles. Repites hasta colocar todo. Si en algún momento te atoras —quedan tareas pero ninguna tiene in-degree cero—, esas tareas sobrantes forman un ciclo, cada una esperando a otra, y no existe orden válido.

El algoritmo DFS piensa al revés. Una tarea va después de todo aquello de lo que depende, así que corres un depth-first search y, en el momento en que un nodo queda totalmente terminado (toda tarea alcanzable desde él ya está lista), lo empujas a una lista. Un nodo termina solo después de que todos sus dependientes más abajo terminaron, así que la lista sale en orden inverso de dependencia: inviértela y toda flecha apunta hacia adelante. Es exactamente el DFS del capítulo pasado con una línea añadida en el punto de finalización, y el mismo esquema de tres colores que detectaba ciclos allá los detecta aquí: si DFS encuentra una arista de regreso a un nodo que sigue abierto en el stack, hay un ciclo y no hay orden topológico.

Complejidad: cómo escala

Ambos algoritmos son $O(V + E)$: el de Kahn toca cada nodo una vez al pelarlo y cada arista una vez al decrementar in-degrees; la versión DFS visita cada nodo y cada arista una vez y agrega a la lista de finalización en $O(1)$. El espacio es $O(V)$ para el array de in-degrees o los arrays de color/finalización. No hay truco para bajar de lineal: como mínimo tienes que leer cada dependencia. El número interesante no es la velocidad del algoritmo sino el tamaño del problema que resuelve, y eso lo deja clarísimo la comparación: ¿cada cuándo un orden aleatorio cumple por casualidad todas las restricciones?

Con nueve tareas y doce aristas de dependencia, apenas alrededor del 0.135% de los órdenes aleatorios resultaron válidos —uno de cada setecientos, más o menos— y esa fracción se desploma conforme se acumulan dependencias, porque cada arista más o menos parte a la mitad a los sobrevivientes. Un ordenamiento topológico encuentra un orden válido siempre, en tiempo lineal, sin adivinar. Esa es toda la propuesta de valor: el espacio de órdenes válidos es una aguja que se desvanece en el pajar de todos los órdenes, y el ordenamiento topológico camina directo hacia una. Para un grafo de build real con miles de aristas, la fracción de órdenes aleatorios válidos está tan cerca de cero que jamás darías con uno por casualidad en lo que dura el universo — y aun así el algoritmo produce uno al instante.

En qué es bueno y en qué no

El ordenamiento topológico es la herramienta correcta en cuanto tu problema tiene la forma "estas cosas dependen de aquellas, dame un orden válido". Build systems, gestores de paquetes, agendadores de tareas, planeadores de cursos y motores de recálculo de fórmulas se reducen todos a esto. Además sirve de detector de ciclos, que muchas veces es el punto: un build system corre un ordenamiento topológico en parte para ordenar la compilación y en parte para rechazar una dependencia circular con un error claro. Y la frontera de nodos "listos" de Kahn es naturalmente paralela —todo lo que está en in-degree cero puede correr al mismo tiempo—, que es justo por lo que graphlib expone un modo que reparte lotes de tareas listas a threads worker.

Donde no aplica es en cualquier grafo con ciclos, por definición: si las tareas dependen entre sí no existe orden válido, y el algoritmo reporta la falla correctamente en lugar de inventarse uno. También te da un orden válido, no el mejor: si quieres el orden que termina un proyecto lo antes posible dadas las duraciones de las tareas y el paralelismo, eso es agendamiento por ruta crítica, un problema con pesos construido encima del orden topológico, no el ordenamiento en sí. Y necesita todo el grafo de dependencias por adelantado; no es un algoritmo online que acepte tareas de una en una.

Los datos, o las entradas

La comparación corre sobre DAGs aleatorios de nueve tareas con un número creciente de aristas de dependencia, y para cada uno muestrea veinte mil órdenes aleatorios para medir qué fracción resulta válida por casualidad: las probabilidades de resolver el problema adivinando. La verificación de correctitud confirma que tanto nuestros algoritmos como graphlib producen órdenes que respetan cada arista, sobre cientos de DAGs aleatorios, y que los tres reportan falla en grafos con un ciclo plantado. La animación corre el algoritmo de Kahn sobre un DAG pequeño estilo build para que veas caer los in-degrees y avanzar la frontera de nodos listos.

Constrúyelo, una función a la vez

El algoritmo de Kahn: pelar los nodos con in-degree cero, liberando a sus dependientes.

def topo_sort_kahn(adj, n):
    """Kahn's algorithm (1962). Count each node's in-degree (how many prerequisites it has).
    Anything with in-degree 0 is ready to go — put it in a queue. Repeatedly take a ready
    node, append it to the order, and 'remove' it by decrementing its neighbors' in-degrees;
    any neighbor that drops to 0 just became ready. O(V+E). If we place fewer than n nodes,
    the leftovers sit in a cycle and NO valid order exists — we return None."""
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    ready = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # u is placed → one fewer prerequisite for v
            if indeg[v] == 0:
                ready.append(v)
    return order if len(order) == n else None   # short order ⇒ a cycle blocked the rest

La versión DFS: el inverso del orden de finalización, consciente de ciclos.

def topo_sort_dfs(adj, n):
    """The DFS route. A node belongs *after* everything reachable from it, so if we append
    each node to a list the moment DFS FINISHES it (all its descendants done) and then
    reverse the list, we get a topological order. The three-color scheme doubles as a cycle
    check: an edge to a gray (still-open) node is a back edge, so no order exists."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    finished = []
    ok = True

    def visit(u):
        nonlocal ok
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge → cycle → no topological order
                ok = False
            elif color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        finished.append(u)                  # record in finish-order

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return finished[::-1] if ok else None   # reverse finish-order = topological order

Y la propiedad que ambos garantizan, y que un orden aleatorio casi nunca tiene:

def is_valid_topo_order(adj, n, order):
    """An order is a valid topological sort iff it lists all n nodes and every edge u → v has
    u before v. This is the property both algorithms guarantee and a random shuffle almost
    never has."""
    if order is None or len(order) != n or set(order) != set(range(n)):
        return False
    pos = [0] * n
    for i, u in enumerate(order):
        pos[u] = i
    return all(pos[u] < pos[v] for u in range(n) for v in adj[u])

Míralo funcionar

Aquí está el algoritmo de Kahn sobre un grafo de build pequeño. Los nodos verdes están listos: in-degree cero, todos sus prerrequisitos cumplidos; el naranja es el nodo que se está colocando en este paso; los nodos con palomita (verde oscuro) ya están colocados y tachados; los nodos oscuros siguen bloqueados, y su etiqueta muestra su in-degree restante. Observa cómo la ola de disponibilidad avanza de izquierda a derecha: los nodos 0 y 1 arrancan listos (nada les apunta); colocarlos baja los in-degrees de 2 y 3; y la frontera de tareas "listas" barre el grafo hasta que todo queda ordenado. Esta es la frontera de BFS de hace dos capítulos, ahora regulada por prerrequisitos en lugar de distancia:

El código completo

Ambos algoritmos más la verificación de validez del lado from scratch; el graphlib.TopologicalSorter de la librería estándar del otro. Alterna entre los dos — la versión de librería es la que realmente mandarías a producción, y es el mismo algoritmo de orden de finalización de DFS con una API de agendamiento encima.

"""Topological sort — order the nodes of a directed acyclic graph (DAG) so that every
edge points forward: if there's an edge u → v ("u must come before v"), then u appears
before v in the order. It's the algorithm behind every "what must happen before what"
question: build systems, task schedulers, course prerequisites, spreadsheet recompute.

There are two classic algorithms, and they come straight from the two traversals of the
last two chapters:

  - Kahn's algorithm is BFS-flavored: repeatedly remove a node that has no remaining
    prerequisites (in-degree 0), which frees its dependents.
  - The DFS algorithm is depth-first-flavored: a node's correct position is *after* all
    the nodes it points to, so the reverse of DFS finish-order is a topological order.

Both run in O(V+E). Both also detect the one case where no order exists — a cycle, where
some nodes mutually depend on each other and nothing can go first.
"""
from collections import deque


# region: kahn
def topo_sort_kahn(adj, n):
    """Kahn's algorithm (1962). Count each node's in-degree (how many prerequisites it has).
    Anything with in-degree 0 is ready to go — put it in a queue. Repeatedly take a ready
    node, append it to the order, and 'remove' it by decrementing its neighbors' in-degrees;
    any neighbor that drops to 0 just became ready. O(V+E). If we place fewer than n nodes,
    the leftovers sit in a cycle and NO valid order exists — we return None."""
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    ready = deque(u for u in range(n) if indeg[u] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1               # u is placed → one fewer prerequisite for v
            if indeg[v] == 0:
                ready.append(v)
    return order if len(order) == n else None   # short order ⇒ a cycle blocked the rest
# endregion


# region: dfs_topo
def topo_sort_dfs(adj, n):
    """The DFS route. A node belongs *after* everything reachable from it, so if we append
    each node to a list the moment DFS FINISHES it (all its descendants done) and then
    reverse the list, we get a topological order. The three-color scheme doubles as a cycle
    check: an edge to a gray (still-open) node is a back edge, so no order exists."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    finished = []
    ok = True

    def visit(u):
        nonlocal ok
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge → cycle → no topological order
                ok = False
            elif color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        finished.append(u)                  # record in finish-order

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return finished[::-1] if ok else None   # reverse finish-order = topological order
# endregion


# region: is_valid_order
def is_valid_topo_order(adj, n, order):
    """An order is a valid topological sort iff it lists all n nodes and every edge u → v has
    u before v. This is the property both algorithms guarantee and a random shuffle almost
    never has."""
    if order is None or len(order) != n or set(order) != set(range(n)):
        return False
    pos = [0] * n
    for i, u in enumerate(order):
        pos[u] = i
    return all(pos[u] < pos[v] for u in range(n) for v in adj[u])
# endregion

"""The library counterpart, and this one is real standard library: since Python 3.9,
`graphlib.TopologicalSorter` does exactly this job.

    from graphlib import TopologicalSorter, CycleError
    ts = TopologicalSorter()
    for u in range(n):
        for v in adj[u]:
            ts.add(v, u)          # v depends on u  (u must come before v)
    order = list(ts.static_order())   # raises CycleError if the graph has a cycle

graphlib uses the DFS/finish-order approach under the hood, and it also supports a
parallel-scheduling mode (`prepare()` + `get_ready()` + `done()`) for handing out
batches of ready tasks to worker threads — the same Kahn's-algorithm frontier, exposed
as an API. networkx's `topological_sort` is the third-party equivalent for graph objects.
"""
from graphlib import CycleError, TopologicalSorter


# region: library
def topo_sort_library(adj, n):
    """Standard-library topological sort via graphlib. Returns the order, or None on a cycle
    (graphlib signals a cycle by raising CycleError)."""
    ts = TopologicalSorter()
    for u in range(n):
        ts.add(u)                     # ensure isolated nodes are included
        for v in adj[u]:
            ts.add(v, u)              # v depends on u
    try:
        return list(ts.static_order())
    except CycleError:
        return None
# endregion

From scratch vs librería

Cosa poco común en este libro: aquí la contraparte de librería es la librería estándar. graphlib llegó con Python 3.9, así que el ordenamiento topológico viene incluido de fábrica. Nuestras versiones from scratch y graphlib produjeron órdenes válidos en todas las pruebas — a veces órdenes válidos distintos, porque un DAG normalmente admite muchos, y ahí está la lección fina. Los dos algoritmos no son aproximaciones uno del otro; ambos son exactos, y toman decisiones arbitrarias diferentes entre tareas que las dependencias dejan sin ordenar. Así que la prueba de correctitud correcta no es "¿coincide con graphlib?", sino "¿toda arista apunta hacia adelante?", la propiedad que está en is_valid_topo_order. Cuando un problema tiene muchas respuestas correctas, probar contra una respuesta específica es un bug; prueba la propiedad que define la correctitud. En producción usarías graphlib (o networkx si trabajas con objetos de grafo); construirlo una vez tú mismo es lo que hace que la pregunta "¿por qué sale distinto el orden?" tenga una respuesta obvia en lugar de misteriosa.

Dónde te lo vas a topar en serio

El ordenamiento topológico corre debajo de una cantidad enorme de software. Todo build system —make, bazel, cargo, npm, gradle— ordena topológicamente su grafo de dependencias para decidir el orden de compilación y para rechazar dependencias circulares. Los gestores de paquetes (apt, el resolver de pip, conda) ordenan la instalación igual. Los motores de hojas de cálculo recalculan celdas en orden topológico y con eso marcan las referencias circulares. Los agendadores de tareas y motores de workflows (Airflow, pipelines de CI, make -j) lo usan para saber qué jobs pueden correr ya y cuáles tienen que esperar. Los compiladores ordenan el scheduling de instrucciones y lo usan en análisis de flujo de datos. Las herramientas de planeación de cursos ordenan prerrequisitos con él. Donde aparezcan las palabras "depende de", "debe ir antes" o "prerrequisito", un ordenamiento topológico está haciendo el trabajo.

Puntos clave

El ordenamiento topológico aplana un grafo dirigido acíclico de dependencias en un orden lineal donde toda arista apunta hacia adelante, en $O(V+E)$. Viene en dos sabores que son los dos capítulos anteriores reutilizados: el algoritmo de Kahn pela los nodos sin prerrequisitos pendientes (una frontera de BFS regulada por in-degree), y la versión DFS invierte el orden de finalización. Ambos detectan el único caso de falla —un ciclo, donde no existe orden— y ambos encuentran un orden válido al instante donde adivinar prácticamente nunca lo lograría. El orden no es único, así que correctitud significa "toda arista apunta hacia adelante", no "coincide con esta secuencia exacta".

De aquí en adelante el nivel de grafos se vuelca a los problemas con pesos. Los siguientes capítulos —Dijkstra, Bellman-Ford y los demás— no preguntan solo "qué orden" o "¿se puede llegar?", sino "¿cuál es el camino más barato?", poniéndoles costo a las aristas. Los recorridos que llevamos trataban cada arista como un paso igual; los pesos rompen esa suposición, y con ella la garantía de camino más corto de BFS, que es exactamente el hueco que llena el algoritmo de Dijkstra a continuación.