Zum Inhalt
wannacode

Topologische Sortierung

Kurz gesagt: Die topologische Sortierung ordnet Aufgaben mit Abhängigkeiten so, dass jede nach ihren Abhängigkeiten kommt; der Algorithmus von Kahn macht das mit einer Warteschlange und erkennt einen Zyklus, falls es einen gibt.

Problem

Was wird zuerst gebaut

Der Online-Shop ist in sieben Module aufgeteilt. core ist der gemeinsame Code. db spricht mit der Datenbank und nutzt core. auth kümmert sich um die Anmeldung der Kunden und nutzt core und db. catalog, cart, payments und web stehen darauf.

Das Build-Tool muss jedes Modul nach allem kompilieren, was es braucht. Baut es cart vor catalog, findet der Compiler die Klassen des Katalogs nicht und bricht ab.

Die erste Lösung ist, die Reihenfolge von Hand in ein Skript zu schreiben. Das geht gut, bis jemand eine neue Abhängigkeit hinzufügt und das Skript vergisst. Ein großes Projekt hat Hunderte Module.

Und was, wenn auth anfängt, etwas aus web zu nutzen, das cart nutzt, das wiederum auth nutzt? Dann wartet jedes auf ein anderes, und der Build ist unmöglich. Das willst du sofort wissen, und auch, welche Module schuld sind.

Die Idee

Ein Abhängigkeitsgraph

Die Module sind die Knoten eines gerichteten Graphen (siehe Darstellung eines Graphen). Wir speichern ihn als Adjazenzliste: für jedes Modul, was es braucht.

Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));

Eine Reihenfolge, in der jedes Modul nach seinen Abhängigkeiten kommt, heißt topologische Reihenfolge, und sie zu finden ist die topologische Sortierung. Es gibt sie nur, wenn der Graph keinen Zyklus hat.

Wie findest du sie? Ein Modul ohne Abhängigkeiten kann sofort gebaut werden. Ist es gebaut, müssen die Module, die es nutzen, auf eine Abhängigkeit weniger warten. Die Zahl „wie viele Abhängigkeiten noch warten“ ist der Eingangsgrad des Moduls.

Das ist der Algorithmus von Kahn:

  1. Zähle den Eingangsgrad jedes Moduls.
  2. Die Module mit Eingangsgrad 0 kommen in eine Warteschlange ready.
  3. Nimm ein Modul aus der Warteschlange und lege es in order. Zähle bei allen, die es nutzen, den Eingangsgrad herunter. Wer 0 erreicht, kommt in die Warteschlange.
  4. Wiederhole, bis die Warteschlange leer ist.

Sieh es dir an

Kahn von innen

static List<String> buildOrder(
        Map<String, List<String>> needs) {
    Map<String, Integer> indegree = new HashMap<>();
    Map<String, List<String>> users = new HashMap<>();
    for (String m : needs.keySet()) {
        indegree.put(m, needs.get(m).size());
        users.put(m, new ArrayList<>());
    }
    for (String m : needs.keySet()) {
        for (String dep : needs.get(m)) {
            users.get(dep).add(m);
        }
    }
    Deque<String> ready = new ArrayDeque<>();
    for (String m : needs.keySet()) {
        if (indegree.get(m) == 0) ready.add(m);
    }
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String m = ready.poll();
        order.add(m);
        for (String user : users.get(m)) {
            indegree.put(user, indegree.get(user) - 1);
            if (indegree.get(user) == 0) ready.add(user);
        }
    }
    return order;
}

users ist die Umkehrung von needs: für jedes Modul, wer es nutzt. Ohne sie müsstest du nach jedem gebauten Modul den ganzen Graphen durchsuchen.

ArrayDeque ist die Warteschlange: add legt hinten ab, poll nimmt vorne heraus, beides in O(1).
Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));
System.out.println("Reihenfolge: " + String.join(", ", buildOrder(needs)));
Ausgabe
Reihenfolge: core, db, auth, catalog, payments, cart, web

