Ordenación topológica

from collections import deque


def ordenar(nodos, flechas):
    sale = {n: [] for n in nodos}
    entrada = {n: 0 for n in nodos}
    tanda = {n: 1 for n in nodos}
    for antes, despues in flechas:
        sale[antes].append(despues)
        entrada[despues] += 1
    cola = deque(n for n in nodos if entrada[n] == 0)
    orden = []
    while cola:
        u = cola.popleft()
        orden.append(u)
        for v in sale[u]:
            tanda[v] = max(tanda[v], tanda[u] + 1)  # después de todo lo que necesita
            entrada[v] -= 1
            if entrada[v] == 0:
                cola.append(v)
    if len(orden) < len(nodos):
        atascados = [n for n in nodos if n not in orden]
        return "Hay un ciclo: " + ", ".join(atascados) + " nunca quedan libres"
    lineas = ["Orden: " + " → ".join(orden)]
    for t in range(1, max(tanda.values()) + 1):
        lineas.append(f"  tanda {t}: " + ", ".join(n for n in orden if tanda[n] == t))
    return "\n".join(lineas)


modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"]
deps = [("util", "modelo"), ("modelo", "datos"), ("util", "datos"), ("datos", "servicio"),
        ("modelo", "servicio"), ("servicio", "web"), ("servicio", "tests"), ("util", "tests"), ("config", "web")]
print(ordenar(modulos, deps))
print(ordenar(modulos, deps + [("tests", "util")]))   # los tests no pueden ir antes que util

function ordenar(nodos, flechas) {
    const sale = new Map(nodos.map((n) => [n, []]));
    const entrada = new Map(nodos.map((n) => [n, 0]));
    const tanda = new Map(nodos.map((n) => [n, 1]));
    for (const [antes, despues] of flechas) {
        sale.get(antes).push(despues);
        entrada.set(despues, entrada.get(despues) + 1);
    }
    const cola = nodos.filter((n) => entrada.get(n) === 0);
    const orden = [];
    for (let i = 0; i < cola.length; i++) {         // un índice que avanza hace de cola
        const u = cola[i];
        orden.push(u);
        for (const v of sale.get(u)) {
            tanda.set(v, Math.max(tanda.get(v), tanda.get(u) + 1));   // después de todo lo que necesita
            entrada.set(v, entrada.get(v) - 1);
            if (entrada.get(v) === 0) cola.push(v);
        }
    }
    if (orden.length < nodos.length) {
        const atascados = nodos.filter((n) => !orden.includes(n));
        return `Hay un ciclo: ${atascados.join(", ")} nunca quedan libres`;
    }
    const lineas = ["Orden: " + orden.join(" → ")];
    for (let t = 1; t <= Math.max(...tanda.values()); t++)
        lineas.push(`  tanda ${t}: ` + orden.filter((n) => tanda.get(n) === t).join(", "));
    return lineas.join("\n");
}

const modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"];
const deps = [["util", "modelo"], ["modelo", "datos"], ["util", "datos"], ["datos", "servicio"],
    ["modelo", "servicio"], ["servicio", "web"], ["servicio", "tests"], ["util", "tests"], ["config", "web"]];
