Diagrammserialisierung

Question

Ich suche nach einem einfachen Algorithmus zum „Serialisieren“ eines gerichteten Graphen.Insbesondere habe ich eine Reihe von Dateien mit gegenseitigen Abhängigkeiten in ihrer Ausführungsreihenfolge, und ich möchte zur Kompilierungszeit die richtige Reihenfolge finden.Ich weiß, dass es ziemlich häufig vorkommen muss – Compiler machen das ständig –, aber mein Google-Fu war heute schwach.Was ist der Go-to-Algorithmus dafür?

Answer 1

Topologische Sortierung (Aus Wikipedia):

In der Graphentheorie ist eine topologische Art oder topologische Reihenfolge eines gerichteten acyclischen Graphen (DAG) eine lineare Reihenfolge seiner Knoten, in der jeder Knoten vor allen Knoten kommt, an denen er ausgehende Kanten verfügt.Jede DAG hat eine oder mehrere topologische Sorten.

Pseudocode:

L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
    remove a node n from Q
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into Q
if graph has edges then
    output error message (graph has a cycle)
else 
    output message (proposed topologically sorted order: L)

Answer 2

Ich würde erwarten, dass Werkzeuge, die dies benötigen, den Baum einfach in der Tiefe ablaufen und, wenn sie auf ein Blatt treffen, es einfach verarbeiten (z. B.kompilieren) und aus dem Diagramm entfernen (oder als verarbeitet markieren und Knoten mit allen verarbeiteten Blättern als Blätter behandeln).

Solange es sich um eine DAG handelt, sollte dieser einfache stapelbasierte Spaziergang trivial sein.

Answer 3

Wenn das Diagramm Zyklen enthält, wie können dann zulässige Ausführungsreihenfolgen für Ihre Dateien vorhanden sein?Es scheint mir, dass Sie keine Lösung haben, wenn das Diagramm Zyklen enthält, und dies wird durch den obigen Algorithmus korrekt gemeldet.

Answer 4

Ich habe mir einen ziemlich naiven rekursiven Algorithmus (Pseudocode) ausgedacht:

Map<Object, List<Object>> source; // map of each object to its dependency list
List<Object> dest; // destination list

function resolve(a):
    if (dest.contains(a)) return;
    foreach (b in source[a]):
        resolve(b);
    dest.add(a);

foreach (a in source):
    resolve(a);

Das größte Problem dabei ist, dass zyklische Abhängigkeiten nicht erkannt werden können – es kann zu einer unendlichen Rekursion kommen (z. B. Stapelüberlauf ;-p).Der einzige Ausweg, den ich sehe, wäre, den rekursiven Algorithmus in einen interaktiven mit einem manuellen Stapel umzuwandeln und den Stapel manuell auf wiederholte Elemente zu überprüfen.

Hat jemand etwas Besseres?