static List<String> buildOrder(
        Map<String, List<String>> needs) {
    Map<String, Integer> indegree = new HashMap<>();
    Map<String, List<String>> users = new HashMap<>();
    for (String m : needs.keySet()) {
        indegree.put(m, needs.get(m).size());
        users.put(m, new ArrayList<>());
    }
    for (String m : needs.keySet()) {
        for (String dep : needs.get(m)) {
            users.get(dep).add(m);
        }
    }
    Deque<String> ready = new ArrayDeque<>();
    for (String m : needs.keySet()) {
        if (indegree.get(m) == 0) ready.add(m);
    }
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String m = ready.poll();
        order.add(m);
        for (String user : users.get(m)) {
            indegree.put(user, indegree.get(user) - 1);
            if (indegree.get(user) == 0) ready.add(user);
        }
    }
    return order;
}
Schritt für Schritt, in Worten
  1. Sieben Module. Ein Pfeil führt von einer Abhängigkeit zu dem Modul, das sie nutzt. Die Zahl über jedem Modul ist sein Eingangsgrad: wie viele seiner Abhängigkeiten noch nicht gebaut sind.
  2. Nur core wartet auf nichts (Eingangsgrad 0). Es kommt in die Warteschlange ready.
  3. core verlässt ready und wird gebaut. Alle, die es nutzen, warten jetzt auf eine Abhängigkeit weniger: db fällt auf 0 und kommt in die Warteschlange, auth fällt auf 1.
  4. db wird gebaut. auth und catalog fallen auf 0: beide haben alles, was sie brauchen, und kommen in die Warteschlange.
  5. auth wird gebaut. payments fällt auf 0 und kommt hinein, cart fällt auf 1: es wartet noch auf catalog.
  6. catalog wird gebaut und cart fällt auf 0. Jetzt kommt auch cart in die Warteschlange.
  7. payments wird gebaut. web fällt auf 1: es wartet noch auf cart.
  8. cart wird gebaut, web fällt auf 0 und kommt als Letztes hinein.
  9. web wird gebaut. Niemand nutzt es, und die Warteschlange ist leer.
  10. buildOrder gibt order mit 7 Modulen zurück, so vielen, wie in needs stehen: jedes steht nach seinen Abhängigkeiten. Weniger würde einen Zyklus bedeuten.

Die Warteschlange enthält nie mehr als zwei Module: nur die, die schon alles haben und auf ihren Einsatz warten.

Probier es aus

Sag die Ausgabe voraus

Die Aufgaben eines Releases: Stilprüfung, Kompilieren, Tests, Paketieren, Deploy, Benachrichtigung. Was gibt buildOrder zurück?

Map<String, List<String>> tasks = new LinkedHashMap<>();
tasks.put("lint", List.of());
tasks.put("compile", List.of());
tasks.put("test", List.of("compile"));
tasks.put("package", List.of("compile", "lint"));
tasks.put("deploy", List.of("test", "package"));
tasks.put("notify", List.of("deploy"));
System.out.println(buildOrder(tasks));
Antwort

Probier es aus

Ergänze

Wann kommt ein Modul in die Warteschlange?

for (String user : users.get(m)) {
    indegree.put(user, indegree.get(user) - 1);
    if () ready.add(user);
}

Die Idee

Der Zyklus

Ein Kollege lässt auth einen Helfer aus web nutzen:

needs.put("auth", List.of("core", "db", "web"));

Jetzt wartet auth auf web, web wartet auf cart, cart wartet auf auth. Keines der drei erreicht den Eingangsgrad 0 oder kommt in die Warteschlange. payments wartet auf auth und bleibt auch zurück. Die Warteschlange läuft leer, und in order stehen nur 3 der 7 Module.

Das ist auch die Prüfung: Weniger Module in order als im Graphen bedeutet einen Zyklus. Um zu sagen, welche Module schuld sind, beginnst du beim ersten ungebauten und folgst einer ungebauten Abhängigkeit. Jedes ungebaute Modul hat mindestens eine, also kommst du früher oder später zu einem Modul, an dem du schon vorbei bist:

