Ir al contenido
wannacode

Ordenamiento topológico

En resumen: El ordenamiento topológico ordena tareas con dependencias de modo que cada una vaya después de sus dependencias; el algoritmo de Kahn lo hace con una cola y se da cuenta si hay un ciclo.

Problema

Qué se construye primero

La tienda online está dividida en siete módulos. core es el código compartido. db habla con la base de datos y usa core. auth gestiona el inicio de sesión de los clientes y usa core y db. catalog, cart, payments y web se apoyan en ellos.

La herramienta de build tiene que compilar cada módulo después de todo lo que necesita. Si construye cart antes que catalog, el compilador no encuentra las clases del catálogo y se detiene.

La primera solución es escribir el orden a mano en un script. Funciona hasta que alguien añade una dependencia nueva y se olvida del script. Un proyecto grande tiene cientos de módulos.

¿Y si auth empieza a usar algo de web, que usa cart, que usa auth? Entonces cada uno espera a otro, y el build es imposible. Quieres saberlo enseguida, y saber qué módulos tienen la culpa.

La idea

Un grafo de dependencias

Los módulos son los vértices de un grafo dirigido (mira representación de un grafo). Lo guardamos como lista de adyacencia: para cada módulo, lo que necesita.

var needs = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};

Un orden en el que cada módulo va después de sus dependencias se llama orden topológico, y encontrarlo es el ordenamiento topológico. Existe solo si el grafo no tiene ciclos.

¿Cómo se encuentra? Un módulo sin dependencias se puede construir de inmediato. Cuando está construido, los módulos que lo usan esperan una dependencia menos. El número «cuántas dependencias siguen esperando» es el grado de entrada del módulo.

Este es el algoritmo de Kahn:

  1. Cuenta el grado de entrada de cada módulo.
  2. Los módulos con grado de entrada 0 entran en una cola ready.
  3. Saca un módulo de la cola y ponlo en order. A todos los que lo usan, réstales uno al grado de entrada. El que llega a 0 entra en la cola.
  4. Repite hasta que la cola quede vacía.

Míralo

Kahn por dentro

static List<string> BuildOrder(
    Dictionary<string, string[]> needs)
{
    var indegree = new Dictionary<string, int>();
    var users = new Dictionary<string, List<string>>();
    foreach (var (m, deps) in needs)
    {
        indegree[m] = deps.Length;
        users[m] = [];
    }
    foreach (var (m, deps) in needs)
    {
        foreach (string dep in deps) users[dep].Add(m);
    }
    var ready = new Queue<string>();
    foreach (string m in needs.Keys)
    {
        if (indegree[m] == 0) ready.Enqueue(m);
    }
    var order = new List<string>();
    while (ready.Count > 0)
    {
        string m = ready.Dequeue();
        order.Add(m);
        foreach (string user in users[m])
        {
            indegree[user]--;
            if (indegree[user] == 0) ready.Enqueue(user);
        }
    }
    return order;
}

users es el reverso de needs: para cada módulo, quién lo usa. Sin ella tendrías que buscar en todo el grafo después de cada módulo construido.

Queue<T> es la cola: Enqueue pone al final, Dequeue saca por delante, ambos en O(1).
var needs = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
Console.WriteLine($"Orden: {string.Join(", ", BuildOrder(needs))}");
Salida
Orden: core, db, auth, catalog, payments, cart, web

static List<string> BuildOrder(
    Dictionary<string, string[]> needs)
{
    var indegree = new Dictionary<string, int>();
    var users = new Dictionary<string, List<string>>();
    foreach (var (m, deps) in needs)
    {
        indegree[m] = deps.Length;
        users[m] = [];
    }
    foreach (var (m, deps) in needs)
    {
        foreach (string dep in deps) users[dep].Add(m);
    }
    var ready = new Queue<string>();
    foreach (string m in needs.Keys)
    {
        if (indegree[m] == 0) ready.Enqueue(m);
    }
    var order = new List<string>();
    while (ready.Count > 0)
    {
        string m = ready.Dequeue();
        order.Add(m);
        foreach (string user in users[m])
        {
            indegree[user]--;
            if (indegree[user] == 0) ready.Enqueue(user);
        }
    }
    return order;
}
Paso a paso, en palabras
  1. Siete módulos. Una flecha va de una dependencia al módulo que la usa. El número sobre cada módulo es su grado de entrada: cuántas de sus dependencias todavía no están construidas.
  2. Solo core no espera nada (grado 0). Entra en la cola ready.
  3. core sale de ready y se construye. Todos los que lo usan esperan ahora una dependencia menos: db baja a 0 y entra en la cola, auth baja a 1.
  4. db se construye. auth y catalog bajan a 0: los dos tienen todo lo que necesitan y entran en la cola.
  5. auth se construye. payments baja a 0 y entra, cart baja a 1: todavía espera a catalog.
  6. catalog se construye y cart baja a 0. Ahora cart también entra en la cola.
  7. payments se construye. web baja a 1: todavía espera a cart.
  8. cart se construye, web baja a 0 y entra el último.
  9. web se construye. Nadie lo usa, y la cola queda vacía.
  10. BuildOrder devuelve order con 7 módulos, tantos como hay en needs: cada uno va después de sus dependencias. Menos significaría un ciclo.