console.log(ordenar(modulos, deps));
console.log(ordenar(modulos, [...deps, ["tests", "util"]]));   // los tests no pueden ir antes que util

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static string Ordenar(List<string> nodos, List<(string Antes, string Despues)> flechas) {
        var sale = nodos.ToDictionary(n => n, _ => new List<string>());
        var entrada = nodos.ToDictionary(n => n, _ => 0);
        var tanda = nodos.ToDictionary(n => n, _ => 1);
        foreach (var (antes, despues) in flechas) {
            sale[antes].Add(despues);
            entrada[despues]++;
        }
        var cola = new Queue<string>(nodos.Where(n => entrada[n] == 0));
        var orden = new List<string>();
        while (cola.Count > 0) {
            string u = cola.Dequeue();
            orden.Add(u);
            foreach (string v in sale[u]) {
                tanda[v] = Math.Max(tanda[v], tanda[u] + 1);      // después de todo lo que necesita
                if (--entrada[v] == 0) cola.Enqueue(v);
            }
        }
        if (orden.Count < nodos.Count)
            return "Hay un ciclo: " + string.Join(", ", nodos.Except(orden)) + " nunca quedan libres";
        var lineas = new List<string> { "Orden: " + string.Join(" → ", orden) };
        for (int t = 1; t <= tanda.Values.Max(); t++)
            lineas.Add(
quot;  tanda {t}: " + string.Join(", ", orden.Where(n => tanda[n] == t)));
        return string.Join("\n", lineas);
    }

    static void Main() {
        var modulos = new List<string> { "util", "config", "modelo", "datos", "servicio", "web", "tests" };
        var deps = new List<(string, string)> { ("util", "modelo"), ("modelo", "datos"), ("util", "datos"), ("datos", "servicio"),
            ("modelo", "servicio"), ("servicio", "web"), ("servicio", "tests"), ("util", "tests"), ("config", "web") };
        Console.WriteLine(Ordenar(modulos, deps));
        Console.WriteLine(Ordenar(modulos, deps.Append(("tests", "util")).ToList()));   // los tests no pueden ir antes que util
    }
}

<?php
function ordenar(array $nodos, array $flechas): string {
    $sale = array_fill_keys($nodos, []);
    $entrada = array_fill_keys($nodos, 0);
    $tanda = array_fill_keys($nodos, 1);
    foreach ($flechas as [$antes, $despues]) {
        $sale[$antes][] = $despues;
        $entrada[$despues]++;
    }
    $cola = new SplQueue();
    foreach ($nodos as $n) if ($entrada[$n] === 0) $cola->enqueue($n);
    $orden = [];
    while (!$cola->isEmpty()) {
        $u = $cola->dequeue();
        $orden[] = $u;
        foreach ($sale[$u] as $v) {
            $tanda[$v] = max($tanda[$v], $tanda[$u] + 1);   // después de todo lo que necesita
            if (--$entrada[$v] === 0) $cola->enqueue($v);
        }
    }
    if (count($orden) < count($nodos))
        return "Hay un ciclo: " . implode(", ", array_diff($nodos, $orden)) . " nunca quedan libres";
    $lineas = ["Orden: " . implode(" → ", $orden)];
    for ($t = 1; $t <= max($tanda); $t++)
        $lineas[] = "  tanda $t: " . implode(", ", array_filter($orden, fn($n) => $tanda[$n] === $t));
    return implode("\n", $lineas);
}

$modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"];
$deps = [["util", "modelo"], ["modelo", "datos"], ["util", "datos"], ["datos", "servicio"],
    ["modelo", "servicio"], ["servicio", "web"], ["servicio", "tests"], ["util", "tests"], ["config", "web"]];
echo ordenar($modulos, $deps), "\n";
echo ordenar($modulos, [...$deps, ["tests", "util"]]), "\n";   // los tests no pueden ir antes que util

sale = {}
vistos = set()
orden = []


def visitar(u):
    vistos.add(u)
    for v in sale[u]:
        if v not in vistos:
            visitar(v)
    orden.insert(0, u)                              # al TERMINAR: todo lo que va después ya está en la lista


modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"]
deps = [("util", "modelo"), ("modelo", "datos"), ("util", "datos"), ("datos", "servicio"),
        ("modelo", "servicio"), ("servicio", "web"), ("servicio", "tests"), ("util", "tests"), ("config", "web")]
for m in modulos:
    sale[m] = []
for antes, despues in deps:
    sale[antes].append(despues)
for m in modulos:
    if m not in vistos:
        visitar(m)
print("Orden con DFS: " + " → ".join(orden))