static List<String> findCycle(
        Map<String, List<String>> needs, List<String> order) {
    Set<String> built = new HashSet<>(order);
    String m = needs.keySet().stream()
            .filter(x -> !built.contains(x)).findFirst().get();
    List<String> path = new ArrayList<>();
    while (!path.contains(m)) {
        path.add(m);
        m = needs.get(m).stream()
                .filter(d -> !built.contains(d)).findFirst().get();
    }
    List<String> loop = new ArrayList<>(
            path.subList(path.indexOf(m), path.size()));
    loop.add(m);
    return loop;
}
List<String> order = buildOrder(needs);
if (order.size() < needs.size()) {
    System.out.println("Gebaut: " + String.join(", ", order));
    List<String> loop = findCycle(needs, order);
    System.out.println("Zyklus: " + String.join(" → ", loop));
} else {
    System.out.println("Reihenfolge: " + String.join(", ", order));
}
Ausgabe
Gebaut: core, db, catalog
Zyklus: auth → web → cart → auth
Genauer, für Neugierige

Echte Tools machen dasselbe und nennen den Zyklus. Gradle sagt „Circular dependency between the following tasks“ und listet sie auf. Maven sagt „The projects in the reactor contain a cyclic reference“. MSBuild lehnt ein Projekt ab, das sich über seine Referenzen selbst erreicht. Die Lösung liegt immer im Code, nicht im Tool: Was die beiden Module teilen, wandert in ein drittes, von dem beide abhängen.

findCycle findet einen Zyklus. Die Module außerhalb, die auf ein Modul des Zyklus warten (hier payments), sind nicht das Problem, sondern seine Opfer. Sie werden gebaut, sobald der Zyklus weg ist.

Probier es aus

Finde den Fehler

Ein Kollege hat die Zyklusprüfung geschrieben. Wenn auth auf web wartet, sagt das Programm:

List<String> order = buildOrder(needs);
if (order.isEmpty()) {
    System.out.println("Gebaut: " + String.join(", ", order));
    List<String> loop = findCycle(needs, order);
    System.out.println("Zyklus: " + String.join(" → ", loop));
} else {
    System.out.println("Reihenfolge: " + String.join(", ", order));
}
Ausgabe
Reihenfolge: core, db, catalog

Der Build läuft mit 3 Modulen weiter, und 4 fehlen stillschweigend. Welche Zeile hat den Fehler?

Wähle die Zeile mit dem Fehler.

Sieh es dir an

Dasselbe mit DFS

Es gibt einen zweiten Weg, mit der Tiefensuche aus der DFS-Lektion. Bevor du ein Modul in die Reihenfolge legst, besuche jede seiner Abhängigkeiten. Das Modul kommt erst in order, nachdem alle seine Abhängigkeiten darin sind. Das ist Post-Order: Du schreibst auf dem Rückweg, nicht auf dem Hinweg.

static List<String> dfsOrder(Map<String, List<String>> needs) {
    List<String> order = new ArrayList<>();
    Set<String> done = new HashSet<>();
    Set<String> onPath = new HashSet<>();
    for (String m : needs.keySet()) {
        visit(m, needs, done, onPath, order);
    }
    return order;
}


static void visit(String m, Map<String, List<String>> needs,
        Set<String> done, Set<String> onPath, List<String> order) {
    if (done.contains(m)) return;
    if (!onPath.add(m)) {
        throw new IllegalStateException("Zyklus bei " + m);
    }
    for (String dep : needs.get(m)) {
        visit(dep, needs, done, onPath, order);
    }
    onPath.remove(m);
    done.add(m);
    order.add(m);
}
Map<String, List<String>> needs = new LinkedHashMap<>();
needs.put("core", List.of());
needs.put("db", List.of("core"));
needs.put("auth", List.of("core", "db"));
needs.put("catalog", List.of("db"));
needs.put("cart", List.of("catalog", "auth"));
needs.put("payments", List.of("auth"));
needs.put("web", List.of("cart", "payments"));
System.out.println("Reihenfolge: " + String.join(", ", dfsOrder(needs)));
Map<String, List<String>> broken = new LinkedHashMap<>();
broken.put("core", List.of());
broken.put("db", List.of("core"));
broken.put("auth", List.of("core", "db", "web"));
broken.put("catalog", List.of("db"));
broken.put("cart", List.of("catalog", "auth"));
broken.put("payments", List.of("auth"));
broken.put("web", List.of("cart", "payments"));
try {
    dfsOrder(broken);
} catch (IllegalStateException e) {
    System.out.println(e.getMessage());
}
Ausgabe
Reihenfolge: core, db, auth, catalog, cart, payments, web
Zyklus bei auth

