Orden topológico y componentes fuertemente conexas

Compilar módulos que se importan entre sí, correr migraciones con dependencias, planificar tareas: todo es la misma pregunta. En qué orden hacer las cosas para que nada empiece antes que aquello de lo que depende. La respuesta existe si y sólo si no hay dependencias circulares.

Existe si y sólo si no hay ciclos

Un orden topológico de un grafo dirigido es una secuencia de todos los vértices donde cada arista va de un vértice anterior a uno posterior. Existe exactamente cuando el grafo es acíclico.

No es único: lo habitual es que haya muchos órdenes válidos, porque las tareas sin relación entre sí pueden hacerse en cualquier orden. Eso mismo es lo que permite paralelizar.

Kahn: empezar por los que no dependen de nadie

El algoritmo de Kahn trabaja por grados de entrada. Se cuentan las dependencias pendientes de cada vértice, se empieza por los que tienen cero y, al procesar uno, se descuenta a sus vecinos; el que llega a cero entra a la cola.

Si al terminar quedaron vértices sin procesar, esos vértices están en ciclos o dependen de ellos: el algoritmo detecta el problema y además señala dónde está. Cuesta $O(V+E)$ y se presta a la planificación por niveles, donde cada tanda puede ejecutarse en paralelo.

La otra forma sale de DFS

La otra forma sale de DFS: recorrer el grafo y, al terminar de explorar un vértice, agregarlo a una lista. El orden topológico es esa lista al revés.

Un vértice se termina después que todos sus descendientes, así que darlo vuelta lo deja adelante. Para detectar ciclos hay que distinguir un vértice ya terminado de uno abierto en la rama actual: sólo una arista hacia uno abierto cierra un ciclo.

Cuando los ciclos no se pueden sacar

¿Y si hay ciclos y no se pueden eliminar? Ahí entran las componentes fuertemente conexas: grupos maximales de vértices donde todos se alcanzan mutuamente.

Contrayendo cada componente en un solo nodo se obtiene el grafo de componentes, que siempre es acíclico —si dos componentes se alcanzaran entre sí, serían una sola—. Sobre ese grafo el orden topológico vuelve a existir, y dentro de cada componente se resuelve el ciclo aparte. Es lo que hace un compilador con módulos mutuamente recursivos.

Los dos algoritmos lineales

Hay dos algoritmos lineales para encontrarlas. Kosaraju corre DFS, invierte todas las aristas y vuelve a correr DFS en el orden inverso de finalización de la primera pasada: cada árbol de la segunda es una componente. Son dos recorridos y es fácil de justificar.

Tarjan lo hace en una sola pasada, llevando por vértice el momento en que fue descubierto y el menor momento alcanzable desde su subárbol. Cuando ambos coinciden, ese vértice es la raíz de una componente. Los dos son $O(V+E)$; Kosaraju se explica mejor, Tarjan recorre una sola vez.

Programación dinámica sobre un grafo acíclico

El orden topológico habilita además la programación dinámica sobre grafos acíclicos: recorrer en ese orden garantiza tener resueltas las dependencias, y ahí se calculan caminos mínimos o máximos en tiempo lineal, incluso con pesos negativos.

Las componentes fuertemente conexas aparecen en análisis de dependencias, detección de ciclos de importación y en 2-SAT, donde la satisfacibilidad se decide comprobando que ninguna variable esté en la misma componente que su negación.

Kahn, escrito

El algoritmo de Kahn es un BFS sobre los grados de entrada, y de yapa detecta ciclos.

type Graph = ReadonlyMap<string, readonly string[]>;

const topologicalOrder = (graph: Graph): string[] | null => {
  const incoming = new Map<string, number>();
  for (const node of graph.keys()) incoming.set(node, 0);
  for (const neighbours of graph.values()) {
    for (const neighbour of neighbours) {
      incoming.set(neighbour, (incoming.get(neighbour) ?? 0) + 1);
    }
  }

  // los que no dependen de nadie pueden arrancar ya
  const ready = [...incoming].filter(([, count]) => count === 0).map(([node]) => node);
  const order: string[] = [];

  while (ready.length > 0) {
    const current = ready.pop()!;
    order.push(current);

    for (const neighbour of graph.get(current) ?? []) {
      const left = incoming.get(neighbour)! - 1;
      incoming.set(neighbour, left);
      if (left === 0) ready.push(neighbour); // ya se resolvieron todas sus dependencias
    }
  }

  return order.length === graph.size ? order : null; // faltan nodos: hay un ciclo
};

La última línea es la que más valor da: si el orden no incluye a todos los vértices, es porque los que faltan están en un ciclo y nunca llegaron a grado de entrada cero. El mismo recorrido que ordena, detecta.

Componentes, y por qué importan

Cierre

Sin ciclos, Kahn o DFS invertido dan el orden en $O(V+E)$ y señalan el problema si lo hay. Con ciclos, Tarjan o Kosaraju los contraen en componentes y devuelven un grafo acíclico, donde el orden vuelve a tener sentido.