pos = {m: i for i, m in enumerate(orden)}
valido = all(pos[a] < pos[b] for a, b in deps)      # una flecha hacia atrás lo estropearía
print("Válido: todas las flechas van hacia delante" if valido else "No válido")

const sale = new Map();
const vistos = new Set();
const orden = [];

function visitar(u) {
    vistos.add(u);
    for (const v of sale.get(u)) if (!vistos.has(v)) visitar(v);
    orden.unshift(u);                               // al TERMINAR: todo lo que va después ya está en la lista
}

const modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"];
const deps = [["util", "modelo"], ["modelo", "datos"], ["util", "datos"], ["datos", "servicio"],
    ["modelo", "servicio"], ["servicio", "web"], ["servicio", "tests"], ["util", "tests"], ["config", "web"]];
for (const m of modulos) sale.set(m, []);
for (const [antes, despues] of deps) sale.get(antes).push(despues);
for (const m of modulos) if (!vistos.has(m)) visitar(m);
console.log("Orden con DFS: " + orden.join(" → "));

const pos = new Map(orden.map((m, i) => [m, i]));
const valido = deps.every(([a, b]) => pos.get(a) < pos.get(b));   // una flecha hacia atrás lo estropearía
console.log(valido ? "Válido: todas las flechas van hacia delante" : "No válido");

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static readonly Dictionary<string, List<string>> sale = new();
    static readonly HashSet<string> vistos = new();
    static readonly LinkedList<string> orden = new();

    static void Visitar(string u) {
        vistos.Add(u);
        foreach (string v in sale[u])
            if (!vistos.Contains(v)) Visitar(v);
        orden.AddFirst(u);                            // al TERMINAR: todo lo que va después ya está en la lista
    }

    static void Main() {
        string[] modulos = { "util", "config", "modelo", "datos", "servicio", "web", "tests" };
        var deps = new[] { ("util", "modelo"), ("modelo", "datos"), ("util", "datos"), ("datos", "servicio"),
            ("modelo", "servicio"), ("servicio", "web"), ("servicio", "tests"), ("util", "tests"), ("config", "web") };
        foreach (string m in modulos) sale[m] = new List<string>();
        foreach (var (antes, despues) in deps) sale[antes].Add(despues);
        foreach (string m in modulos) if (!vistos.Contains(m)) Visitar(m);
        Console.WriteLine("Orden con DFS: " + string.Join(" → ", orden));

        var pos = orden.Select((m, i) => (m, i)).ToDictionary(x => x.m, x => x.i);
        bool valido = deps.All(d => pos[d.Item1] < pos[d.Item2]);   // una flecha hacia atrás lo estropearía
        Console.WriteLine(valido ? "Válido: todas las flechas van hacia delante" : "No válido");
    }
}

<?php
$sale = [];
$vistos = [];
$orden = [];

function visitar(string $u): void {
    global $sale, $vistos, $orden;
    $vistos[$u] = true;
    foreach ($sale[$u] as $v)
        if (!isset($vistos[$v])) visitar($v);
    array_unshift($orden, $u);                     // al TERMINAR: todo lo que va después ya está en la lista
}

$modulos = ["util", "config", "modelo", "datos", "servicio", "web", "tests"];
$deps = [["util", "modelo"], ["modelo", "datos"], ["util", "datos"], ["datos", "servicio"],
    ["modelo", "servicio"], ["servicio", "web"], ["servicio", "tests"], ["util", "tests"], ["config", "web"]];
foreach ($modulos as $m) $sale[$m] = [];
foreach ($deps as [$antes, $despues]) $sale[$antes][] = $despues;
foreach ($modulos as $m) if (!isset($vistos[$m])) visitar($m);
echo "Orden con DFS: " . implode(" → ", $orden) . "\n";

$pos = array_flip($orden);
$valido = true;
foreach ($deps as [$a, $b]) if ($pos[$a] > $pos[$b]) $valido = false;   // una flecha hacia atrás lo estropearía
echo ($valido ? "Válido: todas las flechas van hacia delante" : "No válido") . "\n";