Ich bin auf der Suche nach einem einfachen Algorithmus zum "Serialisieren" eines gerichteten Graphen. Insbesondere habe ich eine Reihe von Dateien mit Abhängigkeiten von ihrer Ausführungsreihenfolge, und ich möchte die richtige Reihenfolge zur Kompilierzeit finden. Ich weiß, dass es ziemlich normal sein muss - Compiler tun es die ganze Zeit - aber mein Google-Fu war heute schwach. Was ist der Go-to-Algorithmus dafür?Graph Serialisierung
Topological Sort (hinzufügen):
in der Graphentheorie, eine topologische Sortierung oder topologischen Anordnung eines gerichteten azyklischer Graph (DAG) eine lineare Ordnung seiner Knoten in dem jeder Knoten kommt vor allen Knoten, zu denen es Outbound-Kanten hat. Jede DAG hat eine oder mehrere topologische Sorten.
Pseudo-Code:
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)
Ich würde erwarten, dass Werkzeuge, die dies benötigen, einfach den Baum in einer Tiefe zuerst gehen und wenn sie ein Blatt treffen, verarbeiten Sie es einfach (zB kompilieren) und entfernen Sie es aus dem Diagramm (oder markieren Sie es als bearbeitet und behandeln Knoten mit allen Blättern als Blätter verarbeitet).
Solange es ein DAG ist, sollte dieser einfache Stack-basierte Weg trivial sein.
Ja, so machen Sie es. Es wird Tiefensuche (DFS) genannt. Und wenn Sie sich nicht sicher sind, dass Sie eine DAG haben, müssen Sie nach hinteren Kanten suchen, sonst wird Sie ein Zyklus in eine Endlosschleife schicken. – sleske
Ich habe mit einem ziemlich naiven rekursive Algorithmus (Pseudo-Code) kommen:
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 es keine Möglichkeit, zyklische Abhängigkeiten zu erkennen, hat - es kann eine unendliche Rekursion geht in (dh Stapelüberlauf ;-p). Der einzige Weg, den ich sehen könnte, wäre, den rekursiven Algorithmus in einen interativen mit einem manuellen Stack zu verwandeln und den Stack manuell auf wiederholte Elemente zu überprüfen.
Jeder hat etwas besseres?
statt einer foreach verwenden Sie eine Weile, pflegen zwei Zeiger die Daten a, eine führende, die Doppelschritte und eine nachfolgende, die einzelnen Schritte. Der vorangestellte Zeiger behandelt die aktuellen Auflösungen und wenn er den abschließenden Zeiger überlappt, gibt es einen Zyklus. – Tenderdude
Wenn der Graph Zyklen enthält, wie kann es existieren erlaubt Hinrichtungsbefehle für Ihre Dateien? Es scheint mir, dass, wenn der Graph Zyklen enthält, dann haben Sie keine Lösung, und diese wird korrekt durch den obigen Algorithmus gemeldet.
Ja, eine topologische Sortierung ist nicht möglich, wenn ein Graph Zyklen enthält. Das entspricht der realen Welt: Wenn ich dich auffordere, A vor B, * und * B vor A zu machen, wirst du mich auf keinen Fall befriedigen ;-). – sleske
Eh ... direkt von Wikipedia kopiert? – Benjol
ja, bitte zitieren Quellen –
Danke. Hat mir geholfen, die Tatsache abzubilden, dass der Abhängigkeitsbaum mit dieser Methode sortiert werden kann. :-) –