La cola nunca tiene más de dos módulos: solo los que ya lo tienen todo y esperan su turno.

Pruébalo

Predice la salida

Las tareas de un release: revisión de estilo, compilación, pruebas, empaquetado, deploy, notificación. ¿Qué devuelve BuildOrder?

var tasks = new Dictionary<string, string[]>
{
    ["lint"] = [],
    ["compile"] = [],
    ["test"] = ["compile"],
    ["package"] = ["compile", "lint"],
    ["deploy"] = ["test", "package"],
    ["notify"] = ["deploy"],
};
Console.WriteLine(string.Join(", ", BuildOrder(tasks)));
Respuesta

Pruébalo

Completa

¿Cuándo entra un módulo en la cola?

foreach (string user in users[m])
{
    indegree[user]--;
    if () ready.Enqueue(user);
}

La idea

El ciclo

Un compañero hace que auth use un ayudante de web:

    ["auth"] = ["core", "db", "web"],

Ahora auth espera a web, web espera a cart, cart espera a auth. Ninguno de los tres llega al grado de entrada 0 ni entra en la cola. payments espera a auth y también se queda atrás. La cola se agota con solo 3 de los 7 módulos en order.

Esa es también la comprobación: menos módulos en order que en el grafo significa un ciclo. Para decir qué módulos tienen la culpa, empieza por el primero sin construir y sigue una dependencia sin construir. Todo módulo sin construir tiene al menos una, así que tarde o temprano llegas a un módulo por el que ya pasaste:

static List<string> FindCycle(
    Dictionary<string, string[]> needs, List<string> order)
{
    var built = order.ToHashSet();
    string m = needs.Keys.First(x => !built.Contains(x));
    var path = new List<string>();
    while (!path.Contains(m))
    {
        path.Add(m);
        m = needs[m].First(d => !built.Contains(d));
    }
    int from = path.IndexOf(m);
    var loop = path.GetRange(from, path.Count - from);
    loop.Add(m);
    return loop;
}
var order = BuildOrder(needs);
if (order.Count < needs.Count)
{
    Console.WriteLine($"Construidos: {string.Join(", ", order)}");
    var loop = FindCycle(needs, order);
    Console.WriteLine($"Ciclo: {string.Join(" → ", loop)}");
}
else
{
    Console.WriteLine($"Orden: {string.Join(", ", order)}");
}
Salida
Construidos: core, db, catalog
Ciclo: auth → web → cart → auth
Más precisamente, para curiosos

Las herramientas reales hacen lo mismo y nombran el ciclo. Gradle dice «Circular dependency between the following tasks» y las lista. Maven dice «The projects in the reactor contain a cyclic reference». MSBuild rechaza un proyecto que se alcanza a sí mismo a través de sus referencias. La solución siempre está en el código, no en la herramienta: lo que comparten los dos módulos pasa a un tercero del que dependen ambos.

findCycle encuentra un ciclo. Los módulos de fuera que esperan a un módulo del ciclo (aquí payments) no son el problema, sino sus víctimas. Se construirán en cuanto el ciclo desaparezca.

Pruébalo

Encuentra el error

Un compañero escribió la comprobación del ciclo. Con auth esperando a web, el programa dice:

var order = BuildOrder(needs);
if (order.Count == 0)
{
    Console.WriteLine($"Construidos: {string.Join(", ", order)}");
    var loop = FindCycle(needs, order);
    Console.WriteLine($"Ciclo: {string.Join(" → ", loop)}");
}
else
{
    Console.WriteLine($"Orden: {string.Join(", ", order)}");
}
Salida
Orden: core, db, catalog

El build sigue con 3 módulos, y 4 faltan en silencio. ¿Qué línea tiene el error?

Elige la línea con el error.

Míralo

Lo mismo con DFS

Hay una segunda manera, con la búsqueda en profundidad de la lección de DFS. Antes de poner un módulo en el orden, visita cada una de sus dependencias. El módulo entra en order solo después de que todas sus dependencias estén ahí. Esto es post-order: escribes al volver, no al ir.