Die Reihenfolge ist anders: Hier steht cart vor payments. Beide Reihenfolgen stimmen, weil cart und payments nicht voneinander abhängen. Eine topologische Reihenfolge ist selten die einzige.

Der Zyklus wird hier anders erkannt. onPath enthält die Module, die DFS begonnen, aber nicht beendet hat: Sie liegen gerade auf dem Aufrufstapel. Triffst du eines davon wieder, bist du im Kreis gegangen. In der DFS-Lektion sind das die grauen Knoten.

Genauer, für Neugierige

Was wählen? Beide kosten O(V + E): Jedes Modul wird einmal bearbeitet, jede Abhängigkeit einmal angesehen. Kahn hat keine Rekursion und liefert ganz natürlich „was jetzt starten kann“, deshalb denken Build-Tools, die parallel bauen, so. DFS ist kürzer, wenn der Graph ohnehin schon in die Tiefe durchlaufen wird.

Rekursives DFS in Java wirft StackOverflowError bei einer Kette von einigen Tausend bis einigen Zehntausend Modulen, je nach Stapelgröße. Kahn hat dieses Problem nicht.

Die Idee

Wo noch

Überall, wo etwas auf etwas anderes wartet, gibt es eine topologische Reihenfolge:

  • Paketabhängigkeiten. npm und pip lösen auf, welche Versionen genutzt werden, und installieren sie dann so, dass jedes Paket nach seinen eigenen kommt. Gradle und MSBuild bauen die Module eines Projekts in topologischer Reihenfolge, die unabhängigen parallel.
  • Makefile. Jede Regel sagt, von welchen Dateien sie abhängt. make baut den Graphen und führt die Befehle so aus, dass jede Datei fertig ist, bevor eine andere sie braucht.
  • Die Tabellenkalkulation. Die Zelle C1 = A1 + B1 hängt von A1 und B1 ab. Ändert sich A1, berechnet die Tabelle nur die Zellen danach neu, in topologischer Reihenfolge. Eine Formel, die sich selbst erreicht, ist ein Zyklus, und Excel sagt es: „Zirkelbezug“.
  • Datenbankmigrationen und CI-Jobs: Jeder Schritt wartet auf seine eigenen.

Übung

Wellen in der CI

Löse es in deinem Editor.

Wellen. Der CI-Server führt alle Jobs gleichzeitig aus, die schon starten können. Schreibe waves(needs), das die Jobs in Wellen zurückgibt: Die erste Welle sind die Jobs ohne Abhängigkeiten, und jede nächste sind die, deren letzte Abhängigkeit in der vorigen Welle liegt. Führe es mit den Jobs aus „Sag die Ausgabe voraus“ aus:

Ausgabe
Welle 1: lint, compile
Welle 2: test, package
Welle 3: deploy
Welle 4: notify

Tipp: Das ist Kahn, aber statt einer Warteschlange behältst du die aktuelle Welle und baust die nächste auf.

Weitere Aufgaben

  • Die längste Kette. Wie viele Wellen braucht die CI mindestens, wenn sie unbegrenzt viele Maschinen hat? Das ist der längste Weg im Graphen.
  • Eine stabile Reihenfolge. Sorge dafür, dass die Ausgabe unabhängig von der Reihenfolge in needs gleich ist: Wenn mehrere Module bereit sind, nimm das erste in alphabetischer Reihenfolge. Welche Struktur brauchst du statt der Warteschlange?
  • Alle Schuldigen. Gib alle Module aus, die wegen des Zyklus nicht gebaut werden, und trenne die, die selbst im Zyklus liegen.

Test

Teste dich

1. Was ist der Eingangsgrad eines Moduls im Algorithmus von Kahn?
2. buildOrder hat 4 Module zurückgegeben, und needs hat 7. Was bedeutet das?
3. Kahn liefert core, db, auth, catalog, payments, cart, web, und DFS liefert core, db, auth, catalog, cart, payments, web. Welche Reihenfolge stimmt?
4. Was kostet der Algorithmus von Kahn bei V Modulen und E Abhängigkeiten?

Erstellt von Ivo Gergov im Rahmen der Kampagne von Evo Tech für zugängliche Programmierausbildung ·