Orden topológico: la cura del glitch

El diamante nos dejó una obligación sin cumplir: un nodo no debe recalcularse hasta que todas sus entradas estén al día. Cumplirla exige responder a una pregunta de orden: ¿en qué secuencia visitar los nodos para que nunca toquemos uno antes que a sus dependencias? La teoría de grafos contestó esa pregunta hace décadas, y la respuesta es el orden topológico. No es una heurística ni un truco de librería: es la única disciplina de visita que elimina los glitches por construcción, y su existencia depende de una propiedad que el grafo reactivo cumple casi siempre —ser acíclico—.

El grafo reactivo es un DAG

Dibuja una arista de cada valor a cada valor del que depende y obtienes un grafo dirigido. Si total depende de subtotal, hay una arista de subtotal hacia total. Ese grafo no puede tener ciclos: si x dependiera de y y y de x, ninguno podría calcularse primero. Un grafo dirigido sin ciclos es, por definición, un DAG —grafo acíclico dirigido—, la misma estructura que gobierna un grafo de tareas de build o un plan de dependencias de paquetes.

El DAG tiene fuentes —nodos sin dependencias, las señales de escritura— y sumideros —nodos que nadie lee, típicamente los efectos—. Entre ambos, cada derivado ocupa una posición determinada por sus dependencias. Esa posición es lo que vamos a ordenar.

El teorema: orden topológico, cero glitches

Un orden topológico es una lista de todos los nodos tal que cada nodo aparece DESPUÉS de todos aquellos de los que depende. La afirmación central del nivel se demuestra en dos líneas.

En el diamante, un orden topológico válido es precio, subtotal, iva, total —o precio, iva, subtotal, total, que también respeta las aristas—. En ambos, total va al final, después de sus dos ramas. Nunca se recalcula con una rama vieja, y si lo visitamos una sola vez, se recalcula una sola vez. Las dos patologías del diamante desaparecen juntas con la misma disciplina.

Alturas: el orden topológico incremental

Recalcular todo el DAG de cero en cada cambio sería absurdo. Los sistemas reactivos mantienen un orden topológico barato asignando a cada nodo una altura: la fuente tiene altura 0, y todo derivado tiene una altura de uno más que la mayor de sus dependencias. Procesar los nodos en altura no decreciente ES un orden topológico, porque un nodo siempre tiene una altura mayor que cualquiera de sus dependencias.

flowchart TD
A[precio altura 0] --> B[subtotal altura 1]
A --> C[iva altura 1]
B --> D[total altura 2]
C --> D
style A fill:#cba6f7,color:#11111b
style B fill:#89b4fa,color:#11111b
style C fill:#89b4fa,color:#11111b
style D fill:#a6e3a1,color:#11111b

Con las alturas a mano, la propagación usa una cola de prioridad —un montículo— ordenada por altura, extrayendo siempre el nodo de menor altura pendiente. Cuando precio cambia, se encolan sus dependientes; se extrae el de menor altura; si al recalcularlo su valor cambió, se encolan sus dependientes; y así hasta vaciar la cola. La clave está en insertar sin duplicar: si total ya está en la cola, la segunda inserción no hace nada.

function propagar(fuente) {
  const cola = new ColaPrioridad((n) => n.altura)   // menor altura primero
  for (const dep of fuente.dependientes) cola.insertarUnico(dep)
  while (!cola.vacia()) {
    const n = cola.extraerMin()   // altura minima: sus entradas ya son finales
    const cambio = n.recalcular()
    if (cambio) {
      for (const d of n.dependientes) cola.insertarUnico(d)  // dedupe implicito
    }
  }
}

Este es, en esencia, el planificador por alturas de la familia FrTime y de los primeros sistemas de señales. La cola por altura garantiza el orden topológico sin re-linealizar el grafo entero, y insertarUnico garantiza una sola visita por nodo. El diamante se resuelve solo: total, con altura 2, no sale de la cola hasta que subtotal e iva, con altura 1, ya se recalcularon.

Kahn y DFS: construir el orden desde cero

Cuando hay que linealizar un grafo completo de una vez —al arrancar, o al importar un plan— el clásico es el algoritmo de Kahn: cuenta cuántas dependencias pendientes tiene cada nodo, empieza por los que no tienen ninguna —las fuentes— y, al emitir un nodo, descuenta uno a cada dependiente; los que llegan a cero entran en la lista de listos.

// Kahn: emite primero los nodos sin dependencias pendientes
function topo(grafo) {
  const grado = new Map()
  for (const n of grafo) grado.set(n, n.fuentes.length)   // aristas de entrada
  const listos = grafo.filter((n) => grado.get(n) === 0)  // las fuentes
  const orden = []
  while (listos.length) {
    const n = listos.pop()
    orden.push(n)
    for (const d of n.dependientes) {
      grado.set(d, grado.get(d) - 1)          // una dependencia menos pendiente
      if (grado.get(d) === 0) listos.push(d)  // ya puede emitirse
    }
  }
  if (orden.length !== grafo.length) throw new Error("ciclo detectado")
  return orden
}

La otra vía es un recorrido en profundidad que emite cada nodo cuando termina de visitar a todas sus dependencias; la lista de finalización, invertida, es un orden topológico. Kahn y DFS producen órdenes válidos que pueden diferir entre sí, y ambos valen: la consistencia solo exige respetar las aristas, no un orden único. Fíjate en la última línea de Kahn: si al terminar quedan nodos sin emitir, es que ninguno pudo llegar a grado cero, y eso solo pasa si hay un ciclo. Ordenar y detectar ciclos son, literalmente, el mismo cómputo.

El orden topológico existe si y solo si el grafo es acíclico. Un ciclo —x depende de y, y depende de x— no admite ninguna linealización: cualquiera de los dos que pongas primero viola una arista. Por eso los sistemas reactivos tratan los ciclos como un error de programa, no como un caso a soportar.

const a = computed(() => b())   // a depende de b
const b = computed(() => a())   // b depende de a: ciclo
// al leer cualquiera de los dos, un sistema serio lanza:
// RangeError: cyclic dependency detected

Las pocas familias que permiten realimentación —ciertos FRP— la modelan aparte, con un retardo explícito que rompe el ciclo instantáneo introduciendo un paso de tiempo. Sin ese truco, un ciclo es sencillamente la ausencia de un orden consistente.

El mismo orden topológico que aquí sincroniza signals es el que un sistema de build usa para decidir qué compilar antes que qué, y el que un planificador de tareas usa para no arrancar un trabajo hasta que terminen sus prerequisitos. No es coincidencia: siempre que hay dependencias y hay que actualizar sin exhibir estados a medias, la respuesta es un DAG recorrido en orden topológico.

Un matiz práctico: cuando varios órdenes topológicos son válidos, conviene que el sistema elija siempre el mismo, para que la propagación sea determinista y depurable. Los planificadores por altura lo consiguen gratis —la altura fija estratos y dentro de un estrato el orden es intercambiable— y por eso dos ejecuciones idénticas producen la misma traza. Un orden que variara entre corridas volvería a introducir, por la puerta de atrás, la dependencia del orden que tanto costó eliminar.

Que la solución sea idéntica en dominios tan distintos es la mejor señal de que el orden topológico no es un truco de implementación, sino la forma canónica de actualizar cualquier red de dependencias sin mostrar estados intermedios inconsistentes.