static List<string> DfsOrder(Dictionary<string, string[]> needs)
{
    var order = new List<string>();
    var done = new HashSet<string>();
    var onPath = new HashSet<string>();
    void Visit(string m)
    {
        if (done.Contains(m)) return;
        if (!onPath.Add(m))
        {
            throw new InvalidOperationException($"Ciclo en {m}");
        }
        foreach (string dep in needs[m]) Visit(dep);
        onPath.Remove(m);
        done.Add(m);
        order.Add(m);
    }
    foreach (string m in needs.Keys) Visit(m);
    return order;
}
var needs = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
Console.WriteLine($"Orden: {string.Join(", ", DfsOrder(needs))}");
var broken = new Dictionary<string, string[]>
{
    ["core"] = [],
    ["db"] = ["core"],
    ["auth"] = ["core", "db", "web"],
    ["catalog"] = ["db"],
    ["cart"] = ["catalog", "auth"],
    ["payments"] = ["auth"],
    ["web"] = ["cart", "payments"],
};
try
{
    DfsOrder(broken);
}
catch (InvalidOperationException e)
{
    Console.WriteLine(e.Message);
}
Salida
Orden: core, db, auth, catalog, cart, payments, web
Ciclo en auth

El orden es distinto: aquí cart va antes que payments. Los dos órdenes son correctos, porque cart y payments no dependen uno del otro. Un orden topológico rara vez es el único.

El ciclo se detecta de otra manera aquí. onPath contiene los módulos que DFS ha empezado pero no ha terminado: ahora mismo están en la pila de llamadas. Si te encuentras con uno de ellos otra vez, has dado una vuelta en círculo. En la lección de DFS son los vértices grises.

Más precisamente, para curiosos

¿Cuál elegir? Los dos cuestan O(V + E): cada módulo se procesa una vez, cada dependencia se mira una vez. Kahn no tiene recursión y da de forma natural «qué puede empezar ahora», por eso las herramientas de build que construyen en paralelo piensan así. DFS es más corto cuando el grafo ya se recorre en profundidad.

En C#, un desbordamiento de pila con una cadena muy larga detiene todo el proceso. Kahn no tiene este problema.

La idea

Dónde más

Hay un orden topológico en cualquier lugar donde algo espera a otra cosa:

  • Dependencias de paquetes. npm y pip resuelven qué versiones usar y luego las instalan de modo que cada paquete vaya después de los suyos. Gradle y MSBuild construyen los módulos de un proyecto en orden topológico, y los independientes en paralelo.
  • Makefile. Cada regla dice de qué archivos depende. make construye el grafo y ejecuta los comandos en un orden tal que cada archivo esté listo antes de que otro lo necesite.
  • La hoja de cálculo. La celda C1 = A1 + B1 depende de A1 y B1. Cuando cambia A1, la hoja recalcula solo las celdas posteriores, en orden topológico. Una fórmula que se alcanza a sí misma es un ciclo, y Excel lo dice: «referencia circular».
  • Migraciones de bases de datos y jobs de CI: cada paso espera a los suyos.

Ejercicio

Olas en CI

Resuélvelo en tu editor.

Olas. El servidor de CI ejecuta a la vez todos los jobs que ya pueden empezar. Escribe Waves(needs), que devuelve los jobs en olas: la primera ola son los jobs sin dependencias, y cada siguiente son aquellos cuya última dependencia está en la ola anterior. Ejecútalo con los jobs de «Predice la salida»:

Salida
Ola 1: lint, compile
Ola 2: test, package
Ola 3: deploy
Ola 4: notify

Pista: es Kahn, pero en lugar de una cola guardas la ola actual y construyes la siguiente.

Más tareas

  • La cadena más larga. ¿Cuántas olas necesita CI como mínimo si tiene máquinas ilimitadas? Es el camino más largo del grafo.
  • Un orden estable. Haz que la salida sea la misma sea cual sea el orden de needs: cuando varios módulos estén listos, toma el primero por orden alfabético. ¿Qué estructura necesitas en lugar de la cola?
  • Todos los culpables. Imprime todos los módulos que no se construyen por culpa del ciclo, y separa los que están en el propio ciclo.

Test

Ponte a prueba

1. ¿Cuál es el grado de entrada de un módulo en el algoritmo de Kahn?
2. buildOrder devolvió 4 módulos, y needs tiene 7. ¿Qué significa?
3. Kahn da core, db, auth, catalog, payments, cart, web, y DFS da core, db, auth, catalog, cart, payments, web. ¿Cuál es correcto?
4. ¿Cuánto cuesta el algoritmo de Kahn con V módulos y E dependencias?

Creado por Ivo Gergov como parte de la campaña de Evo Tech por una educación accesible en programación ·