**igangværende arbejde**
jeg ønskede at starte denne serie med en datastrukturstruktur, som vi alle er som udviklere tæt bekendt med, men måske ikke engang ved det: rettede acykliske grafer. “Det har jeg aldrig hørt om. Du kender mig ikke!”du kan sige, men denne graf er det, der gør versionskontrol mulig. Git er en acyklisk graf. I dette indlæg vil jeg give dig lidt viden på højt niveau om dag ‘ er og derefter vise dig, hvordan du laver en med en kode.
Hvad er en DAG?
så hvad betyder det endda? En dag er en graf, der flyder i en retning, hvor intet element kan være et barn af sig selv. Så de fleste af os er bekendt med LinkedLists, træer og endda grafer. En DAG ligner meget de to første og en implementering af den tredje.
i det mindste vil en dag have 4 ting:
- noder: et sted at gemme dataene.
- rettede kanter: Pile, der peger i en retning (det, der gør denne datastruktur anderledes)
- nogle store forfædres knude uden forældre. (Fun fact: de fleste forfædre træer er faktisk DAGs og ikke faktisk træer, fordi fætre på et tidspunkt bliver gift med hinanden.)
- blade: noder uden børn
lad os lave en
så lad os skrive noget kode. Lad os først oprette en konstruktør med to egenskaber og kalde det DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
næste vil vi tilføje en tilføjelsesmetode. Se hvad jeg gjorde der?
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;
};
så hvordan fungerer dette? Toppunktet objekt er, hvor alle de gode ting sker. Vi tilføjer en node, et objekt med indgående noder og et array med alle deres navne, en boolsk om, hvorvidt det peger på noget og en værdi. Vi kommer til nogle af disse lidt senere.
lad os nu tilføje nogle kanter og få ting til at forbinde hinanden. Før vi kan gøre det, er vi nødt til at oprette en hjælperfunktion, der kontrollerer, om vi har besøgt den knude eller ej. Lad os kalde det besøg.
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();
}
hvad der sker her er
lad os give kredit, hvor det virkelig skyldes
undersøgelse af denne artikel læste jeg nogle gode indlæg af utroligt smarte mennesker, og de fleste af oplysningerne kom fra dem. Jeg lærte det meste af teorien ved at læse dette velskrevne indlæg om DAGs og versionskontrol. Koden her fik al sin inspiration fra emberjs kildekode og de strålende forfattere bag det. Jeg har også læst mange andre artikler og blogindlæg om DAGs fra store mennesker rundt om på internettet. Tak fordi du læste!