**Work in progress**
chciałem rozpocząć tę serię od struktury danych, którą wszyscy jesteśmy dobrze zaznajomieni, ale może nawet jej nie znamy: Directed acyclic Graphs. „Nigdy o tym nie słyszałem. Nie znasz mnie!”można powiedzieć, ale ten wykres jest tym, co umożliwia kontrolę wersji. Git jest grafem acyklicznym. W tym poście Dam ci trochę wysokiej wiedzy na temat dag, a następnie pokażę, jak zrobić jeden z kodem.
co to jest DAG?
więc co to w ogóle znaczy? Dag to wykres, który płynie w jednym kierunku, gdzie żaden element nie może być dzieckiem samym w sobie. Tak więc większość z nas zna Linkedlisty, drzewa, a nawet wykresy. DAG jest bardzo podobny do dwóch pierwszych, a implementacja trzeciego.
co najmniej dag będzie miał 4 rzeczy:
- węzły: miejsce do przechowywania danych.
- krawędzie kierowane: Strzałki, które wskazują w jednym kierunku (rzecz, która sprawia, że ta struktura danych jest inna)
- jakiś wielki węzeł przodków bez rodziców. (Ciekawostka: większość drzew przodków to w rzeczywistości Dagi, a nie drzewa, ponieważ kuzyni w pewnym momencie biorą ślub.)
- pozostawia: węzły bez dzieci
Zróbmy jeden
więc napiszmy jakiś kod. Najpierw stwórzmy konstruktor z dwiema właściwościami i nazwijmy go DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
następnie dodamy metodę add. Widzisz, co tam zrobiłem?
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;
};
więc jak to działa? Obiekt vertex to miejsce, w którym dzieją się dobre rzeczy. Dodajemy węzeł, obiekt przychodzących węzłów i tablicę ze wszystkimi ich nazwami, wartość logiczną dotyczącą tego, czy wskazuje na coś i wartość. Do niektórych z nich dojdziemy trochę później.
teraz dodajmy kilka krawędzi i Sprawmy, aby rzeczy łączyły się ze sobą. Zanim to zrobimy, musimy utworzyć funkcję pomocniczą, która sprawdza, czy odwiedziliśmy ten węzeł, czy nie. Nazwijmy to wizytą.
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();
}
to, co się tutaj dzieje, to
dajmy kredyt, gdzie jest naprawdę należny
badając ten artykuł, przeczytałem kilka świetnych postów przez niesamowicie mądrych ludzi i większość informacji pochodzi od nich. Nauczyłem się większości teorii, czytając ten dobrze napisany post na temat DAGs i kontroli wersji. Kod tutaj czerpał inspirację z kodu źródłowego emberjs i genialnych autorów za nim stojących. Czytałem również wiele innych artykułów i postów na blogu dotyczących dag od wspaniałych ludzi w Internecie. Dziękujemy za przeczytanie!