**Work in progress**
Ich wollte diese Serie mit einer Datenstrukturstruktur beginnen, mit der wir alle als Entwickler vertraut sind, die wir aber vielleicht nicht einmal kennen: Directed Acyclic Graphs. „Davon habe ich noch nie gehört. Du kennst mich nicht!“ Sie mögen sagen, aber dieses Diagramm macht die Versionskontrolle möglich. Git ist ein azyklischer Graph. In diesem Beitrag werde ich Ihnen ein wenig Wissen über DAGs vermitteln und Ihnen dann zeigen, wie Sie mit etwas Code eines erstellen.
Was ist eine DAG?
Was bedeutet das überhaupt? Ein DAG ist ein Graph, der in eine Richtung fließt, in der kein Element ein Kind von sich selbst sein kann. Die meisten von uns sind also mit verknüpften Listen, Bäumen und sogar Grafiken vertraut. Eine DAG ist den ersten beiden sehr ähnlich und eine Implementierung der dritten.
Zumindest wird eine DAG 4 Dinge haben:
- Knoten: Ein Ort zum Speichern der Daten.
- Gerichtete Kanten: Pfeile, die in eine Richtung zeigen (die Sache, die diese Datenstruktur anders macht)
- Ein großer Ahnenknoten ohne Eltern. (Lustige Tatsache: Die meisten Ahnenbäume sind eigentlich DAGs und keine Bäume, weil Cousins irgendwann miteinander heiraten.)
- Blätter: Knoten ohne Kinder
Lass uns einen machen
Also lass uns Code schreiben. Zuerst erstellen wir einen Konstruktor mit zwei Eigenschaften und nennen ihn DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
Als nächstes werden wir eine Add-Methode hinzufügen. Siehst du, was ich dort gemacht habe?
DAG.prototype.add = function(node) {
if (!node) { return; }
if (this.vertices) {
return this.vertices;
}
const vertex = {
node: node,
incoming: {},
incomingNodes: ,
hasOutgoing: false,
value: null
};
this.vertices = vertex;
this.nodes.push(node);
return vertex;
};
Wie funktioniert das? Das Vertex-Objekt ist, wo all die guten Dinge passieren. Wir fügen einen Knoten, ein Objekt eingehender Knoten und ein Array mit all ihren Namen hinzu, einen booleschen Wert, ob er auf etwas zeigt, und einen Wert. Wir werden ein wenig später zu einigen davon kommen.
Jetzt können wir einige Kanten hinzufügen und Sachen miteinander verbinden. Bevor wir das tun können, müssen wir eine Hilfsfunktion erstellen, die überprüft, ob wir diesen Knoten besucht haben oder nicht. Nennen wir es Besuch.
function visit(vertex, fn, visited, path) {
const name = vertex.name,
vertices = vertex.incoming,
names = vertex.incomingNames,
len = names.length,
i;
if (!visited) {
visited = {};
}
if (!path) {
path = ;
}
if (visited.hasOwnProperty(name)) {
return;
}
path.push(name);
visited = true;
for (i = 0; i < len; i++) {
visit(vertices], fn, visited, path);
}
fn(vertex, path);
path.pop();
}
Was hier passiert ist
Lassen Sie uns Kredit geben, wo es wirklich fällig ist
Als ich diesen Artikel recherchierte, las ich einige großartige Beiträge von erstaunlich klugen Leuten und die meisten Informationen kamen von ihnen. Ich habe den größten Teil der Theorie gelernt, indem ich diesen gut geschriebenen Beitrag über DAGs und Versionskontrolle gelesen habe. Der Code hier wurde vom emberjs-Quellcode und den brillanten Autoren dahinter inspiriert. Ich habe auch zahlreiche andere Artikel und Blogbeiträge zu DAGs von großartigen Leuten im Internet gelesen. Danke fürs Lesen!